java - A* スターのオープンリストが期待どおりに機能しない

Question

私はかつて A* のデータ構造について尋ねていました。私は今この問題を解決しました。しかし、別の問題があります。A* が遅く、期待どおりに動作しません。つまり、Wikipedia Pseudocodes (ドイツ語と英語) からソース コードを Java で実装したということです。画像の下のグラフは、テスト目的で使用したグラフです。アルゴリズムは、たとえば、ノード 1 から宛先ノード 8 まで開始されます。ヒューリスティック関数は、ノードの横にある四角いブレーキの座標を使用して、マンハッタン距離を使用して計算されます。クローズドリストは、開始ノード 1 (先行ノード) から 3(1)-6(3)-2(1)-4(1)-3(2)-2(3)-4(3)-8(6) まで構築されます。 ）。A* は 1 から 8 まで直接行くと思っていました。これが最短経路だからです。しかし、2 の f 値がリストの中で最も低いため、ノード 6 からノード 2 にジャンプします。それで、これは正しいですか？例では、後でノードを訪問した後、他のノードに戻ることはありません。他のノードと両方向から接続されたグラフがあります。したがって、ソース コードの if 条件を、逆の方法が対応するリストにあるかどうかを証明するように変更しました。そうしないと、無限ループで終了します。問題は何で、ノード 6 からノード 2 に戻るのはなぜですか? オープンリストのノードを削除する必要がありますか? 問題は何で、ノード 6 からノード 2 に戻るのはなぜですか? オープンリストのノードを削除する必要がありますか? 問題は何で、ノード 6 からノード 2 に戻るのはなぜですか? オープンリストのノードを削除する必要がありますか? .

public ArrayList<NodeD> executeAstar(ArrayList<Arclistentry> data, NodeD start, NodeD dest)
{
    openlist = new PriorityQueue<NodeD>(1,comp);
    closedlist.clear();
    openlist.offer(start);
    start.setg(0);
    start.seth( manhattendistance(start, dest));
    start.setf(start.getg()+start.geth());
    while(!openlist.isEmpty())
    {
        NodeD currentnode = openlist.poll();
        if(currentnode.getnodenumber() == dest.getpredessor())
        {
            closedlist.add(currentnode);
            return closedlist;
        }
        closedlist.add(currentnode);
        for(int i=0; i< data.size(); i++)
        {
            if(data.get(i).getstart()==currentnode.getnodenumber())
            {
                NodeD successor = new NodeD(data.get(i).getnode(),data.get(i).getstart(), data.get(i).getcoorddest());
                NodeD reversesuccessor = new NodeD(data.get(i).getstart(),data.get(i).getnode(),data.get(i).getcoordstart());
                float tentative_g = currentnode.getg()+data.get(i).getcost();
                if((contains(successor, closedlist)||contains(reversesuccessor, closedlist))&&(tentative_g >=successor.getg()))
                {
                    continue;
                }
                if(!(contains(successor, openlist))|| (tentative_g < successor.getg()))
                {
                    successor.setpredessor(currentnode.getnodenumber());
                    successor.setg(tentative_g);
                    successor.seth(manhattendistance(successor, dest));
                    successor.setf(successor.getg()+manhattendistance(successor, dest));
                    if(!contains(successor, openlist))
                    {
                        openlist.offer(successor);
                    }
                }
            }
        }
    }
    ArrayList<NodeD> ret = null;
    return ret;
}