EFC：巡回セールスマン問題の難易度と「1次元っぽさ」

巡回セールスマン問題とはどういうものなのか

僕が以前、新聞配達のバイトをしていたときに思ったことがあるんだけど
新聞配達員問題と名づけてもいいくらい、同じような問題に直面する。

順路の問題

横に長い区域の担当だったとする
そこでは、僕はその横に長い区域を、縦にぶつ切りにしていって
その1つ1つの縦の区域ごとに時計回りに配る順路にしていた

左端のぶつ切りから始めて、1個ずつ右にシフトしていく。
(ストークスの定理とか、土鍋部分に邪魔されたIHクッキングヒーターのうず電流をイメージできる人はそれがいいと思う)

そうすると、問題が生じる

1個目のぶつ切りの帰り道(下向き)と、2個目のぶつ切りの行きの道(上向き)がカブるわけだ。

これじゃ効率がよくない




と思って、今度は担当区域を横にスライスした。
時計回りに配るのは同じだけども
横にスライスすると、スライスの上から順に下にシフトしていくことになる


やっぱり、1個目のスライスの帰り(左向き)と2個目のスライスの行き(右向き)がカブる。
結局効率の悪さは似たり寄ったりなのではないか。
ただし、碁盤の目に満遍なく家があって人が住んでいるとは限らない。

どうすれば効率よく回れる？
↓
めんどくさ！
↓
順路考えたヤツ、good　job！

ものすごく大雑把にいうと、これが「巡回セールスマン問題の根っこ」だ。







今度は、その建物が全部3階建てのアパートだったと考えよう
どうなるか？

アパートはA棟、B棟、C棟、D棟と分かれているのだけど
管理人が割とおせっかいな人で、全部ではないがあちこちに渡り廊下を準備してくれている。渡り廊下に限らず、廊下は走ってはいけないらしい。ボロいのか？ 階段に亀裂が目立つ。

配達員はよけいに悩む。どの順路でいくべきか。

東西ぶつ切りか、
南北スライスか、
各階ごとか、
どれを優先して回ればいいのか、自由度が増えた分、悩みも増える。
(階段上り下りの体力のことはあとで考えることにしている)


ということは、平面でも立体でも、たぶんそれ以上の次元でも、巡回セールスマン問題は存在するということだ。







じゃあ逆に、客の家が一直線上に並んでいる区域を担当したらどうなるか？
ここでは問題は起きない。

販売所のすぐ近くに区域の左端があって、右端の近くに配達員の家があったら、迷うことなく左から右に一気に配達して直帰するだろう。

つまり、1次元だけは巡回セールスマン問題が発生しない。
1次元は特別な次元なのだろう。





次に、1次元っぽい2次元を考える。
家が直線状に並んでいるのは同じだが、2行に配置されている場合だ。
この場合は、1次元ほどではないが、割と簡単だろう。

北のスライスを西から東に進んで
東端についたら、折り返して南側のスライスを東から西に進めばいい。
あまり悩むこともない。

逆にいうと、家が「真四角の中に並んでいる場合」のときは大いに悩む。

これは何を意味するのか？
同じ2次元でも、1次元っぽさの違いによって、問題の難易度が違うということだ。




この難易度は、四角形の外周と面積の比によるのではないか？

カタチを四角形に限定すると、同じ外周で面積が一番でかいのは真四角だ。
紐で作った輪っかを目いっぱい広げようとすると真四角に近くなるだろう。

逆に、一番大きいのは、限りなく線に近い面(細長い長方形)だ。
面積がほとんどないので、外周/面積の比は限りなく大きい。
この量を「1次元っぽさ」と呼ぶことにしよう




1次元っぽさの定義

辺の長さが1cmの真四角でいうと、外周の4cmを面積の1cm2(平方センチメートル)で割った、4といった感じの量。長さの逆数の次元を持ち、 単位は[(cm)^-1]などと表記する。
同じ外周で、棒状になったら限りなく大きくなる、カタチによって変わる量
超球状に配置されていたら、その領域の表面積めいたものを体積めいたもので割った量。
巡回セールスマン問題はこの「1次元っぽさ」が小さいほど難しくなるのではないか。


単位の表現がこめんどくさいので、いっそのこと「ナントカの難易度」＝「1次元っぽさの逆数」(長さの次元を持ち、単位はcmとか)にしてもいいかもしれない。

_{(1次元っぽさを考えていたら1次元なのに単位が長さの逆数で混乱した)}


なーんてことはきっともう誰かが提言してるんだろうなー＾＾って話




これが超時空サッカーだ！　イナズマ・フロンティア

にほんブログ村