これまでのところ、グリッド上の A* 検索とそのバリアントのいくつかしか知りませんでした。最近、Rapidly Random Exploring Trees (RRT) などの確率的検索アルゴリズムについて聞いたことがあります。検索の問題が非常に大きくなると、それらが非常に優れているが、非常に最適ではないパスを提供する方法について聞いています。悲しいことに、RRT やその他の亜種を A* やその亜種とベンチマークする比較は見つかりませんでした。非常に大きなグリッド (2048x2048 以上) での 2 つのアルゴリズムのパフォーマンスの違いを詳しく説明しているリンクを知っている人はいますか? 非格子探索問題もOK
私がこれまでに発見したこと: http://movingai.com/GPPC/は、RRT に基づくツリー キャッシュが、すべての A* バリアントよりも非常に高速であることを示しています。
ベンチマークでない場合、Java で利用可能な RRT の実装はありますか? 編集：私が尋ねる前にグーグルで検索する必要がありました。http://correll.cs.colorado.edu/?p=1623