Ein Kürzester-Pfad-Algorithmus mit der Mindestanzahl von überfahrenen Knoten

Question

Ich suche nach einer Dijkstra-Algorithmus-Implementierung, die auch die Anzahl der durchlaufenen Knoten berücksichtigt. Ein typischer Dijkstra-Algorithmus berücksichtigt das Gewicht der Kanten, die die Knoten verbinden, während er die kürzeste Route von Knoten A zu Knoten B berechnet. Ich möchte hier einen weiteren Parameter einfügen.

Ich möchte, dass der Algorithmus der Anzahl der durchlaufenen Knoten auch eine gewisse Gewichtung gibt.

So ist die unter bestimmten Werten von A nach B berechnete kürzeste Route möglicherweise nicht die kürzeste Route, sondern die Route mit der geringsten Anzahl der durchlaufenen Knoten.

Irgendwelche Gedanken dazu?

Cheers,
RD

Edit:
Ich entschuldige mich. Ich hätte es besser erklären sollen. Also, sagen wir, die kürzeste Route von
(A, B) ist A -> C -> D -> E -> F -> B umfasst insgesamt 10 Einheiten
Aber ich möchte den Algorithmus zu finden die Route A -> M -> N -> B mit insgesamt 12 Einheiten.
Also, was ich will, ist, in der Lage zu sein, die Anzahl der Knoten, nicht nur die Entfernung der verbundenen Knoten etwas Gewicht zu geben.

Answer 1

Ich gehe hier ein bisschen aus, aber hast du den A * -Algorithmus ausprobiert? Ich habe Ihre Frage vielleicht falsch verstanden, aber es scheint, als wäre A * ein guter Ausgangspunkt für das, was Sie tun möchten.

Check out: http://en.wikipedia.org/wiki/A * _search_algorithm

Einige dort Pseudo-Code, den Sie heraus zu helfen :)

Answer 2

Die Art und Weise Sie tun können, dass die Gewichte der Kanten anzupassen, ist immer 1 zu sein, so dass Sie traverse 5 Knoten, und Sie haben eine Entfernung von "5" gegangen. Der Algorithmus wäre an diesem Punkt derselbe, wobei er die Anzahl der durchlaufenen Knoten und nicht die zurückgelegte Entfernung optimiert.

Wenn Sie eine Art von Hybrid wollen, müssen Sie bestimmen, wie wichtig es ist, einen Knoten und die Entfernung zu überqueren. Das Gewicht in Berechnungen verwendet werden, sollten wie etwas aussehen:

weight = node_importance * 1 + (1 - node_importance) * distance

Wo node_importance wäre ein Prozentsatz sein, die Lehren, wie viel Abstand ist ein Faktor, und wie viel minimale Knoten Traversal ist wichtig. Obwohl Sie die Abstände zu einem Durchschnitt von 1 normalisieren müssen.

Answer 3

Wenn ich die Frage richtig verstanden habe, dann wäre die beste Analogie, dass verwendet, um den besten Netzwerkpfad zu finden.

In der Netzwerkkommunikation kann ein Pfad nicht nur ausgewählt werden, da er am kürzesten ist, sondern viele Sprungzahlen (Knoten) aufweist, was zu Verzerrungen, Interferenzen und Rauschen aufgrund von Knotenverbindungen führen kann.

Also die beste Weg Berechnung enthält die Minimierung der Funktion von Variablen wie in Ihrem Fall Distance und Hop Count (Knoten).

Sie müssen eine Funktionsgleichung ableiten, die die Entfernung und die Knotenanzahl mit der Qualität in Beziehung setzen kann.

so etwas wie suppose
1 hop count change = 5 unit distance (was bedeutet, dass die Auswirkungen für 5unit distace oder 1 Knoten Änderung gleiche ist)

so den Verlust zu minimieren Sie es in der linearen Gleichung verwenden können.
minimize(distance + hopcount);
wo hopcount als Abstand ausgedrückt werden kann.

Answer 4

Lassen Sie mich demonstrieren, dass das Hinzufügen eines konstanten Werts zu allen Kanten die Route ändern kann, die "kürzest" ist (geringstes Gesamtgewicht der Kanten).

Hier ist die ursprüngliche Grafik (ein Dreieck):

A-------B 
\ 5/
2 \ /2 
    \/
    C 

kürzester Weg von A nach B über C. Nun Konstante 2 bis alle Kanten hinzuzufügen. Der kürzeste Pfad wird stattdessen der einzige Schritt von A direkt nach B (aufgrund der "Strafe", die wir für die Verwendung zusätzlicher Kanten eingeführt haben).

Beachten Sie, dass die Anzahl der verwendeten Kanten (mit Ausnahme des Knotens, von dem aus Sie starten) gleich der Anzahl der besuchten Knoten ist.