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
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
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.
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.
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.
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.
A to nie jest przypadkiem problem kojarzenia małżeństw ?
http://www.mini.pw.edu.pl/miniwyklady/grafy/prob-malz.html
https://pl.wikipedia.org/wiki/Twierdzenie_o_kojarzeniu_ma%C5%82%C5%BCe%C5%84stw
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 :)
@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.