To mój pierwszy eksperyment z asymptotycznym wyzwaniem złożoności, chociaż cieszę się z odpowiedzi w całości w kodzie, pod warunkiem, że zawierają wyjaśnienie złożoności czasu.

Mam następujący problem.

Rozważ zadania T_1, ... T_n i proc. M_1, ..., M_m. Każde zadanie zajmuje określoną ilość czasu w zależności od procedur.

Każde zadanie kosztuje również pewną kwotę do wykonania w zależności od proc.

Zadania muszą być wykonywane w ścisłej kolejności (nie można ich wykonywać równolegle), a zmiana proc zajmuje dużo czasu. Zadania nie można przenosić z jednego procesu do drugiego po jego uruchomieniu.

Wreszcie każde zadanie musi zostać zakończone do określonego czasu.

zadanie

Celem jest podanie algorytmu (lub jakiegoś kodu), który przy pięciu tabelach powyższego formularza, minimalizuje całkowity koszt wykonania wszystkich zadań, jednocześnie upewniając się, że wszystkie zadania zostały wykonane w wyznaczonym terminie. Jeśli nie jest to możliwe, po prostu informujemy, że nie można tego zrobić.

wynik

Powinieneś dać dużą Oh złożoność swojego rozwiązania w kategoriach zmiennych n, mi id, gdzie d jest ostatnim terminem. W twojej wielkiej złożoności Oh nie powinno być żadnych niepotrzebnych stałych. Tak więc na przykład O (n / 1000) należy zapisać jako O (n).

Twój wynik obliczany jest po prostu przez ustawienie n = 100, m = 100 id = 1000 w podanej złożoności. Chcesz mieć jak najmniejszy wynik.

remis

W przypadku remisu pierwsza odpowiedź wygrywa.

dodane notatki

log w czasie złożoność odpowiedzi zostanie wzięta za podstawę 2.

tablica wyników

• 10 ^ 202 z KSFT ( Python ) Najpierw przesłane, więc dostaje nagrodę.
• 10 ^ 202 od Dominika Müllera ( Scala )

Wynik: 10 ^ 202

Chciałbym mieć teraz wsparcie LaTeX ...

Ponieważ nikt inny nie odpowiedział, pomyślałem, że spróbuję, chociaż nie jest to zbyt wydajne. Nie jestem jednak pewien, co to za wielkie O.

Myślę, że to działa. Przynajmniej tak jest w przypadku jedynego opublikowanego przypadku testowego.

Przyjmuje dane wejściowe jak w pytaniu, z wyjątkiem etykiet maszyn i numerów zadań oraz średników zamiast podziałów linii.

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

Zaznacz wszystko - Scala

Szacowany wynik: 2 mln ^ n

Zaczynam od każdej maszyny i powtarzam wszystkie zadania, aby utworzyć wszystkie permutacje poprzez zadania z różnymi maszynami, które dotrzymują terminów. Oznacza to, że jeśli wszystko jest na czas, uzyskałbym 9 możliwych ścieżek z 2 maszynami i 3 zadaniami. (m ^ n) Następnie wybieram ścieżkę o najniższym koszcie.

Dane wejściowe mają następującą strukturę (-> wyjaśnia części i dlatego nie należy ich wprowadzać):

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

A oto kod:

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

Miałem też pomysł, aby zacząć od tyłu. Ponieważ zawsze możesz wybrać maszynę o najniższych kosztach, jeśli czas jest krótszy, niż różnica między poprzednim terminem a nowym. Nie zmniejszyłoby to jednak maksymalnego czasu działania, jeśli zadanie o lepszych kosztach trwa dłużej niż ostatni termin.

Aktualizacja

======

Oto kolejna konfiguracja. czas:

M_1 2 2 2 7
M_2 1 8 5 10

koszt:

M_1 4 4 4 4
M_2 1 1 1 1

czas przełączania:

    M_1 M_2
M_1  0   2
M_2  6   0

koszt zmiany:

    M_1 M_2
M_1  0   2
M_2  2   0

terminy:

5 10 15 20

Jako dane wejściowe do mojego programu:

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

Ten ma dwa rozwiązania: czas: 18, koszt: 15, ścieżka: Lista (M_1, M_1, M_1, M_2) czas: 18, koszt: 15, ścieżka: Lista (M_2, M_1, M_1, M_1)

Co nasuwa pytanie, jak należy sobie z tym poradzić. Czy wszystkie powinny być wydrukowane, czy tylko jeden? A jeśli czas byłby inny? Czy taki, który ma najniższy koszt i nie ma przekroczonego terminu, czy też powinien to być ten o najniższym czasie?