巡回セールスマン問題

床を綺麗にしてくれるお掃除ロボットの作成依頼がきた。

手当たり次第に床を磨き続けていれば、そのうち汚れた床にたどり着き、綺麗に出来る。

しかし、エコだ！エコだ！と叫ばれる世の中、ロボットを動かしっぱなしにするわけにもいかない。そこで、あなたには、汚れた床を最小限の移動で綺麗にするアルゴリズムを考えてもらおう。

☆印はロボットの初期位置、×印は汚れた床、塗りつぶされた所には家具がおいてあり、通る事が出来ない。

こんな問題があって、ずっと解けなかったわけですが、『距離行列＆TSPで解けるよそれ』と言われ、あぁ、「なんだ解けるじゃないか、巡回セールスマン問題なんてたいしたこと無いのかも」と思った訳です。

まず最初に、距離行列を作る。

上みたいに各場所までの距離を、おのおの求めて距離行列を作る。

もうそしたら、とにかく無理やり！ゴリ押し！力押し！

んで、解けたわけですが

『TSP（巡回セールスマン問題）など恐るるにたらんわ！フハハハハ！！』

みたいに調子に乗って、

『もっと汚れた床増やしちゃえ☆』

と、沢山汚れた床を増やした訳ですが・・・・・・・・・

終わらねぇ・・・・・・・・・・・・・どんだけ待っても終わらねぇ・・・・・・・・

よくよく考えてみると、

１！ ＝ １

２！ ＝ ２

３！ ＝ ６

４！ ＝ ２４

５！ ＝ １２０

６！ ＝ ７２０

７！ ＝ ５０４０

８！ ＝ ４０３２０

９！ ＝ ３６２８８０

１０！ ＝ ３６２８８００

１１！ ＝ ３９９１２８００

１２！ ＝ ４７９００１６００

１３！ ＝ ６２２７０２０８００

なので、汚れた床の数が10を超えたあたりで厳しくなってくるね。

どおりで問題でも『汚れた場所は10個以内』って書いてあるわけだ

そりゃあ、お偉方が頑張って研究してるだけあるわ、TSP

TSPはNP困難問題に入るはずなので、時間がかかって解けないよってことね

ちなみに下の画像のように、30回の移動で全て回れます