2

这是我在图中找到哈密顿循环的算法：

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 个链接到其他节点。

谢谢

编辑：

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

4

2 回答 2

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 编码人员都认为抛出异常来表示成功是一种糟糕的风格。我希望在其他语言中也是如此 - 例外是例外:-)

于 2015-11-12T23:32:16.317 回答
0

现在，当你检测到一个循环时，你会抛出一个异常：

if (graph[vertex][0] >= 1 && pathCount == V) {
    throw new Exception();
}

除了在这里抛出异常是错误的事情之外，因为它并不是一个真正的异常情况 - 请参阅我对这个问题的评论 - 你需要做的就是在你发现循环更少时采取行动“爆炸性”。

在不知道定义的情况下，SolutionArray我无法利用它给出答案。

由于您不知道可能找到多少个周期，请添加一个List来收集您的解决方案：

private List<int[]> solutions = new ArrayList<>();

现在，当您找到解决方案时，只需在此列表中添加一些内容 - 然后从该方法返回：

if (graph[vertex][0] >= 1 && pathCount == V) {
    solutions.add(java.util.Arrays.copyOf(path, V));
    return;
}

因为这只是从方法返回，而不是抛出异常，所以调用函数的执行会继续检查下一个可能的路径。

获取路径的副本很重要，否则您只需添加对用作工作副本的数组的引用 - 所以它们都是同一个数组，并且因为您可能会在之后更新它，最后甚至不一定包含有效的解决方案。

然后，在您的 main 方法中，只需检查此列表是否为非空：

if (!solutions.isEmpty()) {
  System.out.println("\nSolution(s) found");
  displayAndWrite();
}
于 2015-11-13T00:06:45.310 回答