巡回セールスマン問題で解く！
効率のいいスーパーの回り方

概要

---

巡回セールスマン問題とは、いくつかの地点を効率よく回るには 最短経路がどのようなものになるか？といったことを考える問題で アルゴリズムの勉強をしていると目にする事も多いかと思います。
詳しくはこちらに書きました。

効率のいい道を探す！「巡回セールスマン問題」

今回はこの巡回セールスマン問題を使い、スーパで買い物をするときの 最短ルートを計算するアルゴリズムを考えたいと思います。

巡回セールスマン問題とは

---

（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
wikipediaより

つまり、効率よく最短ルートを回るにはどうしたらいいのか？ということを考える問題ということでいいと思います。

スーパーで巡回セールスマン

---

巡回地点が多い場合、パターンが途方もないことになるが、今回は24通りなので表にしてみた。

表にして気が付いたが、道順は逆に回ろうと距離は変わるはずがないので2で割れて12通りになる。

表のなかから距離が最も短いものを探してみたところ距離数は9

最適ルートは「0⇒1⇒2⇒3⇒4⇒0」とでた。

つまり、効率のいい買い物順は、「肉、魚、乳製品、お菓子」とわかった。

まとめ

---

地図の曲がり角ごとをチェックポイントにして、距離パターンを考えて短い距離を算出できれば 効率のいい買い物ルートを作るナビゲーションシステムになりそうだが、実際には途方もないパターンが 算出されそうな予感がする。