0

私はグリッドの世界にかなり慣れていないので、GridGain を使用してアルゴリズムにアプローチする方法についてのガイダンスが必要です。アルゴリズムは再帰的な TravellingSalesmanProblem です。

TSP は次のようになります。

public int tsp(int hops, byte[] path, int length, int minimum,
        DistanceTable distance) {
    int city, dist, me;
    int NTowns = distance.dist.length;

    // stop searching, this path is too long...
    if (length + distance.lowerBound[NTowns - hops] >= minimum) {
        return minimum;
    }

    if (hops == NTowns) {
        /* Found a full route better than current best route,
         * update minimum. */
        return length;
    }

    /* "path" really is a partial route.
     * Call tsp recursively for each subtree. */
    me = path[hops - 1]; /* Last city of path */

    /* Try all cities that are not on the initial path,
     * in "nearest-city-first" order. */
    for (int i = 0; i < NTowns; i++) {
        city = distance.toCity[me][i];
        if (city != me && !present(city, hops, path)) {
            dist = distance.dist[me][i];
            int min;
            path[hops] = (byte) city;
            min = tsp(hops + 1, path, length + dist, minimum, distance);
            minimum = minimum < min ? minimum : min;         
        }
    }
    return minimum;
}

GG の Fibonacci の例のように、集約を行う必要があると思います。問題は、ループ内に再帰呼び出しがあるため、GridFuture に何を設定すればよいかわからないことです (できるだけ多くの先物を作成できないと思います)。私が持っている再帰呼び出しは意味がありません)。より多くの例を検索しましたが、アルゴリズムにマップできませんでした。

基本的に、それを GridGain に変換する必要があります...どんな提案でも大歓迎です。

4

1 に答える 1

0

再帰的な計算を開始するための先物を作成することに問題はありません。呼び出しと同じ数の先物を作成する必要があり、ループ内でそれを行うことができると思います。試してみましたか？

GridGain Fibonacci の例は、ここではまさに正しいアプローチです。

于 2014-07-01T01:09:41.337 に答える