はじめに
42の課題で、N Puzzleを解くプログラムをRust言語で２人で作成したため、その備忘録として書いています。
課題全体の解説というわけではない点についてはご了承ください。
作成したものはこちらにあります。
ちなみに前回解いた課題の記事はこちらになります。
N Puzzleとは
まずはN Puzzleについて少しだけ。
N Puzzleとはこんな感じのやつです。
空白の部分だけを動かすことができて、ぐちゃぐちゃになった状態から、ゴールの盤面にもっていくことを目標とするパズルになります。
15 パズルだと、4x4になっていますが、今回はnxnのパズルを対象としています。
通常のN Puzzleは、例えば4x4だと以下の盤面をゴールとすることが多いようです。
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 0
※ 0は空白部分
しかし、今回は以下のように時計回りにくるくると回った状態をゴールとしています。
1 2 3 4
12 13 14 5
11 0 15 6
10 9 8 7
実装したもの
ということで実装したものについてです。
上記のN Puzzleを解くプログラムを作成しました。
$ ./n_puzzle 3 --verbose
Complexity in time: 4
Complexity in size: 4
Elapsed time: 0.000435 seconds
Number of moves: 1
Complexity in time: 1905
Complexity in size: 1880
Elapsed time: 0.004878 seconds
Number of moves: 25
3 8 7
5 4 0
2 1 6
↓ Left
...
↓ Right
1 2 3
8 0 4
7 6 5
引数や使い方の詳細は、冒頭のgithubのページをご覧ください。
機能としては、以下のようなことができるようになっています。
- パズルが書かれたファイルを読み込んでそのパズルを解く
- ランダムなパズルを作成してそれを解く
- 以下のアルゴリズムの選択
- A*アルゴリズム
- 均一コスト探索
- 貪欲法
- 以下のヒューリスティック関数の選択
- マンハッタン距離
- ハミング距離
- Linear Conflicts
- Inversion Distance
- タイムアウト機能
- 詳細表示
またプログラムがパズルを解き終わると以下のような表示をしてくれます。
- パズルが解けない場合は解けないという
- パズルが解ける場合は以下を伝える
- complexity in time: 考慮された状態の総数
- complexity in size: 同時に展開された状態の総数
- Elapsed time: 経過時間
- Number of moves: 探索によって導かれた、最初の状態から最終状態までに必要な移動回数
- Moves: 探索によって導かれた、最初の状態から最終状態までに移動する方向のシーケンス
性能はそんなにいいわけではありませんが（あまり最適化できていない）、一応3x3パズルなら1秒もかからず解くことができます。
実装にあたって
ここからは実装をするにあたってのあれこれを書いていきます。
チーム開発のために
今回はじめてRust言語でチーム開発を行ったため、チーム開発しやすくするためのあれこれを調べました。
最終的にLinterとFormatter、そしてテストをGitHub Actionsでかけるようにして、変なコードを入れられないようにしました。
こちらの詳細は以下の記事にまとめています。
N Puzzleの解けるかどうかの判定
N Puzzleはいつでも解ける……つまりゴールの盤面にできる、というわけではありません。
これについての詳細は以下の記事を参考にしました。
以下では非常にざっくりとこの判定について話します。
空白部分をスライドさせることは、パズル内の２つの位置を入れ替えることに対応します。
入れ替えといえば、数学では「置換」という概念が役に立ちます。
数学の置換の知識を使うと、入れ替え操作は、例えば偶数回でゴールの盤面にいける場合、奇数回ではゴールの盤面に到達できないことがわかります。
そのため、この偶奇の関係を使うことで、パズルが解けるかどうかを判定することができます。
ただし、
「nパズルが完成できる⇒偶奇の関係が成り立つ」
の方は偶奇の話で証明ができるのですが、この逆は証明できません。
この逆については、記事にも書いている通り、きちんと書くと煩雑なようで、簡単に理解できる証明は探すことができませんでした。
そのため、「偶奇の関係が成り立たない⇒nパズルが解けない！」という判定は保証されることがわかるのですが、「偶奇の関係が成り立つ⇒nパズルが解ける」は自分の中ではちゃんと証明できていない状態になります。
ただ、これは実際にプログラムによってnパズルが解ければなんの問題もないため、私は考えるのをやめました。
計算量について
今回の出力には以下の２つが含まれています。
- complexity in time: 考慮された状態の総数
- complexity in size: 同時に展開された状態の総数
これらは日本語だとそれぞれ「時間計算量」と「空間計算量」と訳されます。
これらについての詳細は以下が参考になるかもしれません。
アルゴリズム
今回は3つのアルゴリズムを実装しました。
A*アルゴリズム
私たちが実装したプログラムはこのA*アルゴリズムがメインの部分になります。
https://ja.wikipedia.org/wiki/A*
A*アルゴリズムのポイントとして、最短経路のコストの推定値を
f=g+h
として計算し、探索を行います。
この「g」はその状態までのコストであり、「h」はその状態からゴールまでの推定値になります。
また「h」をヒューリスティック関数といいます。
均一コスト探索
均一コスト探索は、幅優先探索の少し広い概念という感じのようです。
Wikiいわく、均一コスト探索で辺のコストがすべて同じ場合が、幅優先探索と同じになるようです。
今回は、N Puzzleの一回のスライドをコスト１として考えているため、おそらく幅優先探索といってもいいのだと思います。
また、A*との関係性で言うと、A*の
f=g+h
で、h=0の場合が均一コスト探索にあたります。
この方法のメリットは、必ず最短経路が見つかるということだと思います。
（A*ではヒューリスティック関数によっては最短経路が見つからない……はず）
貪欲法
貪欲法は保持する状態が一つで、とにかく最善手を取り続けるという感じのアルゴリズムです。
A*との関係性で言うと、A*の
f=g+h
で、g=0の場合にあたります。
過去の状態などは見ずに、とにかくヒューリスティック関数の結果がよい……つまりゴールに近い結果を採用し続けるものになっています。
この方法だと必ずしも解が求まるとは限らないようですが、過去の状態を一切保存しないためメモリ効率は非常に良いようです。
実装
ここまでで、均一コスト探索と貪欲法が、ある意味A*の派生であるということを話してきました。
そのため、実装的には、A*アルゴリズムを少し拡張して、均一コスト探索や貪欲法の際にはA*アルゴリズムの関数を呼び出すようになっています。
ヒューリスティック関数
今回は4つのヒューリスティック関数を実装しました。
ハミング距離
ハミング距離は、ざっくりというと、一致していない箇所をカウントするだけの関数になっています。
一致していなければ一致していないほど、ゴールの盤面から遠い、という考え方です。
マンハッタン距離
数学におけるマンハッタン距離といえば、例えば座標平面上で点（1,2）と点（3,1）のマンハッタン距離は
|1 - 3| + |2 - 1| = 3
というように計算されます。
こんな感じで、現在の盤面と、ゴールでの盤面で、各値がどれだけ離れているかをマンハッタン距離で測ったものをヒューリスティック関数の結果としています。
これはハミング距離と比べるとだいぶ精度がよくなっています。
Linear Conflicts
マンハッタン距離を強化するために、「Linear Conflicts」という概念を追加しました。
マンハッタン距離では、例えば「1 2」となってほしかった部分が「2 1」だった場合、合計で「2」のコストということになります。
ただし、実際には空白部分をスライドさせて移動する必要があるので、２回で「2 1」を「1 2」にすることは不可能です。
そこで、こういった場合にさらにコストを加えるようにしたのが、このヒューリスティック関数になります。
詳細は以下をご覧ください。
Inversion Distance
今度はN Puzzleを横に並べて考えます。
空白部分を無視して横に並べたときに、ゴールの盤面とどれだけ位置がずれているかを元にコストを計算していきます。
結構複雑なアルゴリズムなので詳細は省きますが、以下を参考にしたり、ChatGPTに聞いて理解しながら実装を行いました。
おわりに
今回色々なアルゴリズムに触れて、もっと色々なアルゴリズムを知りたくなりました。
何か特定の問題に関して、さまざまなアルゴリズムで実装して、その状態の推移を可視化して違いを楽しんだりなどしたいなと思いました。