Najszybsze wyzwanie optymalizacji algorytmu

9

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 )

źródło
„czas przełączania z maszyny rzędowej na maszynę kolumnową” Masz na myśli koszt czasu przejścia z M_1 na M_2? Jaka jest różnica między „kosztem zmiany” a „czasem zmiany”. Zazwyczaj oznaczają to samo w odniesieniu do opisywania algorytmów planowania.
Luminous
@ Luminous Pomyśl o czasie w sekundach i koszcie w dolarach. W tym pytaniu są różne rzeczy. Tabele pokazują czas (odpowiednio koszt) zmiany maszyny do wykonania następnego zadania. Może to być od M_1 do M_2 lub od M_2 do M_1.
Ok, to wyjaśnia.
Luminous
Krótka odpowiedź brzmi: złożoność będzie O(m ^ n). Żaden algorytm nie będzie „szybszy” niż to. Przycinanie oparte na maksymalnym wymaganym czasie lub koszcie nie zmienia złożoności algorytmu, ani nie ma zarówno kosztu w dolarach, jak i kosztu czasu, dlatego dnie jest elementem złożoności.
Bob Dalgleish,
1
@BobDalgleish To daje wynik 100 do potęgi 100. Wierzę, że możesz zrobić znacznie więcej.

Odpowiedzi:

2

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())]
KSFT
źródło
Czy możesz podać jakieś wyjaśnienie i powiedzieć, jaki powinien być Twój wynik? Czy możesz również pokazać, co daje przykład z pytania?
Jak powiedziałem w mojej odpowiedzi, wypróbowałem to i działa na tym przykładzie. Nie jestem pewien, co to jest duże O (co chciałem wspomnieć w mojej odpowiedzi).
KSFT,
Zasadniczo z grubsza, ile operacji zajmie wykonanie. Wygląda na to, że zajmuje to z grubsza czas ntasks * m (zakładając, że wszystkie zadania w pętlach wymagają ciągłego czasu), co budzi podejrzenia co do jego poprawności, muszę przyznać. Czy możesz powiedzieć coś o tym, dlaczego uważasz, że to działa?
1
O! Tęsknie za tym. Więc m jest wielkością nmachines ^ ntasks. OK, teraz wierzę, że to działa. Myślę, że twój wynik to (100 ^ 100) * 100.
4
@Lembik Ma jak dotąd najlepszy wynik!
KSFT,
1

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?

Dominik Müller
źródło
Pytanie mówi, że celem jest „[zminimalizować] całkowity koszt”. Nawiasem mówiąc, czy możesz podsumować działanie algorytmu? Nie znam Scali i nie mogę zrozumieć, jak to działa.
KSFT
Iteracja po wszystkich ścieżkach wymaga O(m^n)czasu. Iteracja po każdej maszynie dla wszystkich zadań wymaga O(n*m^n)czasu.
KSFT
Czy nie O(n*m^n)iteruje się po każdym zadaniu dla każdej ścieżki? I iteracja po każdej maszynie dla każdego zadania jakoś tak O(n*m).
Dominik Müller
Ach, literówka. Chciałem napisać „iteracji po każdej maszyny na wszystkich ścieżkach trwa O(n*m^n)”.
KSFT
Czekaj, nie, to jest O(m*m^n)=O(m^n+1). Nadal jednak ten sam wynik.
KSFT