Gauche:パズル探索
- 単純な幅優先探索では、局面数が多すぎるようで、解けない面がありました。
上記ページでは、その解けなかった面のデータを設定しています。
枝刈りの条件等を追加できるとよさそうですが。。。
- 探索済みの局面については、保存して重複をチェックすることで、無限ループを回避しています。
ただ、100万局面とか たまってくるので、その重複のチェックが、ボトルネックになっています。
最初は、リストにして find で検索していたのですが、
hash-table に変更したところ 100 倍以上高速になりました。
しかし 自分の PC だと、300万局面あたりでメモリ不足になってしまうようです。
- hamayama(2019/01/03 14:57:15 UTC): その後、make-hash-table の引数を、
bytevector-comparator から equal-comparator に変更したところ、
2引数の object-hash でいけるようになりました。
- hamayama(2019/06/23 03:10:36 UTC): Gauche 0.9.8 から、object-hash を定義しなくても、
u8vector をハッシュテーブル (make-hash-table 'equal?) のキーに使えるようになりました。
hamayama(2019/01/03 14:43:12 UTC)(2019/01/03 23:56:33 UTC)
Last modified : 2019/06/23 03:10:36 UTC