巡回セールスマン問題

青木です。paizaラーニング担当のエンジニアです。プログラミングの多様な練習問題を公開している「レベルアップ問題集」に、「巡回セールスマン問題メニュー」を追加しました！この「巡回セールスマン問題」、アルゴリズムを勉強したことがある方は耳にしたことがあるかもしれません。競技プログラミングでも定番の問題となっています。今回は、「巡回セールスマン問題」とはそもそもどんなものなのか？から始まり、解法や実際の問題の解き方まで詳しく解説していきたいと思います。自分のプログラミングのスキルを一段引き上げたい方はぜひ一緒に取り組んでいきましょう。プログラミング初心者の方は、少し難しく感じるかもしれませんが、…

今回は膜アルゴリズムを使い巡回セールスマン問題を解きます。 巡回セールスマン問題は、都市がいくつか(nとします)あり、それらを全てちょうど一回ずつ訪れて出発都市に戻る、距離が最短の経路を見つける問題です。詳しいことは例によってWikipediaにお任せしましょう。巡回セールスマン問題の解はn都市からなる系列です。出発都市は固定してよく、距離は幾何学的距離とすれば逆に回っても距離は同じなので、可能な解の候補は(n-1)!/2となります。!は階乗で、3!=6, 4!=24, 5!=120, 6!=720, とnが大きくなるとすごい勢いで大きくなります。だから可能な解を全部調べて・・・というやり方は…

こんにちは。 平衡二分探索木で2-optを高速化する方法について研究したので、本記事ではそれについて書こうと思います。 2-optとは 2-optは巡回セールスマン問題(TSP)の近似解を求めるヒューリスティックアルゴリズムです。 下図のように、サイクルに対してランダムに二つのパスを選び、パスを組み替えた方がサイクルの長さが短くなる場合、パスを組み替えます。具体的には、A→B + C→D > A→C + B→D の時、辺ABと辺CDを辺ACと辺BDに組み替えます。 しかし、辺を張り直すだけではサイクルにならないので、B~CまたはD~Aの間の順序を逆にする必要があります。 2-opt法では順路を…

西口です。paiza（ギノ）に入社して2ヶ月目の新人エンジニアです先日、11月2日～4日の3連休で、アルゴリズムを使ってナポリタン専門店のパンチョさんのスタンプラリーに挑戦し、ナポリタン1年分無料券をゲットしました。やったー！！今回は、その経緯と攻略法をお伝えします。スタンプラリー攻略におけるアルゴリズムに興味がある方、パンチョとナポリタンを愛する方々の参考になればと思います。 パンチョのスタンプラリーと挑戦した経緯 paiza（ギノ）に入社するために引っ越してきた（もとは関西にいました）私が、慣れない東京で迷い込んだのがパンチョ渋谷店でした。naporitanpancho.comそのインパク…