Fugu-MT 論文翻訳(概要): On AO*, Proof Number Search and Minimax Search

論文の概要: On AO*, Proof Number Search and Minimax Search

arxiv url: http://arxiv.org/abs/2103.16692v1
Date: Tue, 30 Mar 2021 21:27:40 GMT
ステータス: 翻訳完了
システム内更新日: 2021-04-01 14:38:37.656416
Title: On AO*, Proof Number Search and Minimax Search
Title（参考訳）: AO*, Proof Number Search と Minimax Search について
Authors: Chao Gao
Abstract要約: AO*、敵対的ゲーム探索アルゴリズム、例えば証明数探索とミニマックス探索の相互接続について議論する。一般化された証明数探索は任意のAND/ORグラフを解くためのAO*のより情報的な代替と見なすことができる。
参考スコア（独自算出の注目度）: 19.376328966299322
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We discuss the interconnections between AO*, adversarial game-searching algorithms, e.g., proof number search and minimax search. The former was developed in the context of a general AND/OR graph model, while the latter were mostly presented in game-trees which are sometimes modeled using AND/OR trees. It is thus worth investigating to what extent these algorithms are related and how they are connected. In this paper, we explicate the interconnections between these search paradigms. We argue that generalized proof number search might be regarded as a more informed replacement of AO* for solving arbitrary AND/OR graphs, and the minimax principle might also extended to use dual heuristics.
Abstract（参考訳）: 本稿では,AO*,対戦型ゲーム探索アルゴリズム,例えば証明数探索とミニマックス探索の相互接続について論じる。前者は一般および/またはグラフモデルの文脈で開発され、後者は主にゲームツリーで示され、時には木を使ってモデル化される。したがって、これらのアルゴリズムがどの程度関連し、どのように接続されているかを調べる価値がある。本稿では,これらの探索パラダイム間の相互関係を解明する。一般化された証明数探索は任意のAND/ORグラフを解くためのAO*のより情報的な代替と見なすことができるし、ミニマックス原理も双対ヒューリスティックスを使うように拡張されるかもしれない。

関連論文リスト

Improved Anonymous Multi-Agent Path Finding Algorithm [3.694001372535405]
エージェントの集合をグラフに限定する匿名多エージェントパスフィンディング(AMAPF)問題を考える。我々は,検索空間を探索するアイデアを,個別の検索状態ではなく,一括して考えることによって活用する,特定の検索アルゴリズムを提案する。その結果、AMAPFソルバは最先端の競合に比べて優れた性能を示し、30秒未満で利用可能なすべてのMAPFインスタンスを解決できる。
論文参考訳（メタデータ） (2023-12-17T00:49:30Z)
A Theoretical Analysis Of Nearest Neighbor Search On Approximate Near Neighbor Graph [51.880164098926166]
グラフベースのアルゴリズムは、近隣探索(NN-Search)問題において最先端の性能を示す。グラフベースのNN-Searchアルゴリズムには実践と理論のギャップがある。低次元および高密度ベクトルに対する ANN-Graph 上の欲求探索による NN-Search の解法を理論的に保証する。
論文参考訳（メタデータ） (2023-03-10T21:18:34Z)
Subset verification and search algorithms for causal DAGs [13.108039226223793]
エッジのサブセット(ターゲットエッジ)間の因果関係を学習するために必要な最小の介入セットを特定する問題について検討する。介入因果グラフのいくつかの興味深い構造的特性を証明し、ここで研究されるサブセット検証・探索問題以外の応用があると信じている。
論文参考訳（メタデータ） (2023-01-09T06:25:44Z)
RetroGraph: Retrosynthetic Planning with Graph Search [101.92603715499112]
再合成計画(Retrosynthetic Planning)は、標的分子を合成する反応経路を見つけることを目的としている。本稿では,任意の中間分子の冗長な探索を排除したグラフベースの探索ポリシーを提案する。提案手法は,グラフ内のターゲットの集合を探索し,木構造に基づく探索手法におけるターゲット間重複を除去する。
論文参考訳（メタデータ） (2022-06-23T05:01:29Z)
Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。 4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
論文参考訳（メタデータ） (2022-05-31T10:38:04Z)
Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
論文参考訳（メタデータ） (2022-01-25T00:10:03Z)
Probabilistic DAG Search [29.47649645431227]
探索空間の潜伏構造を利用して探索木間で情報を共有するための確率的フレームワークを開発する。我々は、Tic-Tac-Toeの既存の非確率的代替品と特徴選択アプリケーションとを比較検討するアルゴリズムを実証的に見出した。
論文参考訳（メタデータ） (2021-06-16T11:35:19Z)
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)
MPLP++: Fast, Parallel Dual Block-Coordinate Ascent for Dense Graphical Models [96.1052289276254]
この研究は、人気のあるDual Block-Coordinate Ascent原則に基づく新しいMAP-solverを導入している。驚いたことに、性能の低い解法に小さな変更を加えることで、既存の解法を大きなマージンで大幅に上回る新しい解法MPLP++を導出します。
論文参考訳（メタデータ） (2020-04-16T16:20:53Z)
GLSearch: Maximum Common Subgraph Detection via Learning to Search [33.9052190473029]
検索モデルに対するグラフニューラルネットワーク(GNN)に基づく学習手法であるGLSearchを提案する。このモデルでは2つの入力グラフから1対のノードを選択して一度に拡張する。我々のGLSearchは、グラフ上の制約で他の多くの問題を解決するために拡張できる可能性がある。
論文参考訳（メタデータ） (2020-02-08T10:03:40Z)

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