プログラマーなら知っておきたい「巡回セールスマン問題」と舞茸の話

Pocket

ここでは、プログラマーやシステムエンジニアなら知っている方も多いと思いますが、「巡回セールスマン問題」のおさらいです。

スポンサーリンク

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

簡単に言ってしまうと、ある地域の顧客の家を巡回することになったセールスマンがなるべく総移動距離が少なくなるようになるための経路を求める問題です。

私の場合は、「マイタケ問題」と同じです。すべての木の位置は把握しています。どのようにすべての木を探索するかの経路を求める問題になります。

マイタケ問題で良くね?しかも人数が2人の場合とか2人の場合とか、考えるの大変なんですけど。。。

コンピュータで計算するのも大変なほどに計算量がビッグバンします。ハイパーインフレ上等です。「ここはジンバブエか?」って感じです。なお、「ある総移動距離以下の経路があるかないかを求める問題は「NP完全問題」であることが知られています。

NP完全問題とは

NP問題とは、計算理論において、解くのに時間のかかる問題のことで、NP完全問題とは、さらに難しく計算に時間がかかる問題を指します。なお、世の中の重要な問題は、「NP完全問題」であることが知られています。

量子コンピュータで解決するか?

計算量がハイパーインフレを起こすと、計算終了までに地球がお亡くなりになっている可能性があります。しかし、現在、開発が進んでいると思われる量子コンピュータが登場すると、瞬殺で計算が完了するかもしれません。

詳しくはさっぱりわかりません。適当に言っています。

 

マイタケに関するウンチクと小言

マイタケは、「ブナやミズナラの大木の根元に生えている」といくつかのサイトに書いてありますが、私は、ミズナラの根元に生えているのを見たことしかありません。

ブナとミズナラは一緒に生えていますが、ブナの根元に「舞茸?」って感じです。ブナに「なめこ」なら分かりますが。まあ、詳細は知らないです。そんなこともあるのかもしれないですね。

スポンサーリンク


Pocket

Leave a Comment

Your email address will not be published. Required fields are marked *