Mit A * -Algorithmus

Question

Ich arbeite in Graph Bergbau und für meine aktuelle Forschung, Ich versuche, die Nähe zwischen nicht benachbarten Knoten in dem Graphen zu finanzieren.

Da jedoch nicht benachbarten Knoten allgegenwärtig sind, so möchte ich die Anzahl der nicht-benachbarten Knoten verengen-down, die an einem beliebigen Knoten in einem Graphen in Beziehung stehen. Lassen Sie a ein Knoten in einem Diagramm sein, würde ich gerne die meisten verwandten nicht benachbarten Knoten zu ihm finden. Dafür entschied ich mich, den Suchalgorithmus zu verwenden, um zum Beispiel n-hop Knoten vom Knoten a zu finden.

Ich wollte zunächst BFS verwenden und dann habe ich beschlossen, einen genaueren Algorithmus: A-Sterne, so kann ich den Startknoten und haben die g und h Funktionen minimiert werden bestimmen und eine Obergrenze für die Kostenfunktion minimiert werden, da ich den Zielknoten nicht angeben möchte.

Wird das möglich sein? Weil mein Ziel ist, den Zielknoten zu finden, aber nicht zu spezifizieren.

Answer 1

Betrachten Sie es auf diese Weise. Erweitern Sie Ihr Diagramm, indem Sie einen weiteren Eckpunkt einfügen, der an alle Zielknoten angehängt ist. Kannst du danach A * suchen? Wenn ja, dann ist A * Suche für Sie nützlich.

Die entscheidende Sache ist, eine Kostenfunktion zu haben, die eine nützliche untere Schranke dafür setzt, wie weit Sie von einem Zielknoten entfernt sind, so dass Sie die momentan aussichtsreichste Zeile der Suche über nicht vielversprechende suchen und sofort wechseln es funktioniert nicht so gut wie etwas anderes.