3

再帰を使用して、可能なすべてのハミルトニアン サイクルをリストに追加する方法を実装しようとしています。これまでのところ、私の停止条件は十分ではなく、リストに頂点を追加する行に「OutOfMemoryError: Java heap space」が表示されます。

private boolean getHamiltonianCycles(int first, int v, int[] parent,
        boolean[] isVisited, List<List<Integer>> cycles) {
    isVisited[v] = true;
    if (allVisited(isVisited) && neighbors.get(v).contains(new Integer(first))) {
        ArrayList<Integer> cycle = new ArrayList<>();
        int vertex = v;
        while (vertex != -1) {
            cycle.add(vertex);
            vertex = parent[vertex];
        }
        cycles.add(cycle);
        return true;
    } else if (allVisited(isVisited)) {
        isVisited[v] = false;
        return false;
    }
    boolean cycleExists = false;
    for (int i = 0; i < neighbors.get(v).size(); i++) {
        int u = neighbors.get(v).get(i);
        parent[u] = v;
        if (!isVisited[u]
                && getHamiltonianCycles(first, u, parent, isVisited, cycles)) {
            cycleExists = true;
        }
    }
    //if (!cycleExists) {
        isVisited[v] = false; // Backtrack
    //}
    return cycleExists;
}

誰かが私が間違っていること、または私のアプローチが完全に間違っていることを教えてもらえますか?

編集:コメントで示唆されているように、犯人は親配列であり、無限ループを引き起こしました。修正できず、子要素を格納するように配列を変更しました。今、すべてがうまくいくようです：

private boolean getHamiltonianCycles(int first, int v, int[] next,
        boolean[] isVisited, List<List<Integer>> cycles) {
    isVisited[v] = true;
    if (allVisited(isVisited) && neighbors.get(v).contains(first)) {
        ArrayList<Integer> cycle = new ArrayList<>();
        int vertex = first;
        while (vertex != -1) {
            cycle.add(vertex);
            vertex = next[vertex];
        }
        cycles.add(cycle);
        isVisited[v] = false;
        return true;
    }
    boolean cycleExists = false;
    for (int u : neighbors.get(v)) {
        next[v] = u;
        if (!isVisited[u]
                && getHamiltonianCycles(first, u, next, isVisited, cycles)) {
            cycleExists = true;
        }
    }

    next[v] = -1;
    isVisited[v] = false; // Backtrack
    return cycleExists;
}
4

1 に答える 1

1

ここで Disjoint Hamiltonian Cycles を探している場合は、Backtracking を使用した実装があります。

于 2013-06-08T18:39:31.143 に答える