思考アルゴリズムの王様バックトラックにも弱点があります。その弱点と克服法を考えてみます。ちょっと難しくなりますが「再帰」は使用しないので、ある意味ではむしろ人に分かり易いアルゴリズムなのかも知れません。 1.「15パズル」のミニ版「5パズル」を解く 右図の5枚のパネルをランダムにシャッフル後、パネルを上下左右に スライドして元の順番通りになる様に最小の手順で並べ直して下さい。 この問題に先ほどのバックトラックを使っても失敗します。何故なら 「堂々巡り」という現象が発生してしまうからです。 堂々巡りとは、局面Aから局面Bへと変化しさらに局面Cへと探索が 進んでいったが、もしいつしか元の局面Aに変化してしまったらこれま での探索の過程が繰り返し実行されてしまいます。これでは無限地獄。 これを防止するには、探索過程の総ての局面を保存しておいて過去に 同じ局面がなかったかをチェックしながら探索しな