Fugu-MT 論文翻訳(概要): Monte Carlo Graph Coloring

論文の概要: Monte Carlo Graph Coloring

arxiv url: http://arxiv.org/abs/2504.03277v1
Date: Fri, 04 Apr 2025 08:57:01 GMT
ステータス: 翻訳完了
システム内更新日: 2025-04-07 14:46:22.355108
Title: Monte Carlo Graph Coloring
Title（参考訳）: モンテカルログラフカラー化
Authors: Tristan Cazenave, Benjamin Negrevergne, Florian Sikora,
Abstract要約: グラフ色付けはおそらく、グラフアルゴリズムにおいて最も研究され有名な問題の1つである。グラフカラー化にモンテカルロ探索を効果的に適用する方法を示す。
参考スコア（独自算出の注目度）: 3.435169201271934
License:
Abstract: Graph Coloring is probably one of the most studied and famous problem in graph algorithms. Exact methods fail to solve instances with more than few hundred vertices, therefore, a large number of heuristics have been proposed. Nested Monte Carlo Search (NMCS) and Nested Rollout Policy Adaptation (NRPA) are Monte Carlo search algorithms for single player games. Surprisingly, few work has been dedicated to evaluating Monte Carlo search algorithms to combinatorial graph problems. In this paper we expose how to efficiently apply Monte Carlo search to Graph Coloring and compare this approach to existing ones.
Abstract（参考訳）: グラフ色付けはおそらく、グラフアルゴリズムにおいて最も研究され有名な問題の1つである。厳密な方法は数百以上の頂点を持つインスタンスを解くことができないため、多くのヒューリスティックが提案されている。 Nested Monte Carlo Search (NMCS) とNested Rollout Policy Adaptation (NRPA) は、モンテカルロ検索アルゴリズムである。驚くべきことに、モンテカルロ探索アルゴリズムを組合せグラフ問題に適用する研究はほとんど行われていない。本稿では,モンテカルロ探索をグラフカラー化に効果的に適用する方法を明らかにし,この手法を既存手法と比較する。

関連論文リスト

Monte Carlo Search Algorithms Discovering Monte Carlo Tree Search Exploration Terms [4.561007128508218]
最適化されたモンテカルロ木探索アルゴリズムはPUCTとSHUSSである。 32評価の小さな探索予算に対して、発見されたルート探索条件は両方のアルゴリズムを競合させる。
論文参考訳（メタデータ） (2024-04-14T17:06:20Z)
Graph Sparsifications using Neural Network Assisted Monte Carlo Tree Search [9.128418945452088]
グラフニューラルネットワークとモンテカルロ木探索を組み合わせたグラフスペーサーの計算手法について述べる。まず、部分解として入力されるグラフニューラルネットワークをトレーニングし、出力として追加される新しいノードを提案する。このニューラルネットワークはモンテカルロ探索に使われ、スペーサーを計算する。
論文参考訳（メタデータ） (2023-11-17T03:59:50Z)
Monte-Carlo Tree Search for Multi-Agent Pathfinding: Preliminary Results [60.4817465598352]
マルチエージェントパスフィンディングに適したモンテカルロ木探索(MCTS)のオリジナル版を紹介する。具体的には,エージェントの目標達成行動を支援するために,個別の経路を用いる。また,木探索手順の分岐係数を低減するために,専用の分解手法を用いる。
論文参考訳（メタデータ） (2023-07-25T12:33:53Z)
Quantitative approach to Grover's quantum walk on graphs [62.997667081978825]
グラフ上の連続時間量子ウォークに着目したGroverの探索アルゴリズムについて検討する。関連する量子ウォークに便利なグラフトポロジーを見つける代わりに、グラフトポロジーを修正し、ラプラシアンを基礎とするグラフを変化させる。
論文参考訳（メタデータ） (2022-07-04T19:33:06Z)
Refutation of Spectral Graph Theory Conjectures with Monte Carlo Search [4.38602607138044]
我々はモンテカルロ探索(MCS)アルゴリズムを用いてグラフを構築し、スペクトルグラフ理論の予想に対する反例を見つける方法について実証する。ピーター・ショア(Peter Shor)が残した予想に反論する。
論文参考訳（メタデータ） (2022-07-04T07:06:48Z)
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)
A Grover search-based algorithm for the list coloring problem [1.332560004325655]
本稿では,Grover 探索に基づく量子アルゴリズムを提案する。我々のアルゴリズムは、制限された特定のケースでは古典的な場合に比べて複雑性が低いが、自然に考慮されたリストやグラフが任意である場合の徹底的な探索を改善する。
論文参考訳（メタデータ） (2021-08-20T08:41:22Z)
Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。そこで本研究では,学習可能なグラフマッチング手法を提案する。
論文参考訳（メタデータ） (2021-03-30T08:58:45Z)
Monte-Carlo Graph Search for AlphaZero [15.567057178736402]
探索木を有向非巡回グラフに一般化する,新しい改良されたalphazero探索アルゴリズムを提案する。評価では、チェスとクレイジーハウスでCrazyAraエンジンを使用して、これらの変更がAlphaZeroに大きな改善をもたらすことを示す。
論文参考訳（メタデータ） (2020-12-20T22:51:38Z)
Generalize a Small Pre-trained Model to Arbitrarily Large TSP Instances [55.64521598173897]
本稿では,旅行セールスマン問題(TSP)のヒートマップ構築に繰り返し使用可能な,小規模モデルのトレーニングを試みる。ヒートマップは強化学習アプローチ(モンテカルロツリーサーチ)に供給され、高品質のソリューションの検索を案内します。実験結果によると、この新しいアプローチは、既存の機械学習ベースのTSPアルゴリズムを明らかに上回る。
論文参考訳（メタデータ） (2020-12-19T11:06:30Z)
Online Dense Subgraph Discovery via Blurred-Graph Feedback [87.9850024070244]
我々は高密度サブグラフ発見のための新しい学習問題を導入する。まず,確率の高いほぼ最適解を求めるエッジ時間アルゴリズムを提案する。そして、理論的保証のあるよりスケーラブルなアルゴリズムを設計する。
論文参考訳（メタデータ） (2020-06-24T11:37:33Z)

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