経路アルゴリズムを検討した話 その３
2014 年 1 月 7 日 by 山平前回、それっぽいアルゴリズムができました。
ぱっと見た感じそれっぽいのですが、アルゴリズム改良の前後であまり変化がないように見えるのが気になります。
少し真面目に結果を分析してみたくなりました。
分析用データは、アルゴリズム改善の前後それぞれについて以下のルールで自動化して作成しました。
- 乱数から3～6を得る
- NxNの正方形のマス目で経路を作成する
- 開始位置も乱数で決める
- 以上を1万回繰り返す
以下が集計結果です。
【改善前】
| サイズ | 試行回数 | 成功回数 | 成功率（%） |
|---|---|---|---|
| 3×3 | 2461 | 1395 | 57% |
| 4×4 | 2518 | 2486 | 99% |
| 5×5 | 2542 | 997 | 39% |
| 6×6 | 2479 | 1226 | 49% |
【改善後】
| サイズ | 試行回数 | 成功回数 | 成功率（%） |
|---|---|---|---|
| 3×3 | 2495 | 2197 | 88% |
| 4×4 | 2612 | 2594 | 99% |
| 5×5 | 2508 | 1369 | 55% |
| 6×6 | 2385 | 1545 | 65% |
改善の前後で、それなりに効果が出ているのが分かります。
しかし、最初に結果を見て「おや？」と思ったのは、マスの大きさに比例して失敗が多くなる訳ではない、と言う点です。
開始点に注目して3×3の結果を眺めてみましょう。
なお、開始点は左上が0、右下が8です。
| 開始点 | 試行回数 | 成功回数 | 成功率（%） |
|---|---|---|---|
| 0 | 450 | 450 | 100% |
| 1 | 79 | 0 | 0% |
| 2 | 369 | 369 | 100% |
| 3 | 85 | 0 | 0% |
| 4 | 566 | 566 | 100% |
| 5 | 59 | 0 | 0% |
| 6 | 415 | 415 | 100% |
| 7 | 75 | 0 | 0% |
| 8 | 397 | 397 | 100% |
不思議な事に奇数の開始点では必ず失敗する、という結果が出ています。
5×5も同様の事象が確認できました。
紙の上で3×3のマス目での状況をトレースしてみると、奇数の開始点は前回の「窪地の問題」が発生しやすい開始点と言えるようです。
試していないのですが、5×5でも同じことが起こっていると考えられます。
今回はここまでです。
タグ: アルゴリズム
