Die beste Route durch ein Labyrinth

Question

Eine zweidimensionale ganzzahlige Matrix mit der Dimension (m,n) ist gegeben und eine Person darf von (0,0) bis (m-1,n-1) durchqueren. Die gültigen Züge gehen nach rechts oder nach unten. Ich werde gebeten, den maximalen Summenpfad zu finden, um das Ziel zu erreichen. Das ist ganz einfach, da

MaxPathSum(i,j) = Math.max(MaxPathSum(i,j-1),MaxPathSum(i-1,j)) + Matrix[i][j] 

Allerdings, wenn es zwei Menschen sind beide erlaubt sind (0,0)-(m-1,n-1) zu durchqueren. Der Wert einer Zelle wird auf Null gesetzt, sobald diese Zelle von jemandem besucht wurde. Unter dieser Einschränkung, was wäre die maximale Summe dieser beiden Pfade?

Jeder Hinweis wird geschätzt. Vielen Dank.

Answer 1

Beachten Sie zunächst, dass bei jedem Schritt der Manhattan-Abstand vom Ursprung (x + y) immer um eins erhöht wird. Das heißt, wenn Sie zwei Marker gleichzeitig auf zwei Pfaden bewegen und sie abwechselnd bewegen, müssen die Marker, wenn sie sich kreuzen, übereinander liegen: Sie können nicht erreichen, dass ein Marker ein Feld erreicht und der andere mehrere Züge entfernt hat .

Jetzt können Sie sich die ursprüngliche MaxPathSum (i, j) = ... Berechnung als dynamisches Programm in einem Zustandsraum vorstellen, in dem der Zustand die Position eines einzelnen Markers ist. Für zwei Pfade wäre es naheliegend, ein dynamisches Programm in einem Zustandsraum auszuführen, in dem der Zustand die Position von zwei Markern ist. Dann könnten Sie MaxPathSum (i, j, k, l) = ... haben, wobei ein komplexerer Ausdruck die vier möglichen Bewegungen von zwei Markern berücksichtigt und sicherstellt, dass Matrix [i, j] nicht zweimal gezählt wird, wenn i == j & & k == l. Aufgrund dessen, was wir oben ausgeführt haben, müssen wir nur Kollisionen dieser Form berücksichtigen, damit wir uns nicht an die Pfade erinnern müssen, die die Marker zu ihren aktuellen Positionen zurückgelegt haben.

Dies sieht so aus, als ob es die Größe des Zustandsraums quadriert. Es ist schlecht, aber nicht so schlimm, wieder wegen der Manhattan-Distanzbeschränkung. Sie können die Rekursionsberechnungen in einer Reihe von Schritten durchführen, wobei jeder Schritt alle Antworten für die Zustände einer bestimmten Manhattan-Entfernung vom Ursprung aus berechnet. Sie müssen nur Paare von Zuständen berücksichtigen, die den gleichen Manhattan-Unterschied aufweisen. Wenn Sie ein NxN-Array haben, kostet die ursprüngliche Berechnung O (N^2). Wenn Sie das in Schritten tun wollen, in denen jeder Schritt alle Zellen mit einer bestimmten Manhattan-Distanz abdeckt, dann haben Sie O (N) Schritte, die jeweils O (N) -Zellen abdecken. Wenn Sie sich um zwei Pfade kümmern, haben Sie immer noch O (N) Schritte, aber jeder Schritt deckt O (N^2) Zellenpaare ab, so dass die Gesamtkosten O (N^3) sind - aber die Eingabedaten (die Matrix) ist von der Größe O (N^2), also könntest du es genauso gut als O (N^1.5) betrachten oder die ursprünglichen Kosten für die Power 1.5 erhöhen.

Answer 2

Wenn die Werte nicht negativ sind (> = 0), dann gibt es ein Paar maximaler Pfade, die sich nicht kreuzen. Es kann durch Konstruktion überprüft werden.

Angenommen, dass die maximale Wege (A und B), die einander kreuzen, wie:

..B. 
.B.A 
AXA. 
.B.. 

als wir Teile von Pfaden austauschen können nur einander berühren, wo Summe gleich ist.

..A. 
.A.B 
AXB. 
.B.. 

Da die Werte nicht negativ sind, Summe neuer Wege ist> =, dass der original A + B

..A.  ..A. 
AA.B or .A.B 
ABB.  AAB. 
.B..  .BB. 

Es scheint mir, dass einige DP Lösung sollte vorhanden sein, aber ich kann nicht Finde einen :-)

Es gibt einen gierigen Ansatz, der recht gute Lösung findet.Es verwendet die Eigenschaft , dass zwei unabhängige Pfade mit höheren Operationen verbessert werden können. Algorithmus ist wie:

find first maximal path 
set 0 to path elements 
find second maximal path 
improve paths with upper operations 

nicht optimal eingestellt sind Teil Nullen auf dem ersten Pfadelementen. Diese Nullen erzwingen zweiten Pfad, um den ersten nicht zu kreuzen. Verbesserungsoperationen verwenden Elemente um die Kreuzung herum, so dass die Verbesserung ein benachbartes Element zu dem Ergebnis hinzufügen wird. Es kann verwendet werden, um die ersten Pfadelemente auf den Wert eines Nachbarwerts zu setzen. Im Moment bin ich nicht sicher, welcher Nachbar zu verwenden ist, da es mehr Kombinationen gibt, besonders wenn das Überqueren eine längere Überlappung ist. Ich denke, dass ein guter Startpunkt darin besteht, es auf den Wert des minimalen möglichen Nachbarn einzustellen.