Dynamische Queue zur effizienten Implementierung des Breadth-First-Algorithmus

Ich bin gerade dabei, einen Breadth-First Graph-Suchalgorithmus zu erstellen, um die Londoner U-Bahn zu durchsuchen.Dynamische Queue zur effizienten Implementierung des Breadth-First-Algorithmus

Ich habe den Algorithmus herausgefunden, aber wie Sie vielleicht wissen, benötigt der Algorithmus eine Warteschlange ADS, um alle Kanten zu verfolgen, die gesucht werden müssen (in der richtigen Reihenfolge).

Ich habe über Effizienz Probleme mit der Verwaltung der Warteschlange und eine große oder sehr große Anzahl der eingereihten Elemente (Kanten) zu lesen.

Kann mir bitte jemand sagen, wie man eine Warteschlange basierend auf der Java ArrayList implementiert, die Kopf und Schwanz verfolgen kann und den Speicher effektiv verwaltet, während er wächst?

Alle Tipps/Hinweise sehr geschätzt!

Quelle

2011-01-06 Alex

Das erste, was ich fragen würde ist, haben Sie tatsächlich ein Problem - ist es Sie warten lassen? Die zweite ist, wenn Sie warten müssen, haben Sie gesampelt, um zu sehen, was es die meiste Zeit macht. Dieser FIFO könnte ein Problem sein, aber a priori, wahrscheinlich nicht. Genau wie ein Baseballstadion, sollten Sie in der Lage sein, 1 Knoten jede Mikrosekunde zu verarbeiten, also würde ich nicht denken, dass die Geschwindigkeit ein Problem wäre. –

Ich würde lieber eine spezielle Warteschlange verwenden, weil es besser wäre, meine Warteschlange ständig zu sortieren. Obwohl es nicht unbedingt notwendig ist, möchte ich nur mehr über Warteschlangen und deren Möglichkeiten erfahren. – Alex

Ich denke, ich verstehe nicht, warum Sie sortieren müssen, aber wie auch immer, @ Kims Antwort sieht gut aus. –

Ich glaube, Ihre Frage in engen Zusammenhang mit diesem Thema ist: Breadth-First search in Java

nicht Arraylist verwenden Sie, wenn Sie ein wirklich guten Grund haben. Java enthält bereits eine Reihe von Warteschlangenimplementierungen - Details finden Sie unter der Nummer Queue.

In Ihrem Fall könnte es ausreichen, LinkedList als Ihre Warteschlangenimplementierung auszuwählen. Siehe auch http://www.codeproject.com/KB/java/BFSDFS.aspx für ein leicht zu befolgendes Beispiel für eine breite erste Suchimplementierung, die LinkedList als Warteschlange verwendet.

Quelle

2011-01-06 19:10:21

Ah ha ich sehe, Sie können LinkedList einfach so verwenden. Nun, das ist nicht allzu schwierig. Ich bin sicher, dass einige über Techniken zur Warteschlangeneffizienz recherchieren werden! – Alex

Sie können auch PriorityQueue auschecken, wenn Sie Ihre Elemente sortieren müssen. Und @ Keiths Vorschlag, ein Set für schnelle Graphfärbung zu verwenden. Ich denke, der erste Code der Breite verwendet auch ein Set zu diesem Zweck. –

Nochmals vielen Dank ... – Alex

Denken Sie daran, dass Sie einen schnellen Test wünschen, um zu sehen, ob Ihr Objekt bereits in der Warteschlange ist oder nicht. Weder ArrayList noch Queue bieten diese Funktionalität (ihre contains Überprüfung ist O(n)). Wenn Sie die Objekte, mit denen Sie zu tun haben, ändern können, indem Sie ein zusätzliches Feld hinzufügen, ist das einfach. Wenn nicht, sollten Sie eine schnelle Set (eine HashSet, wahrscheinlich) pflegen, um zu verfolgen, welche Objekte in der Warteschlange sind.

Quelle

2011-01-06 19:21:33

Ich sehe das ist wirklich interessant. Ich kann ein HashSet von Objekten, die zuvor durchlaufen wurden, leicht einführen und sicherstellen, dass sie nicht zur Warteschlange (ihren Kanten) hinzugefügt werden. – Alex

Dies wäre über die Methode 'HashSet'' containts() '? Ist dies schneller, weil es eine 'hashCode()' Suche verwendet? – Alex

Ja, HashSet.contains ist schnell. Lesen Sie Hashtabellen, wenn Sie verstehen wollen, warum sie schnell sind. Es ist mehr als nur Hashcode() zu verwenden. –

Dynamische Queue zur effizienten Implementierung des Breadth-First-Algorithmus

Antwort

Verwandte Themen