--15puzzle問題の探索結果--

-15puzzleの探索-

ここでは、15パズル問題を実際に探索した結果についてまとめる。探索方法としては、幅優先探索、A*探索について行い、ヒューリスティック関数はマンハッタン距離を用いた。

-幅優先探索-

幅優先探索は、ツリーの深さによって探索を行っていく方法である。よって、盤面の状態として空白の位置が同じであれば生成されるツリーは同じである。
測定では空白のタイルの位置が角にある場合(状態1)、
空白のタイルの位置が角ではない4辺にある場合(状態2)、
空白のタイルの位置が中心4マス場合(状態3)
のそれぞれで行った。
以下に、深さごとの状態の数、及び、その深さまでの合計数を示す。

	状態1		状態2		状態3
深さ	状態数	状態数の合計	状態数	状態数の合計	状態数	状態数の合計
0	1	1	1	1	1	1
1	2	3	3	4	4	5
2	4	7	6	10	10	15
3	10	17	14	24	20	35
4	24	41	32	56	38	73
5	54	95	66	122	80	153
6	107	202	134	256	174	327
7	212	414	280	536	372	699
8	446	860	585	1121	762	1461
9	946	1860	1214	2335	1540	3001
10	1948	3754	2462	4794	3072	6073
11	3938	7692	4946	9743	6196	12269
12	7808	15500	9861	19604	12356	24625
13	15544	31044	19600	39204	24516	49141
14	30812	61865	38688	77892	48719	97320
15	60842	122707	76086	153978	94356	191676
16	119000	241707	148435	302413	183432	375180
17	231844	473551	288098	590511	355330	730438
18	447342	920893	554970	1145481	682250	1412688
19	859744	1780673	1062628	2208109	1301874	2714562
20	1637383	3418020	2016814	4224923	2460591	5175153

-A*探索-

A*探索はヒューリスティック関数を用いて探索を行うため、盤面の状態によってヒューリスティック関数から求められる値が変わる。よって、幅優先探索と違い、初期状態ごとに探索する状態が違うことになる。以下に解くために必要な手数とそのときにかかった探索数の値の一例を示す。

深さ	状態数	深さ	状態数
1	1	11	166
2	5	12	716
3	11	13	2303
4	19	14	3050
5	49	15	5180
6	53	16	37398
7	58	17	37400
8	81	18	37726
9	89	19	37796
10	130	20	37981

以上の結果から分かるように、A探索はヒューリスティック関数を用いて探索を行うため、幅優先探索と比べて探索数が大幅に減少していることが分かる。
15puzzle_A探索プログラム

戻る