3

Java で A* 検索アルゴリズムを使用しています。ツアーを印刷して、ユーザーがどのルートを試し、どのルートが最適かを確認できるようにしたいと考えています。現時点では、最適なルートを出力するだけですが、それは問題ありません。それを実行したいのですが、ルートのリストも出力して、それぞれの最悪のコストと関連するコストを確認できるようにしたいと考えています。以下のコードから、すべてのツアーを出力する followedRoute を出力すると、それぞれのコストを出力できますか? アルゴリズムは、完全な各ツアーとそれらの最低コストを見つけることで機能します。理想的には、{0}、{0、3} などではなく、完全なツアーのみを印刷したいのです。

以下は、私が信じている関連するコード セグメントです。これ以上見る必要がある場合は、お問い合わせください:)

Cities aux = currentCities;
ArrayList followedRoute = new ArrayList();
followedRoute.add(aux.number);
while (aux.level != 0) {
    aux = aux.parent;
    followedRoute.add(0, aux.number);
}

if (currentCities.level == distances.getCitiesCount()) {
    solution = true;
    bestRoute = followedRoute;
    bestCost = currentCities.g;
} else {
    for (int i=0; i<distances.getCitiesCount(); i++) {
        // have we visited this city in the current followed route?
        boolean visited = followedRoute.contains(i);
        boolean isSolution = (followedRoute.size() == distances.getCitiesCount())&&(i == firstNode);

        if (!visited || isSolution) {
            Cities childCities = new Cities(i, currentCities.g + distances.getCost(currentCities.number, i), 
                    getHeuristicValue(currentCities.level + 1), currentCities.level + 1);
            childCities.parent = currentCities;
            opened.add(childCities);  
            System.out.println(followedRoute);
        }
    }                
}

どんな助けでも大歓迎です！前もって感謝します ：）

4

1 に答える 1

2

そうするために A* を変更するのは大変で、非常に非効率的です1。

実際、あなたが求めていることを行うための既知のアルゴリズムはありません。これは最長経路問題と呼ばれ、 NP-Hardであるため、既知の多項式解はありません。

(なぜそれが真なのか直感的に知るために - 頂点から最も長い単純な経路を見つけることができるアルゴリズムを考えてくださいv- そのようなアルゴリズムが与えられた場合 - からのハミルトニアン経路があるかどうかを簡単に判断できます。ハミルトニアン経路vがあるかどうかを確認するプロセスを繰り返しますハミルトニアン経路問題は NP 困難であるため、この問題も NP 困難です。

最長のパスを見つける 1 つの方法は、ブルート フォースを使用することです (考えられるすべてのパスを検索します)。これは、 DFSの変更 (「訪問した」ノードを忘れる) を使用して実現でき、グラフ内のすべてのパスを再帰的にチェックし、すべてが使い果たされるまで、最長のものを返します。

残念なニュースで申し訳ありませんが、少なくとも、(おそらく) 実行できない (効率的に) できないことに時間を費やす必要がなくなることを願っています。

(1)ほとんどの CS 研究者が一般的に信じているP!=NP と仮定します。

于 2013-01-15T15:38:52.480 に答える