Eine schnellste Herausforderung bei der Algorithmusoptimierung

9

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 )

quelle
"Umschaltzeit von der Zeilenmaschine zur Spaltenmaschine" Sie meinen die Zeitkosten für den Wechsel von M_1 zu M_2? Was ist auch der Unterschied zwischen "Schaltkosten" und "Schaltzeit"? Sie bedeuten in der Regel dasselbe in Bezug auf die Beschreibung von Planungsalgorithmen.
Leuchtend
@Luminous Denken Sie an Zeit in Sekunden und Kosten in Dollar. Sie sind verschiedene Dinge in dieser Frage. Die Tabellen zeigen die Zeit (bzw. die Kosten) für den Maschinenwechsel, um die nächste Aufgabe auszuführen. Dies kann von M_1 bis M_2 oder von M_2 bis M_1 sein.
Ok, das verdeutlicht das.
Leuchtend
Die kurze Antwort ist, dass die Komplexität sein wird O(m ^ n). Kein Algorithmus wird "schneller" sein. Das Beschneiden auf der Grundlage eines maximal erforderlichen Zeit- oder Kostenaufwands ändert weder die Komplexität des Algorithmus noch die Kosten für Dollar und Zeit und ist daher dkein Element der Komplexität.
Bob Dalgleish
1
@ BobDalgleish Das ergibt eine Punktzahl von 100 zur Potenz von 100. Ich glaube, Sie können viel besser machen.

Antworten:

2

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())]
KSFT
quelle
Können Sie eine Erklärung abgeben und sagen, wie hoch Ihre Punktzahl sein sollte? Können Sie auch zeigen, was es für das Beispiel in der Frage gibt?
Wie ich in meiner Antwort angegeben habe, habe ich es versucht und es funktioniert am Beispiel. Ich bin mir nicht sicher, was das große O ist (was ich in meiner Antwort erwähnen wollte).
KSFT
Grundsätzlich ungefähr wie viele Operationen es dauern wird, um abzuschließen. Es sieht so aus, als würde es ungefähr nt * m Zeit dauern (vorausgesetzt, alle Zuweisungen in den Schleifen nehmen konstante Zeit in Anspruch), was mich misstrauisch macht, was die Richtigkeit betrifft, die ich zugeben muss. Können Sie etwas darüber sagen, warum Sie denken, dass es funktioniert?
1
Oh! Das habe ich vermisst. Also ist m tatsächlich von der Größe nmachines ^ ntasks. OK, jetzt glaube ich, dass es funktioniert. Ich denke, Ihre Punktzahl ist (100 ^ 100) * 100.
4
@Lembik Es hat die beste Punktzahl bisher!
KSFT
1

Ü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?

Dominik Müller
quelle
Die Frage besagt, dass das Ziel darin besteht, "die Gesamtkosten zu minimieren". Können Sie übrigens zusammenfassen, wie Ihr Algorithmus funktioniert? Ich kenne Scala nicht und kann nicht herausfinden, wie das funktioniert.
KSFT
Das Durchlaufen aller Pfade braucht O(m^n)Zeit. Iterieren jede Maschine für alle Aufgaben nimmt O(n*m^n)Zeit.
KSFT
Wird nicht O(n*m^n)jede Aufgabe für jeden der Pfade durchlaufen? Und Iteration über jede Maschine für jede Aufgabe so etwas wie O(n*m).
Dominik Müller
Ah, Tippfehler. Ich wollte schreiben "Iterieren über jede Maschine für alle Pfade dauert O(n*m^n)".
KSFT
Warten Sie, nein, es ist O(m*m^n)=O(m^n+1). Es ist jedoch immer noch die gleiche Punktzahl.
KSFT