m-Erreichbarkeit in Graphen
Angenommen, du hast ein NxN-Labyrinth mit einem Ritter, einer Prinzessin und einem Ausgang.
Es gibt auch eine böse Hexe, die vorhat, M Quadrate zu blockieren (sie in Brand zu setzen). Sie wird alle diese Blöcke in Brand setzen, bevor der Ritter seinen ersten Zug macht (sie nicht wechseln sich ab).
Wenn du dir die Karte zum Labyrinth und M anschaust, kannst du in O (N ^ 2) entscheiden, ob der Ritter die Prinzessin und dann den Ausgang erreichen kann, um eine beliebige Auswahl an Blöcken durch die Hexe zu treffen. Kann die Hexe Entscheidungen treffen, die verhindern, dass der Knight und die Prinzessin entkommen können?
1 Antwort
Dieses Problem scheint der Feststellung zu entsprechen, ob M + 1 eindeutige Pfade vom Ritter zur Prinzessin und M + 1 eindeutige Pfade von der Prinzessin zum Ausgang existieren. Wenn es nur bestimmte Wege vom Ritter zur Prinzessin (oder Prinzessin zum Ausgang) gibt, kann die Hexe nur ein Quadrat von jedem Pfad wegbrennen und die Rettung blockieren (und, leider, jede Chance auf ein Happy-ever-after Romantik zwischen ihnen).
Zum Beispiel hat das Labyrinth in Ihrer Frage zwei verschiedene Wege vom Ritter zur Prinzessin und zwei verschiedene Wege von der Prinzessin zum Ausgang. Also, das kann M brennen, um ein Entkommen zu verhindern.
Die Anzahl der verschiedenen Pfade zwischen zwei Punkten kann mithilfe eines maximalen Netzwerkflusses -Algorithmus ermittelt werden. Jede Zelle im Gitter ist ein Knoten im Netzwerk; Zwei Knoten haben eine Kante (der Kapazität 1), die sie verbindet, wenn sie benachbart sind und beide weiß sind. Der maximale Netzwerkfluss von einem Punkt zum anderen stellt die Anzahl der verschiedenen Pfade zwischen ihnen dar.
Der Ford Fulkerson-Algorithmus löst das Netzwerkflussproblem in min(2, 2) time, wo O(E * f) ist die Anzahl der Kanten im Netzwerk (höchstens E ) und N^2 ist der Wert des maximalen Netzwerkflusses. Da der maximale Netzwerkfluss maximal 4 beträgt (der Ritter hat nur vier mögliche Richtungen für seinen ersten Zug), wird die gesamte Komplexität wie angefordert f .
Mehr als einmal die Verwendung eines Knotens vermeiden
Wie andere bereits erwähnt haben, verhindert die obige Lösung, dass Kanten mehr als einmal in Knoten hinein und heraus gehen. nicht die Knoten selbst.
Wir können den Flussgraphen modifizieren, um zu vermeiden, dass Knoten mehr als einmal verwendet werden, indem jeder Zelle vier Eingangskanten, eine einzelne Schutzkante und vier Ausgangskanten (jede mit einem Gewicht von 1) gegeben wird folgt:
Die Ausgabekante einer Zelle entspricht der Eingabe einer anderen Zelle. Jede Zelle kann nur noch für einen Pfad verwendet werden, da die Schutzkante nur einen Fluss von 1 haben kann. Sink- und Source-Zellen bleiben unverändert. Wir haben immer noch eine konstante Anzahl von Kanten pro Zelle, wodurch die Komplexität des Algorithmus unverändert bleibt.