論文の概要: When does the Physarum Solver Distinguish the Shortest Path from other Paths: the Transition Point and its Applications

• arxiv url: http://arxiv.org/abs/2101.02913v1
• Date: Fri, 8 Jan 2021 08:48:56 GMT
• ステータス: 処理完了
• システム内更新日: 2023-04-17 08:35:39.355957
• Title: When does the Physarum Solver Distinguish the Shortest Path from other Paths: the Transition Point and its Applications
• Title（参考訳）: physarum solverはいつ、最も短い経路を他の経路と区別するのか? -遷移点とその応用-
• Authors: Yusheng Huang (1), Dong Chu (1), Joel Weijia Lai (2), Yong Deng (1), Kang Hao Cheong (2) ((1) Institute of Fundamental and Frontier Science, University of Electronic Science and Technology of China, Chengdu, China, (2) Science and Math Cluster, Singapore University of Technology and Design (SUTD), Singapore)
• Abstract要約: PPA(Physarum Polycephalum inspired algorithm)は、与えられたグラフの中で最も短い経路を見つける能力を持つバイオインスパイアされたアルゴリズムである。 近年の研究では、PPAのパスフィニングプロセスの高速化により、このアルゴリズムをさらに発展させる手法が提案されている。 PPAが最短経路を見つけるとき、遷移点 (T-Point) と呼ばれる正確なモーメントである支配経路 (D-Path) の概念を提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Physarum solver, also called the physarum polycephalum inspired algorithm (PPA), is a newly developed bio-inspired algorithm that has an inherent ability to find the shortest path in a given graph. Recent research has proposed methods to develop this algorithm further by accelerating the original PPA (OPPA)'s path-finding process. However, when does the PPA ascertain that the shortest path has been found? Is there a point after which the PPA could distinguish the shortest path from other paths? By innovatively proposing the concept of the dominant path (D-Path), the exact moment, named the transition point (T-Point), when the PPA finds the shortest path can be identified. Based on the D-Path and T-Point, a newly accelerated PPA named OPPA-D using the proposed termination criterion is developed which is superior to all other baseline algorithms according to the experiments conducted in this paper. The validity and the superiority of the proposed termination criterion is also demonstrated. Furthermore, an evaluation method is proposed to provide new insights for the comparison of different accelerated OPPAs. The breakthrough of this paper lies in using D-path and T-point to terminate the OPPA. The novel termination criterion reveals the actual performance of this OPPA. This OPPA is the fastest algorithm, outperforming some so-called accelerated OPPAs. Furthermore, we explain why some existing works inappropriately claim to be accelerated algorithms is in fact a product of inappropriate termination criterion, thus giving rise to the illusion that the method is accelerated.
• Abstract（参考訳）: physarum solver または physarum polycephalum inspired algorithm (ppa) は、生物にインスパイアされたアルゴリズムで、与えられたグラフの中で最も短い経路を見つけることができる。 近年,PPA(OPPA)のパスフィニングプロセスの高速化により,このアルゴリズムをさらに発展させる手法が提案されている。 しかし、PPAはいつ、最も短い経路が見つかったことを確かめるのだろうか? PPAが最短経路を他の経路と区別できるポイントはあるだろうか? 支配経路(D-Path)の概念を革新的に提案することにより、PPAが最短経路を見つけるときの正確な瞬間を遷移点(T-Point)と呼ぶ。 D-PathとT-Pointに基づいて,提案した終端基準を用いたOPPA-DというPPAを新たに開発した。 また,提案した終端基準の有効性と優越性を実証した。 さらに,異なるOPPAの比較のための新しい知見を提供するために,評価手法を提案する。 本論文のブレークスルーは,OPPAの終了にDパスとTポイントを用いることである。 新規終末基準は、このOPPAの実際の性能を明らかにする。 このOPPAは最速のアルゴリズムであり、いわゆる加速OPPAよりも優れている。 さらに, 高速化アルゴリズムを不適切に主張する既存の著作物が実際に不適切な終了基準の積である理由を解説し, その方法が加速されているという錯覚を生じさせる。

