On Tue, 21 Dec 2010 10:36:27 +0100, "bagno" <b...@o...pl> wrote:

>Witam
>
>Temat może jest głupi ale nie wiedziałem jak to napisać.
>
>Mam jakieś pojemniki a w nich losowe ilości "cosiów". Muszę je tak poprzenosić
>aby uzyskać równe ilości najmniejszym kosztem. Koszt przeniesienia każdego elementu
>między dwoma dowolnymi pojemnikami jest z góry określony.
>
>Jaki w miarę prosty algorytm zastosować ? Jest w ogóle jakiś w miarę prosty ?
>
>Pojemników jest 500 a cosiów jakieś 5000. W większości pojemników jest już na
starcie
>prawidłowa ilość elementów więc można ich nie ruszać chyba, że koszt przeniesiania
do
>takiego pojemnika a potem z niego dalej będzie mniejszy niż koszt bezpośredniego
przeniesienia
>między dwoma pojemnikami.
>
>Fajnie by było dodatkowo założyć, że lepiej przenieść do jednego pojemnika więcej
>elementów z tego samego pojemnika niż z różnych. To pewnie dałoby się uzyskać przez
>dynamiczne zmiany tych kosztów zależnie od tego co już wcześniej zostało
przeniesione.

Jak pisal Wit Jakuczun, to jest "Assignment problem". Assignment
problem mozna rozwiazac przy pomocy programowania liniowego (albo
specjalnej wersji dla assignment problem zwanej Hungarian algorithm.
Implementacje mozna znaleac w sieci).

Twoj problem jest dosyc duzy, wiec programowania liniowego bym nie
zalecal.

Assignment problem jest znany jako "bipartite matching minimum weight
problem", co z kolei jes tszczegolnym przypadkiem "general minimum
weigh matching problem". Do tego ostatniego sa dobre algorytmy
przyblizone. Gwarantuja ze koszt nei bedzie gorszy niz 1/2 kosztu
optymalnego.

Opis algorytmu (a wlasciwie dwoch) jest tutaj

http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.
1.1.11.5212

Kazdy z nich zapisuje sie na pol stronei Javy i oba sa bardzo szybkie.

Ci sami autorzy podaja algorytmy gwarantujace 2/3 optymalnosci, ale sa
one bardzo skomplikwoane i jak wykazuje moje doswiadczenie, nei warte
zachodu

A.L.