Frage nach Suchalgorithmus

[Senior Sanchez]

Hallo,

Ich habe eine geometrische Punktmenge gegeben, die sich in einem zwei-dimensionalen Koordinatensystem befindet.

Weiterhin sind in diesem Koordinatensystem Ziele (kreisrunde Flächen) gegeben, die ein bestimmtes Fassungsvermögen haben.
Die Aufgabe ist nun die Punkte in die Ziele zu bewegen und zwar so, dass das Fassungsvermögen jeden Zieles nicht überschritten wird.
Dabei soll die Lösung optimal sein, das heißt dass die Summe der Strecken die bei der Bewegung der Punkte zurückgelegt werden muss, minimal ist.

Es können aber auch noch weitere Bedingungen auftreten, sodass nur bestimmte Punkte in bestimmte Ziele passen.

Es kann aber auch vorkommen, dass ich z.B. 30 Punkte habe und nur ein Ziel gegeben ist, in welches 15 Punkte hineinverschoben werden sollen.
(Was aber nicht wirklich ein Problem darstellen sollte)

Das ganze scheint auch als Spezialfall das kapazitiven Transportproblems bekannt zu sein und meine Frage ist nun, welches der schnellste, praktisch-anwendbare Algorithmus ist, um dieses Problem zu lösen.

Im Moment denke ich in die Richtung minimaler Fluss in einem Graphen, aber ob das die beste Variante ist?

EDIT: Wenn diese Variante auch gleichzeitig noch dazu geeignet ist, auch nach einer zufälligen Bewegung der Punkte weiterhin zu entscheiden ob die Lösung optimal bleibt, wäre das ideal

[Stone2001]

Interessante Aufgabe!

So wie es aussieht, ist dein Problem aber NP-Vollständig, damit ist eine optimale Lösung nicht "sonderlich" schnell zu finden. (In Wikipedia wird das kapazitive Transportproblem auf ILP abgebildet).

Eine Lösung bekommt man aber recht schnell (über die Güte lässt sich dann allerdings nichts aussagen). Trivialerweise würde man die Entfernung jedes Punktes zu jedem Ziel berechnen und den Punkt mit der geringsten Entfernung zu einem Ziel verschieben. Falls ein Ziel seine Kapazität erreicht, werden alle Entfernungen zu ihm auf unendlich gesetzt, damit verhindert man, dass weitere Punkt zu diesem Ziel verschoben werden.

[Gnafoo]

@Stone2001: Ich kann zwar nicht direkt helfen, aber mich (und die anderen vielleicht auch) würde interessieren, auf welchen Wikipedia-Artikel du dich genau beziehst. Ich habe eben eine Weile in der deutschen und englischen Wikipedia gesucht, aber leider nichts finden können.
Vielleicht fehlen mir aber auch nur alternative Bezeichnungen für das Kapazitive Transportproblem. :D

Edit: Vielen Dank @Stone. Da hätte ich nach "kapazitives Transportproblem", "capacitive transport problem" etc. pp. auch selber drauf kommen können :D.

[Trap]

Man könnte das soweit ich sehe auch als minimum cost flow modellieren (oder ist das das gleiche wie das kapazitive Transportproblem?). Ob das was bringt musst du selbst nachrechnen, mir ist das Problem nicht so 100% klar.

[Stone2001]

@Stone2001: Ich kann zwar nicht direkt helfen, aber mich (und die anderen vielleicht auch) würde interessieren, auf welchen Wikipedia-Artikel du dich genau beziehst. Ich habe eben eine Weile in der deutschen und englischen Wikipedia gesucht, aber leider nichts finden können.
Vielleicht fehlen mir aber auch nur alternative Bezeichnungen für das Kapazitive Transportproblem. :D
Lass mal "kapazitive" weg... :D
Dann kommst du auf diese Seite: http://de.wikipedia.org/wiki/Transportproblem (war bei mir gleich der erste Link in Google) Beim kapazitiven Transportproblem haben die Transporter eine bestimmte Kapzität.

@Trap: das Transportproblem kann man auch als Min-Cost-Flow-Problem formulieren (zumindest steht das im Wiki-Artikel).

[bulla]

Schau dir mal das Savings-Verfahren an, evtl. in Kombination mit der Zirkelmethode.

[Senior Sanchez]

Schau dir mal das Savings-Verfahren an, evtl. in Kombination mit der Zirkelmethode.

Haste dazu nen Link?

@trap, richtig, dieses Problem entspricht einem min-cost-flow-Problem, deshalb auch meine Idee mit dem minimalen Fluss in einem Graphen.

Mir ist aber aufgefallen, dass man das ganze doch auch als bipartiten Graphen auffassen könnte, da die beiden Mengen (Punkte und Ziele) ansich ja disjunkt sind. Damit lassen sich ja bestimmte Graphenalgorithmen wesentlich schneller berechnen.
Das bestimmte Punkte nicht in bestimmte Ziele passen, könnte man dann durch ein unendliches Kantengewicht ausdrücken.

Ich habe auch noch etwas recherchiert und ansich würde ich momentan zwei Verfahren ins Auge fassen: Zuerst ein min-cost-flow-Algorithmus, der vielleicht etwas lange braucht. Zum Validieren, ob die Lösung nach einer zufälligen Bewegung der Punkte weiterhin optimal ist, würde sich eine iterative Variante noch in der Kombination anbieten.

@Stone2001
Wie kommste darauf, dass das NP-vollständig ist?

[Senior Sanchez]

