論文の概要: A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph
- arxiv url: http://arxiv.org/abs/2403.07886v1
- Date: Thu, 1 Feb 2024 22:02:07 GMT
- ステータス: 処理完了
- システム内更新日: 2024-03-25 08:27:08.978453
- Title: A Memetic Algorithm To Find a Hamiltonian Cycle in a Hamiltonian Graph
- Title（参考訳）: ハミルトニアングラフにおけるハミルトニアンサイクル探索アルゴリズム
- Authors: Sarwan Ali, Pablo Moscato,
- Abstract要約: ハミルトングラフにおいてハミルトニアンサイクルを求めるためのメメティックアルゴリズム(maa)を提案する。
提案手法では,ハミルトン性を考慮した入力グラフの分散化手法も導入している。
このアプローチはメタヒューリスティック(メタヒューリスティック)であり、すなわち、ハミルトニアンサイクルを見つけるための理論的保証を与えていないが、この手法が実際に成功していることを我々は見てきた。
- 参考スコア（独自算出の注目度）: 3.231572093516736
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: We present a memetic algorithm (\maa) approach for finding a Hamiltonian cycle in a Hamiltonian graph. The \ma is based on a proven approach to the Asymmetric Travelling Salesman Problem (\atspp) that, in this contribution, is boosted by the introduction of more powerful local searches. Our approach also introduces a novel technique that sparsifies the input graph under consideration for Hamiltonicity and dynamically augments it during the search. Such a combined heuristic approach helps to prove Hamiltonicity by finding a Hamiltonian cycle in less time. In addition, we also employ a recently introduced polynomial-time reduction from the \hamcyc to the Symmetric \tsp, which is based on computing the transitive closure of the graph. Although our approach is a metaheuristic, i.e., it does not give a theoretical guarantee for finding a Hamiltonian cycle, we have observed that the method is successful in practice in verifying the Hamiltonicity of a larger number of instances from the \textit{Flinder University Hamiltonian Cycle Problem Challenge Set} (\fhcpsc), even for the graphs that have large treewidth. The experiments on the \fhcpscc instances and a computational comparison with five recent state-of-the-art baseline approaches show that the proposed method outperforms those for the majority of the instances in the \fhcpsc.
- Abstract（参考訳）: ハミルトングラフのハミルトニアンサイクルを求めるためのメメティックアルゴリズム (\maa) を提案する。
\maは、非対称トラベリングセールスマン問題(\atspp)に対する証明済みのアプローチに基づいている。
提案手法では,ハミルトン性を考慮した入力グラフの分散化や,探索中に動的に拡張する手法も導入している。
このような結合ヒューリスティックなアプローチは、より少ない時間でハミルトンサイクルを見つけることによってハミルトン性を証明するのに役立つ。
さらに,最近導入された多項式時間短縮法を,グラフの推移的閉包を計算したSymmetric \tspに導入した。
我々のアプローチはメタヒューリスティック(メタヒューリスティック)であり、すなわち、ハミルトニアンサイクルを見つけるための理論的保証を与えていないが、大きな木幅を持つグラフでさえも、その方法が、より多くのインスタンスのハミルトニシティーを検証することに成功していることを我々は見てきた。
近年の5つの最先端ベースライン手法との比較実験により,提案手法は,fhcpscのほとんどのインスタンスにおいて,より優れた性能を示すことが示された。
関連論文リスト
- New random compiler for Hamiltonians via Markov Chains [0.08192907805418585]
アディアバティックアルゴリズムのような多くの量子アルゴリズムは、ハミルトン進化をシミュレートする必要がある。
我々は,第1次ランダム化トロッターに似た新しいコンパイラを開発したが,そのフレームワークは間違いなくシンプルである。
大規模なランダム化スキームと時間依存重みをサポートするため、より多用途である。
論文 参考訳（メタデータ） (2024-11-10T14:57:25Z) - Automorphism-Assisted Quantum Approximate Optimization Algorithm for efficient graph optimization [0.0]
我々は、グラフ自己同型を識別するために、Nautyパッケージを使用し、エッジ同値クラスを決定することに重点を置いている。
これらの対称性を利用することで、ハミルトニアンの複雑性を著しく低減することができる。
この結果から, 自己同型に基づく対称性を用いて, 得られた解の質を損なうことなく, 計算オーバーヘッドを著しく低減できることが示唆された。
論文 参考訳（メタデータ） (2024-10-29T17:10:25Z) - Hamiltonian Learning via Shadow Tomography of Pseudo-Choi States [0.6768558752130311]
我々は、疑似チョイ状態と呼ばれるリソースを通じてハミルトン語を学ぶための新しいアプローチを導入する。
M$ の項を持つハミルトニアンに対して、ハミルトニアン係数は誤差の中で古典的なシャドウトモグラフィーによって推定できることを示す。
また、我々の学習プロセスは、リソース状態のエラーやハミルトンクラスのエラーに対して堅牢であることを示す。
論文 参考訳（メタデータ） (2023-08-24T18:36:51Z) - On the Impossibility of General Parallel Fast-forwarding of Hamiltonian
Simulation [4.925967492198012]
ハミルトンシミュレーションは量子コンピューティングの分野で最も重要な問題の1つである。
既存のシミュレーションアルゴリズムでは、進化時間$T$で少なくとも線形に実行する必要がある。
高速ハミルトニアンシミュレーションが並列性の力で達成できるかどうかは興味深い。
論文 参考訳（メタデータ） (2023-05-21T12:30:00Z) - Improved Product-state Approximation Algorithms for Quantum Local
Hamiltonians [0.15229257192293202]
量子局所ハミルトニアンの基底状態エネルギーと自由エネルギーは、量子多体物理学の基本的な量である。
我々はQuantum $k$-Local Hamiltonians の族において、これらの量に対する古典的で付加的な積-状態近似を求める新しい手法を開発した。
論文 参考訳（メタデータ） (2022-10-17T00:55:35Z) - Some Remarks on the Regularized Hamiltonian for Three Bosons with
Contact Interactions [77.34726150561087]
3次元のゼロレンジ力を介して相互作用する3つのボソン系のモデルハミルトンの性質について論じる。
特に、適当な二次形式 $Q$ から始め、自己随伴およびハミルトンの$mathcal H$ の下から有界となるものを構築することができる。
しきい値 $gamma_c$ が最適であることは、次の2次形式 $Q$ が下から非有界であるという意味では、$gamma_c$ が最適であることを示している。
論文 参考訳（メタデータ） (2022-07-01T10:01:14Z) - Hamiltonian simulation with random inputs [74.82351543483588]
ランダム初期状態を持つハミルトンシミュレーションの平均ケース性能の理論
数値的な証拠は、この理論がコンクリート模型の平均誤差を正確に特徴づけていることを示唆している。
論文 参考訳（メタデータ） (2021-11-08T19:08:42Z) - Algebraic Compression of Quantum Circuits for Hamiltonian Evolution [52.77024349608834]
時間依存ハミルトニアンの下でのユニタリ進化は、量子ハードウェアにおけるシミュレーションの重要な構成要素である。
本稿では、トロッターステップを1ブロックの量子ゲートに圧縮するアルゴリズムを提案する。
この結果、ハミルトニアンのある種のクラスに対する固定深度時間進化がもたらされる。
論文 参考訳（メタデータ） (2021-08-06T19:38:01Z) - Stoquasticity in circuit QED [78.980148137396]
スケーラブルな符号-確率自由経路積分モンテカルロシミュレーションは一般にそのようなシステムに対して可能であることを示す。
我々は、実効的、非確率的クビットハミルトニアンが容量結合された束量子ビットの系に現れるという最近の発見を裏付ける。
論文 参考訳（メタデータ） (2020-11-02T16:41:28Z) - Stochastic Hamiltonian Gradient Methods for Smooth Games [51.47367707388402]
ハミルトンの手法のクラスに焦点をあて、滑らかなゲームのあるクラスに対する最初の収束保証を提供する。
最適化文献からのツールを用いて、SHGDは勾配の近傍に直線的に収束することを示す。
この結果から,一般ゲームのクラスに対して,非漸近的でない最後の収束保証を初めて提供する。
論文 参考訳（メタデータ） (2020-07-08T15:42:13Z) - Continuous-time quantum walks in the presence of a quadratic
perturbation [55.41644538483948]
連続時間量子ウォークの特性を、$mathcalH=L + lambda L2$という形のハミルトン群で解決する。
低/高接続性および/または対称性を持つパラダイムモデルであるため、サイクル、完全、およびスターグラフを考える。
論文 参考訳（メタデータ） (2020-05-13T14:53:36Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。