(このページは、もっとプログラマ脳を鍛える数学パズルの宣伝も含まれています。
なぜ宣伝しているかというと、書籍プレゼント企画にめでたく当選したからです。)
・この記事の目標
CODE QUESTというサイトをご存知だろうか。
プログラマーヘッドハンティングを目的として、難問を解かせるサイトである。
まずは実際に遊んでみてほしい。下記リンクの黄色の砦、毒沼ノ試練をクリックしよう。
・CODE QUEST
本来の趣旨はこの問題の解答をプログラムに解析させて解かせるものである。
プログラムとかわからん！という方も大丈夫、私は人力で解いた。
人力でもそこそこ時間をかければどうにかなる。
（実はクリア後に高難易度版がある。裏面はさすがに人力では無理。）
しかし、これをプログラムに解かせようとすると無茶苦茶難しくなるのだ。
プログラムで解かせるときには、
普通は全移動パターンを探索して、
一番良い結果を返すように記述する。
しかしこの問題を全探索すると、
組み合わせ爆発により膨大な量の移動パターンが考えられる
ため、普通にやったら一生探索が終わらない事態になってしまうのである。
【参考】組み合わせ爆発とは
実際にコードを書いてみた
とりあえず、全探索のアルゴリズムを作成したので、実際に動かしてみた。
テキストに以下コードをコピーして、.htmlファイルで保存してから実行するだけ動作する。
（※ブラウザがフリーズするのでホントに実行しなくてもいいよ！）
window.onload=function() {
//マップ情報 (1:回復 -1:毒沼 0:移動した後 S:自分 L:敵 G：魔王)
var map=[[-1,1,1,-1,-1,1,1,-1,-1,1],[1,"S",1,"L",-1,-1,-1,-1,-1,-1],[-1,-1,-1,1,1,-1,1,-1,1,1],[1,"L",-1,-1,1,-1,1,-1,1,-1],[-1,1,1,-1,-1,-1,-1,"L",1,-1],[1,-1,1,-1,-1,1,-1,1,-1,1],[-1,"L",-1,-1,-1,1,-1,-1,-1,1],[-1,1,-1,1,1,-1,1,-1,-1,-1],[-1,1,-1,-1,-1,1,1,-1,"G",1],[-1,-1,1,1,-1,-1,-1,1,-1,-1]];
var hp=36; //初期HP
var goalhp=50; //魔王到達時に目指すHP
var vec=[[1,0],[-1,0],[0,1],[0,-1]]; //移動ベクトル:0:右、1:左、2:下、3:上
var bestroute=[]; //最適ルートを保存する配列
var route=[]; //現在探索しているルート
function Search(_hp,_map){ //再帰的に探索を行う関数 返り値：HP
if(_hp<=0)return -999; //hpが０なら探索打ち切り
var x,y; //今現在の場所(x,y)
//Sの現在位置をx,yに代入
for(var i=0;i<map.length;i++){
for(var j=0;j<map[0].length;j++){
if(_map[j][i]=="S"){
x=i;
y=j;
}
}
}
//自分のマップ位置を空にする
_map[y][x]=0;
//四方向移動時の最適HPを保存
var besthp=-999;
//上下左右に移動
for(var i=0;i<4;i++){ //移動ベクトル:0:右、1:左、2:下、3:上 var nx=x+vec[i][0]; //次に移動するx座標 var ny=y+vec[i][1]; //次に移動するy座標 if(ny>=0&&ny<map.length&&nx>=0&&nx<map[0].length){ //マップから出ていないならその位置を探索 var nmap=_map[ny][nx]; //次の移動位置の情報をnmapに代入 if(nmap!=0&&nmap!="L"){ //もし次の移動位置が0か敵ではないなら探索続行 route.push(i); //現在の移動方向を代入(移動ベクトル:0:右、1:左、2:下、3:上) if(nmap=="G"){ //もしゴールにたどり着いたら besthp=Math.max(besthp,_hp); //besthpと現在のhpを比較し、大きい方をbesthpとする if(_hp>=goalhp){
bestroute=route.slice(); //もし、目的のhpに達していれば最適解なので通ってきた探索ルートを取得
}
}else{
_map[ny][nx]="S"; //そうでないときは回復か毒沼なので、その位置にSを移動
besthp=Math.max(besthp,Search(_hp+nmap,_map));//次の位置に移動してSearch関数を再帰的に実行。besthpと比べて大きい方をbesthpとする
}
route.pop(); //移動完了後なので、最後の移動方向を吐き出す
}
_map[ny][nx]=nmap; //_移動完了後なので、マップ情報を元に戻す
}
}
_map[y][x]="S"; //元居た位置にSを置く
return besthp; //最適なHPを返す
}
document.write(Search(hp,map,route)+"best:"+bestroute); //Search関数を実行し、その結果と最適ルートを返す
};
再帰的にルート探索を実行している。深さ優先探索で、とりあえず全通り探索して魔王到達時に目的のHPになっているとそのHPとbestrouteに進むべき方向が記される寸法である。
試してみた限りでは、6×６まではなんとか解析できた。しかし、7×７になるともう解析不能になってしまった。膨大な数の探索パターンが生まれてしまったからである。
ここで大事なのが、「いかに探索パターンを削れるか」である。
これを人は枝刈りという。
経路探索問題において、ダイクストラ法が最も有名ではあるが、経路に負の値を持つと成り立たないため、この方法は使えない。さてどうしたものか・・・。
（ダイクストラ法についてはこのページを見てね。）
と、ここまで来て一旦あきらめてしまったのが去年の１１月。
数学パズルの本で再起を図る
寝ぼけてはいけない。
ここからは、ヒマさえあれば数学パズルの本を読み込んでいた自分の力を試すときである。
ぜひともこの難問を解析するプログラムを作って、数学パズルの本スゲー！と
いう結論に持っていきたいところ。
ちなみにこの本、最初の数ページの入門編からしてそこそこ難易度は高い。
大まかな処理の流れを説明しているが、コメントアウトなどでコードの意味をほぼ書いていないので、プログラム処理の流れは自力で読み解く必要がある。
どちらかといえば、プログラムにある程度慣れた方向けである。
しかしながら、頑張ってコードを読み解いていくとなかなか面白いのだ。
面白い解き方、より処理を短くする解き方など、目から鱗の内容ばかりである。ただ、一問一問そこそこ頭を使わなければならないので、集中力をかなり使うことになる。
ちなみに、回答はjavascriptとrubyで書かれている。私はrubyを知らないので、javascriptのコードを見て勉強していた。
さて、ここからはこの本で得た知識とセンスを使うことになる。
いかに経路探索の枝刈りをしていくか。そこに絞って試行錯誤を以下に記す。
・メモ化作戦
あるマップが与えられたとき、最適な経路は一通りに定まるはずである。
全探索中は、同じマップを何度も計算しなおすことになるから、あるマップでの到達HPを保存しておけば、何度も同じ計算をしなくて済みそう！
ということで、書いてみたコードがこちら。
（起動しないでください。またフリーズします。）
window.onload=function() {
//マップ情報 (1:回復 -1:毒沼 0:移動した後 S:自分 L:敵 G：魔王)
var map=[[-1,1,1,-1,-1,1,1,-1,-1,1],[1,"S",1,"L",-1,-1,-1,-1,-1,-1],[-1,-1,-1,1,1,-1,1,-1,1,1],[1,"L",-1,-1,1,-1,1,-1,1,-1],[-1,1,1,-1,-1,-1,-1,"L",1,-1],[1,-1,1,-1,-1,1,-1,1,-1,1],[-1,"L",-1,-1,-1,1,-1,-1,-1,1],[-1,1,-1,1,1,-1,1,-1,-1,-1],[-1,1,-1,-1,-1,1,1,-1,"G",1],[-1,-1,1,1,-1,-1,-1,1,-1,-1]];
var hp=36; //初期HP
var goalhp=50; //魔王到達時に目指すHP
var vec=[[1,0],[-1,0],[0,1],[0,-1]]; //移動ベクトル:0:右、1:左、2:下、3:上
var bestroute=[]; //最適ルートを保存する配列
var route=[]; //現在探索しているルート
function Search(_hp,_map){ //再帰的に探索を行う関数 返り値：HP
if(_hp<=0)return -999; //hpが０なら探索打ち切り var txt=_map.join(""); //マップ情報を文字列化する txt=txt.split(",").join(""); if(memo[txt]>_hp)return memo[txt]; //マップ情報で検索が完了しているのなら、結果のHPを返す
var x,y; //今現在の場所(x,y)
//Sの現在位置をx,yに代入
for(var i=0;i<map.length;i++){
for(var j=0;j<map[0].length;j++){
if(_map[j][i]=="S"){
x=i;
y=j;
}
}
}
//自分のマップ位置を空にする
_map[y][x]=0;
//四方向移動時の最適HPを保存
var besthp=-999;
//上下左右に移動
for(var i=0;i<4;i++){ //移動ベクトル:0:右、1:左、2:下、3:上 var nx=x+vec[i][0]; //次に移動するx座標 var ny=y+vec[i][1]; //次に移動するy座標 if(ny>=0&&ny<map.length&&nx>=0&&nx<map[0].length){ //マップから出ていないならその位置を探索 var nmap=_map[ny][nx]; //次の移動位置の情報をnmapに代入 if(nmap!=0&&nmap!="L"){ //もし次の移動位置が0か敵ではないなら探索続行 route.push(i); //現在の移動方向を代入(移動ベクトル:0:右、1:左、2:下、3:上) if(nmap=="G"){ //もしゴールにたどり着いたら besthp=Math.max(besthp,_hp); //besthpと現在のhpを比較し、大きい方をbesthpとする if(_hp>=goalhp){
bestroute=route.slice(); //もし、目的のhpに達していれば最適解なので通ってきた探索ルートを取得
}
}else{
_map[ny][nx]="S"; //そうでないときは回復か毒沼なので、その位置にSを移動
besthp=Math.max(besthp,Search(_hp+nmap,_map));//次の位置に移動してSearch関数を再帰的に実行。besthpと比べて大きい方をbesthpとする
}
route.pop(); //移動完了後なので、最後の移動方向を吐き出す
}
_map[ny][nx]=nmap; //_移動完了後なので、マップ情報を元に戻す
}
}
memo[txt]=besthp; //その経路でのベストHPを保存
_map[y][x]="S"; //元居た位置にSを置く
return besthp; //最適なHPを返す
}
document.write(Search(hp,map,route)+"best:"+bestroute); //Search関数を実行し、その結果と最適ルートを返す
};
ダメでした！
そもそも、全探索がナンセンスなことにこの時点でようやく気が付きました。
最適解にたどり着きそうな経路をさがそう
今回は、正解のルートはHP:50以上であれば問題ないはずです。
ならば全探索せずに、HP50以上ありそうなルートを深さ優先探索した方がよい気がします。
そして、うまくいかなそうな経路を枝刈りして検索してどんどん効率をあげていきます。
具体的には、移動歩数が多くなるにつれHPの値は増えていくはず、という性質を利用します。
移動歩数が増えれば、その際HPも一定以上でないといけないはず。
ということで、探索途中の現在HPが一定以下（この足切りラインは移動歩数によって決まる）ようにすれば、最適解を発見しやすくなりそうですね。
その代わり、足切りラインで正解の経路を刈ってしまい、うまく計測できない可能性もあります。足切りラインをいかに適切に設定するかが重要です。
ということで、足切りライン追加後のコードがこちら。
window.onload=function() {
//マップ情報 (1:回復 -1:毒沼 0:移動した後 S:自分 L:敵 G：魔王)
var map=[[-1,1,1,-1,-1,1,1,-1,-1,1],[1,"S",1,"L",-1,-1,-1,-1,-1,-1],[-1,-1,-1,1,1,-1,1,-1,1,1],[1,"L",-1,-1,1,-1,1,-1,1,-1],[-1,1,1,-1,-1,-1,-1,"L",1,-1],[1,-1,1,-1,-1,1,-1,1,-1,1],[-1,"L",-1,-1,-1,1,-1,-1,-1,1],[-1,1,-1,1,1,-1,1,-1,-1,-1],[-1,1,-1,-1,-1,1,1,-1,"G",1],[-1,-1,1,1,-1,-1,-1,1,-1,-1]];
var hp=36; //初期HP
var goalhp=50; //魔王到達時に目指すHP
var vec=[[1,0],[-1,0],[0,1],[0,-1]]; //移動ベクトル:0:右、1:左、2:下、3:上
var bestroute=[]; //最適ルートを保存する配列
var route=[]; //現在探索しているルート
function Search(_hp,_map){ //再帰的に探索を行う関数 返り値：HP
if(_hp<=32+_route.length/3)return -999; //現在HPが(32+現在歩数/3)よりも小さければ探索終了 var txt=_map.join(""); //マップ情報を文字列化する txt=txt.split(",").join(""); if(memo[txt]>_hp)return memo[txt]; //マップ情報で検索が完了しているのなら、結果のHPを返す
var x,y; //今現在の場所(x,y)
//Sの現在位置をx,yに代入
for(var i=0;i<map.length;i++){
for(var j=0;j<map[0].length;j++){
if(_map[j][i]=="S"){
x=i;
y=j;
}
}
}
//自分のマップ位置を空にする
_map[y][x]=0;
//四方向移動時の最適HPを保存
var besthp=-999;
//上下左右に移動
for(var i=0;i<4;i++){ //移動ベクトル:0:右、1:左、2:下、3:上 var nx=x+vec[i][0]; //次に移動するx座標 var ny=y+vec[i][1]; //次に移動するy座標 if(ny>=0&&ny<map.length&&nx>=0&&nx<map[0].length){ //マップから出ていないならその位置を探索 var nmap=_map[ny][nx]; //次の移動位置の情報をnmapに代入 if(nmap!=0&&nmap!="L"){ //もし次の移動位置が0か敵ではないなら探索続行 route.push(i); //現在の移動方向を代入(移動ベクトル:0:右、1:左、2:下、3:上) if(nmap=="G"){ //もしゴールにたどり着いたら besthp=Math.max(besthp,_hp); //besthpと現在のhpを比較し、大きい方をbesthpとする if(_hp>=goalhp){
bestroute=route.slice(); //もし、目的のhpに達していれば最適解なので通ってきた探索ルートを取得
}
}else{
_map[ny][nx]="S"; //そうでないときは回復か毒沼なので、その位置にSを移動
besthp=Math.max(besthp,Search(_hp+nmap,_map));//次の位置に移動してSearch関数を再帰的に実行。besthpと比べて大きい方をbesthpとする
}
route.pop(); //移動完了後なので、最後の移動方向を吐き出す
}
_map[ny][nx]=nmap; //_移動完了後なので、マップ情報を元に戻す
}
}
memo[txt]=besthp; //その経路でのベストHPを保存
_map[y][x]="S"; //元居た位置にSを置く
return besthp; //最適なHPを返す
}
document.write(Search(hp,map,route)+"best:"+bestroute); //Search関数を実行し、その結果と最適ルートを返す
};
ということで、先ほどのコードの１８行目を以下に変更しました。
if(_hp<=32+_route.length/3)return -999; //現在HPが(32+現在歩数/3)よりも小さければ探索終了
HP０以下で打ち切りしていた部分の足切りラインを上げていく発想になります。
このコードを実行すると、９０秒ほどかかりますがきちんと回答を示してくれます。
回答を翻訳したものが以下となります。
HP:51
Route:右下右右下右右上上上左左左左左左下下下下右右下下下左下下右右上上右下右右上上左上右右右上上上右下下下下下下左
（Routeには数字が出力されますが、これを上下左右に置き換えています。）
できた！やったー！！！！！！
試行錯誤のためにコードの処理時間を計測しよう
とはいえ、このコードの処理時間が気になるところ。
今回の問題の要点は「いかに枝刈りして処理時間を減らせるか」にかかっていると思うので、関数実行前後でDate関数を取り、（実行後の時間 new Date()）ー（実行前の時間 new Date()）で引き算をすることで処理時間を計測してみましょう。
（ついでに、出力は数字なので上下左右できちんと表示させてみました。）
window.onload=function() {
var startTime = new Date(); //処理時間計測 (start時間)
//マップ情報 (1:回復 -1:毒沼 0:移動した後 S:自分 L:敵 G：魔王)
var map=[[-1,1,1,-1,-1,1,1,-1,-1,1],[1,"S",1,"L",-1,-1,-1,-1,-1,-1],[-1,-1,-1,1,1,-1,1,-1,1,1],[1,"L",-1,-1,1,-1,1,-1,1,-1],[-1,1,1,-1,-1,-1,-1,"L",1,-1],[1,-1,1,-1,-1,1,-1,1,-1,1],[-1,"L",-1,-1,-1,1,-1,-1,-1,1],[-1,1,-1,1,1,-1,1,-1,-1,-1],[-1,1,-1,-1,-1,1,1,-1,"G",1],[-1,-1,1,1,-1,-1,-1,1,-1,-1]];
var hp=36; //初期HP
var goalhp=50; //魔王到達時に目指すHP
var vec=[[1,0],[-1,0],[0,1],[0,-1]]; //移動ベクトル:0:右、1:左、2:下、3:上
var bestroute=[]; //最適ルートを保存する配列
var route=[]; //現在探索しているルート
var memo=[];
function Search(_hp,_map){ //再帰的に探索を行う関数 返り値：HP
if(_hp<=32+route.length/2.9)return -999; //hpが０なら探索打ち切り var txt=_map.join(""); //マップ情報を文字列化する txt=txt.split(",").join(""); if(memo[txt]>_hp)return memo[txt]; //マップ情報をキーとした連想配列にbestHPを代入
var x,y; //今現在の場所(x,y)
//Sの現在位置をx,yに代入
for(var i=0;i<map.length;i++){
for(var j=0;j<map[0].length;j++){
if(_map[j][i]=="S"){
x=i;
y=j;
}
}
}
//自分のマップ位置を空にする
_map[y][x]=0;
//四方向移動時の最適HPを保存
var besthp=-999;
//上下左右に移動
for(var i=0;i<4;i++){ //移動ベクトル:0:右、1:左、2:下、3:上 var nx=x+vec[i][0]; //次に移動するx座標 var ny=y+vec[i][1]; //次に移動するy座標 if(ny>=0&&ny<map.length&&nx>=0&&nx<map[0].length){ //マップから出ていないならその位置を探索 var nmap=_map[ny][nx]; //次の移動位置の情報をnmapに代入 if(nmap!=0&&nmap!="L"){ //もし次の移動位置が0か敵ではないなら探索続行 route.push(i); //現在の移動方向を代入(移動ベクトル:0:右、1:左、2:下、3:上) if(nmap=="G"){ //もしゴールにたどり着いたら besthp=Math.max(besthp,_hp); //besthpと現在のhpを比較し、大きい方をbesthpとする if(_hp>=goalhp){
bestroute=route.slice(); //もし、目的のhpに達していれば最適解なので通ってきた探索ルートを取得
}
}else{
_map[ny][nx]="S"; //そうでないときは回復か毒沼なので、その位置にSを移動
besthp=Math.max(besthp,Search(_hp+nmap,_map));//次の位置に移動してSearch関数を再帰的に実行。besthpと比べて大きい方をbesthpとする
}
route.pop(); //移動完了後なので、最後の移動方向を吐き出す
}
_map[ny][nx]=nmap; //_移動完了後なので、マップ情報を元に戻す
}
}
memo[txt]=besthp; //その経路でのベストHPを保存
_map[y][x]="S"; //元居た位置にSを置く
return besthp; //最適なHPを返す
}
document.write("HP:"+Search(hp,map,route)+"
"); //Search関数を実行し、その結果と最適ルートを返す
//bestrouteを数字から文字に変換
var cbestroute="";
for(var i=0;i<bestroute.length;i++){
if(bestroute[i]==0)cbestroute+="右";
else if(bestroute[i]==1)cbestroute+="左";
else if(bestroute[i]==2)cbestroute+="下";
else if(bestroute[i]==3)cbestroute+="上";
}
document.write("Route:"+cbestroute+"
");
//結果を出力
var endTime=new Date(); //処理時間計測（終了時間）
document.write((endTime-startTime)+"ms"+"
");
};
・結果
HP:51
Route:右下右右下右右上上上左左左左左左下下下下右右下下下左下下右右上上右下右右上上左上右右右上上上右下下下下下下左
81445ms
・メモ化処理を外した場合
HP:51
Route:右下右右下右右上上上左左左左左左下下下下右右下下下左下下右右上上右下右右上上左上右右右上上上右下下下下下下左
14855ms
メモ化処理でずいぶんと時間をかけていたことが判明したので、メモ処理を消しておきましょう。
原因としては、同じマップはそう何度も出現しないこと、マップ情報が配列なので、文字列化に時間がかかりすぎるためと考えられます。
計測前後の処理時間を計測すると試行錯誤がスムーズにいきそうです。
今回の方法って実際どうなん・・・
今回の経路で変化したHPと足切り設定ラインのグラフです。
足切りラインにギリギリつくかつかないかでHPが上下しているため、ギリギリで回答が枝刈りされずに済んだことがわかります。一歩の移動で±１しかなく、変化量が少ないため、今回の方式が成り立つのだと思います。
ただ、これって足切りラインの設定が無茶苦茶大変そうじゃないですか。
というより、
あり得ない可能性を切るよりも、
あり得る可能性をどんどん追求していった方が
早く解にたどり着きそうです。
普通はどうやって解いていくか・・・。と調べたところ、どうもビームサーチが有効であることがわかりました。
ということで、次回はビームサーチを使った解析を行ってみたいと思います。
長くなってしまったので、今回はここまで！
もっとプログラマ脳を鍛える数学パズルで勉強してきます！