論文の概要: A First Guess is Rarely the Final Answer: Learning to Search in the Travelling Salesperson Problem

• arxiv url: http://arxiv.org/abs/2604.06940v1
• Date: Wed, 08 Apr 2026 11:04:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-04-09 17:30:51.485256
• Title: A First Guess is Rarely the Final Answer: Learning to Search in the Travelling Salesperson Problem
• Title（参考訳）: 旅のセールスパーソン問題における検索の学習
• Authors: Andoni Irazusta Garmendia,
• Abstract要約: トラベリングセールスパーソン問題(TSP)のほとんどのニューラルソルバは、1つのソリューションを出力するように訓練されています。 多くのアプローチでは、局所探索のメカニズムを中心に構築されるのではなく、状態表現、アーキテクチャの選択、単一解法から受け継いだレシピを再利用しています。 NICOTSPは、ちょうど$n$のエッジトークンを近所のオペレータと一致させ、2-optはツアー位置エンコーディングなしで直接動き、2-optは2-optで列車を走らせる。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Most neural solvers for the Traveling Salesperson Problem (TSP) are trained to output a single solution, even though practitioners rarely stop there: at test time, they routinely spend extra compute on sampling or post-hoc search. This raises a natural question: can the search procedure itself be learned? Neural improvement methods take this perspective by learning a policy that applies local modifications to a candidate solution, accumulating gains over an improvement trajectory. Yet learned improvement for TSP remains comparatively immature, with existing methods still falling short of robust, scalable performance. We argue that a key reason is design mismatch: many approaches reuse state representations, architectural choices, and training recipes inherited from single-solution methods, rather than being built around the mechanics of local search. This mismatch motivates NICO-TSP (Neural Improvement for Combinatorial Optimization): a 2-opt improvement framework for TSP. NICO-TSP represents the current tour with exactly $n$ edge tokens aligned with the neighborhood operator, scores 2-opt moves directly without tour positional encodings, and trains via a two-stage procedure: imitation learning to short-horizon optimal trajectories, followed by critic-free group-based reinforcement learning over longer rollouts. Under compute-matched evaluations that measure improvement as a function of both search steps and wall-clock time, NICO-TSP delivers consistently stronger and markedly more step-efficient improvement than prior learned and heuristic search baselines, generalizes far more reliably to larger out-of-distribution instances, and serves both as a competitive replacement for classical local search and as a powerful test-time refinement module for constructive solvers.
• Abstract（参考訳）: トラベリングセールスパーソン問題(TSP)のほとんどのニューラルソルバは、1つのソリューションを出力するように訓練されている。 検索手順自体が学べるのか? ニューラル改善法は、局所的な修正を候補解に適用するポリシーを学習し、改善軌道上のゲインを蓄積することで、この視点を捉えている。 しかし、TSPの学習された改善は、まだ比較的未成熟であり、既存のメソッドはまだ堅牢でスケーラブルなパフォーマンスに欠けています。 多くのアプローチでは、局所探索のメカニズムを中心に構築されるのではなく、状態表現、アーキテクチャの選択、単一解法から受け継いだレシピを再利用しています。 このミスマッチはNICO-TSP(Neural Improvement for Combinatorial Optimization)を動機付けている。 NICO-TSPは、ちょうど$n$のエッジトークンを近所のオペレーターと一致させ、スコア2-optはツアーの位置エンコーディングなしで直接移動し、2段階の手順で列車を走らせる。 NICO-TSPは、探索ステップと壁面時間の両方の関数として改善を計測する計算マッチング評価の下で、学習済みおよびヒューリスティックな探索ベースラインよりも一貫して強力なステップ効率の向上を実現し、より大きなアウト・オブ・ディストリビューション・インスタンスにはるかに確実に一般化し、古典的な局所探索の競合的な代替として機能し、構成的ソルバのための強力なテスト時間改善モジュールとして機能する。

関連論文リスト

