Ich kann nicht meine statische Variable in Java ändern

Question

Sie geben ein Raster (4x4 hier). Sie müssen die Gesamtzahl der eindeutigen Pfade von (0,0) bis (4,4) herausfinden. main() ruft dazu eine Funktion pathify auf. Es findet die möglichen "nächsten Schritte" und ruft sie erneut auf. Wenn (4,4) erreicht ist, noOfPaths ++; soll ausführen. Dies passiert nicht und ich kann das Problem nicht finden.

import java.util.ArrayList; 

    public class NoOfPaths { 
     static int xRows = 4; 
     static int yColumns = 4; 
     static int noOfPaths = 0; 

     /*A robot is located in the upper-left corner of a 4×4 grid. 
     * The robot can move either up, down, left, or right, 
     * but cannot go to the same location twice. 
     * The robot is trying to reach the lower-right corner of the grid. 
     * Your task is to find out the number of unique ways to reach the destination. 
     **/ 

     static ArrayList validNeighbours (int x,int y, ArrayList visited) { 
      ArrayList valid = new ArrayList(); 

      if((x+1 <= xRows) && !visited.contains(((x+1)*10)+y)) { 
       valid.add(((x+1)*10)+y); 
      } 
      if((x-1 >= 0) && !visited.contains(((x-1)*10)+y)) { 
       valid.add(((x-1)*10)+y); 
      } 
      if((y+1 <= yColumns) && !visited.contains(x*10+y+1)) { 
       valid.add(x*10+y+1); 
      } 
      if((y-1 >= 0) && !visited.contains(x*10+y-1)) { 
       valid.add(x*10+y-1); 
      } 

      return valid; 
     } 

     static void pathify(int x,int y, ArrayList alreadyVisited) { 
      if(x == xRows && y == yColumns) { 
       noOfPaths++; 
      } else { 
       alreadyVisited.add(x*10+y); 
       ArrayList callAgain = new ArrayList(); 
       callAgain = validNeighbours(x,y,alreadyVisited); 
       for (int t=0,temp; t<callAgain.size(); t++) { 
        temp=(int) callAgain.get(t); 
        pathify(temp/10, temp%10, alreadyVisited); 
       } 

      } 
     } 

     public static void main(String[] args) { 


      ArrayList alreadyVisited = new ArrayList(); 

      pathify(0, 0, alreadyVisited); 

      System.out.println(noOfPaths); 
     } 

    } 

Answer 1

Der Fehler ist in, wie Sie alreadyVisited sind Handhabung. Wenn das erste Mal pathify aufgerufen wird, enthält diese Liste nur das ursprüngliche Quadrat (0,0), was in Ordnung ist. Hier ist der wichtige Teil Ihres Codes:

  for (int t=0,temp; t<callAgain.size(); t++) { 
       temp=(int) callAgain.get(t); 
       pathify(temp/10, temp%10, alreadyVisited); 
      } 

Sie haben die Nachbarn der ersten Zelle gefunden. Ihr Code wählt den ersten Nachbarn aus. dann findet es Wege, die mit diesem Nachbarn beginnen, und die rekursiven Aufrufe an pathify fügen Zellen zu alreadyVisited hinzu.

Jetzt, nachdem alle rekursiven Aufrufe zurückkommen, sind Sie bereit, Zellen beginnend mit dem zweiten Nachbar der ersten Zelle zu finden. Aber Sie haben ein Problem: alreadyVisited hat immer noch alle Zellen aus den gefundenen Pfaden beginnend mit dem zweiten Nachbarn gesammelt. So finden Sie nicht alle möglichen Pfade beginnend mit dem zweiten Nachbarn; Sie werden keinen Pfad finden, der irgendeine Zelle in irgendein Pfad enthält, den Sie zuvor gefunden haben. Dies ist nicht das, was Sie wollen, da Sie nur vermeiden wollen, die gleiche Zelle in jeder Pfad zu besuchen - Sie wollen nicht vermeiden, die gleiche Zelle in allen Ihren vorherigen Pfaden zu besuchen. (Ich habe das ein wenig vereinfacht. In Wirklichkeit wird das Problem tiefer im rekursiven Stapel auftreten und Sie werden nicht einmal alle Pfade finden, die mit dem ersten Nachbarn beginnen.)

Bei der Implementierung eines rekursiven Algorithmus I Ich habe festgestellt, dass es generell eine schlechte Idee ist, eine Zwischendatenstruktur beizubehalten, die von rekursiven Aufrufen geteilt wird, die von diesen Aufrufen modifiziert werden. In diesem Fall ist das die Liste alreadyVisited. Das Problem ist, dass wenn ein Aufruf tiefer im Stapel die Struktur verändert, dies die Aufrufe weiter oben beeinflusst, weil sie die Änderungen sehen, nachdem die tieferen Aufrufe zurückkehren, was im Grunde Daten sind, die sie unter ihnen ändern müssen. (Ich spreche nicht über eine Sammlung, die verwendet wird, um eine Liste von Ergebnissen zu halten, wenn die Liste im Grunde schreibgeschützt ist.) Die Möglichkeit, es hier zu vermeiden, besteht darin, anstelle alreadyVisited einen Klon zu erstellen dieser Liste hinzufügen und dann hinzufügen. Auf diese Weise kann ein tiefer gehender Aufruf sicher sein, dass er die flacheren Aufrufe nicht beeinflusst, indem er seine Daten ändert. Das heißt, statt

alreadyVisited.add(x*10+y); 

Schreib

alreadyVisited = [make a copy of alreadyVisited]; 
alreadyVisited.add(x*10+y); 

Die add wird eine neue Liste ändern, nicht die Liste, die anderen Anrufungen verwenden. (Ich persönlich würde eine neue Variable wie newAlreadyVisited deklarieren, da ich aus Gründen der Lesbarkeit die Parameter nicht wirklich modifizieren möchte.)

Dies scheint ineffizient zu sein. Es wird definitiv mehr Speicher verwenden (obwohl der Speicher ziemlich schnell Müll sammeln sollte). Aber es ist sehr, sehr schwierig, eine Datenstruktur zwischen rekursiven Aufrufen zu teilen. Dies ist möglich, wenn Sie sehr vorsichtig sind, die Änderungen zu bereinigen und die Struktur so wiederherzustellen, wie sie zu Beginn der Methode war. Das kann notwendig sein, wenn die Struktur so etwas wie ein großer Baum ist, was es unmöglich macht, sie für jeden Aufruf zu kopieren.Aber es kann viel Geschick erfordern, Dinge zum Laufen zu bringen.

EDIT: ich es getestet und es scheint zu funktionieren: 12, wenn xRows = yColumns = 2, 8512, wenn beide sind 4 (das ist richtig?). Ein anderer Ansatz: Anstatt die Liste zu kopieren, habe ich versucht,

alreadyVisited.remove((Object)(x*10+y)); 

am Ende des Verfahrens ((Object) ist erforderlich, so dass Java nicht denken, dass Sie bei einem Index zu entfernen) und das gab mir die gleichen Ergebnisse . Wenn Sie das tun, werden Sie sicherstellen, dass alreadyVisited das gleiche ist, wenn pathify zurückgibt, wie es war, als es begann. Aber ich möchte betonen, dass ich diesen "Bereinigungs" -Ansatz nicht empfehle, es sei denn, Sie wissen wirklich, was Sie tun.