差分ヒューリスティクス
Differential Heuristics (redblobgames.com)
要約
著者は、2007年のGoogle Mapsにおけるインタラクティブな経路再計算機能に触発され、大規模なA*パスファインディングの最適化手法である「差分ヒューリスティクス」を探求してきました。長年の試行錯誤と実験を経て、ヒューリスティックの改善がA*探索を高速化する仕組みを、矢印やインタラクティブな図を用いた新しい視覚化手法で解説したウェブページを公開しました。
全文翻訳
差分ヒューリスティック
ブログ記事: 2026年8月8日
2005年、GoogleはGoogleマップを発表し、MapQuestなどのようにページをリロードするのではなく、地図をドラッグして移動できるようにしました。それが皆の注目を集めた機能でした。しかし、私の注目を集めたのは、2007年に追加された機能でした経路の始点/終点をドラッグできる機能 [1] で、ドラッグするたびに最短経路が再計算されました。これは、彼らが世界全体に対して高速な A*パスファインディング [2] を持っていたことを意味します。何百万もの道路があったのです。どうやってそれを実現したのでしょうか?
私はすでにA*と一般的な最適化について学んでいましたが、Googleマップは私がまだ学んでいない最適化を使用していました。論文を読み始めました。ほとんどの論文に対する私の反応は「この複雑さは、地図が非常に大きくない限り、それだけの価値はない」というものでした。しかし、比較的簡単な一つのテクニックがあり、それをさらに探求したいと思いました。
[画像: より良いヒューリスティックは、A*が探索する地図の範囲を減らします]
2014年、私はA*パスファインディングのインタラクティブガイドを書きました。グラフ、ヒューリスティック、最適化、データ構造など、カバーしたい追加トピックのリストを作成しました。これらのトピックの一つが、2007年に学んだ最適化でした:差分ヒューリスティック(ただし、この名前がついたのは後になってからです)。
2015年にそれについてのチュートリアルを書こうとしましたが、気に入る説明が見つかりませんでした。2016年、2018年、2019年、2022年、2024年にもう一度試みました。ついに、チュートリアルを書こうとすることをやめる必要があると悟りました。アルゴリズムは理解していましたが、それを教えるほど十分に理解していませんでした。
もっとよく理解する必要がありました。そこで、学習と実験モードに切り替えました。多くのことを学びました。いくつかの浮き沈みを経験しました。まだ学ぶべきことがたくさんあることを知りました。その過程で、より満足のいく説明を見つけ、ページを再び書き直しました。
-
以前はヒューリスティックを多くの数字で示していました。2つの矢印を使うように変更しました。1つはヒューリスティックが示唆する方向、もう1つは正しい方向です。それらが一致すると、ヒューリスティックはA*をより速く実行させます。
[画像: ヒューリスティックの不一致を示す矢印]
-
最適化が効果的な領域を示す視覚化を追加しました。これに、ポイントを移動させてそれらの領域がどのように変化するかを確認できるインタラクティブな図を組み合わせました。
[画像: 改善された領域の視覚化]
差分ヒューリスティックに関する私の新しいページはこちらです。10年以上前に始めたので、古いテキストやコードの残骸がまだ残っています。改善の余地はまだたくさんあると思いますが、これは私が「リリース済み」と見なす最初のバージョンです。