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.

do góry

W dniu 2010-12-21 10:36, bagno pisze:
> 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 ?
>
To jest wariacja assignment problem (
http://en.wikipedia.org/wiki/Assignment_problem ). Prostych algorytmów
nie ma.

Pozdrawiam,
Wit

do góry

On 21 Gru, 10:36, "bagno" <b...@o...pl> wrote:
> Witam
>
> Temat może jest głupi ale nie wiedziałem jak to napisać.
Wrecz przeciwnie, jest ciekawy.

> 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.

Czyli masz N pojemikow, K*N obiektow i macierz NxN kosztow. Dazysz
do tego, aby w kazdym pojemniku bylo K elementow jak najmniejszym
kosztem.

Pierwsza sprawa, jakie sa wartosci kosztow w macierzy NxN? Jesli sa
zerowe, to kazdy sposob przeniesienia jest sobie rowny, a jesli
zdarzaja sie ujemne, to koszt mozna obnizac w nieskonczonosc :)

> Jaki w miarę prosty algorytm zastosować ? Jest w ogóle jakiś w miarę prosty ?
Wyglada to na jakas odmiane zadania transportowego. Prosty i chyba
dosc
dobry algorytm zachalnny na pewno istnieje.

Pozdrawiam

do góry

Mariusz Marszałkowski wrote:

> On 21 Gru, 10:36, "bagno" <b...@o...pl> wrote:
>> Witam
>>
>> Temat może jest głupi ale nie wiedziałem jak to napisać.
> Wrecz przeciwnie, jest ciekawy.
>
>> 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.
>
> Czyli masz N pojemikow, K*N obiektow i macierz NxN kosztow. Dazysz
> do tego, aby w kazdym pojemniku bylo K elementow jak najmniejszym
> kosztem.
>
> Pierwsza sprawa, jakie sa wartosci kosztow w macierzy NxN? Jesli sa
> zerowe, to kazdy sposob przeniesienia jest sobie rowny, a jesli
> zdarzaja sie ujemne, to koszt mozna obnizac w nieskonczonosc :)

Może być logarytmiczny im wiecej przenosisz tym drożej. (lub taniej)

>> Jaki w miarę prosty algorytm zastosować ? Jest w ogóle jakiś w miarę
>> prosty ?
> Wyglada to na jakas odmiane zadania transportowego. Prosty i chyba
> dosc
> dobry algorytm zachalnny na pewno istnieje.

Ciekawe czy nie jest to związane z szyfrowaniem plecakowym.

do góry

On 21 Gru, 13:18, Marcin Gąska <w...@w...pl> wrote:
> Mariusz Marszałkowski wrote:
> > On 21 Gru, 10:36, "bagno" <b...@o...pl> wrote:
> >> Witam
>
> >> Temat może jest głupi ale nie wiedziałem jak to napisać.
> > Wrecz przeciwnie, jest ciekawy.
>
> >> 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.
>
> > Czyli masz N pojemikow, K*N obiektow i macierz NxN kosztow. Dazysz
> > do tego, aby w kazdym pojemniku bylo K elementow jak najmniejszym
> > kosztem.
>
> > Pierwsza sprawa, jakie sa wartosci  kosztow w macierzy NxN? Jesli sa
> > zerowe, to kazdy sposob przeniesienia jest sobie rowny, a jesli
> > zdarzaja sie ujemne, to koszt mozna obnizac w nieskonczonosc :)
>
> Może być logarytmiczny im wiecej przenosisz tym drożej. (lub taniej)
>
> >> Jaki w miarę prosty algorytm zastosować ? Jest w ogóle jakiś w miarę
> >> prosty ?
> > Wyglada to na jakas odmiane zadania transportowego. Prosty i chyba
> > dosc
> > dobry algorytm zachalnny na pewno istnieje.
>
> Ciekawe czy nie jest to związane z szyfrowaniem plecakowym.

Nie wiem, ale na pewno programowanie nieliniowe może podsunąć
przybliżone rozwiązanie.
http://www.przeklej.pl/plik/tt-xls-00250lbvq1dc
Pozdrawiam

do góry

On Tue, 21 Dec 2010 11:08:15 +0100, Wit Jakuczun
<w...@g...com> wrote:

>W dniu 2010-12-21 10:36, bagno pisze:
>> 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 ?
>>
>To jest wariacja assignment problem (
>http://en.wikipedia.org/wiki/Assignment_problem ). Prostych algorytmów
>nie ma.
>
>Pozdrawiam,
> Wit

Jezeli to jest assignment problem, to sa bardzo proste algorytmy
"greedy" dajace gwarantowana 50% sprawnosc. Sa tez algorytmy dajace
gwarantowana sprawnosc 2/3, ake sa skomplikwoane.

No i zawsze jest programowanie liniowe ktore nie jest rocket science

A.L.

P.S. Linki do artykulow dam Oryginalnemu Pytaczowi jak dotre do pracy
bo tam mam owe artykuly

do góry

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.

do góry

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

Nie zawsze sie da rowne ilosci. Na przykald 13 cosow nie da sie
podzielic na 3 pojemniki tak zeby bylo po rowno

A.L.

do góry

W dniu 2010-12-21 16:27, A.L. pisze:
> 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
>
> Nie zawsze sie da rowne ilosci. Na przykald 13 cosow nie da sie
> podzielic na 3 pojemniki tak zeby bylo po rowno
>
Problem jest niedoprecyzowany. Wygląda, że jest dwu-kryterialny: koszt i
to na ile równo rozdzielono. W szczególności nie wiadomo jak postąpić w
przypadku, który podałeś.

Pozdrawiam,
Wit

do góry

On Tue, 21 Dec 2010 16:44:17 +0100, Wit Jakuczun
<w...@g...com> wrote:

>W dniu 2010-12-21 16:27, A.L. pisze:
>> 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
>>
>> Nie zawsze sie da rowne ilosci. Na przykald 13 cosow nie da sie
>> podzielic na 3 pojemniki tak zeby bylo po rowno
>>
>Problem jest niedoprecyzowany. Wygląda, że jest dwu-kryterialny: koszt i
>to na ile równo rozdzielono. W szczególności nie wiadomo jak postąpić w
>przypadku, który podałeś.
>
>Pozdrawiam,
> Wit

Podzial mozna przyjac arbitralnie. jak podzial sie zacznie
optymalizowac, to problem wyjdzie gigantyczny i juz nie bedzie
assignment. Ja mam podobny problem i rozwiazuje go dwuetapowo przy
pomocy LP, ale oczywiscie rozwiazanei globalnie nie jest optymalne

A.L.

do góry