巡回セールスマン問題

青木です。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そのインパク…

マスターズ参加してました。とりあえず酔ってる勢いでもろもろと。 とにかく反省点がめちゃくちゃ多かったけどとっても楽しかったです。まあ、あめんばーさんは14歳(N進数)なんですけどね(Nは[5,1e18]）例によって私のブログは誰かのために書くというよりは後への自分のかきなぐりです。（コレ毎回言ってる気がする）

参加の記念にメモ程度ですが残しておきます 予選 しれっと応募が始まって予選の一週間くらい前には終わっているので忘れないようにしましょう 過去問を見てもらうとわかるんですが、謎の入力形式になっています 終わるまで気づかなかったんですが、そのままソースコードに貼ることを想定していそうです(文字列が""で囲んであったり、vectorなどにしやすそうなものが{}で囲んであったり) これをいちいちパースしているとそれだけでも時間がかかるので、特に非就活枠の人はあらかじめどう取り組むか決めておいた方がいいと思います 手元実行をするタイプですが入力のサイズがかなり小さいので、AtCoderのコードテストで全…

東京はようやく桜が咲きそうです。桜並木の散歩が楽しみです。 今回は、巡回セールスマン問題です。複数の地点を訪れる際の最短経路を見つける問題です。時間の制約があり効率化が求められる現代ではより良い解が必要とされますね。可能であれば、時間を気にせず気の向くままに好きな方向に進んでいきたいですが。 では、巡回セールスマン問題の解法をGoogle Maps APIを利用して確認してみましょう。 設計 画面上で、以下5地点を指定し、Google Maps APIを呼び出して最短経路を取得・確認できるようにします。 出発地 経由地1 経由地2 経由地3 到着地 APIの構築 画面から呼び出すAPIをPyt…

JOI23/24の参加記です。春合宿です。雑です。躊躇なくネタバレします。 また、記憶の捏造があるかもしれません*1 春合宿前 特段特殊な精進はしてなかったはずです。難易度10を少し埋めたり遅延セグ木の空書きとかはしました。 というので、本選前よりは精進してないと思います。 Day0 交流会 いろんな人と話しました。楽しかった。 紙でタワーを作る大会がありました。この積み方で思ってた数億倍安定してて笑いました。*2 JOI交流会にて pic.twitter.com/hSmAkExcod— Yuk. (@Yuk3u) 2024年3月20日 プラクティス 実機を触る練習をしました。一応しっかり書き…

お近づきになりたい人向けシリーズです。 いろいろなトピックを詰め込みましたが、「これら全部を知らないといけない」のようなつもりではなく、いろいろなことを知るきっかけになったらいいなという気持ちなので、あまり身構えずにちょっとずつ読んでもらえたらうれしい気がします。 まえがき 予備知識 規格 用語 精度という語について 記法 表現について 有限値の表現について エンコードについて 丸めについて よくある誤差や勘違いの例 0.1 = 1 / 10? 0.1 + 0.2 = 0.3? 整数の誤差 Rump’s Example 基本的な誤差評価 用語に関して 実数の丸め 有理数の丸め 基本演算の丸め …

記事としてはけっこう前のお話だけど、MEOについての知識や情報を集積している者にとっては、非常に気になる話題が上っていました。 Googleマップに生成AI利用で場所を探す機能が新登場 - GIGAZINE 対するにYahoo地図は、シェアとしてGoogleMapsの不透明性が取り出たされたころには、シェアを結構伸ばしたように思うのですが、如何せん圧倒的にシェアの差があるにも関わらず、機能性や取り回し・扱いやすさではむしろ水を空けられている。 こちらアメリカでは2024年2月初旬開始とあるので、もうすぐのお話なのですが、基本的には「情報を総括」してくれる機能であるらしい。どちらかと言うと、ゆっ…

みなさんこんにちは！ 自然科学研究科 M2 の S.K です． この記事に興味を持ってくださりありがとうございます！ 前回の記事では，数学における ”原理” について考えました． 今回の記事でも，抽象的な数学の世界を具体例と結びつけながら紹介していきたいと思います． 早速ですがみなさんは「巡回セールスマン問題」という言葉を聞いたことはないでしょうか？ あるセールスマンが，いくつかの都市を訪れて戻ってくる出張をしようとしています．各都市間の距離はわかっているとします．各都市に一回ずつ寄るとすると，この出張旅行の総移動距離を最小にするにはどのような順で都市をまわればよいでしょうか？ いくつかの都市…

Rustで競プロするのに慣れたりライブラリを整備したりするのも兼ねて、ABC338を解き直します。 コンテスト時はA～Eの5完でした。 温まったとはいえ、Fが解けなかったのがめちゃくちゃ悔しいです。自作ライブラリを使用し、ローカルで事前に明らかに未使用な部分を除いて展開する形で提出しています。展開前のソースコードを記述します。 AtCoderで使えるクレートに含まれない関数などを使っている可能性があること、破壊的変更をこの記事の投稿後にしている可能性があることにご注意ください。 github.com A問題 atcoder.jp is_uppercase()関数やis_lowercase()関…

■A - Capitalized? やる ■B - Frequency やる ■C - Leftover Recipes 料理Aを作れる個数を全探索する ■D - Island Tour どの橋を壊すと最短と比べてどれだけコストが掛かるかを考える imosでいいが面倒なので遅延セグ木で ■E - Chords 典型90のNo17を引っ張ってくる ■F - Negative Traveling Salesman ワーシャルフロイドを行い、頂点距離をすべて調べておき 巡回セールスマン問題 ■G - evall a + b * cを考える

蒼 天 復 興 Fateと蒐集品やってみたけど一生虚無。 なんで実装したん？ ついでに言うと戦闘システムも微妙に感じ始めた。 頑張ってスキル回ししてもマクロ流してるのと大して変わらん。 強い技を高火力で出せたら特殊な効果音が鳴るとか、 短時間に複数の敵を倒すとchainのエフェクトが出るとか、 そう言うのが何もない。 コムニオは唯一出せたら気持ちいいと思ったけど。 探検手帳とか風脈集めとかも たまにそこから眺める景色が綺麗だと思うことはあるけど 高台に登ったら風の音が強くなったり 川の上流に行くとせせらぎの音が聞こえるなんてことはなく ただ巡回セールスマン問題を解いているだけ。 少ない食事を用…

https://www.amazon.co.jp/dp/4794220588 とりとめのない読書メモ。 1. 思考の基本部品 2. 部品としての論理回路 3. プログラミング 4. チューリングの万能機械 5. アルゴリズムと発見的手法（ヒューリスティック） 6. メモリ 8. 学習できるコンピュータ 9. 工学的アプローチの次にくるもの 最後に感想

ホロライブ×観光周遊企画「ほろ〜かる」第1弾 京都編。ホロライブ好きだし、まあ旅行もほどほどに好きなので1泊2日で行ってきた。 普通の旅行は「さあどこから回ろう」となるところだが、「ほろ〜かる」の場合行くところは決まってる。決める必要があるのはどういうルートで回るかだけ、つまり巡回セールスマン問題だ。 回る箇所が多かったからChatGPTに聞いてみたりもしたけど 京都旅行の予定を考えてください。 行くところは下記です。 1. 京都高島屋 2. 伏見稲荷エリア 3. 京都駅 4. 下鴨神社 5. 京都市京セラ美術館 6. 京都国際マンガミュージアム 7. 壬生寺 8. 車折神社 2日で回ります。…