私は、プライオリティ キューを実装して、比較的シンプルな Astar の効率的な実装を可能にすることに関心があります (プライオリティ キューはシンプルです)。
スキップ リストは単純な O(1) の抽出最小操作と O(Log N) の挿入操作を提供するため、O(log N) の抽出を持つフィボナッチ ヒープを実装するのがより困難な場合と競合する可能性があります。 Min と O(1) の挿入。まばらなノードを持つグラフには Skip-List が適しているのに対し、ノードが密に接続されている環境にはフィボナッチ ヒープが適していると思います。
これにより、通常はフィボナッチ ヒープが改善される可能性があります。
フィボナッチ ヒープの存在理由は、O(1) キーの減少操作であり、ダイクストラのアルゴリズムを時間 O(|V| log |V| + |E|) で実行できるようにします。ただし、実際には、効率的なキーの減少操作が必要な場合は、ペアリング ヒープを使用します。フィボナッチ ヒープにはひどい定数があるためです。キーが小さい整数である場合は、ビンを使用するだけでさらに良い場合があります。
フィボナッチ ヒープは、非常に非常に非常に非常に遅く、非常に非常に非常に大規模で高密度のグラフ (数億のエッジのオーダー) を除きます。また、正しく実装するのが非常に難しいことでも知られています。
一方、スキップ リストは非常に優れたデータ構造であり、比較的簡単に実装できます。
しかし、単純なバイナリ ヒープの使用を検討していないのはなぜでしょうか。バイナリ ヒープ ベースのプライオリティ キューは、スキップ リスト ベースのプライオリティ キューよりもさらに高速であると思います。スキップ リストは、主に同時実行性を利用するために使用されます。