Algorytm do znalezienia optymalnego połączenia produktów i sklepów, aby zminimalizować koszty

Question

Witam Stackoverflow ludzie,

uruchomić witrynę, która znajduje swój użytkowników najtańsze miejsce na zakup książek. Jest to łatwe w przypadku pojedynczej książki, ale w przypadku wielu książek czasami taniej jest kupić jedną książkę w jednym sklepie i inną książkę z innego sklepu.

Obecnie znajduję najtańszy sklep, który sprzedaje wszystkie książki na liście użytkowników, ale chcę mieć inteligentniejszy system. Oto kilka dodatkowych informacji:

• Cena książki jest stała dla sklepu.
• Cena wysyłki może się różnić w zależności od liczby książek lub łącznej wartości książek.
• Każdy obiekt sklepu może przyjmować wiele książek i zwracać koszty wysyłki.
• Często nie każdy sklep sprzedaje każdą książkę.

Nie jestem pewien czy fajnie jest linkować do mojej strony tutaj, ale jest ona wymieniona w moim profilu użytkownika.

Chciałbym móc znaleźć najtańszą kombinację sklepów i książek.

Obawiam się, że wymaga to brutalnej siły - a przy 35 sklepach liczba kombinacji będzie olbrzymia dla niewielkiej liczby książek. Mam wrażenie, że liczba kombinacji to (#shops)^(# books) - ale nie 100%

Pytanie brzmi, z jakiego punktu widzenia należy korzystać? Czy ten problem pasuje do dobrze znanej klasy problemów? Jeśli wymagana jest brutalna siła, jaki jest dobry sposób na zrobienie tego w Ruby i czy mogę najpierw nadać priorytet sklepom?

Answer 1

Niestety, jest to przykład kombinatorycznego problemu optymalizacji, który nie ma łatwego rozwiązania. Masz rację, że tak naprawdę potrzebujesz podejścia opartego na brutalnej sile. Jednak! Podejrzewam, że w tym problemie jest jakaś specjalna struktura, która pomoże. Na przykład koszt wysyłki nie zmieni się losowo, gdy zmienisz połączenie książek - prawdopodobnie zwiększy się podliniowo i/lub nasycenie podczas dodawania książek.

Oto co polecam, a następnie:

1. w trybie offline, oszacować politykę wysyłki każdego sklepu, tak że, biorąc pod uwagę książki (a może ich wagi) można oszacować koszt wysyłki bez odnosząc się do ich strony.
2. Dla każdego sklepu obliczyć koszt każdej książki, jeśli jest dostępna.
3. W trybie offline przejrzyj każdy sklep lub zestaw sklepów i oszacuj, korzystając z zasad dotyczących wysyłki offline, ile będzie kosztować całość.
4. Wybierz sklep (lub sklepy) o najniższym koszcie. Jeśli istnieje wiele podobnych, obliczyć dokładną odpowiedź.

To powinno wystartować i nie pozwoli na pełne przeszukanie.

Answer 2

Brute Force prawie zawsze można zastąpić dobrą heurystyką, to znaczy algorytmem, który jest znany z tego, że nie jest optymalny, ale "wystarczająco dobry".

Chociaż nie jestem w 100% pewny, myślę, że odnosi się on do Knapsack problem, który jest (jak wszyscy powinniśmy teraz haha ​​..) NP-complete.

Nie masz nic lepszego do zaoferowania, ale powodzenia!

Answer 3

Jest to odmiana klasycznie nazywanego "Problemem przydziału". Klasyczny AP ma kilka standardowych rozwiązań, w tym algorytm Munkres (znany również jako "węgierski") i algorytm JVC (Junker Volgenant Castanon iirc).

Podstawową ideą jest obliczenie kosztu każdego przydziału (czyli kosztu zakupu każdej książki w każdym sklepie), a następnie wybór zestawu zadań, które minimalizują całkowity koszt. Moim zdaniem można to zrobić w czasie wielomianowym.

Fakt, że koszt wysyłki od każdego sprzedawcy zależy od całkowitego zamówienia, sprawia, że ​​jest to znacznie trudniejsze. Możesz użyć metody hybrydowej, która początkowo nie bierze pod uwagę kosztów wysyłki, a następnie wykonuje dla zamówień zbiorczych po zidentyfikowaniu kilku obiecujących przydziałów.

Powodzenia, brzmi jak zabawny problem!

Answer 4

Spróbuj użyć podejścia do programowania dynamicznego. Możesz przeczytać o tym tutaj: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=dynProg Możesz również przeczytać o tym na wikipedii lub w książce "Introduction to Algorithms" (Cormen).

Jest to dość standardowy problem.

Answer 5

czy to może być problem z Lp? http://en.wikipedia.org/wiki/Linear_programming