Wie man eine Karte speichern und ein Diagramm mit BFS in Ruby generiert

Question

Also ich denke, das ist eine klassische Frage für jemanden mit MSC in CS.

habe ich N-Element, und ich habe die Abstände als auch. Sagen wir, ich habe 3 Elemente mit den folgenden Strecken. Es ist symmetrisch, so

A -> B == B -> A

Es sieht aus wie eine Matrix:

   A,  B,  C,  
A  0, 10,  20 
B 10,  0,  30
C 20, 30,   0

Meine Frage wäre:

• Wie kann ich dies effizient speichern (was für Datenstruktur)
• was ist der effizienteste Weg, um eine Liste zu erhalten, wo die Summe des Abstandes minimal ist

In diesem Fall ist die beste

B -> A -> C = 30 which equals to C -> A -> B

anderer Fall:

A -> B -> C = 40 which equals to C -> B -> A

Ich hatte den Eindruck, dass BFS hierfür geeignet sein könnte. Link zur Dokumentation in Englisch ist gut, auch Bücher auf Amazon ...

Answer 1

Die ideale Lösung für Ihre Datenstruktur ist eine Adjazenzliste .

Eine Adjazenzliste ist einfach eine Liste von Objekten (die Eckpunkte auf dem Diagramm). Jedes Objekt hat eine Liste, die alle Eckpunkte enthalten, dass sie eine benachbarte Kante hat und das entsprechende Gewicht.

In Rubin, eine einfache Implementierung könnte suchen so etwas wie:

vertices = {}
a = Vertex.new
b = Vertex.new

a.add(b, 10)
b.add(a, 10)

vertices[a] = a
vertices[b] = b

Der Algorithmus den kürzesten gewichtete Pfad zu finden, ist Dijkstra genannt.

Wenn Sie den kürzesten Weg bekommen möchten, nachdem der Algorithmus ausgeführt wird, können Sie eine Rückverfolgung tun. Dies wird durch die Speicherung der (optimal) Eltern jedes Knotens durchgeführt, wie Sie es erreichen. Um dies zu tun, könnten Sie einen Hash für jeden besuchten Knoten haben, die mit dem Knoten abbildet, die mit den geringsten Kosten für sie führen.

Wenn Sie den Algorithmus beendet haben, Ihre rekursive Zurückverfolgungs etwas wie folgt aussehen:

def traceback(parent, start, node, path)
  if(start == node)
     (path + start.to_s).reverse
  else
     path += node.to_s + " "
     traceback(parent, start, parent[node], path)
  end
end

Answer 2

Ich höre Dijkstra einen Algorithmus hat einen gewichteten Graphen zu navigieren.