チェスのナイトが出発地点から目標地点まで移動する時のルートを保存、出力したい。BFS Knight's Tour

Question

knight's tourという問題で、queueを利用したBFSで作っています。
基盤となるボードの大きさは8x8で、出発点は(0, 0)、目標地点は(6, 7)です。
問題は
1、最短何ステップで到着するかint型で出力。
2、その際通った道を1、2、3、、、と表示する。(参考写真あり)
このようになっています。これの2番で悩んでいます。

大幅な進行を説明します。
盤は2つあり、訪問したマスをマークする（何回目で訪れたかを数字で保存してある）ものと、出力用のものです。2次元arrayで作られています。(int path 出力用、一つの道のみ表示し、他は0にしたい)（int visited）

Moveは別で宣言されているstructで、x座標とy座表を保存できます。(2, 3)このように。
firは初期地点（0、0）がはいっており、destには目標地点（6、7）が保存されています。
*moveはナイトが動くことのできる8種類の座標移動が入っており、（move[0] = {+2, +1},,,）これを一つずつ足すことによって探索をします。
visitedには訪問済みのvertixのマークおよび何回でそのvertixに行けたのかを保存しています。

**今、下のコードではvisitedを丸ごとpathに移していますが、これを最適な道だけをpathに保存したいです。
**
しかし、ずっと考えているのですがアイデアが浮かびません。
ソースコードを全て載せたいのですが、コピー検査もあるはずなので載せれませんでした。
なにかアイデアをいただきたいです。

int shortdistance(Move fir, Move dest, int path[b_size][b_size], int nrMove, Move *move) {
        int q_limit= pow(nrMove, b_size);
    struct Node{

            int distance;  //何回目で到着したかをカウント
            Move position;  //現在位置を表す変数

    };



    Queue<Node> q(q_limit);
    int visited[b_size][b_size] = {0, };　　//すべてのvertixを未訪問に設定
    visited[0][0] = 1;　//初期位置を訪問済みにする

    Node n;
    n.distance = 0;  //何回動いたかカウントする
    n.position = fir;  //現在いる位置を表す

    q.enqueue(n);

    while(!q.isEmpty()){

            auto v = q.dequeue();  //初期位置を設定

            for(int i = 0; i < 8; i++)}　　//ナイトの動き方が8種類ある

                    if(v.position == dest){  //目標地点に到着 > その時のdistanceをreturn、mainで出力（問題1番）

                            for(int i = 0; i < b_size; i++){
                                     for(int j = 0; j < b_size; j++){

                                            path[i][j] = visited[i][j];

                                     }
                            }

                            return v.distance;
                    }

                    auto next_v = v;
                    next_v.distance = v.distance + 1;  //次に行くvertixのdistanceを1プラスする
                    next_v.position = v.position + movements[i];  //次に行くvertix設定

                    if((next_v.position.x > b_size) || (next_v.position.y > b_size)){  //boardの範囲を超えたらcontinue
                         continue;
                    }
                    else if((next_v.position.x < 0) || (next_v.position.y < 0)){  //boardの範囲を超えたらcontinue
                         continue;
                    }

                    if(visited[next_v.position.x][next_v.position.y] != 0){  //既に通ったvertexは何もしない
                         continue;
                    }

                    visited[next_v.position.x][next_v.position.y] = next_v.distance + 1;  //何回目でvertixに行けたか8x8の盤に保存
                        q.enqueue(next_v);  //新しいvertixをenqueue

              }

        }
        return 0;
}

Answer 1

int visited[b_size][b_size] = {0, };　　//すべてのvertixを未訪問に設定

この情報だけでは目的を達成できない，と言うのであれば，「目的に必要な記録」を追加で取ればよいのでは．
例えば，「探索の過程で各マスにどのマスから到達したのか」とかいう記録も取るならば，ゴールからスタートまで辿れますよね．

Comments

[fana]

「ルートを保存」したいというのであれば，直接的にルート情報を作ればいいよね，っていう．

Answer 2

一応、今の構造のままでも、最短経路を返すことは可能です。(BFSで見つけた経路と同じとは限りませんが)
destからfirまで、visitedが減る順番でナイトを動かせば、それが最短経路となります。
あとは、たどったところだけvisitedからpathに転記すればよいでしょう。

こちらのリンク先に、単純な迷路における最短経路復元方法の説明があります。移動をナイトの動きに変えてあげれば、この問題の解決にも応用できます。なお、私の方法が「方法1」、他の方が説明しているのが「方法2」に対応します。
意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法

Answer 3

せっかくなので、
queueにパスをためていく
→mainにqueueをまんまわたす
→パスを追うときにqueueからひとつずつ出していく
とかどうでしょうか？

Nodeとか使わずに済みますし！

#include <iostream>
#include <queue>
using namespace std;

#define _SIZE 8

int absolute(int a) {
    return (a < 0) ? -1 * a : a;
}

struct Move
{
    int x;
    int y;

    Move operator +(Move a) {
        Move b;
        b.x = this->x + a.x;
        b.y = this->y + a.y;
        return b;
    }
    Move operator -(Move a) {
        Move b;
        b.x = this->x - a.x;
        b.y = this->y - a.y;
        return b;
    }
    int operator <(Move a) {
        return ((absolute(this->x) + absolute(this->y)) < (absolute(a.x) + absolute(a.y)));
    }
    int operator !=(Move a) {
        return ((this->x != a.x) || (this->y != a.y));
    }
};

int shortdistance(Move fir, Move dest, queue<Move>& q, Move* move) {
    Move position = fir;

    q.push(position);

    while (position != dest) {
        Move tem = position + move[0];
        for (int i = 1; i < 8; i++) {
            if ((dest - (position + move[i])) < (dest - tem)) {
                tem = position + move[i];
            }
        }
        position = tem;
        q.push(position);
    }

    return q.size();
}

int main(void) {
    Move fir = { 0, 0 };
    Move dest = { 6, 7 };
    Move* move = new Move[8];
    queue<Move> path;

    move[0] = { 2, 1 };
    move[1] = { 2, -1 };
    move[2] = { 1, 2 };
    move[3] = { 1, -2 };
    move[4] = { -2, 1 };
    move[5] = { -2, -1 };
    move[6] = { -1, 2 };
    move[7] = { -1, -2 };

    int count = shortdistance(fir, dest, path, move);

    cout << "到着時の移動回数 : " << count << '\n' << endl;

    for (int i = 1; i <= count; i++) {
        Move tem = path.front();
        cout << i << "回目 : [" << tem.x << ", " << tem.y << "]" << endl;
        path.pop();
    }

    return 0;
}

Comments

[8524ba23]

ためしに「Move fir = { 1, 1 }」で動かしてみたが、終わらないようです。
到達済みを記録する必要はないでしょうか。

[actorbug]

Move dest = { 1, 1 };
にして実行すると、どうなるでしょうか。

ちなみに、到達済みを記録する修正をしたとしても、このコードだと最短経路は見つかりません。
(0,0)→(1,2)→(3,1)→(2,3)→(1,1)

Answer 4

単純なのは現在位置を表す変数positionを、これまで到達した位置の配列positionsに変更することでしょうか。
条件を満たしたNodeをキューに追加する前に、現在位置を配列に追加します。
ゴールに到達したら、それらから順番と位置が分かります。
なお、この変更によりdistanceはpositionsの要素数から算出できるので不要になります。