UNItopia News: Brett Computer, Gruppe Allgemeines, Artikel 1741
-------------------------------------------------------------------------------
Titel: Re: Idee oder Algorithmus gesucht
Artikel: 1741 Bezug: 1740
Verfasser: Tao Datum: 04.03.05 09:05:09
-------------------------------------------------------------------------------
Hallo,
euer Gefuehl truegt euch nicht. Das Rucksackproblem ist
NP-vollstaendig.
Fuer Traveling-Salesman habe ich mal einen Algorithmus gesehen, der
darauf beruht hat, Teilstrecken "umzudrehen". Wenn das Umdrehen zu
einem besseren Ergebnis gefuehrt hat, wird die Loesung beibehalten,
wenn das Umdrehen das Ergbnis verschlechtert hat, wird es rueckgaengig
gemacht. Und damit das Verfahren zu einem Ende kommt, wird die
maximale Groesse der Teilstrecke, die veraendert wird, immer mehr
verringert.
Das koennte man vielleicht auch auf das Rucksackproblem anwenden. Du
raetst eine Loesung, faengst an, eingepackte Teile mit den nicht
eingepackten zu vertauschen, und verringerst bei jedem Schritt die
Maximalgroesse, die ein ausgetauschtes Teil haben darf.
Vermutlich gibt es aber irgendwo im Web einen viel besseren
Algorithmus.
Gruss,
Tao
