algorytm - dystrybucja przedmiotow, jak do tego podejsc

0

Witam, jestem przekonany ze taki algorytm juz ktos kiedys napisal, ale nie wiem wedlug jakiego klucza go szukac. Mam nastepujacu problem. Wyobrazmy sobie ze mamy N samochodow i N klientow. Samochody maja okreslone kolory, np. mamy a czerwonych, b czarnych, c zielonych itd. Z drugiej strony mamy klientow, ktorych interesuja pewne kolory, np klient A chce tylko czarny lub zielony, klient B tylko czerwony, klient D jakis kolor ktorego nie mamy itd. Potrzebuje stwierdzic czy da sie kazdemu klientowi zaoferowac auto w takim kolorze, jaki mu odpowiada, a jesli tak, podac przykladowe przyporzadkowanie, kto dostanie jaki kolor (najlepiej wszystkie mozliwe przyporzadkowania). Oczywiscie metoda brute force w stylu sprawdzania wszystkich mozliwych kombinacji nie wchodzi w gre

0

Ogólnie brzmi to na https://en.wikipedia.org/wiki/Boolean_satisfiability_problem; w zależności od tego, jak złożone warunki chcesz obsługiwać ^1, być może da się podejść do tego sprytniej niż wykorzystując / wynajdując solver.

^1 w szczególności kłopotliwe mogą być sytuacje, w których klienci przestają być niezależni - tj. zapytania w stylu jeśli klient A dostanie czerwone, to klient B się obrazi i będzie chciał zielone

1

Jest to zadanie optymalizacyjne. Masz zbiór klientów A, B, C, D, ..., oraz zbiór dostępnych kolorów aut: K1, K2, K3, .... Określ preferencyjność (zadowolenie) danego koloru dla każdego z klientów, np:

A - K1 - zadowolenie 10
A - K2 - zadowolenie -inf
A - K3 - zadowolenie 9
...
B - K1 - zadowolenie -inf
B - K2 - zadowolenie 10
B - K3 - zadowolenie 9
...

-inf oznacza, że osoba całkowicie nie akceptuje danego koloru - rozwiązanie nie spełnia wymagań. Z tego dostaniesz funkcję dwuargumentową: F(osoba, kolor) -> zadowolenie

Następnie musisz zmaksymalizować funkcję celu, czyli znaleźć taki zestaw przypisań osoba_i -> kolor_i dla którego ta funkcja ma maksymalną wartość.

F_celu(osoba_1, kolor_1, osoba_2, kolor_2, ..., osoba_n, kolor_n) = suma po i ( F(osoba_i, kolor_i) ).

Jeśli dostaniesz -inf to oznacza, że nie ma rozwiązania - nie ma takiej kombinacji, aby nie było osoby niezadowolonej z koloru.
Jeśli się nie mylę można to rozwiązać jakimś algorytmem z programowania dynamicznego.

1

@Patryk27:

Następnie musisz zmaksymalizować funkcję celu i cyk algorytm genetyczny

Jeśli sprowadzisz problem optymalizacyjny do programowania liniowego (zagadnienie transportowo-produkcyjne i tym podobne) to absolutnie nie potrzebujesz żadnych algorytmów genetycznych :] A mając taką "macierz zadowolenia", "zapotrzebowania" poszczególnych odbiorców i możliwości produkcyjne dla poszczególnych modeli, jak najbardziej powinieneś być w stanie sprowadzić zadanie do tego typu. Do tego już wystarczy pierwszy lepszy solwer wykorzystujący np. metodę symplex/simplex (nigdy nie pamiętam), np. ten z Excela.

https://pl.wikipedia.org/wiki/Algorytm_sympleksowy

0