So nach weiterer Recherche scheint der Netzwerk-Simplex-Algorithmus recht gut zu sein. Dieser löst das min-cost-flow-Problem in polynomialer Laufzeit und somit ist das Problem nicht NP-vollständig.

Allerdings ist das ganze ziemlich komplex und gute, verständliche Literatur zu finden, ist nicht gerade einfach.

Ich bin aber weiterhin offen für andere Verfahren *g*

[Trap]

Man muss aufpassen die richtigen Problemgrößen in der Laufzeitbetrachtung zu benutzen, die Zahl der Kanten wächst schneller als linear mit Zielen und Punkten. Glücklicherweise aber immernoch polynomiell und nicht exponentiell.

Graphenalgorithmen für min-cost-flow wären:
pseudopolynomiell: "capacity scaling", "cost scaling" und "double scaling"
echt polynomiell: "minimum mean cycle-canceling", "repeated capacity scaling" und "enhanced capacity scaling"

Ich würd vorschlagen du guckst dir einen der pseudopolynomiellen an, die sind alle relativ einleuchtend wenn man sich schon mit Graphenalgorithmen auskennt. Das "pseudo-" stört bei deiner Aufgabenstellung ja nicht.

Achso: Optimierungsprobleme können nicht NP-vollständig sein, die Kategorie existiert nur für Entscheidungsprobleme.

[bulla]

http://www.ifl.uni-karlsruhe.de/download/vorlesungen/logistik/060515_Kap_4_Tourenplanung.pdf
http://dsor.uni-paderborn.de/vawi/16_tourenplanung_heuristisch/
http://www.wior.uni-karlsruhe.de/LS_Neumann/Lehre/SS2003/GraphenUndNetzwerkeSS03_html

[Senior Sanchez]

Man muss aufpassen die richtigen Problemgrößen in der Laufzeitbetrachtung zu benutzen, die Zahl der Kanten wächst schneller als linear mit Zielen und Punkten. Glücklicherweise aber immernoch polynomiell und nicht exponentiell.

Graphenalgorithmen für min-cost-flow wären:
pseudopolynomiell: "capacity scaling", "cost scaling" und "double scaling"
echt polynomiell: "minimum mean cycle-canceling", "repeated capacity scaling" und "enhanced capacity scaling"

Ich würd vorschlagen du guckst dir einen der pseudopolynomiellen an, die sind alle relativ einleuchtend wenn man sich schon mit Graphenalgorithmen auskennt. Das "pseudo-" stört bei deiner Aufgabenstellung ja nicht.

Achso: Optimierungsprobleme können nicht NP-vollständig sein, die Kategorie existiert nur für Entscheidungsprobleme.

Ich denke die pseudopolynomiellen wären denke ich am besten. Netzwerk-Simplex wäre IMO völlig oversized! Meine Punktmenge besteht vllt aus maximal 50 Punkten und Ziele gibt es glaube ich maximal 3.

Haste da ne Empfehlung welcher am besten geeignet wäre?

[Trap]

Haste da ne Empfehlung welcher am besten geeignet wäre?
Gute Frage, als ersten Schritt kann man entweder cost oder capacity scaling nehmen, double scaling ist halt beides kombiniert. Die Idee bei beiden ist falsche Konfigurationen zuzulassen und die maximalen Fehler immer kleiner zu machen bis man am Ende eine optimale Lösung hat. Beim cost scaling hat man zuerst welche die nicht optimal sind, beim capacity scaling hat man zuerst welche die die Kapazitätsgrenzen nicht beachten.

Ich würde cost scaling nehmen, die Implementierung scheint mir etwas einfacher zu sein. Könnte auch ganz gut auf die Anforderung, dass man ähnliche Konfigurationen schnell lösen können soll, passen.

[Senior Sanchez]

Danke für den Tipp :)
Ich schaue mir das mal an!

Für weitere Ratschläge bin ich aber weiterhin offen.

[Magnum]

So nach weiterer Recherche scheint der Netzwerk-Simplex-Algorithmus recht gut zu sein. Dieser löst das min-cost-flow-Problem in polynomialer Laufzeit und somit ist das Problem nicht NP-vollständig. Diese Aussage ist leider falsch! Der Simplex-Algorithmus löst die meisten ILP-Probleme in polynomialer Laufzeit. Die meisten heisst eben nicht alle. Es können Beispiele konstruiert werden, bei denen der Simplex-Algorithmus eine exponentielle Laufzeit hat! (siehe Wikipedia (http://de.wikipedia.org/wiki/Simplex-Algorithmus))

ILP selbst gehört zu Karps 21 NP-Vollständigen Problemen (http://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme). Dies würde bedeuten, wenn man es wirklich in polynomieller Laufzeit lösen könnte, hätte man P = NP bewiesen!

[Senior Sanchez]

Diese Aussage ist leider falsch! Der Simplex-Algorithmus löst die meisten ILP-Probleme in polynomialer Laufzeit. Die meisten heisst eben nicht alle. Es können Beispiele konstruiert werden, bei denen der Simplex-Algorithmus eine exponentielle Laufzeit hat! (siehe Wikipedia (http://de.wikipedia.org/wiki/Simplex-Algorithmus))

ILP selbst gehört zu Karps 21 NP-Vollständigen Problemen (http://de.wikipedia.org/wiki/Karps_21_NP-vollständige_Probleme). Dies würde bedeuten, wenn man es wirklich in polynomieller Laufzeit lösen könnte, hätte man P = NP bewiesen!

Hmm, scheinst recht zu haben. Dann habe ich mich getäuscht und ziehe diese Aussage zurück.