Я пытаюсь найти "алгоритм бармена",

Я решал некоторые примеры из старого конкурса программирования. В этом вопросе мы получаем информацию о том, сколько у нас бармена и какой рецепт они знают. Каждый коктейль занимает 1 минуту, и нам нужно рассчитать, может ли заказ быть завершен в течение 5 минут, используя всех барменов.

Ключом к решению этой проблемы является максимально эффективное использование коктейлей. И вот где я застрял, мой текущий алгоритм дает заказ бармену, который знает наименьшие другие рецепты. Но, конечно, это еще не 100% правильно. Может ли кто-нибудь указать мне в правильном направлении (или дать мне имя алгоритма для google), который решает эту проблему "бармена"?

Ответ 1

Это можно решить с помощью сети потока.

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

Вычислить максимальный поток от источника до приемника. Если какой-либо порядок остается невыполненным, решения нет.

Ответ 2

Создайте список коктейлей по заказу, упорядоченный тем, сколько тендеров знают, как сделать этот коктейль

т.е. порядок для (2 * CocktailA, 1 * CocktailB, 2 * CocktailC, 1 * CocktailD)

Коктейль может быть сделан четырьмя тендерами (тендеры A, B, C, D)
CocktailA может быть изготовлен четырьмя тендерами (тендеры A, B, C, D)
CocktailB может быть изготовлен тремя тендерами (тендеры A, B, C)
CocktailC можно сделать одним тендером (тендер A)
CocktailC можно сделать одним тендером (тендер A)
CocktailD можно сделать одним тендером (тендер B)

Работайте в обратном направлении через этот список, назначая задания на тендеры. Если несколько тендеров могут сделать коктейль, а затем выберите тот, у которого минимальное количество заданий уже назначено.

КоктейльD = Тендер B
CocktailC = Тендер A
CocktailC = Тендер A (снова)
КоктейльB = Тендер C
CocktailA = Тендер D
Коктейль A = Тендер B (снова)

Тендеры A и B имеют 2 задания, поэтому порядок займет 2 минуты.

Ответ 3

Это проблема с раскраской вершин. Это точно аналогично проблеме распределения регистров, которая очень хорошо изучена. См. http://en.wikipedia.org/wiki/Register_allocation. Его также можно рассматривать как заданную проблему обложки, аналогичную окраске вершин.

Конечно, здесь нам не нужно найти фактическую окраску, нам просто нужно определить, имеет ли ее мощность 5 или меньше. Если график бармена может быть окрашен в 5 или менее цветов, тогда ответ будет да, иначе Нет. Вот еще одна хорошая статья, описывающая проблему с точки зрения "задач" и "дней" и "машин": http://www.polymtl.ca/pub/sites/lagrapheur/docs/en/documents/NotesChap7.pdf.

Теперь, чтобы понять это, то, что называется "хроматическим числом" или "хроматическим индексом" графика, является NP-трудным. На самом деле, кто-то уже спросил о SO для того, чтобы алгоритм нашел хроматическое число графа, но, к сожалению, не получил ответа, см. Алгоритм для хроматического числа графа?

Просто оглядываясь по сети, я нашел некоторые ресурсы кода для создания раскрасок. Тот, который может решить эту проблему, называется SMALLK. SMALLK может найти расцветки до 8. Поскольку нам нужна только 5 для этой проблемы, этот пакет может это сделать.

Ответ 4

Это вариант в проблема соответствия колледжа. Где напитки - студенты, а бармены - колледжи. В свою очередь это является обобщением стабильной проблемы с браком, которая может быть более полезной для вас.