Hallo,
ich brauche mal einen kleinen Denkanstoß. Ich habe z.B. 64 Waagen und möchte möglichst genau an ein Wunschgewicht als Summe kommen.
z.B: Waage 1 = 60g, Waage 2 = 70, Waage 3 = 80 g, Waage 4 = 72 g
Das Ziel ist 131g, also soll das Ergebnis Waage 1 + Waage 2 oder Wage 1 + Waage 4 sein.
Wenn ich das allerding für alle 2^64 Kombinationen ausführen lasse dauert es ewig ...
Wie löst man solche Aufgaben?
Hardy
Wie kann ich am schnellsten eine Summe von Werten bilden
-
__blackjack__
- User
- Beiträge: 13122
- Registriert: Samstag 2. Juni 2018, 10:21
- Wohnort: 127.0.0.1
- Kontaktdaten:
@HFlor: Grundsätzliche Überlegung: Du musst alle Möglichkeiten berücksichtigen, denn wenn Du ein Ergebnis hast, aber noch nicht alle Kombinationen geprüft hast, kann es ja sein, dass in den nicht geprüften ein besseres Ergebnis steckt.
Was man machen kann ist „branch and bound“, also schauen das man Wege im Suchraum nicht weiter verfolgt, die beispielsweise schlechter sind als das bisher beste Ergebnis, und da es keine negativen Gewichte gibt, auch nicht besser werden können. Falls „möglichst nahe“ bedeutet, dass das Wunschgewicht auch tatsächlich die Obergrenze ist, dann braucht man auch keine Wege zu verfolgen, deren Summe das Wunschgewicht überschreiten.
Was man machen kann ist „branch and bound“, also schauen das man Wege im Suchraum nicht weiter verfolgt, die beispielsweise schlechter sind als das bisher beste Ergebnis, und da es keine negativen Gewichte gibt, auch nicht besser werden können. Falls „möglichst nahe“ bedeutet, dass das Wunschgewicht auch tatsächlich die Obergrenze ist, dann braucht man auch keine Wege zu verfolgen, deren Summe das Wunschgewicht überschreiten.
„All religions are the same: religion is basically guilt, with different holidays.” — Cathy Ladman
Nähere dich der Lösung schrittweise und werfe möglichst früh die Kombinationen raus, die garantiert nicht zum Ziel führen. So könntest du dir erstmal alle Kombinationen mit zwei Waagen ansehen. Ich würde dann bloß die Kombis behalten, die kleiner sind als das Ziel, sowie von den zu großen nur noch diejenige mit dem kleinsten Übergewicht. Die berechneten Kombis samt Gewichte kann man dabei zwischenspeichern, wenn sie ein vielversprechender Kandidat sind. Anschließend die verbliebenen Zweier-Kombis durchgehen und dabei eine dritte Waage hinzunehmen. Mit denen das gleiche Verfahren benutzen wie vorher, usw. Wenn man das halbwegs durchdacht hinbekommt, dann landet man letztlich bei dynamischer Programmierung.
Ich werfe mal zwei Möglichkeiten ein:
Genetische Algorithmen: https://www.pythonpool.com/python-genetic-algorithm/
und https://de.wikipedia.org/wiki/Simulated_Annealing
Genetische Algorithmen: https://www.pythonpool.com/python-genetic-algorithm/
und https://de.wikipedia.org/wiki/Simulated_Annealing
Ich bin Pazifist und greife niemanden an, auch nicht mit Worten.
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
Für alle meine Code Beispiele gilt: "There is always a better way."
https://projecteuler.net/profile/Brotherluii.png
