差分ヒューリスティクス

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