ロンドンの地下鉄を検索するための幅優先グラフ検索アルゴリズムを構築中です。
アルゴリズムを理解しましたが、ご存知かもしれませんが、このアルゴリズムでは、検索が必要なすべてのエッジを (正しい順序で) 追跡するために Queue ADS が必要です。
私は、キューと大量または非常に多数のキューに入れられたアイテム (エッジ) の管理に関する効率性の問題について読んでいます。
Java ArrayList に基づいてキューを実装する方法を教えてください。これは、ヘッドとテールを追跡でき、メモリの成長中に効果的にメモリを管理しますか?
どんなヒント/ポインタも大歓迎です!!
オブジェクトがすでにキューにあるかどうかを確認するための高速テストが必要になることに注意してください。この機能はどちらArrayListもQueue提供していません (彼らのcontainsチェックは ですO(n))。追加のフィールドを追加して、扱っているオブジェクトを変更できる場合、それは簡単です。そうでない場合は、キューにあるオブジェクトを追跡するために、ある種の高速Set(おそらく ) を維持する必要があります。HashSet
あなたの質問はこのトピックに密接に関連していると思います: Javaでの幅優先検索
本当に正当な理由がない限り、ArrayList を使用しないでください。Java には、すでに優れた一連のキュー実装が付属しています。詳細については、Queueインターフェースを参照してください。
あなたの場合、キューの実装としてLinkedListを選択するだけで十分かもしれません。LinkedList をキューとして使用する幅優先検索の実装のわかりやすい例については、http://www.codeproject.com/KB/java/BFSDFS.aspxも参照してください。