論文の概要: ERA*: Enhanced Relaxed A* algorithm for Solving the Shortest Path
Problem in Regular Grid Maps
- arxiv url: http://arxiv.org/abs/2308.10988v1
- Date: Tue, 15 Aug 2023 07:25:13 GMT
- ステータス: 処理完了
- システム内更新日: 2023-08-27 05:07:41.401434
- Title: ERA*: Enhanced Relaxed A* algorithm for Solving the Shortest Path
Problem in Regular Grid Maps
- Title（参考訳）: ERA*:正規格子図における最短経路問題の解法のための拡張緩和A*アルゴリズム
- Authors: Adel Ammar
- Abstract要約: 本稿では,静的な8つの隣り合う接続(G8)グリッドにおいて,ポイント・ツー・ポイントの最短経路問題の解法を提案する。
理論上は、与えられた解の経路長の点で、緩和された$A*$$(RA*$)アルゴリズムと等価であることが示されている。
RA*$より2.25倍、A*$より17倍速いことが証明されている。
- 参考スコア（独自算出の注目度）: 0.7977229957867868
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: This paper introduces a novel algorithm for solving the point-to-point
shortest path problem in a static regular 8-neighbor connectivity (G8) grid.
This algorithm can be seen as a generalization of Hadlock algorithm to G8
grids, and is shown to be theoretically equivalent to the relaxed $A^*$
($RA^*$) algorithm in terms of the provided solution's path length, but with
substantial time and memory savings, due to a completely different computation
strategy, based on defining a set of lookup matrices. Through an experimental
study on grid maps of various types and sizes (1290 runs on 43 maps), it is
proven to be 2.25 times faster than $RA^*$ and 17 times faster than the
original $A^*$, in average. Moreover, it is more memory-efficient, since it
does not need to store a G score matrix.
- Abstract（参考訳）: 本稿では,静的な8隣接接続(G8)グリッドにおいて,最短経路問題の解法を提案する。
このアルゴリズムは、g8グリッドへのハドロックアルゴリズムの一般化と見なすことができ、理論的には、与えられた解の経路長の点で、緩和された$a^*$ (ra^*$) アルゴリズムと同値であるが、ルックアップ行列の集合を定義することに基づく、全く異なる計算戦略のために、かなりの時間とメモリ節約がある。
様々な種類と大きさのグリッドマップ(43のマップで1290が動作する)に関する実験的研究により、平均すると、$ra^*$よりも2.25倍速く、元の$a^*$よりも17倍速いことが証明された。
さらに、Gスコア行列を格納する必要がないため、メモリ効率が向上する。
関連論文リスト
- A Scalable Algorithm for Individually Fair K-means Clustering [77.93955971520549]
Jung et al. と Mahabadi et al が導入した個別フェア (p$, $k$) クラスタリング問題に対するスケーラブルなアルゴリズムを提案する。
クラスタリングは、各$xin P$に対して$delta(x)$ of $x$の範囲内で中心となる場合、個別にフェアと呼ばれる。
我々は,従来よりもアルゴリズムがはるかに高速であるだけでなく,低コストのソリューションを生み出すことを実証的に示す。
論文 参考訳（メタデータ） (2024-02-09T19:01:48Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳（メタデータ） (2023-07-24T14:37:22Z) - Breaking 3-Factor Approximation for Correlation Clustering in
Polylogarithmic Rounds [0.23633885460047763]
相関クラスタリング問題に対する並列アルゴリズムについて検討する。
目標は、エンティティをクラスタに分割し、ラベルとの相違を最小限にすることである。
現在、全ての効率的な並列アルゴリズムは、近似比が少なくとも3である。
3 より優れた近似比を実現するための最初の多元対数アルゴリズムを提案する。
論文 参考訳（メタデータ） (2023-07-13T12:32:49Z) - Sketching the Best Approximate Quantum Compiling Problem [4.125187280299247]
最適化問題を古典的に解き、より多くの量子ビットに拡張するアルゴリズムツールを検討する。
これら3つのアルゴリズムに対して,行列行列演算の代わりに行列ベクトルを用いて勾配を効率的に計算する。
実装では、9量子ビット、27個のCNOT回路、12個のCNOT回路、24個のCNOT回路、15個のCNOT回路をコンパイルできる。
論文 参考訳（メタデータ） (2022-05-09T04:21:33Z) - Sketching Algorithms and Lower Bounds for Ridge Regression [65.0720777731368]
リッジ回帰問題に対する1+varepsilon$近似解を計算するスケッチベース反復アルゴリズムを提案する。
また,このアルゴリズムがカーネルリッジ回帰の高速化に有効であることを示す。
論文 参考訳（メタデータ） (2022-04-13T22:18:47Z) - Multilevel Memetic Hypergraph Partitioning with Greedy Recombination [0.0]
KaHyPar-Eはハイパーグラフ分割問題のために設計された最初のマルチレベルメメティック計算アルゴリズムである。
問題固有のリコンビネーションと突然変異演算子を導入し,KaHyPar-Eとそれらの演算子を組み合わせることで,新しいマルチレベルメメティックアルゴリズムを開発した。
我々のアルゴリズムは他のすべてより優れていて、最高のソリューションは12ドル、15ドル、25ドル、それぞれ2ドル、4ドル、そして8ドルだ。
論文 参考訳（メタデータ） (2022-04-07T20:45:17Z) - Hierarchical Agglomerative Graph Clustering in Nearly-Linear Time [1.5644420658691407]
エッジ重み付きグラフ上での階層的凝集クラスタリング(HAC)アルゴリズムについて検討する。
階層的な集合グラフクラスタリングのためのアルゴリズムフレームワークを定義する。
提案手法は,ポイントデータセットのクラスタリングを20.7～76.5倍の速度で高速化できることを示す。
論文 参考訳（メタデータ） (2021-06-10T09:29:05Z) - Provably Faster Algorithms for Bilevel Optimization [54.83583213812667]
バイレベル最適化は多くの重要な機械学習アプリケーションに広く適用されている。
両レベル最適化のための2つの新しいアルゴリズムを提案する。
両アルゴリズムが$mathcalO(epsilon-1.5)$の複雑さを達成し,既存のアルゴリズムを桁違いに上回っていることを示す。
論文 参考訳（メタデータ） (2021-06-08T21:05:30Z) - Waypoint Planning Networks [66.72790309889432]
本稿では,ローカルカーネル(A*のような古典的アルゴリズム)と学習アルゴリズムを用いたグローバルカーネルを用いたLSTMに基づくハイブリッドアルゴリズムを提案する。
我々は、WPNとA*を比較し、動き計画ネットワーク(MPNet)やバリューネットワーク(VIN)を含む関連する作業と比較する。
WPN の探索空間は A* よりもかなり小さいが、ほぼ最適な結果が得られることが示されている。
論文 参考訳（メタデータ） (2021-05-01T18:02:01Z) - Fast Parallel Algorithms for Euclidean Minimum Spanning Tree and
Hierarchical Spatial Clustering [6.4805900740861]
HDBSCAN$*$のための私達のアルゴリズムの仕事そしてスペースを減らすために十分分離の新しい概念を導入します。
我々のアルゴリズムは理論的に効率的であることを示す: 彼らは逐次対応の作業(操作数)と多対数深さ(並列時間)を持っている。
48コアマシンを用いた大規模実世界および合成データセットの実験により、我々の最速のアルゴリズムは11.13-55.89x、既存の並列アルゴリズムを少なくとも桁違いに上回った。
論文 参考訳（メタデータ） (2021-04-02T16:05:00Z) - Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。
問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。
本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-01-07T08:00:02Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。