2009年9月3日木曜日

プログラムの巨大化

 5年もマウスをやっているとプログラムがどんどん大きくなってくる.とくにひどいのが迷路解析の部分.探索と最短経路計算のために現状ではRAMを50kByteも占める.何も考えずに32*32の迷路に対応しようとしたからであるが,予想以上にひどい.なんとか20kByteくらいにおさめなければ.

2 件のコメント:

福井 さんのコメント...

斜め・回転を考えず、単純な歩数を幅優先探索で求めるだけなら、192byteでいけるよ!
探査or未探査=1bit*32*32=128byte
探索ノードが保持すべき親ノードを示す情報:2bit
同時にあらわれる探索ノードの最悪個数:(32-1)*4=124マス
128+124*2/4=192byte

kojima さんのコメント...

まあもちろん何かをあきらめれば小さくできますが...
ちなみに50kByteの内訳は,

迷路の壁,既探索か未探索かの情報・・・4k
枝情報・・・1.6k
上記迷路情報の退避用配列・・・(4+1.6)*2k
簡易最短経路計算用配列・・・8k
経路計算高速化用配列・・・8k

最短経路計算用配列・・・8k
経路計算高速化用配列・・・8k
経路格納用配列・・・1k

現在はざっと削って25kくらいになっています

コメントを投稿