Gegeben eine Grafik <V, E>, Startknoten st, Endknoten ed und bestimmte Knotensatz M, die besucht werden müssen. Meine Frage ist, den einfachen Weg zu finden, der alle M besucht. Ich möchte auch wissen:Beurteilung, ob ein einfacher Pfad vorhanden ist, der bestimmte Knoten besucht?
1 Ist der Pfad vorhanden?
2 Falls vorhanden, wie finde ich es so schnell wie möglich?
Wegen der Menge M kann das Problem auf den Hamilton-Pfad reduziert werden, von dem bekannt ist, dass es NP-vollständig ist.
Der Weg zu sagen, ob ein Pfad existiert ist, einen zu finden, und einen zu finden, das schnellste ist N! in der Anzahl der Knoten.
Sie können schnell suchen, wenn ein Pfad nicht existiert (getrennte Komponenten oder kritische Knoten, die mehrmals durchlaufen werden müssen, um den Pfad zu vervollständigen) und einige intelligente Heuristiken haben, die früh in der Rekursion stoppen (wenn es offensichtlich wird, dass kein Pfad auf diese Weise abgeschlossen werden kann) oder wählen Sie eine bessere Knotenreihenfolge.
Wenn M = V ist, erhalten Sie das Hamilton-Pfad-Problem, daher ist es im allgemeinen Fall nicht "schnell" lösbar. –
Danke @ n.m. Aber können wir einen ungefähren oder randomisierten Algorithmus bekommen, um ihn zu lösen? – mickeyandkaka
Wie nähern Sie sich einem Pfad, der alle Vertices besucht? Sollte ein ungefährer Weg die meisten Ecken besuchen oder was? Ich habe auch keine Ahnung, nur neugierig. –