java - 在偏向图中找出所有可能的哈密尔顿圈

Question

这是我在图中寻找哈密顿循环的算法:

private SolutionArray solution;
private int V, pathCount;
private int[] path;
private int[][] graph;

/**
 * Constructor
 */
public ConcreteSolver() {
    solution = new SolutionArray();
}

@Override
public SolutionArray solve(PathMatrix input) {

    V = input.getNbVertex();
    path = new int[V];

    /** Set all path to non-visited **/
    boolean[] visited = new boolean[V];
    for (int i = 0; i < V; i++) {
        visited[i] = false;
    }

    Arrays.fill(path, -1);
    graph = input.getMatrix();

    try {
        path[0] = input.getFirstVertex();
        pathCount = 1;

        findPaths(0);

        System.out.println("No solution");
    } catch (Exception e) {

        System.out.println("\nSolution found");
        //input.printMatrix();
        displayAndWrite();
    }

    return solution;

}

/**
 * function to find paths recursively
 */
private void findPaths(int vertex) throws Exception {


    /** solution **/
    if (graph[vertex][0] >= 1 && pathCount == V) {
        throw new Exception();
    }
    /** all vertices selected but last vertex not linked to 0 **/
    if (pathCount == V)
        return;

    for (int v = 0; v < V; v++) {
        /** if connected **/
        if (graph[vertex][v] >= 1) {
            /** add to path **/
            path[pathCount++] = v;

            /** if vertex not already selected solve recursively **/
            if (!isPresent(v))
                findPaths(v);

            /** remove path **/
            path[--pathCount] = -1;

        }

    }

}

/**
 * function to check if path is already selected
 */
private boolean isPresent(int v) {
    for (int i = 0; i < pathCount - 1; i++)
        if (path[i] == v)
            return true;
    return false;
}

我能够找到一个单一的第一个哈密顿循环。是否可以对其进行调整以找到图中所有可能的哈密顿循环？

输入是一个非对称矩阵(一些节点之间的链接是单向的)，一些节点可能有 2 或 3 个链接到其他节点。

谢谢

编辑:

澄清一下，该算法已经可以找到一个解决方案，但找不到第二个，依此类推。从阅读中可以看出，A* 使用 bactracking 可能会解决这个问题，但我不确定它是否可以添加到我已有的内容中。

Answer 1

目前您只有一个数组来捕获当前正在探索的路径。大概您的 displayAndWrite 方法使用此信息来打印解决方案。

要记录所有解决方案，您需要在找到哈密顿循环时复制路径。

类似的东西:

private static final int MAX_SOLUTIONS = 100;
private int[][] solutions = new int[MAX_SOLUTIONS][];
private int solutionCount = 0;

private void addSolution(int[] path) {
    if (solutionCount < MAX_SOLUTIONS)
        solutions[solutionCoun++] = Arrays.copyOf(path, path.length);
}

您需要在您当前通过异常的递归方法中调用addSolution。

顺便说一句，几乎所有有经验的 Java 编码人员都认为抛出异常来表示成功是糟糕的风格。我希望其他语言也是如此 - 异常(exception)是异常(exception):-)