Posted at: 2018-02-28 08:47:47  Category: programming


ヒューリスティックを用いない網羅的な探索を行う場合、反復深化深さ優先探索はかなり強力です。
探索空間が無限に広くても、解が存在する限りは必ず、解を見つけてきます。(もちろんマシンスペックによる制約はありますが)

Common Lisp で雑に書きました。iddfs

iddfsパッケージをロードして、メソッドを2つ定義すると使えます。
下記の様な無限に広い探索空間を持つ自然数の木構造から6700417を探索してみます。


$ ros run -s iddfs -l search.lisp 
Evaluation took:
0.790 seconds of real time
0.789956 seconds of total run time (0.782400 user, 0.007556 system)
[ Run times consist of 0.046 seconds GC time, and 0.744 seconds non-GC time. ]
100.00% CPU
50 lambdas converted
1,972,356,400 processor cycles
431,615,088 bytes consed

depth = 22, value = #S(EVEN-OR-ODD :NUMBER 6700417)
深さ、22のところに見つかりました。