17/10/24 17:00:25.81 Hbs/5tbH.net
>>444
> ディープラーニングでNP問題とか学習させたらいい線いくんかね？
> 巡回セールスマン問題なんか相性よさそうだが。
その質問に対する答えは、NP（完全）問題に対してどういう解が欲しいかに依る。
巡回セールスマン問題のような最適化問題の多くはNP完全問題だが
そういう最適化問題に対して厳密な意味での正解、つまり本当の最適解を求めたいならば
ディープラーニングは全くと言っても過言でないほど役に立たない。
そうではなくて現実のセールスマンが客先を巡回する際は別に文字通りの最小コスト経路でなく
「そこそこ良い解」とか「常識的な解」つまり厳密には最適ではないかも知れないが
現実に使い物になる程度の解で良しとするのであれば、ディープラーニングのような帰納的（経験的）方法は確かに有効だろう。
だから同じ巡回セールスマン問題であっても、実際の営業マンの出張経路の立案ならば常識的に受け容れられる程度の最適度で良いので
ディープラーニングは有効（それ以前に従来も様々な路線検索サービスが既に同様の「最適」解の情報を提供している）であるが、
例えばデジタル通信での暗号化技術として素因数分解問題の代わりに巡回セールスマン問題を使った暗号（実際、そういう研究は
以前から成されている…実用化の有無に関しては私は知らない）の暗号破りのために巡回セールスマン問題を解かねばならないと
なると、厳密解（唯一つだけ存在する数学的な意味での解）以外は無意味なので、ディープラーニングは無力ということになる。