Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
20. Okt 2006
Ja, das ist die einzig beweisbare Möglichkeit für NP-komplette Probleme.
In der Praxis hat sich jedoch gezeigt, das es reicht, eine "hinreichend optimale" Lösung zu finden. Wenn ich sowieso drei (statt 5) LKW benötige (hinreichend optimal), dann ist es mir doch egal, wenn ob der eine LKW zu 55 oder 60% gefüllt ist.
Diese suboptimalen Algorithmen (auch zum 'Traveling Salesman') sind die...
Forum: Sonstige Fragen zu Delphi
Delphi
by alzaimar,
19. Okt 2006
Beim 0/1-Knapsack-Problem gibt es keine richtige Strategie. Brute-Force und Backtracking ist das einzige Verfahren, das die optimale Ergebnis liefert.
Die 'Chaos'-Suche (evoutionäre Programmierung) ist aber schon lustig:
1. Finde eine (suboptimale) Lösung (Rucksack ist voll)
2. Nimm ein paar Dinge raus und pack ein paar wieder rein.
3. Wenn der Rucksack nun besser gepackt ist, fein. Dann...