• Neural Chain-of-Thought Search: Searching the Optimal Reasoning Path to Enhance Large Language Models [61.55758048622473]
  最適思考戦略の動的探索として推論を再構成するフレームワークであるNeural Chain-of-Thought Search (NCoTS)を導入する。 解空間を定量的に特徴づけることで、標準出力よりも正確かつ簡潔なスパース優良推論経路の存在を明らかにする。
  論文  参考訳（メタデータ） (2026-01-16T14:38:18Z)
• PROPA: Toward Process-level Optimization in Visual Reasoning via Reinforcement Learning [30.44007644340425]
  本稿では,モンテカルロ木探索 (MCTS) とGRPOを統合した新しいフレームワーク PROPA について紹介する。 7つのベンチマークと4つのVLMバックボーンで、PROPAはSFTとRLVRベースのベースラインを一貫して上回っている。 ドメイン内タスクで最大17.0%、ドメイン外タスクで最大21.0%のゲインを達成する。
  論文  参考訳（メタデータ） (2025-11-13T13:06:12Z)
• Is Optimal Transport Necessary for Inverse Reinforcement Learning? [0.0]
  逆強化学習(IRL)は、専門家によるデモンストレーションから報酬関数を回復することを目的としている。 IRLにおける最適輸送(OT)の2つの簡単な代替案を提案する。 我々の単純な報酬は、最近のOTベースのアプローチと一致しているか、上回っていることを示す。
  論文  参考訳（メタデータ） (2025-06-07T13:29:37Z)
• To Backtrack or Not to Backtrack: When Sequential Search Limits Model Reasoning [37.179289850042764]
  バックトラックは、長いチェーン・オブ・シント(CoT)生成による逐次線形化探索を可能にすることによって、テスト時間計算を自然にスケールする。 本稿では,これらの2つの手法を,CountDown と Sudoku の2つの難解な推論タスクに対して体系的に比較する。 意外なことに、シーケンシャルな検索はCountDown上で並列サンプリングを過小評価するが、Sudoku上では性能が優れており、バックトラッキングは普遍的に有益ではないことを示唆している。
  論文  参考訳（メタデータ） (2025-04-09T17:12:49Z)
• Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization [83.65278205301576]
  雑音レベルから与えられたインスタンスの最適解への直接写像を学習し、最小限のショットで高品質な生成を容易にすることを提案する。 これは、サンプル間の差を最小限に抑える最適化一貫性トレーニングプロトコルによって達成される。 The Traveling Salesman Problem (TSP) と Maximal Independent Set (MIS) は、ソリューションの品質と効率の両方に関して、Fast T2Tの優位性を実証している。
  論文  参考訳（メタデータ） (2025-02-05T07:13:43Z)
• Efficient Methods for Non-stationary Online Learning [63.268670895111654]
  動的後悔と適応的後悔を最適化する効率的な方法を提案する。 提案アルゴリズムでは,各ラウンドで1つの勾配クエリと1つの関数評価しか必要としない。 また、さらに強力な測度、すなわち「内部的動的後悔」を研究し、ラウンド当たりの射影数を$O(log2 T)$から$$$$に減らした。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• Learning to Optimize for Reinforcement Learning [58.01132862590378]
  強化学習(Reinforcement Learning, RL)は、教師付き学習とは本質的に異なり、実際、これらの学習は単純なRLタスクでもうまく機能しない。 エージェント勾配分布は非独立で同一分布であり、非効率なメタトレーニングをもたらす。 おもちゃのタスクでしか訓練されていないが、我々の学習はブラックスの目に見えない複雑なタスクを一般化できることを示した。
  論文  参考訳（メタデータ） (2023-02-03T00:11:02Z)
• Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learning [2.4565068569913384]
  本研究では,2オプト演算子に基づく局所的な探索勾配を深層強化学習により学習することを提案する。 学習したポリシは、ランダムな初期解よりも改善でき、従来の最先端のディープラーニング手法よりも高速に、ほぼ最適解にアプローチできることを示す。
  論文  参考訳（メタデータ） (2020-04-03T14:51:54Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。