[英] traveling salesman problem(TSP)
巡回セールスマン問題とは、組み合わせ最適化問題の一つで、「ある都市を出発したセールスマンの移動距離が最小値を取るように、すべての都市を一度ずつ必ず訪問して出発点に戻るための経路を求める」を求める問題のことで、最適化問題の代表例として知られている。
もともとはアメリカ合衆国のランド社が提出した懸賞問題である。
都市数が少ないうちは、最適解を求めるのは楽な問題だが、都市数が増えるにしたがって、計算量は2の2乗に比例して増えるため、コンピュータでも最適解を求めるのは難しくなっていき、効率よく厳密な解を求める手法は未だに確立されていない。
そのため、ニューラルネットワークや遺伝的アルゴリズムを利用した方法やアニーリング法などを用いて、近似解を求める方法が一般的である。
ただし、実際にこの問題の解を応用できる事例は多く、配送計画や表面実装ロボットの動作計画などに適用されている。
青木です。paizaラーニング担当のエンジニアです。プログラミングの多様な練習問題を公開している「レベルアップ問題集」に、「巡回セールスマン問題メニュー」を追加しました!この「巡回セールスマン問題」、アルゴリズムを勉強したことがある方は耳にしたことがあるかもしれません。競技プログラミングでも定番の問題となっています。今回は、「巡回セールスマン問題」とはそもそもどんなものなのか?から始まり、解法や実際の問題の解き方まで詳しく解説していきたいと思います。自分のプログラミングのスキルを一段引き上げたい方はぜひ一緒に取り組んでいきましょう。プログラミング初心者の方は、少し難しく感じるかもしれませんが、…
西口です。paiza(ギノ)に入社して2ヶ月目の新人エンジニアです先日、11月2日~4日の3連休で、アルゴリズムを使ってナポリタン専門店のパンチョさんのスタンプラリーに挑戦し、ナポリタン1年分無料券をゲットしました。やったー!!今回は、その経緯と攻略法をお伝えします。スタンプラリー攻略におけるアルゴリズムに興味がある方、パンチョとナポリタンを愛する方々の参考になればと思います。 パンチョのスタンプラリーと挑戦した経緯 paiza(ギノ)に入社するために引っ越してきた(もとは関西にいました)私が、慣れない東京で迷い込んだのがパンチョ渋谷店でした。naporitanpancho.comそのインパク…