Um desafio de otimização de algoritmo mais rápido

9

Esta é a minha primeira experiência com um desafio de complexidade assintótica, embora eu esteja feliz com respostas inteiramente em código, desde que elas apresentem uma explicação de sua complexidade de tempo.

Eu tenho o seguinte problema.

Considere as tarefas T_1, ... T_n e procs M_1, ..., M_m. Cada tarefa leva um certo tempo para ser executada, dependendo dos procs.

Cada tarefa também custa uma certa quantia para executar, dependendo dos procs.

As tarefas precisam ser executadas em ordem estrita (elas não podem ser realizadas em paralelo) e leva tempo para alterar o processo. Uma tarefa não pode ser movida de um processo para outro após ter sido iniciada.

Finalmente, cada tarefa deve ser concluída em um determinado período de tempo.

a tarefa

O objetivo é fornecer um algoritmo (ou algum código) que, com cinco tabelas do formulário acima, minimize o custo total para concluir todas as tarefas e garanta que todas as tarefas sejam concluídas dentro dos prazos. Se isso não for possível, apenas informamos que isso não pode ser feito.

Ponto

Você deve fornecer a grande complexidade Oh da sua solução em termos das variáveis ​​n, me onde d é o último prazo. Não deve haver constantes desnecessárias em sua grande complexidade Oh. Portanto, O (n / 1000) deve ser escrito como O (n), por exemplo.

Sua pontuação é calculada simplesmente definindo n = 100, m = 100 ed = 1000 em sua complexidade declarada. Você quer a menor pontuação possível.

desempate

Em caso de empate, a primeira resposta vence.


notas adicionadas

log no tempo, a complexidade de uma resposta será tomada como base 2.

placar

  • 10 ^ 202 de KSFT ( Python ) Primeiro enviado, então recebe a recompensa.
  • 10 ^ 202 de Dominik Müller ( Scala )

fonte
"alternando o tempo da máquina de linha para a máquina de coluna" Você quer dizer o tempo necessário para mudar de M_1 para M_2? Além disso, qual é a diferença entre "custo de troca" e "tempo de troca". Eles normalmente significam o mesmo em relação à descrição de algoritmos de agendamento.
luminosa
@ Luminoso Pense no tempo em segundos e no custo em dólares. São coisas diferentes nesta questão. As tabelas mostram o tempo (custo respectivamente) da troca de máquina para executar a próxima tarefa. Pode ser de M_1 a M_2 ou de M_2 a M_1.
Ok, isso esclarece isso.
luminoso
A resposta curta é que a complexidade será O(m ^ n). Nenhum algoritmo será "mais rápido" do que isso. A poda com base em um tempo ou custo máximo necessário não altera a complexidade do algoritmo, nem possui um custo em dólar e um tempo, portanto, dnão é um elemento da complexidade.
precisa saber é o seguinte
11
@BobDalgleish Isso dá uma pontuação de 100 ao poder de 100. Eu acredito que você pode fazer muito melhor.

Respostas:

2

Pontuação: 10 ^ 202

Eu meio que gostaria que tivéssemos suporte para LaTeX agora ...

Como ninguém mais respondeu, pensei em tentar, mesmo que não seja muito eficiente. Não tenho certeza de qual é o grande O disso.

Eu acho que funciona. Pelo menos, é o único caso de teste publicado.

Ele recebe entradas como na pergunta, exceto sem os rótulos de número de máquina ou tarefa e com ponto e vírgula em vez de quebras de linha.

import itertools
time = [[int(j) for j in i.split()] for i in raw_input().split(";")]
cost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
nmachines=len(time)
ntasks=len(time[0])
switchtime = [[int(j) for j in i.split()] for i in raw_input().split(";")]
switchcost = [[int(j) for j in i.split()] for i in raw_input().split(";")]
deadline = [int(i) for i in raw_input().split()]
d={}
m=itertools.product(range(nmachines),repeat=ntasks)
for i in m:
    t=-switchtime[i[-1]][i[0]]
    c=-switchcost[i[-1]][i[0]]
    e=0
    meetsdeadline=True
    for j in range(ntasks):
        t+=switchtime[i[e-1]][i[e]]+time[i[e]][j]
        c+=switchcost[i[e-1]][i[e]]+cost[i[e]][j]
        e+=1
        if t>deadline[j]:
            meetsdeadline=False
    if meetsdeadline:
        d[(c,t)]=i
print min(d.keys()),d[min(d.keys())]
KSFT
fonte
Você pode dar uma explicação e dizer qual deve ser sua pontuação? Além disso, você poderia mostrar o que isso dá para o exemplo da pergunta?
Como afirmei na minha resposta, tentei e funciona no exemplo. Não sei ao certo qual é o grande O (que eu quis mencionar na minha resposta).
KSFT
Basicamente, aproximadamente quantas operações serão necessárias para concluir. Parece que leva ntasks * m tempo aproximadamente (suponha que todas as atribuições nos loops levem tempo constante), o que me deixa desconfiada sobre sua correção, tenho que admitir. Você pode dizer algo sobre por que você acha que funciona?
11
Oh! Eu senti falta disso. Então m é de fato de máquinas de tamanho ^ tarefas. OK, agora eu acredito que funciona. Eu acho que sua pontuação é (100 ^ 100) * 100.
4
@Lembik Tem a melhor pontuação até agora!
KSFT
1

Verificar todos - Scala

Pontuação estimada: 2m ^ n

Começo em cada máquina e repito todas as tarefas para criar todas as permutações através das tarefas com diferentes máquinas que cumprem os prazos. Ou seja, se tudo estiver dentro do prazo, eu obteria 9 caminhos possíveis com 2 máquinas e 3 tarefas. (m ^ n) Depois, segui o caminho com o menor custo.

