Dies ist mein erstes Experiment mit einer asymptotischen Komplexitätsherausforderung, obwohl ich mit Antworten vollständig im Code zufrieden bin, solange sie eine Erklärung für ihre zeitliche Komplexität enthalten.

Ich habe folgendes Problem.

Betrachten Sie die Aufgaben T_1, ... T_n und procs M_1, ..., M_m. Jede Aufgabe benötigt abhängig von den Prozessen eine bestimmte Zeit.

Jede Aufgabe kostet je nach Prozess auch einen bestimmten Betrag.

Die Aufgaben müssen in strikter Reihenfolge ausgeführt werden (sie können nicht parallel ausgeführt werden) und es braucht Zeit, um den Prozess zu ändern. Eine Aufgabe kann nach dem Start nicht mehr von einem Prozess zu einem anderen verschoben werden.

Schließlich muss jede Aufgabe zu einem bestimmten Zeitpunkt abgeschlossen sein.

die Aufgabe

Das Ziel besteht darin, einen Algorithmus (oder einen Code) anzugeben, der anhand von fünf Tabellen des obigen Formulars die Gesamtkosten für die Ausführung aller Aufgaben minimiert und gleichzeitig sicherstellt, dass alle Aufgaben innerhalb ihrer Fristen ausgeführt werden. Wenn dies nicht möglich ist, melden wir nur, dass dies nicht möglich ist.

Ergebnis

Sie sollten die große Oh-Komplexität Ihrer Lösung in Bezug auf die Variablen n, m und d angeben, wobei d die letzte Frist ist. Es sollte keine unnötigen Konstanten in Ihrer großen Oh-Komplexität geben. So sollte beispielsweise O (n / 1000) als O (n) geschrieben werden.

Ihre Punktzahl wird einfach berechnet, indem Sie n = 100, m = 100 und d = 1000 in Ihre angegebene Komplexität setzen. Sie möchten die kleinstmögliche Punktzahl.

Kabelbinder

Bei einem Unentschieden gewinnt die erste Antwort.

Notizen hinzugefügt

log In der Zeit wird die Komplexität einer Antwort auf Basis 2 genommen.

Anzeigetafel

• 10 ^ 202 von KSFT ( Python ) Zuerst eingereicht, bekommt also das Kopfgeld.
• 10 ^ 202 von Dominik Müller ( Scala )

Punktzahl: 10 ^ 202

Ich wünschte, wir hätten jetzt LaTeX-Unterstützung ...

Da sonst niemand geantwortet hat, dachte ich, ich würde es versuchen, obwohl es nicht sehr effizient ist. Ich bin mir jedoch nicht sicher, was das große O davon ist.

Ich denke es funktioniert. Zumindest für den einzigen veröffentlichten Testfall.

Es werden Eingaben wie in der Frage vorgenommen, außer ohne die Maschinen- oder Aufgabennummernbezeichnungen und mit Semikolons anstelle von Zeilenumbrüchen.

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())]

Überprüfen Sie alle - Scala

Geschätzte Punktzahl: 2m ^ n

Ich starte von jeder Maschine und iteriere über alle Aufgaben, um alle Permutationen durch die Aufgaben mit verschiedenen Maschinen zu erstellen, die die Fristen einhalten. Das heißt, wenn alles rechtzeitig ist, würde ich 9 mögliche Pfade mit 2 Maschinen und 3 Aufgaben erhalten. (m ^ n) Danach gehe ich den Weg mit den niedrigsten Kosten.

Die Eingabe ist wie folgt aufgebaut (-> erklärt die Teile und sollte daher nicht eingegeben werden):

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

Und hier ist der Code:

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)
    }
}

Ich hatte auch die Idee, von hinten zu beginnen. Da Sie immer eine Maschine mit den niedrigsten Kosten wählen können, wenn die Zeit kleiner ist als die Differenz zwischen der vorherigen und der neuen Frist. Dies würde jedoch die maximale Laufzeit nicht verringern, wenn die Aufgabe mit den besseren Kosten länger dauert als die letzte Frist.

Aktualisieren

======

Hier ist eine andere Einstellung. Zeit:

M_1 2 2 2 7
M_2 1 8 5 10

Kosten:

M_1 4 4 4 4
M_2 1 1 1 1

Schaltzeit:

    M_1 M_2
M_1  0   2
M_2  6   0

Wechselkosten:

    M_1 M_2
M_1  0   2
M_2  2   0

Fristen:

5 10 15 20

Als Eingabe in mein Programm:

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

Dieser hat zwei Lösungen: Zeit: 18, Kosten: 15, Pfad: Liste (M_1, M_1, M_1, M_2) Zeit: 18, Kosten: 15, Pfad: Liste (M_2, M_1, M_1, M_1)

Was die Frage aufwirft, wie damit umgegangen werden soll. Sollten alle gedruckt werden oder nur einer? Und was wäre, wenn die Zeit anders wäre? Ist einer mit den niedrigsten Kosten und ohne versäumte Frist genug oder sollte es auch derjenige mit der niedrigsten Zeit sein?