Самый быстрый алгоритм оптимизации задачи

9

Это мой первый эксперимент с проблемой асимптотической сложности, хотя я доволен ответами полностью в коде, если они приходят с объяснением сложности времени.

У меня следующая проблема.

Рассмотрим задачи T_1, ... T_n и процы M_1, ..., M_m. Каждая задача занимает определенное количество времени для выполнения в зависимости от процедур.

Каждое задание также стоит определенной суммы для выполнения в зависимости от процедур.

Задачи должны выполняться в строгом порядке (их нельзя выполнять параллельно), и для изменения процедуры требуется время. Задание не может быть перемещено из одного процесса в другой после его запуска.

Наконец, каждое задание должно быть выполнено к определенному времени.

задание

Задача состоит в том, чтобы дать алгоритм (или некоторый код), который с учетом пяти таблиц в приведенной выше форме минимизирует общую стоимость выполнения всех задач, при этом гарантируя, что все задачи будут выполнены в установленные сроки. Если это невозможно, мы просто сообщаем, что это невозможно сделать.

Гол

Вы должны дать большую сложность своего решения в терминах переменных n, m и d, где d - последний срок. В вашей большой сложности не должно быть лишних констант. Таким образом, O (n / 1000) должно быть записано как O (n), например.

Ваша оценка рассчитывается просто путем установки n = 100, m = 100 и d = 1000 в вашей заявленной сложности. Вы хотите наименьшее возможное количество баллов.

прерыватель связи

В случае ничьей победит первый ответ.


добавленные заметки

log во время сложности ответа будет принята основа 2.

табло

  • 10 ^ 202 от KSFT ( Python ) Сначала отправлено, поэтому получает награду.
  • 10 ^ 202 от Доминика Мюллера ( Скала )

источник
"переключение времени с машины строки на машину столбца" Вы имеете в виду затраты времени на переключение с М_1 на М_2? Также в чем разница между «стоимостью переключения» и «временем переключения». Они обычно означают одно и то же в отношении описания алгоритмов планирования.
Светящийся
@ Светящиеся Подумайте о времени в секундах и о стоимости в долларах. Это разные вещи в этом вопросе. В таблицах показано время (соответственно стоимость) смены машины для выполнения следующей задачи. Это может быть от M_1 до M_2 или от M_2 до M_1.
Хорошо, это проясняет это.
Светящиеся
Короткий ответ: сложность будет O(m ^ n). Ни один алгоритм не будет «быстрее» этого. Обрезка, основанная на максимальном требуемом времени или стоимости, не меняет сложности алгоритма и не требует затрат в долларах и времени, следовательно d, не является элементом сложности.
Боб Далглиш
1
@BobDalgleish Это дает оценку 100 к степени 100. Я считаю, что вы можете сделать намного лучше.

Ответы:

2

Оценка: 10 ^ 202

Я бы хотел, чтобы у нас была поддержка LaTeX сейчас ...

Поскольку никто не ответил, я подумал, что попробую, хотя это не очень эффективно. Хотя я не уверен, что это за большой смысл.

Я думаю, что это работает. По крайней мере, это относится к единственному тестовому сообщению.

Он принимает ввод, как в вопросе, за исключением того, что без меток номера машины или задачи и с точками с запятой вместо разрывов строк.

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
источник
Можете ли вы дать какое-то объяснение и сказать, каким, по вашему мнению, должен быть ваш счет? Кроме того, не могли бы вы показать, что это дает для примера в вопросе?
Как я сказал в своем ответе, я попробовал это, и это работает на примере. Я не уверен, что такое большая буква О (которую я хотел упомянуть в своем ответе).
KSFT
Как правило, примерно, сколько операций потребуется для завершения. Похоже, что это занимает приблизительно n * заданий * m времени (предположим, что все назначения в циклах занимают постоянное время), что заставляет меня подозревать его правильность, которую я должен признать. Можете ли вы сказать что-то о том, почему вы думаете, что это работает?
1
Ой! Я пропустил это. Таким образом, m на самом деле имеет размер nmachines ^ ntasks. Хорошо, теперь я верю, что это работает. Я думаю, что ваш счет (100 ^ 100) * 100.
4
@Lembik У него пока лучший результат!
KSFT
1

Проверить все - Scala

Ориентировочный балл: 2m ^ n

Я начинаю с каждой машины и перебираю все задачи для создания всех перестановок в задачах с разными машинами, которые соответствуют срокам. То есть, если бы все было вовремя, я бы получил 9 возможных путей с 2 ​​машинами и 3 задачами. (m ^ n) После этого я выбираю путь с наименьшими затратами.

Ввод структурирован следующим образом (-> объясняет части и поэтому не должен вводиться):

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

И вот код:

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

У меня также была идея начать со спины. Так как вы всегда можете выбрать машину с наименьшей стоимостью, если время меньше, то разница от предыдущего срока до нового. Но это не уменьшит максимальное время выполнения, если задача с лучшими затратами займет больше времени, чем установлен последний срок.

Обновить

======

Вот еще одна установка. время:

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_2
M_1  0   2
M_2  6   0

Стоимость переключения:

    M_1 M_2
M_1  0   2
M_2  2   0

сроки:

5 10 15 20

Как вход в мою программу:

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

У этого есть два решения: время: 18, стоимость: 15, путь: список (M_1, M_1, M_1, M_2) время: 18, стоимость: 15, путь: список (M_2, M_1, M_1, M_1)

Что поднимает вопрос, как это должно быть обработано. Должны ли все быть напечатаны или только один? А что если время будет другим? Является ли тот, который имеет наименьшую стоимость и не пропущен крайний срок, достаточно ли, или он также должен быть с наименьшим временем?

Доминик Мюллер
источник
Вопрос говорит, что цель состоит в том, чтобы «[минимизировать] общую стоимость». Кстати, можете ли вы обобщить, как работает ваш алгоритм? Я не знаю Scala, и я не могу понять, как это работает.
KSFT
Перебор всех путей занимает O(m^n)время. Итерации по каждой машине для всех задач требуют O(n*m^n)времени.
KSFT
Разве не O(n*m^n)перебирает каждую задачу для каждого из путей? И перебирать каждую машину для каждой задачи что-то вроде O(n*m).
Доминик Мюллер
Ах, опечатка. Я хотел написать «Перебор каждой машины для всех путей принимает O(n*m^n)».
KSFT
Подожди, нет, это так O(m*m^n)=O(m^n+1). Это все тот же счет, хотя.
KSFT