番号迷路解決アルゴリズム

Question

私は、「番号迷路」と呼ばれる固有のタイプの迷路のためのソルバーに取り組んでいます。基本的に、あなたがいるすべての位置は、次の可能な移動位置（上向き、下向き、斜め）を示す数字（1-4）です。ここで私が何を話しているかを明確にするためのイラストがあります。

最後に、すべての位置は一度だけ訪問することができます。目標は、迷路を通る最長の経路を見つけることができるようにすることです。

現在、私は各位置から可能な移動を見つけることができ、迷路のすべての可能な経路を反復することができます。このプログラムは、迷路の「終わり」が何であるかを知らないが、後で実装するのは簡単です。私が現在持っている問題は、すべての可能な経路を分析し、どれが最長かを知るために "パスの記憶"をどのように実装するのか分かりません。基本的に私は、さまざまなパスをすべて保存して分析する方法が必要です。私はArrayList<String> MovePathでそれをやろうとしましたが、それはうまく動作しませんでした。私は、これの全体的な再帰の側面が私を踏みにじっていると思います。私のコードのすべての重要な部分が以下に掲載されています。任意のポインタが評価されるだろう。

private static String changeString(String currentstring, String addendum) { 
     return currentstring + addendum; 
    } 

static ArrayList<String> solve(int X, int Y, String path, ArrayList<String> MovePath, int[][] PuzzleBoard) { 

     if (PuzzleBoard[X][Y] == 0) { 
      //If current position is blank, don't attempt to find moves 

    } else { 

     ArrayList<Point> AllMoves = FindMoves(PuzzleBoard, X, Y); //Find possible moves from current board location based on piece type 


     for (int i = 0; i < AllMoves.size(); i++) {//Iterate through possible moves 
      PuzzleBoard[X][Y] = 0; //set current position to 0 (empty) 
      X = (int) AllMoves.get(i).getX();//get move X coordinate 
      Y = (int) AllMoves.get(i).getY();//get move Y coordinate 

      String xstring = String.valueOf(X); 
      String ystring = String.valueOf(Y); 

      path = changeString(path, xstring);//Adds the current X coordinate to a string 
      path = changeString(path, ystring);//Adds the current Y coordinate to a string 

      MovePath.add(path); 

      solve(X, Y, path, MovePath, PuzzleBoard); 

     } 
    } 

    return MovePath; 
} 

public static void main(String[] args) { 

    int[][] BoardArray = new int[][]{ 
      {4, 0, 0, 0, 1, 0}, 
      {0, 1, 1, 1, 1, 0}, 
      {0, 1, 0, 0, 3, 0}, 
      {0, 0, 2, 0, 0, 0}, 
      {0, 0, 0, 0, 0, 0}, 
      {0, 0, 3, 0, 1, 9} 
     //0 = empty 
     //9 = end 

    int x = 0; //starting x 
    int y = 0; //starting y 
    String paths = ""; 
    ArrayList<String> MovePath = new ArrayList<String>(); 
    ArrayList<String> Answer = new ArrayList<String>(); 

    Answer = solve(x, y, paths, MovePath, BoardArray) 

    String longestpath = Collections.max(Answer, Comparator.comparing(s -> s.length())); 
    System.out.println(longestpath); 

} 

}

Answer 1

私の最初に考えたのは、すべて完成し、パスの後に更新されます最大のパスを、含まれているVARを追加しています。再帰の深さを格納し、終了後にmaxと比較します。

Answer 2

私はあなたが小さな部分であなたの問題を破ると、それを解決する提案：

1 - それは問題を見つける簡単なグラフの最短パスです。だから最初のステップは、あなたのデータからグラフマトリックスを構築することです。番号が付いたノードは、そのセルに示されている番号のコストで隣接ノード（nノード離れたノード）に移動することができます。したがって、(0,0)から(0,4)/(4,0)/(4/4)に移動するコストは4となります。だから私が言及したように、あなたの問題をグラフに減らしてください。

2-（最短の可能なパスのために）あなたのソリューションに必要なすべてのパス探索アルゴリズムを実装してください。私はより速いDijkstraまたはA*アルゴリズムを提案しますが、好きな場合はdepth firstまたはbreadth first検索を試すこともできます。これらのアルゴリズムをインターネット上に実装するためのチュートリアルや例が多数あります。 Dijkstraの場合はthis、A*の場合はthisが見つかりました。

3-（最長の可能なパス）すべての重みを無効にし、Bellman-Fordアルゴリズムを使用して最短パスを見つけます。あなたがすべての体重を否定したので、あなたは結果として最長の道を見つけるでしょう。 Thisあなたを助けることができます。