Próbuję znaleźć "algorytm barmański"

Question

Rozwiązałem kilka przykładowych pytań ze starego konkursu programistycznego. W tym pytaniu otrzymujemy informacje o tym, ile mamy barmanów i jaki przepis oni znają. Każdy koktajl trwa 1 minutę i musimy obliczyć, czy zamówienie można ukończyć w ciągu 5 minut, używając wszystkich barmanów.

Kluczem do rozwiązania tego problemu jest przypisywanie koktajli tak efektywnych, jak to tylko możliwe. I to tam utknąłem, mój obecny algorytm przekazuje zamówienie barmanowi, który zna najmniej innych przepisów. Ale oczywiście nie jest to jeszcze w 100% poprawne. Czy ktoś może wskazać mi właściwy kierunek (lub podać mi nazwę algorytmu google), który rozwiązuje ten "problem barmański"?

Answer 1

Jest to wariant na college matching problem. Gdzie napoje są studenci i barmani są kolegiami. Z kolei jest to generalizacja stable marriage problem, która może być dla ciebie bardziej użyteczna.

Answer 2

Tworzenie listy koktajli na zamówienie, zsekwencjonowany przez ile przetargi wiedzą, jak sprawić, że koktajl

tj Kolejność jest (2 * CocktailA, 1 * CocktailB, 2 * CocktailC, 1 * CocktailD)

CocktailA mogą być wykonane przez 4 ofert (Oferty A, B, C, D)
CocktailA mogą być wykonane przez 4 ofert (Oferty A, B, C, D)
CocktailB mogą być wykonane przez 3 ofert (Oferty A, B, C)
Koktajl może być złożony z 1 oferty (Przetarg A)
CocktailC może być wykonane do dnia 1 Tender przetargu (A)
CocktailD może być wykonane do dnia 1 Tender przetargu (B)

praca wstecz dzięki tej liście, przydzielanie zadań ofert. Jeśli wiele przetargów może wykonać koktajl, wybierz ten, który ma najmniej przydzielonych zadań.

CocktailD = Tender B
CocktailC = udzielać
CocktailC = udzielać (ponownie)
CocktailB = Tender C
CocktailA = Tender D
CocktailA = Tender B (ponownie)

Oferty i B oba mają 2 zadania, więc zamówienie zajmie 2 minuty.

Answer 3

Można to rozwiązać za pomocą sieci przepływowej.

• Źródłem ma krawędzie każdego barmana, o pojemności 5.
• Każdy barman mają krawędzie każdego napoju on/ona może zrobić, o pojemności 5.
• Każdy napój mieć krawędzie do zlewu, z pojemność odpowiadająca zamówionej liczbie.

Obliczyć maximum flow od źródła do zlewu. Jeśli jakiekolwiek zamówienie pozostanie niespełnione, nie ma rozwiązania.

Answer 4

To jest problem z kolorowaniem wierzchołków. Jest to dokładnie analogiczne do problemu alokacji rejestru, który jest bardzo dobrze zbadany. Zobacz http://en.wikipedia.org/wiki/Register_allocation. Można go również traktować jako problem z pokrywą, który jest analogiczny do kolorowania wierzchołków.

Oczywiście tutaj nie potrzebujemy znaleźć właściwego koloru, musimy jedynie ustalić, czy jego liczność wynosi 5 lub mniej. Jeśli wykres barmański może być kolorowy w 5 lub mniejszej ilości kolorów, odpowiedź brzmi: Tak, w przeciwnym razie Nie. Oto kolejna fajna praca opisująca problem w kategoriach "zadań" i "dni" oraz "maszyn": http://www.polymtl.ca/pub/sites/lagrapheur/docs/en/documents/NotesChap7.pdf.

Teraz, aby to zrozumieć, tak zwana "liczba chromatyczna" lub "indeks chromatyczny" wykresu jest NP-trudna. W rzeczywistości, ktoś już zapytał na SO o algorytm znajdowania liczby chromatycznej wykresu, ale niestety nie otrzymałem dużej odpowiedzi, zobacz Algorithm for Chromatic Number of a Graph? Po prostu rozglądałem się po sieci znalazłem jakieś zasoby kodu do robienia barwniki. Jeden, który może zrobić ten problem, nazywa się SMALLK. SMALLK może znaleźć kolorowania do 8. Ponieważ potrzebujemy tylko 5 dla tego problemu, ten pakiet może to zrobić.