巡回セールスマン問題(TSP)の面白いと思った応用３例(色・単語・音楽) - Qiita

巡回セールスマン問題 巡回セールスマン問題(以下TSP)についてご存知でしょうか。 完全グラフと全ての辺の移動コストが与えられた上で、全ての点を１回ずつ通り、始点に戻る巡回路の中で総移動コストが最小となる巡回路を求める組合せ最適化の問題です。 今回の記事の趣旨とは異なるため、ソルバーの詳細及びTSPを解くアルゴリズムの紹介は他の文献に譲ります。(個人的には辺の移動コストが定数でないTSP (dynamic TSP)にも興味があるので追ってまとめたいと思います。実応用としては、渋滞が発生して移動時間が変わる等の状況を考慮することに相当します。) TSPの応用としてはその名についているように人が全ての与えられた場所の集合を回る、郵便物などの配送*やテーマパークで回る順番を考える問題が多いかと思いますが、それらの実空間で何かの対象物が移動する以外の面白いなと思った応用例について３つ紹介して行きた

[sh19910711]

2022 / "色集合から"自然な"カラーパレットの作成 (SIGGRAPH'21) / Word Tour (NAACL 2022): Wordをなんと1次元ユークリッド空間に埋め込んでしまおうという研究 + 完全性を諦めて健全性を満たすように埋め込み"

[junglejungle]

線で応用できないのかな。すべての路線を最短ルートで通る計算がしたい。

[alyya]

TSPは応用がイメージされやすいから良く記事にされるけど、上位版のQAP（二次割当問題）も是非お願い

[grocio]

巡回セールスマン問題って聞くと移動とか輸送の話を連想しがちだけど、類似度に基づくソートやクラスタリングのようなこともできるのか！

[opnihc]

プレイリストも巡回セールスマン問題になるんだ。類似性の高いやつだけ次々に拾っていけばできそうなんだけど

[programmablekinoko]

個人的には、“個人の資質や能力や空きに応じてルーティン作業を割り振る”と言うやつが面倒くさくて、結局エクセルでペタペタしてる