0

騎士は (a,b) の位置にあり、(c,d) にいる王を取る必要があります。どうやって：

A: ツアーを視覚化する

B: (a,b) から (c,d) に移動するために必要な最小ステップを計算します。

私が見つけた実装は、基本的にチェス盤上の騎士の一連の動きであり、騎士はすべての正方形を 1 回だけ訪れますが、より具体的に特定の場所に足を踏み入れたいと考えています。

どのようなアルゴリズムまたは戦略を探す必要がありますか?

私はpythonの使用を考えています

4

2 に答える 2

1

上記を達成するためにBFSアルゴリズムを使用できます。位置を何度も訪問しないように、訪問した位置をキャッシュするだけです。これで、完全な反復ごとに行われる最小ステップ数となる目的地にアクセスするたびに、1 度の分離を探索していることになります。

チェス盤の各ブロックを表す Point を持つ NXM チェス盤を想定し、それに BFS を適用します。

class Point{
        int x;
        int y;
        int dist;
}

public int knight(int N, int M, int x1, int y1, int x2, int y2) {
           Point source = new Point(x1, y1);
           Point destination = new Point(x2, y2);

           Queue<Point> q = new LinkedList<>();
           q.add(source);
           Set<Point> hset = new HashSet<>();
           hset.add(source);
           int[][] dir = {{1, 2}, {-1, 2}, {1, -2}, {-1, -2}, {2, 1}, {-2, 1}, {2, -1}, {-2, -1}};
           while(!q.isEmpty()){
               Point p = q.poll();

               if(p.equals(destination)){
                   return p.dist;
               }

               for(int[] d : dir){

                   int row = p.x + d[0];
                   int col = p.y + d[1];
                   Point temp = new Point(row, col);
                   if(row <= 0 || col <= 0 || row > N || col > M || hset.contains(temp)){
                       continue;
                   }
                   temp.dist = p.dist + 1;

                   q.add(temp);
                   hset.add(temp);

               }

           }

           return -1;   //unreachable point from source position
}

ツアーの視覚化ははるかに簡単です。たどったパスを格納するために ArrayList などを使用するだけです。別のアプローチは、上記にダイクストラのアルゴリズムを使用することです。

于 2016-09-22T00:35:50.447 に答える
0

Knight's tour問題の正確な解決策を見つける最良の方法は、バックトラッキング アルゴリズムを使用することです。(a,b) から選択できるすべての可能な手順を見て、最初の手順を選択し、行き止まりが見つかるまで先に進みます。

行き止まりが発生した場合は、一歩下がって他のオプションを検討してください。

これは、DFS (Depth First Searh)の例です。

于 2016-09-22T05:55:45.643 に答える