A entrada está estruturada desta forma (-> explica as partes e, portanto, não deve ser inserida):

M_1:5 3 5 4;M_2:4 2 7 5                 --> time
M_1:5 4 2 6;M_2:3 7 3 3                 --> cost
M_1:M_1}0 M_2}1;M_2:M_1}2 M_2}0         --> switch itme
M_1:M_1}0 M_2}2;M_2:M_1}1 M_2}0         --> switch cost
5 10 15 20                              --> deadlines

E aqui está o código:

package Scheduling

import scala.io.StdIn.readLine

case class Cost(task: Map[String, List[Int]])
case class Switch(machine: Map[String, Map[String, Int]])
case class Path(time: Int, cost: Int, machine: List[String])

object Main {

    def main(args: Array[String]) {
        val (machines, cost_time, cost_money, switch_time, switch_money, deadlines) = getInput

        val s = new Scheduler(machines, cost_time, cost_money, switch_time, switch_money, deadlines)
        s.schedule
    }

    def getInput(): (List[String], Cost, Cost, Switch, Switch, List[Int]) = {
        val cost_time = Cost(readLine("time to complete task").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map(_.toInt).toList)
            }.toMap)

        val cost_money = Cost(readLine("cost to complete task").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map(_.toInt).toList)
            }.toMap)

        val switch_time = Switch(readLine("time to switch").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map{t =>
                        val entries = t.split("}")
                        (entries(0) -> entries(1).toInt)
                    }.toMap)
            }.toMap)

        val switch_money = Switch(readLine("time to switch").split(";").map{s => 
                val parts = s.split(":")
                (parts(0) -> parts(1).split(" ").map{t =>
                        val entries = t.split("}")
                        (entries(0) -> entries(1).toInt)
                    }.toMap)
            }.toMap)

        val deadlines = readLine("deadlines").split(" ").map(_.toInt).toList

        val machines = cost_time.task.keys.toList

        (machines, cost_time, cost_money, switch_time, switch_money, deadlines)
    }
}

class Scheduler(machines: List[String], cost_time: Cost, cost_money: Cost, switch_time: Switch, switch_money: Switch, deadlines: List[Int]) {

    def schedule() {
        var paths = List[Path]()
        var alternatives = List[(Int, Path)]()

        for (i <- machines) {
            if (cost_time.task(i)(0) <= deadlines(0)) {
                paths = paths ::: List(Path(cost_time.task(i)(0), cost_money.task(i)(0), List(i)))
            }
        }

        val allPaths = deadlines.zipWithIndex.tail.foldLeft(paths)((paths, b) => paths.flatMap(x => calculatePath(x, b._1, b._2)))

        if (allPaths.isEmpty) {
            println("It is not possible")
        } else {
            println(allPaths.minBy(p=>p.cost).machine)
        }
    }

    def calculatePath(prev: Path, deadline: Int, task: Int): List[Path] = {
        val paths = machines.map(m => calculatePath(prev, task, m))
        paths.filter(p => p.time <= deadline)
    }

    def calculatePath(prev: Path, task: Int, machine: String): Path = {
        val time = prev.time + switch_time.machine(prev.machine.last)(machine) + cost_time.task(machine)(task)
        val cost = prev.cost + switch_money.machine(prev.machine.last)(machine) + cost_money.task(machine)(task)

        Path(time, cost, prev.machine :+ machine)
    }
}

Eu também tive uma idéia para começar por trás. Como você sempre pode escolher uma máquina com o menor custo, se o tempo for menor do que a diferença do prazo anterior para o novo. Mas isso não diminuiria o tempo de execução máximo se a tarefa com o melhor custo demorar mais do que o prazo final.

Atualizar

======

Aqui está outra configuração. Tempo:

M_1 2 2 2 7
M_2 1 8 5 10

custo:

M_1 4 4 4 4
M_2 1 1 1 1

mudar o tempo:

    M_1 M_2
M_1  0   2
M_2  6   0

custo do switch:

    M_1 M_2
M_1  0   2
M_2  2   0

prazos:

5 10 15 20

Como entrada no meu programa:

M_1:2 2 2 7;M_2:1 8 5 10
M_1:4 4 4 4;M_2:1 1 1 1
M_1:M_1}0 M_2}2;M_2:M_1}6 M_2}0
M_1:M_1}0 M_2}2;M_2:M_1}2 M_2}0
5 10 15 20

Este possui duas soluções: tempo: 18, custo: 15, caminho: Lista (M_1, M_1, M_1, M_2) tempo: 18, custo: 15, caminho: Lista (M_2, M_1, M_1, M_1)

O que levanta a questão de como isso deve ser tratado. Todos devem ser impressos ou apenas um? E se o tempo fosse diferente? Um com o menor custo e sem prazo perdido é suficiente ou também deve ser o de menor tempo?

Dominik Müller
fonte
A pergunta diz que o objetivo é "[minimizar] o custo total". A propósito, você pode resumir como seu algoritmo funciona? Não conheço Scala e não consigo descobrir como isso funciona.
KSFT
A iteração sobre todos os caminhos leva O(m^n)tempo. A repetição de cada máquina para todas as tarefas leva O(n*m^n)tempo.
KSFT
A O(n*m^n)iteração sobre cada tarefa para cada um dos caminhos? E iterando sobre cada máquina para cada tarefa, algo como O(n*m).
Dominik Müller
Ah, erro de digitação. Eu pretendia escrever "iteração sobre cada máquina para todos os caminhos leva O(n*m^n)".
KSFT
Espere, não, é O(m*m^n)=O(m^n+1). Ainda é a mesma pontuação, no entanto.
KSFT