バックトラッキングアルゴリズム:例を使用して説明された再帰的および検索

バックトラックを使用してパズルや問題を解決できる例は次のとおりです。

  1. エイトクイーンパズル、クロスワードパズル、覆面算、数独[nb 1]、ペグソリテールなどのパズル。
  2. 構文解析やナップサック問題などの組み合わせ最適化問題。
  3. Icon、Planner、Prologなどの論理プログラミング言語。内部でバックトラッキングを使用して回答を生成します。

問題の例(ナイトツアーの問題)

騎士は空のボードの最初のブロックに配置され、チェスのルールに従って移動し、各正方形を1回だけ訪問する必要があります。

すべてのセルをカバーするためにナイトがたどるパス

以下は、8 x8セルのチェス盤です。セル内の数字はナイトの移動数を示します。

ナイトツアーソリューション-オイラー作

ナイトツアーのナイーブアルゴリズム

ナイーブアルゴリズムは、すべてのツアーを1つずつ生成し、生成されたツアーが制約を満たしているかどうかを確認することです。

while there are untried tours { generate the next tour if this tour covers all squares { print this path; } } 

ナイトツアーのバックトラッキングアルゴリズム

以下は、ナイトのツアー問題のバックトラッキングアルゴリズムです。

If all squares are visited print the solution Else a) Add one of the next moves to solution vector and recursively check if this move leads to a solution. (A Knight can make maximum eight moves. We choose one of the 8 moves in this step). b) If the move chosen in the above step doesn't lead to a solution then remove this move from the solution vector and try other alternative moves. c) If none of the alternatives work then return false (Returning false will remove the previously added item in recursion and if false is returned by the initial call of recursion then "no solution exists" ) 

そして、ここにあなたのためのビデオ説明があります