論文の概要: Enhanced Methods for the Weight Constrained Shortest Path Problem
- arxiv url: http://arxiv.org/abs/2207.14744v2
- Date: Fri, 30 Jun 2023 04:25:12 GMT
- ステータス: 処理完了
- システム内更新日: 2023-07-03 16:02:58.067333
- Title: Enhanced Methods for the Weight Constrained Shortest Path Problem
- Title（参考訳）: 重み制約付き最短経路問題に対する拡張法
- Authors: Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby, Mahdi Jalili
- Abstract要約: WCSPP(Weight Constrained Shortest Path Problem)は、AIにおいてよく研究されているが、難しいトピックである。
本稿では, A* 探索に基づく WCSPP に対する2つの新しい解法を提案する。
我々は,大規模で現実的な問題事例の集合に対して,アルゴリズムの性能を実証的に評価した。
- 参考スコア（独自算出の注目度）: 18.567812400186092
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The classic problem of constrained pathfinding is a well-studied, yet
challenging, topic in AI with a broad range of applications in various areas
such as communication and transportation. The Weight Constrained Shortest Path
Problem (WCSPP), the base form of constrained pathfinding with only one side
constraint, aims to plan a cost-optimum path with limited weight/resource
usage. Given the bi-criteria nature of the problem (i.e., dealing with the cost
and weight of paths), methods addressing the WCSPP have some common properties
with bi-objective search. This paper leverages the recent state-of-the-art
techniques in both constrained pathfinding and bi-objective search and presents
two new solution approaches to the WCSPP on the basis of A* search, both
capable of solving hard WCSPP instances on very large graphs. We empirically
evaluate the performance of our algorithms on a set of large and realistic
problem instances and show their advantages over the state-of-the-art
algorithms in both time and space metrics. This paper also investigates the
importance of priority queues in constrained search with A*. We show with
extensive experiments on both realistic and randomised graphs how bucket-based
queues without tie-breaking can effectively improve the algorithmic performance
of exhaustive A*-based bi-criteria searches.
- Abstract（参考訳）: 制約付きパスフィンディングの古典的な問題は、コミュニケーションや輸送などさまざまな分野の幅広い応用を持つAIにおいて、十分に研究されているが難しいトピックである。
WCSPP (Weight Constrained Shortest Path Problem) は、制約付きパスフィニングの基本的な形式であり、一方の制約のみで、重量/資源使用量に制限のあるコスト最適化パスを計画することを目的としている。
この問題の双基準性(すなわちパスのコストと重みを扱う)を考えると、WCSPPに対処する手法は双対象探索に共通する性質を持つ。
本稿では,制約付きパスフィンディングと双対象探索の両方において最近の最先端技術を活用し,A*探索に基づくWCSPPに対する2つの新しい解法を提案する。
我々は,大規模で現実的な問題インスタンス上でのアルゴリズムの性能を実証的に評価し,時間と空間の両方で最先端のアルゴリズムに対して優位性を示す。
本稿では,A*を用いた制約探索における優先度待ち行列の重要性についても検討する。
本稿では,実数グラフとランダム化グラフの両方について,結束のないバケット型キューが,a*型bi-criteria探索のアルゴリズム性能を効果的に改善できることを示す。
関連論文リスト
- Training Greedy Policy for Proposal Batch Selection in Expensive Multi-Objective Combinatorial Optimization [52.80408805368928]
本稿では,バッチ取得のための新しいグリーディ型サブセット選択アルゴリズムを提案する。
赤蛍光タンパク質に関する実験により,提案手法は1.69倍少ないクエリでベースライン性能を達成できることが判明した。
論文 参考訳（メタデータ） (2024-06-21T05:57:08Z) - Optimizing Tensor Contraction Paths: A Greedy Algorithm Approach With Improved Cost Functions [1.3812010983144802]
より少ない時間で効率的な収縮経路を計算できる opt_einsum による欲求アルゴリズムに基づく新しい手法を提案する。
我々のアプローチでは、現代のアルゴリズムが失敗する大きな問題に対するパスを計算できる。
論文 参考訳（メタデータ） (2024-05-08T09:25:39Z) - BalMCTS: Balancing Objective Function and Search Nodes in MCTS for
Constraint Optimization Problems [7.196057722218442]
制約問題最適化(COP)は、通常ブランチ・アンド・バウンド(B&B)法によって解決される問題において、複雑な課題を提起する。
COPを解くための深度優先探索アルゴリズムに基づく新しいニューラルネットワークアルゴリズムを提案する。
提案手法は,最初の5つの実現可能な解のうち17.63%未満のギャップを有する実現可能な解を同定する。
論文 参考訳（メタデータ） (2023-12-26T03:09:08Z) - Optimizing Solution-Samplers for Combinatorial Problems: The Landscape
of Policy-Gradient Methods [52.0617030129699]
本稿では,DeepMatching NetworksとReinforcement Learningメソッドの有効性を解析するための新しい理論フレームワークを提案する。
我々の主な貢献は、Max- and Min-Cut、Max-$k$-Bipartite-Bi、Maximum-Weight-Bipartite-Bi、Traveing Salesman Problemを含む幅広い問題である。
本分析の副産物として,バニラ降下による新たな正則化プロセスを導入し,失効する段階的な問題に対処し,悪い静止点から逃れる上で有効であることを示す理論的および実験的証拠を提供する。
論文 参考訳（メタデータ） (2023-10-08T23:39:38Z) - Tightest Admissible Shortest Path [4.928034044959278]
グラフにおける最短経路問題はAIの基本である。
本稿では,最適コストに縛られた最短経路である許容最短経路(TASP)の探索問題を紹介する。
我々は、ソリューションの品質を保証し、TASPを解くための完全なアルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-08-15T14:39:05Z) - A Metaheuristic Algorithm for Large Maximum Weight Independent Set
Problems [58.348679046591265]
ノード重み付きグラフが与えられたとき、ノード重みが最大となる独立した(相互に非隣接な)ノードの集合を見つける。
このアプリケーションで放送されるグラフの中には、数十万のノードと数億のエッジを持つ大きなものもあります。
我々は,不規則なランダム化適応検索フレームワークにおいてメタヒューリスティックな新しい局所探索アルゴリズムを開発した。
論文 参考訳（メタデータ） (2022-03-28T21:34:16Z) - Learning to Detect Critical Nodes in Sparse Graphs via Feature Importance Awareness [53.351863569314794]
クリティカルノード問題(CNP)は、削除が残余ネットワークのペア接続性を最大に低下させるネットワークから臨界ノードの集合を見つけることを目的としている。
本研究は,ノード表現のための特徴重要度対応グラフアテンションネットワークを提案する。
ダブルディープQネットワークと組み合わせて、初めてCNPを解くエンドツーエンドのアルゴリズムを作成する。
論文 参考訳（メタデータ） (2021-12-03T14:23:05Z) - Revisiting the Complexity Analysis of Conflict-Based Search: New
Computational Techniques and Improved Bounds [5.158632635415881]
最適解に対する最先端のアプローチは Conflict-Based Search (CBS) である
CBSの複雑性分析を再検討し、最悪の場合のアルゴリズムの実行時間に厳密な制限を与える。
論文 参考訳（メタデータ） (2021-04-18T07:46:28Z) - Towards Time-Optimal Any-Angle Path Planning With Dynamic Obstacles [1.370633147306388]
パス探索は、しばしばグラフ検索としてフレーム化されるAIのよく研究された問題です。
同じアイデアを基礎とした2つのアルゴリズムを提示し,検討した問題の最適解を求める。
論文 参考訳（メタデータ） (2021-04-14T07:59:53Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳（メタデータ） (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。