Randsuche - Fringe search

Algorithmen zur Diagramm- und Baumsuche
Auflistungen
verwandte Themen

In der Informatik , fringe Suche ist ein Graph Suchalgorithmus , der die Least-Cost - Pfad von einem gegebenen Anfangs findet Knoten zu einem Zielknoten .

Im Wesentlichen ist die Streifensuche ein Mittelweg zwischen A * und der iterativ vertiefenden A * -Variante (IDA *).

Wenn g ( x ) die Kosten des Suchpfads vom ersten Knoten zum aktuellen Knoten sind und h ( x ) die heuristische Schätzung der Kosten vom aktuellen Knoten zum Ziel ist, dann ist ƒ ( x ) =  g ( x ) +  h ( x ) und h * sind die tatsächlichen Pfadkosten zum Ziel. Betrachten Sie IDA *, das eine rekursive Tiefensuche von links nach rechts vom Stammknoten aus durchführt und die Rekursion stoppt, sobald das Ziel gefunden wurde oder die Knoten einen Maximalwert erreicht haben ƒ . Wenn im ersten Schwellenwert ƒ kein Ziel gefunden wird , wird der Schwellenwert erhöht und der Algorithmus sucht erneut. IE Es iteriert auf dem Schwellenwert.

Es gibt drei Hauptineffizienzen bei IDA *. Erstens wiederholt IDA * Zustände, wenn mehrere (manchmal nicht optimale) Pfade zu einem Zielknoten vorhanden sind. Dies wird häufig dadurch gelöst, dass ein Cache mit besuchten Zuständen geführt wird. Der so geänderte IDA * wird als speichererweiterter IDA * (ME-IDA *) bezeichnet, da er Speicherplatz verwendet. Darüber hinaus wiederholt IDA * alle vorherigen Vorgänge in einer Suche, wenn es in einem neuen Schwellenwert iteriert, der erforderlich ist, um ohne Speicher zu arbeiten. Durch Speichern der Blattknoten einer vorherigen Iteration und deren Verwendung als Startposition der nächsten wird die Effizienz von IDA * erheblich verbessert (andernfalls müsste in der letzten Iteration immer jeder Knoten im Baum besucht werden).

Die Streifensuche implementiert diese Verbesserungen in IDA *, indem eine Datenstruktur verwendet wird, die mehr oder weniger zwei Listen umfasst , um über die Grenze oder den Rand des Suchbaums zu iterieren. Eine Liste speichert jetzt die aktuelle Iteration und die andere Liste speichert später die unmittelbar nächste Iteration. Vom Stammknoten des Suchbaums aus ist jetzt der Stamm und später leer. Dann führt der Algorithmus eine von zwei Aktionen aus: Wenn ƒ (Kopf) größer als der aktuelle Schwellenwert ist, entfernen Sie den Kopf von jetzt und hängen Sie ihn an das Ende von später an ; dh Kopf für die nächste Iteration speichern . Andernfalls, wenn ƒ (Kopf) kleiner oder gleich dem Schwellenwert ist, erweitern Sie den Kopf und werfen Sie den Kopf weg , betrachten Sie seine untergeordneten Elemente und fügen Sie sie am Anfang von jetzt hinzu . Am Ende einer Iteration wird der Schwellenwert erhöht, die spätere Liste wird zur Jetzt- Liste und später wird geleert.

Ein wichtiger Unterschied zwischen Rand und A * besteht darin, dass der Inhalt der Listen in Rand nicht unbedingt sortiert werden muss - ein erheblicher Gewinn gegenüber A *, der die oft teure Aufrechterhaltung der Reihenfolge in der offenen Liste erfordert. Im Gegensatz zu A * muss der Rand jedoch wiederholt dieselben Knoten besuchen, aber die Kosten für jeden solchen Besuch sind im Vergleich zur logarithmischen Zeit im schlimmsten Fall für das Sortieren der Liste in A * konstant.

Pseudocode

Implementieren beider Listen in einer doppelt verknüpften Liste, wobei Knoten, die dem aktuellen Knoten vorangehen, der spätere Teil und alle anderen die Jetzt- Liste sind. Durch die Verwendung eines Arrays vorab zugewiesener Knoten in der Liste für jeden Knoten im Raster wird die Zugriffszeit auf Knoten in der Liste auf eine Konstante reduziert. In ähnlicher Weise ermöglicht ein Markierungsarray die Suche nach einem Knoten in der Liste in konstanter Zeit. g wird als Hash-Tabelle gespeichert, und ein letztes Marker-Array wird gespeichert, um zeitlich konstant zu prüfen, ob ein Knoten zuvor besucht wurde oder nicht und ob ein Cache-Eintrag gültig ist. 

init(start, goal)
    fringe F = s
    cache C[start] = (0, null)
    flimit = h(start)
    found = false

    while (found == false) AND (F not empty)
        fmin = ∞
        for node in F, from left to right
            (g, parent) = C[node]
            f = g + h(node)
            if f > flimit
                fmin = min(f, fmin)
                continue
            if node == goal
                found = true
                break
            for child in children(node), from right to left
                g_child = g + cost(node, child)
                if C[child] != null
                    (g_cached, parent) = C[child]
                    if g_child >= g_cached
                        continue
                if child in F
                    remove child from F
                insert child in F past node
                C[child] = (g_child, node)
            remove node from F
        flimit = fmin

    if reachedgoal == true
        reverse_path(goal)

Pseudo-Code umkehren. 

reverse_path(node)
    (g, parent) = C[node]
    if parent != null
        reverse_path(parent)
    print node

Experimente

Bei Tests in gitterbasierten Umgebungen, die für Computerspiele typisch sind, einschließlich unpassierbarer Hindernisse, übertraf der Rand A * je nach Verwendung von Kacheln oder Oktilen um etwa 10 bis 40 Prozent. Mögliche weitere Verbesserungen umfassen die Verwendung einer Datenstruktur, die sich leichter für Caches eignet.

Verweise

Externe Links