Przydział pracy bez kosztów, czy węgierska metoda zadziałałaby?

Mam problem z przydziałem pracy, który nie ma tradycyjnego kosztu, którego wymaga węgierska metoda.Przydział pracy bez kosztów, czy węgierska metoda zadziałałaby?

Na przykład:

I have 3 workers - A, B and C 
I have 5 jobs - 1, 2, 3, 4 and 5

Każdy pracownik ma listę zadań może on wykonywać, tak jak poniżej:

worker A can work on job 1, 2, 5 
worker B can work on job 1, 2 
worker C can work on job 1

końcowy wynik (ponieważ nie ma kosztów) jest maksymalna liczba zadań Osiągam. W tym przykładzie mogę wykonać maksymalnie 3 zadania:

worker A on job 5 
worker B on job 2 
worker C on job 1

Czy metoda węgierska jest dobrym sposobem na rozwiązanie tego problemu? Czy powinienem po prostu użyć "fikcyjnego" kosztu? Myślałem, że może wykorzystywać indeks preferencji pracy jako koszt; czy to dobry pomysł?

Źródło

2013-05-09 sap

Ponieważ nie ma żadnych kosztów, jak porównać dwa różne zadania? –

Myślałem o dodaniu "koszta" kosztów w oparciu o indeks preferencji pracy, na przykład pracownik A dla zadania 5 ma koszt 3 (ponieważ jest to trzecia praca na tej liście pracowników), to jest dobry pomysł? – sap

Przypisz koszt -1 do pracy, którą mogą, a pozostałe zero.

Następnie uruchom węgierski algorytm, który da ci odpowiedź (Zwróci ona - w rzeczywistości odpowiedź).

Nie rób tego z dużymi liczbami, może to spowodować przepełnienie (chyba, że bardzo ostrożnie wdrożysz język węgierski).

Rzeczywiście, to Maksymalnie skojarzeń w graf dwudzielny, i istnieje wiele sposobów, aby rozwiązać ten problem, można znaleźć na stronach wiki:

http://en.wikipedia.org/wiki/Matching_(graph_theory)#Maximum_matchings_in_bipartite_graphs

PS: algorytm Hopcroft-Karp jest szybsze niż węgierski i jest również prostszy. Warto spróbować. Niektóre metody komplikacji są szybsze niż te dwa, ale nie jest zalecane, aby uczyć się tych algorytmów na samym początku.

PSS: Twój identyfikator w stackoverflow to metoda rozwiązania tego problemu. Jest to sposób przepływu w sieci. Nazywa się ona najkrótszą ścieżką argumentu (sap).Zobacz: http://coral.ie.lehigh.edu/~ted/files/ie411/lectures/Lecture11.pdf

Źródło

2013-05-09 14:22:22 Sayakiss

Ignorujesz preferencje. Prawdopodobnie możesz zrobić kanalizację, ale jak szczęśliwy byłbyś (żartując)? –

Przepraszam, powinienem powiedzieć, że preferencje nie są ważne, o ile mogę przypisać maksymalną liczbę zadań. – sap

@ZiyaoWei Nie rozumiem dokładnie, jakie są preferencje. – Sayakiss

Kosztowne koszta powinny wystarczyć. Przypisz koszt 1 do dowolnej pracy, którą mogą wykonać, i nieskończony koszt (jeśli twój system na to pozwala) do zadań, których nie mogą. Węgierski algorytm został zaprojektowany w taki sposób, aby zminimalizować całkowity koszt wszystkich zadań, dzięki czemu można w naturalny sposób wykryć pewne rzeczy. Nie powinno być żadnej potrzeby rozliczania się z tego, co według ciebie ich preferencje dotyczące pracy; to jest zadanie algorytmu.

Źródło

2013-05-09 14:17:15

dziękuję za odpowiedź, pomyślałem o tym pierwszy ale bałem się, że matryca końcowa będzie wypełniona 0s po minimalizacji rzędu i kolumny (z wyjątkiem pozycji o nieskończonym koszcie), ale może to nie jest problem? Wciąż jestem nowy w algorytmie i próbuję go nauczyć. – sap

To nie powinno stanowić problemu - oznacza to, że może istnieć więcej niż jedno równie dobre rozwiązanie. –

Węgierski algorytm da ci odpowiedź, ale nie używaj kosztów nieskończoności, ponieważ nie możesz porównać (infinity + infinity) i infinity (chyba że samemu porównasz koszty).

A: 1, 2, 3 

B: 1 

C: 1

Formularz matrix:

1 2 3 

A 1 2 3 

B 1 inf inf 

C 1 inf inf

Jak komputer porównać 1, inf, inf i 2, 1, inf?

Zamiast tego należy użyć niektórych kosztów, które są tak duże, że zagwarantują, że nie zostaną przypisane (i tak, należy zachować ostrożność przy przepełnieniu).

Źródło

2013-05-09 14:21:16

Niestety, nie da się określić takiego kosztu w ogólnym przypadku. –

To prawda - nie patrzyliśmy na węgierski od dłuższego czasu, ale z niezbyt jasno zdefiniowanymi preferencjami, będzie to trudne do zmienienia (wątpię), chyba że podobnie jak ty i inna odpowiedź, zignorujcie preferencje. –

Algorytm węgierski mógłby być tu pracować, ale algorytm nieważone maksymalnej dwustronny dopasowywania jak Hopcroft–Karp byłoby szybciej.

Źródło

2013-05-09 14:35:02

Przydział pracy bez kosztów, czy węgierska metoda zadziałałaby?

Odpowiedz

Powiązane problemy