1. 概要

このチュートリアルでは、チェス盤での騎士の最短経路問題について説明します。 さらに、問題の説明を説明し、効率的な解決策を提供します。

2. 問題文

標準のチェス盤を前提として、騎士がソース位置から目的の位置に到達するための最小ステップ数を見つけたいと考えています。 ここでは、チェス盤上の騎士の出発地と目的地の位置がわかります。

次に、チェス盤のランダムな位置からの騎士の可能な動きを見てみましょう。

チェス盤では、騎士は2つの方法で移動できます。 水平方向に1マス、垂直方向に2マス、または縦に1マス、横に2マス移動できます。 したがって、特定の位置（X、Y）から、可能な移動は次のようになります。

   

ここでは、騎士が特定の初期位置から移動できるチェス盤の可能な位置を示しました。 どの時点でも、騎士はチェス盤から出ることはできません。 最後に、騎士が指定された初期位置から目的地に到達できない状況が発生した場合は、に戻ります。

3. アプローチ

この問題を解決するために、まず、チェス盤を騎士のグラフに変換します：

騎士のグラフでは、チェス盤の各ボックスは頂点を示しています。 各頂点は、チェス盤上の騎士の位置に対応しています。 各エッジは、騎士の合法的な動きを表しています。 したがって、騎士の最短経路問題を解決するために、任意の検索アルゴリズムを適用して、ある地点から別の地点への最短経路を見つけることができます。 ここでは幅優先探索（BFS）アルゴリズムを使用しています。

最初に、騎士をチェス盤にランダムに配置します。 最初のポイントから、すべての可能な位置を探索することを目指します。 初期位置から到達できる可能性のあるすべての位置にアクセスできない場合は、この状態をキューにエンキューします。 さらに、キューの最後の状態から移動回数を増やします。

新しい位置ごとに、騎士の現在の位置が目的地の位置であるかどうかを確認します。現在の位置が目的地でない場合は、キューから現在の位置をポップしてキューに入れます騎士が現在の位置から移動できる可能な位置。

目的の位置に到達するか、チェス盤で可能なすべての位置を探索するまで続行します。

4. 擬似コード

ここで擬似コードを見てみましょう。

ここで、と は、X方向とY方向の変化を表す2方向の配列です。さらに、キューを作成し、騎士の初期位置をプッシュしました。

最初に、チェス盤の特定の位置がすでに探索されているかどうかを判断するための配列を作成しました。  最初は、すべての位置が未踏であることを示すために初期化しました。 反復を開始すると、配列内の騎士の初期位置がとして作成されます。

さらに、騎士が目的の位置に到達するために必要なステップ数を格納するために、配列を使用しました。 キューが空になるか、宛先に到達するまでアルゴリズムを実行します。

特定の位置がチェス盤の内側にあるかどうかを確認するために、関数が定義されています。 これがの拡張です：

最後に、擬似コードの時間計算量について話しましょう。 したがって、この擬似コードの主な複雑さは、目的地に到達するためにチェス盤のセルにアクセスすることです。 指定されたチェス盤の次元が、の場合、このアルゴリズムの時間計算量は。になります。

5. 結論

このチュートリアルでは、チェス盤での騎士の最短経路問題について説明しました。 この問題を擬似コードで解決するためのBFSベースのアプローチを紹介しました。