Ich habe ein Problem. Ich versuche, A * durch ein Grid-basiertes Spiel wie Pacman oder Sokoban zu durchsuchen, aber ich muss "Gehege" finden. Was meine ich mit Gehäusen? Untergraphen mit so wenig Schnittkanten wie möglich, wenn eine maximale Größe und eine minimale Größe für die Anzahl der Stützpunkte für jeden Untergraphen gegeben sind agieren als weiche Constraints.
Alternativ könnte man sagen, ich suche nach Brücken zwischen Subgraphen, aber es ist im Allgemeinen das gleiche Problem.
Gridbasiertes Gamemap-Beispiel http://dl.dropbox.com/u/1029671/map1.jpg
Bei einem Spiel, das so aussieht, möchte ich Gehege finden, damit ich Eingänge zu ihnen finden kann und somit eine gute Heuristik für das Erreichen von Scheitelpunkten innerhalb dieser Gehege erhalten.
alt text http://dl.dropbox.com/u/1029671/map.jpg
Also ich möchte diese farbigen Regionen auf jeder beliebigen Karte finden.
Der Grund für mich, dies zu tun und nicht nur mit der Leistung einer einfachen Manhattan-Distanz-Heuristik zufrieden zu sein, ist, dass eine Gehäuse-Heuristik bessere Ergebnisse liefern kann und ich nicht wirklich das A * machen müsste, um etwas richtig zu bekommen Entfernungsberechnungen und auch für das spätere Hinzufügen von kompetitivem Blockieren von Gegnern in diesen Gehäusen, wenn Spiele vom Sokoban-Typ gespielt werden. Auch die Gehäuse-Heuristik kann für einen Minimax-Ansatz verwendet werden, um Zielscheitelpunkte richtiger zu finden.
Eine mögliche Lösung für das Problem ist der Kernighan Lin Algorithmus :
%Vor%Mein Problem mit diesem Algorithmus ist seine Laufzeit bei O (n ^ 2 * lg (n)), ich denke daran, die Knoten in A1 und B1 an den Rand jedes Untergraphen zu begrenzen, um den Arbeitsaufwand zu reduzieren.
Ich verstehe auch nicht die c [a] [b] -Kosten im Algorithmus, wenn a und b keine Kante zwischen ihnen haben, sind die angenommenen Kosten 0 oder unendlich, oder sollte ich eine Kante basierend auf einigen erstellen Heuristik.
Weißt du, was c [a] [b] sein soll, wenn es keine Kante zwischen a und b gibt? Denkst du, dass mein Problem geeignet ist, eine Multi-Level-Methode zu verwenden? Warum oder warum nicht? Haben Sie eine gute Idee, wie Sie die Arbeit mit dem Kernighan-Lin-Algorithmus für mein Problem reduzieren können?
Die Frage ist nicht sicher, aber vielleicht können Sie die Max-Flow / Min-Cut-Dualität verwenden.
Es gibt spezialisierte und effiziente Algorithmen für den max-flow , mit denen Sie das ursprüngliche Problem lösen können.
Sie müssen dann die duale Lösung mit der hier beschriebenen Methode hier .
PS: lassen Sie es mich wissen, wenn Sie Hilfe bei Operations Research Jargon benötigen.
Vielleicht werfen Sie einen Blick auf diesen Link auf Wikipedia für weitere Lektüre.
Das Graphpartitionierungsproblem in Die Mathematik besteht darin, a zu teilen Graph in Stücke, so dass die Stücke sind von etwa gleicher Größe und Es gibt wenige Verbindungen zwischen den Stücke.
Tags und Links algorithm graph artificial-intelligence a-star heuristics
