2016-02-21 8 views
5

Lassen Sie uns sagen, ich habe eine n^n Matrix. In jeder Zelle gibt es eine positive Zahl, und ich muss den Pfad mit dem niedrigsten Gewicht abrufen.den Pfad mit dem niedrigsten Gewicht von Matrix rekursiv abrufen

Weg ist jeder Weg, der in matrix[matrix.length-1][matrix[0].length-1] in matrix[0][0] beginnen und enden, ohne Diagonalen.

Gewicht eines Pfads ist die Menge aller Zahlen in seinen Zellen.

Zum Beispiel lassen Sie uns sagen, ich habe diese Matrix:

mat = {{1,2},{3,4}}; 

so {1,2,4} ist ein Weg und {1,3,4} ist ein weiterer Weg.

Das Gewicht des ersten Pfades ist (1 + 2 + 4) und die zweite ein Gewicht von (1 + 3 + 4) hat, so wird die Funktion zurückzukehren.

Ich muss es rekursiv lösen. Der Pseudo-Code sollte wie folgt sein:

if i > matrix.length-1 || i < 0 || j > matrix[0].length-1 || j < 0 
//then I passed the borders, so I need to step back. 
if i == matrix.length-1 && j == matrix[0].length-1 
//Then I reached the last cell, and I need to retrieve sum 

Dann vier recursives Anrufe nennen:

public static int smallPath(a, i+1, j, sum); 
public static int smallPath(a, i, j+1, sum); 
public static int smallPath(a, i-1, j, sum); 
public static int smallPath(a, i, j-1, sum); 

Dann muss ich etwas holen, was?

Ich weiß, es ist nicht aktuell, aber das ist die allgemeine Idee, kann mir jemand helfen, dies zu lösen? Vielen Dank!

Antwort

1

Ich bin nicht sicher, ob dies die effektivste Lösung ist, aber man sollte darüber nachdenken:

  1. Sie haben zuerst die zufällige Art und Weise zu testen und erhalten ihre Summe.
  2. Annäherung systematisch. Versuchen Sie einen anderen und wenn sein Summe im Fortschritt größer ist, stoppen Sie es und versuchen Sie das andere.
  3. Wenn Sie den kleinsten Summe Weg finden, erfassen seine Summe (und Richtung) und ein weiteres versuchen, bis es keine Möglichkeit
  4. links ist
  5. Sie haben das Ergebnis :)

Diese Lösung würde Arbeit für direkte Pfade. Ich meine, du trittst immer nach rechts oder nach unten. Nicht zurück gehen (oben oder links) - wenn Sie von der oberen linken Zelle beginnen und in der unteren rechten enden.

Überprüfen des Unterschied:

enter image description here

Die erste ist offensichtlich, ist die kleinsten Summen 18 (3 + 2 + 1 + 0 + 1 + 2 + 4 + 3 + 2) .. aber im zweiten Fall ist das Ergebnis meiner Direktmethode 107 und nicht 17, da die richtige Lösung ist.

Allgemein gesagt, um die beste Lösung zu finden, ist in diesem Fall sehr kompliziert und Sie müssen angeben, ob Sie irgendwelche Grenzen setzen oder nicht.

+0

Danke für die Antwort! Welche Parameter muss ich an die Funktion senden? eine für die zufälligen, die sich nicht ändern, und eine für die linken Summen, die immer um die Matrix [x] [y] zunehmen? Ich brauche wirklich etwas Hilfe mit dem Code .. – Avishay28

+0

Oben bearbeitet. Es ist nicht schwer, meine Direktanfluglösung zu finden, aber es ist normalerweise nicht korrekt. –

0

Sie sollten den Dijstra-Algorithmus verwenden können, bei dem die Knoten "zwischen" den Zellen der Matrix liegen und die Verbindungen durch die Gewichte der Zellen impliziert werden.

Für eine ausführliche Antwort finden Sie auf diese Frage: Javascript: Pathfinding in a (50000*50000 grid) 2d array?

Verwandte Themen