「マンガ TREE3 vs 巡回セールスマン問題 （2019/04/21)」
マンガ TREE3 vs 巡回セールスマン問題
巡回セールスマン問題は数学の中でも「解けない問題」として有名ですねえ。
例えば日本にあるコンビニ55000店の最短経路を求めるだけでも
55000! = おおよそ 10260000
の計算が必要。
計算の根拠:
55000! = 55000×54999×54998×...(55000個)...×2×1
55000 = 10x
log(55000) = log(10x)
log(55000) = x log(10)
log(55000) = x
x = 4.740
55000 = 104.740
55000! = 55000×54999×54998×...(55000個)...×2×1
55000! = 104.740×104.740×104.740×...(55000個)...×2×1
仮に全ての項目が104.740だと多めに見積もって
55000! = 104.740 + 4.740 + ...(55000個) ... + 4.740
55000! ＜ 104.740 × 55000
55000! ＜ 10260719
※「真の最短経路」ではない、「それなりの最短経路」。妥協バージョンでいいなら
瞬時に計算できるアルゴリズムがあります。
リアルではそっちを使います。
55000! = 55000×54999×54998×...(55000個)...×2×1
55000 = 10x
log(55000) = log(10x)
log(55000) = x log(10)
log(55000) = x
x = 4.740
55000 = 104.740
55000! = 55000×54999×54998×...(55000個)...×2×1
55000! = 104.740×104.740×104.740×...(55000個)...×2×1
仮に全ての項目が104.740だと多めに見積もって
55000! = 104.740 + 4.740 + ...(55000個) ... + 4.740
55000! ＜ 104.740 × 55000
55000! ＜ 10260719
※「真の最短経路」ではない、「それなりの最短経路」。妥協バージョンでいいなら
瞬時に計算できるアルゴリズムがあります。
リアルではそっちを使います。
将棋の全パターンが10200、囲碁の全パターンが10360
だったのですから
コンビニ55000店舗の最短巡回経路を求める計算量
10260000はそれよりかなり上の問題です。
それを宇宙の全原子、1080規模でやると
かなり大きい。
前回と同じ要領で見積もると
1010000000000....(0が82個).......00000000000
の計算量になる事がわかる。
・・・んが！
グラハム数、TREE3など巨大有限数のサイズは
1010000000000....(0が1兆個).......00000000000
は余裕である。
うーん。これでもまるで相手にならない。^_^;
全宇宙規模。1080程度の数を使ってるレベルではどうあがいても
巨大有限数の領域には届かないのだ。