論文の概要: Enhanced Methods for the Weight Constrained Shortest Path Problem:
Constrained Path Finding Meets Bi-objective Search
- arxiv url: http://arxiv.org/abs/2207.14744v1
- Date: Fri, 29 Jul 2022 15:32:45 GMT
- ステータス: 処理完了
- システム内更新日: 2022-08-01 13:15:02.440156
- Title: Enhanced Methods for the Weight Constrained Shortest Path Problem:
Constrained Path Finding Meets Bi-objective Search
- Title（参考訳）: 重み制約された最短経路問題に対する拡張手法:双目的探索による制約付き経路探索
- Authors: Saman Ahmadi, Guido Tack, Daniel Harabor, Philip Kilby
- Abstract要約: WCSPP (Weight Constrained Shortest Path Problem) は、重量/資源使用量に制限のあるコスト最適経路を計画することを目的としている。
この問題の双基準性(すなわちパスのコストと重みを扱う)を考えると、WCSPPに対処する手法は、双対象探索に共通する性質を持つ。
本稿では,WCSPPに対する2つの厳密な解法を提案する。
- 参考スコア（独自算出の注目度）: 10.654876600946867
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The classic problem of \textit{constrained path finding} is a well-studied
but yet challenging topic in AI with a broad range of applications in various
areas such communication and transportation. The Weight Constrained Shortest
Path Problem (WCSPP), as the base form of constrained path finding with only
one side constraint, aims to plan a cost optimum path whose weight/resource
usage is limited. Given the bi-criteria nature of the problem (i.e., dealing
with 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 A*-based techniques in both constrained path finding and
bi-objective search and presents two exact solution approaches to the WCSPP,
both capable of solving hard problem instances on very large graphs. We
empirically evaluate the performance of our algorithms on a new 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 bi-criteria searches.
- Abstract（参考訳）: textit{constrained path find}の古典的な問題は、コミュニケーションや輸送などさまざまな分野で幅広い応用があるAIにおいて、よく研究されているが難しいトピックである。
WCSPP(Weight Constrained Shortest Path Problem)は、一方の制約しか持たない制約経路の基本的な形として、重量/資源使用量に制限のあるコスト最適経路を計画することを目的としている。
この問題の双基準性(すなわちパスのコストと重みを扱う)を考えると、WCSPPに対処する手法は双対象探索と共通する性質を持つ。
本稿では,制約された経路探索と二目的探索の両面において,最近の最先端の A* に基づく手法を活用し,WCSPP に対する2つの厳密な解法を提案する。
我々は、新しい大規模かつ現実的な問題インスタンス群におけるアルゴリズムの性能を実証的に評価し、時間と空間のメトリクスの両方において最先端のアルゴリズムよりもその利点を示す。
本稿では,A*を用いた制約探索における優先度待ち行列の重要性についても検討する。
本稿では,実数グラフとランダム化グラフの両方について,結束のないバケットベースの待ち行列が,徹底的な二行探索のアルゴリズム性能を効果的に改善できることを示す。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。