Ogolnie nie ma zadnych poziomow zadowolenia klientow, przyklad z klientami i samochodem byl tylko do przedstawienia problemu. Klient nie ma zadnego rankingu kolorow, wszystkie maja jednakowa wartosc, ale nie akceptuje innych kolorow niz deklarowane. Tutaj celem jest 'sprzedaz' wszystkich samochodow, a nie maksymilizacja zadowolenia. Chodzi o znalezienie rozwiazania (najlepiej wszystkich mozliwych) lub stwierdzenie ze takiego rozwiazania nie ma (na przyklad kiedy 3 osoby chca tylko auto jednego, tego samego koloru, ale auta sa tylko 2) - to chyba nie jest problem pod simplex. Oczywiscie "klientom" ktorzy maja tylko jeden preferowany wybor moge dac to co chca, nastepnie odjac ten samochod i klienta z listy dostepnych, oraz z drugiej strony, jesli jest samochod ktory chce tylko jedna osoba, dac go jej, i tak postepowac dopoki istnieja jakies "jedynaki" i tak dojde do sytuacji gdzie na kazde auto jest przynajmniej dwoch chetnych i kazdy klient ma jeszcze przynajmniej dwie opcje i wtedy sprawdzac wszystkie mozliwe podstawienia (lub kiedy dla kogos nie bedzie auta, lub auta nikt nie bedzie chcial - wtedy juz na tym etapie wiadomo ze rozwiazania nie ma). Samochodow i klientow jest zawsze dokladnie 25. Moge zaczac od osoby, ktora ma najmniej akceptowanych kolorow, i przyporzadkowac jej auto, ktore akceptuje najwiecej osob, i z duzym prawdopodobienstwem po kilku petlach znajde rozwiazanie, ale moze sie to w najgorszym przypadku skonczyc testowaniem 25! mozliwosci.

0

Nie wiem jak ten algorytm się nazywa, ale pokażę na przykładzie. Mamy 3 klientów i 3 samochody.

K[] = [K1, K2, K3]
P[] = [P1, P2, P3]

Macierz jakie samochody są dozwolone dla danego klienta niech wygląda tak:

   | K1 | K2 | K3
P1 | 1  | 1  | 0
P2 | 1  | 0  | 1
P3 | 0  | 1  | 0

Zakładamy, że żonglujemy (zmieniamy kolejność elementów) tablicą P[], a tablica K[] ma niezmienną kolejność.
Szukamy więc wszystkich ustawień elementów tablicy P[], aby pasowały do K[].

Tak więc:

[K1, K2, K3]
[P2, P1, P3]

jest poprawnym rozwiązaniem, ale na przykład:

[K1, K2, K3]
[P3, P2, P1]

już nie.

Teraz tylko jak zrobić to jak najmniejszym kosztem. Jednym z rozwiązań jest sprawdzenie wszystkich permutacji tablicy P[], ale to jest słabe podejście.

Tworzenie tej tablicy można potraktować jak przechodzenie po drzewie, składającym się z elementów P[]. A właściwie po trzech drzewach, dlatego, że mamy 3 pojazdy. Takie przejście po wszystkich drzewach wygląda tak:

P1
P1 -> P2
P1 -> P2 -> P3   nie ok
P1 -> P3
P1 -> P3 -> P2   nie ok
P2
P2 -> P1
P2 -> P1 -> P3   ok - poprawne rozwiązanie
P2 -> P3
P2 -> P3 -> P1   nie ok
P3
P3 -> P1
P3 -> P1 -> P2   nie ok
P3 -> P2
P3 -> P2 -> P1   nie ok

Wyszło więcej operacji, niż przy permutacji. Ale takie rozwiązanie ma jedną sztuczkę, którą można wykorzystać. Jeśli aktualny wierzchołek na który przeszliśmy nie spełnia warunku - możemy pominąć wszystkie kolejne poddrzewa. Na przykład będzie to tak:

P1               ok
P1 -> P2         nie ok, pomiń wszystkie kolejne poddrzewa
P1 -> P3         nie ok, pomiń wszystkie kolejne poddrzewa
P2               ok
P2 -> P1         ok
P2 -> P1 -> P3   ok - poprawne rozwiązanie
P2 -> P3         nie ok, pomiń wszystkie kolejne poddrzewa
P3               nie ok, pomiń wszystkie kolejne poddrzewa

Przy 25 pojazdach i klientach zysk obliczeniowy z takiego rozwiązania będzie ogromny.

0

tak, to jest problem kojarzenia malzenstw, gdzie najpierw trzeba sprawdzic zdaje sie 2 do n grup klientow czy jest dla nich przynajmniej tyle aut co wielkosc grupy, a jesli tak, to przejezdzam takie drzewko, ktore w najgorszym przypadku (jesli sypie sie na ostatnim wierzcholku) moze oznaczac 25! prob, choc dla kilkuset testowych zestawow danych tylko raz tych prob bylo wiecej jak 1k - w tych zestawach klient akceptuje ok 10 z 25 samochodow. Chyba nic lepszefo nie wymysle :)

0

@kaile darnell: Jeśli algorytm o którym pisałem wcześniej sprawdzi się - napisałem kiedyś dokładnie taki algorytm przechodzenia po drzewie w C#. Mam go u siebie na GH. Może w jakiś sposób pomoże.

PermutationTree
Dokumentacja, przykład

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0