関連論文リスト

• Faster WIND: Accelerating Iterative Best-of-$N$ Distillation for LLM Alignment [81.84950252537618]
  本稿では,反復的BONDと自己プレイアライメントの統一的なゲーム理論接続を明らかにする。 WINレート支配(WIN rate Dominance, WIND)という新しいフレームワークを構築し, 正規化利率支配最適化のためのアルゴリズムを多数提案する。
  論文  参考訳（メタデータ） (2024-10-28T04:47:39Z)
• Tightest Admissible Shortest Path [4.928034044959278]
  グラフにおける最短経路問題はAIの基本である。 本稿では,最適コストに縛られた最短経路である許容最短経路(TASP)の探索問題を紹介する。 我々は、ソリューションの品質を保証し、TASPを解くための完全なアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-08-15T14:39:05Z)
• Lagrangian based A* algorithm for automated reasoning [0.0]
  重み付けはA*アルゴリズムの一部として導入され、効率が向上する。 このアルゴリズムの応用はUAV経路計画に適用される。
  論文  参考訳（メタデータ） (2023-06-28T17:01:03Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。 FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。 我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
  論文  参考訳（メタデータ） (2023-03-17T02:01:11Z)
• Using Particle Swarm Optimization as Pathfinding Strategy in a Space with Obstacles [4.899469599577755]
  Particle Swarm Optimization (PSO) は集団適応最適化に基づく探索アルゴリズムである。 本稿では,幅広いアプリケーションを対象としたパスプランニングの効率化を図るため,パスフィニング戦略を提案する。
  論文  参考訳（メタデータ） (2021-12-16T12:16:02Z)
• Prioritized SIPP for Multi-Agent Path Finding With Kinematic Constraints [0.0]
  MAPF(Multi-Agent Path Finding)は、ロボティクスと人工知能における長年の問題である。 この問題をある程度緩和する手法を提案する。
  論文  参考訳（メタデータ） (2021-08-11T10:42:11Z)
• Adaptive Sampling for Best Policy Identification in Markov Decision Processes [79.4957965474334]
  本稿では,学習者が生成モデルにアクセスできる場合の,割引マルコフ決定(MDP)における最良の政治的識別の問題について検討する。 最先端アルゴリズムの利点を論じ、解説する。
  論文  参考訳（メタデータ） (2020-09-28T15:22:24Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• Minimum Potential Energy of Point Cloud for Robust Global Registration [45.82423981744138]
  本稿では,大域点集合登録のための最小重力ポテンシャルエネルギー(MPE)に基づく新しいアルゴリズムを提案する。 本稿では,提案アルゴリズムの性能を実データだけでなく合成データにも示す。
  論文  参考訳（メタデータ） (2020-06-11T14:13:40Z)
• Determinantal Point Processes in Randomized Numerical Linear Algebra [80.27102478796613]
  数値線形代数(RandNLA)は、科学計算、データサイエンス、機械学習などで発生する行列問題に対する改良されたアルゴリズムを開発するためにランダム性を使用する。 最近の研究により、DPPとRandNLAの間の深い実りある関係が明らかになり、新たな保証とアルゴリズムの改善につながった。
  論文  参考訳（メタデータ） (2020-05-07T00:39:52Z)
• Provably Efficient Exploration in Policy Optimization [117.09887790160406]
  本稿では,最適化アルゴリズム(OPPO)の最適変種を提案する。 OPPO は $tildeO(sqrtd2 H3 T )$ regret を達成する。 我々の知る限りでは、OPPOは、探索する最初の証明可能な効率的なポリシー最適化アルゴリズムである。
  論文  参考訳（メタデータ） (2019-12-12T08:40:02Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。