|
|
私は結構あきっぽいようです。プログラミングも黙々とやらなくてはいけないものは苦手です。ついふらふらと出かけてしまったりして，なぜかバグが多くなってしまいます。そんな私でも好きだと言えそうなのが画像処理やグラフ問題といった「作った結果が目に見える」題材です。自分で作った成果が目で見てすぐわかると，とても楽しくなります。今回の問題はそうしたものの一つです。プログラミングに飽きてきたら，今回のような問題にちょっとチャレンジしてみてください。きっと楽しめると思います。
手当たり次第に調べてもうまくいかない
問題を整理してみましょう。まずは，自分がロボットになったつもりで，図1を眺めてみてください。スタートからゴールまでの道筋（パス＝path）を探していけばいいのですが，まっすぐゴールに向かおうとすると壁（障害物）に突き当たってしまいます。
|
|
| 図1●できるだけ少ない歩数でロボットをA地点からB地点まで進める方法は？ 黒で塗りつぶしたマスは障害物 |
よくある方法として，「壁にぶつかるまでまっすぐ進む」「壁に当たったら左右どちらかに，進行方向を変える」というのがあります（図2）。迷路を歩くようなゲームでよく見かける移動方法です。でも，回り道や後戻りを繰り返したり，障害物であふれていると動けなくなったりするので，あまりいい方法とはいえません。
|
|
| 図2●「壁にぶつかったら右に曲がる」というアルゴリズムで移動した場合。見るからに効率が悪い |
では，すべてのパスを調べ挙げ，その中から最短のものを選ぶ，というのはどうでしょうか。確かに，本連載の第1回で紹介したバックトラックなどを使えば，原理的にはすべてのパスを得ることができます。しかし，マップ（地図）が大きくなると，計算量が膨大になって大変です。加えて，同じ場所をぐるぐる回るような場合を取り除くといった工夫も必要になります。
障害物を避けながら最短のパスを求める方法は，パス探索問題として多くの人たちが考えています。あなたならどう考えますか？
選択肢がたくさんあるときは「重み付け」
問題をもう少し検討してみると，ゴールの方向がわかっているときには，今いる地点（マス）から「ゴールの方向」と「それ以外の方向」に進むのは明らかに差があることに気が付きます。障害物の有無があるにせよ，ゴールに近いマスをたどっていく方がより良いパスになりやすいはずです。ゴールが北の方にあるなら北に向かって進めば，とりあえずゴールに近くなるはず，という感じです。
ちょっと試してみましょう。そのマスがどれぐらいゴールに近いかを表すために，各マスにゴールまでの距離を書き込みます。そして移動する際には，距離がなるべく短くなるマスを選びながら一歩ずつ進んでいきます。障害物にぶつかって進めなくなったときは一歩戻って，さっき選んだマスよりも少し距離が長くなるマスを次の一歩として選択します。これを繰り返すことで，すべてを調べるよりも効率よく最短パスを選ぶことができるはずです。
このように「選択肢一つひとつに対して，どの程度望ましいか/望ましくないかを表す値（重み）を割り振り，それを基に判断する」手法を「重み付け」といいます。重み付けは，いろいろな条件が重なっている問題であまり面倒なく答えを得られる方法です。例えばテトロミノ＊2などのパズルなら答えを得るまでに多くの選択肢があります。そこで悪い条件にあたったらそれに応じて「重み」（「コスト」「ペナルティ」と呼ぶこともあります）をつけるようにします。最も重みが少ない選択肢が多分ベストな選択肢となるはずです。これを繰り返すことで「良い答え」が得られます。
重み付けで最短パスを探す
「重み付け」でパスを探す具体的な方法を考えてみます（図3）。まず，今いるマスから8方向のマスを調べます。一つのマスは1回だけ調べます。もし，そのマスがすでに重みを与えられていたら，別の方向にあるマスを調べます。
|
|
| 図3●重み付けでパスを探索する際の手順 |
ここでは，そのマスからゴールまでの幾何学的な距離＊3を計算し，その距離の値を各マスの「重み」とします。ゴールに近いマスほど重みは軽くなるわけです。調べたマスの重みは，そのマスの位置などの情報とともに，あらかじめ用意した「探索リスト」に登録しておきます。このリストには，こうした新しく重みが置かれたマスが集まることになります。
8方向を調べ終えたら，探索リストの中から最も重みが軽いマスに進んで，そのマスの周りについて重みを調べます。重みが軽いマスを選ぶことで，ゴールにより近いマスが選ばれていくことになります。ここまでの処理を繰り返してゴールまでたどりついたら探索終了です。
ここまで説明してきた方法は，A＊（「エー・スター」と読みます）などと呼ばれる，有名なパス探索アルゴリズムの一つです。重み付けの方法を変えることで，いろいろな場面に対応できるので，知っておくととても便利です。
