Get Weg in Graph mit gewichteten Ecken und Kanten

Question

Wenn ich das folgende ungerichteten Graphen mit gewichteten Ecken und Kanten:

Ich versuche, mit einem Rubin-Algorithmus zu entwickeln, um einen besten kürzesten Weg innerhalb eines definierten zu finden Grenze (Summe der Kanten) mit dem höchsten Wert (Summe der Ecken).

Der Startpunkt ist auch der Endpunkt.

für z.B. einen Pfad mit maximal 20 mit dem höchsten Gesamtwert finden.

Dieses Problem scheint wie ein schweres Problem und es ist schwer, die beste Lösung zu finden.

Gibt es einen modifizierten Algorithmus von Dijkstra? Ich habe versucht, einen Greedy-Algorithmus zu verwenden, aber es gab mir keine optimale Lösung. und durch die Verwendung von Bruteforce auf allen möglichen Pfad funktioniert, aber es wird sehr lange dauern, wenn die Anzahl der Knoten erhöht wird.

Ich frage mich, ob es eine Kombination von Algorithmen gibt, mit denen ich meine Lösung verbessern kann?

Danke.

Answer 1

Sie können an example of Djikstra's algorithm here finden. Was ich tun würde, ist eine Variable hinzuzufügen, um die Anzahl der Scheitelpunkte im kürzesten Pfad zu zählen, und auszuwerten, ob der kürzeste Pfad zu viele Scheitelpunkte hat oder zu lang ist, wenn der kürzeste Pfad selbst ist.

Answer 2

Das Problem ist tatsächlich NP hart, Sie können dies eine Reduktion von Hamiltonian path problem zu diesem Problem beweisen. Im Grunde genommen einen Eingang für die Hamilton-Pfad Problem gegeben (wir können mit dem ungerichteten Graphen bleiben) Sie können einen Eingang für das Problem schaffen Sie beschreiben, wenn diese Schritte folgen:

• bauen ein neues Diagramm

  ein erstellen neue grafische Darstellung, die die gleiche ist, die das Hamilton-Pfad Problem erhalten, aber 1.

• erstellen einen Eingang für Ihr Problem

  Pass für Ihr Problem der graph nur in der Previ erstellt zu jedem Vertex und Kantengewicht geben Schritt und Limit ist unendlich.

Hinweis nun, dass das Ergebnis durch das Problem gegeben ist, einen Pfad als längste als posible Bezug auf die Anzahl der Scheitel, da die Grenze Einschränkung ist eine Obergrenze in der Summe des Gewichts der Kanten. Dies bedeutet, dass Sie als Eckpunkt beliebig hinzufügen können und immer noch die Limitbeschränkung beanstanden.

Wie viele Scheitelpunkte im Pfad liegen, bestimmt den Gesamtwert (Anzahl der Scheitelpunkte im Pfad), da das Gewicht für alle Knoten 1 ist. Der resultierende Pfad ist also der längste im Diagramm. Mit dieser Einsicht können wir überprüfen, ob dieser Pfad ein hamiltonischer Pfad ist. Überprüfen Sie einfach die Länge des Pfades. Wenn der Pfad die Länge N hat, wobei N die Anzahl der Knoten im Graphen ist, gibt es einen Hamilton-Pfad, andernfalls nicht.

Um das Problem zu lösen, können Sie einen ähnlichen Ansatz wie Bellman-Ford mit einigen Änderungen verwenden. Erstellen Sie zunächst eine Matrix A [i, j], in der Sie alle Pfade mit dem höchsten Gesamtwert speichern, die mit j enden und die Länge (Anzahl der Kanten) haben.Dies ist der Schlüssel, Sie können nicht nur einen dieser Pfade speichern, denn im nächsten Schritt müssen Sie alle überprüfen, um sich zu entspannen, hier wird die Implementierung nicht-polynomial. Die Relax-Technik im Schritt I durchläuft den gesamten Speicherpfad in A [i-1, u] und versucht, den Wert in A [i, v] zu verbessern und die neuen Pfade zu speichern, die es tatsächlich tun (Sie müssen nach> = suchen wenn versucht wird, A [i, v] zu verbessern, um alle Wege zu bekommen, sollte diese Relaxation natürlich die Limitbeschränkung berücksichtigen. Wenn Sie einen globalen Max- und einen globalen Pfad verwenden und ihn in jedem Relax-Prozess aktualisieren, endet der Pfad mit dem höchsten Wert für den gesamten Graphen.