文献

J-GLOBAL ID：202002218947641545   整理番号：20A2083401

最短経路の発見におけるDijkstraとA-Star:チュートリアル【JST・京大機械翻訳】

Dijkstra’s and A-Star in Finding the Shortest Path: a Tutorial

著者 (3件)： Candra Ade (Universitas Sumatra Utara,Faculty of Computer Science and Information Technology,Department of Computer Science,Medan,Indonesia) ,  Budiman Mohammad Andri (Universitas Sumatra Utara,Faculty of Computer Science and Information Technology,Department of Computer Science,Medan,Indonesia) ,  Hartanto Kevin (Universitas Sumatra Utara,Faculty of Computer Science and Information Technology,Department of Computer Science,Medan,Indonesia)
資料名： IEEE Conference Proceedings  (IEEE Conference Proceedings)
巻： 2020  号： DATABIA  ページ： 28-32  発行年： 2020年 
JST資料番号： W2441A  資料種別： 会議録 (C)
記事区分： 原著論文  発行国： アメリカ合衆国 (USA)  言語： 英語 (EN)

抄録/ポイント： greedy欲アルゴリズムの1つの形態として,Dijkstraは,より長い探索時間で最適結果で最短経路探索を扱うことができる。Dijkstraは,A-Starとは反対であり,最優先探索アルゴリズムであり,これは,最短経路探索を高速時間で処理できるが,常に最適ではない。DijkstraとA-Starの長所と短所を見ることによって,このチュートリアルは24のSPBU(ガスステーション)の間の経路選択における最短経路を見つける際の2つのアルゴリズムの実用化を論じる。経路はMedan市に位置し,有向グラフで表された。さらに,Big-θ(Θ)と走行時間の複雑性に基づくDijkstraとA-starを比較した。結果は,SPBUの間の最短経路探索をDijkstraとA-Starで解決することができ,いくつかの場合,2つのアルゴリズムによって作り出される経路が異なるので,発生する全距離も異なることを示した。この場合,A-Starの実行時間はDijkstraよりも速く,A-Star原理に従い,最良の発見的値に基づく位置点を選択するが,Dijkstraはそうではない。複雑性のために,DijkstraはΘ(n2)であり,A-StarはΘ(m×n)で,0≦m≦nであった。Copyright 2020 The Institute of Electrical and Electronics Engineers, Inc. All rights reserved. Translated from English into Japanese by JST.【JST・京大機械翻訳】

シソーラス用語： *アルゴリズム ,  ガソリンスタンド ,  有向グラフ ,  経路選定 ,  走行時間
準シソーラス用語： 探索時間 ,  実行時間 ,  探索アルゴリズム ,  複雑性 ,  *最短経路 , 【Automatic Indexing@JST】

分類 (1件)： 図形・画像処理一般  (JE04010I)

タイトルに関連する用語 (4件)： 最短経路 ,  発見 ,  StAR ,  チュートリアル