サイエンス
最短経路アルゴリズムが40年ぶりに更新される：ダイクストラ法の限界「ソーティング・バリア」はいかにして克服されたのか？
カーナビが示す最適なルート、ネット通販の迅速な配送網、あるいは金融市場での瞬時のデータ伝送。我々の現代社会は、無数の「点」と「線」で結ばれたネットワークの上で、最も効率的な経路、すなわち「最短経路」を絶えず計算することで […]
Term
貪欲法
別名: Greedy Algorithm
Overview
最終更新: 2026年7月9日アルゴリズムの設計手法の一つで、問題を複数のステップに分割し、各ステップにおいてその時点で最も有利に見える選択（局所的最適解）を繰り返すことで、最終的な解を得ようとする手法。ダイクストラ法はこの代表例であり、常に「最も近い未確定の頂点」を確定させていく。実装が単純で効率的である一方、問題によっては必ずしも全体の最適解（大域的最適解）が得られるとは限らないが、最短経路問題においては正解を導くことが保証されている。