1

我正在尝试实现 Held-Karp 算法以在未加权的有向图上找到哈密顿路径。为了实现这一点，我创建了一个内部类 Combination ，它存储一个 Stack ，它表示所采用的路径的顺序，以及一个 Set ，它存储当前在路径中的元素。

哈密​​顿路径的定义是只访问图中每个顶点一次的路径

我还使用队列来存储算法尚未完全探索或折扣的路径。

最初，这个队列充满了组合，每个组合在图中都包含一个顶点。这满足了 Held-Karp 的基本情况，其中平凡的哈密顿路径是通过单个顶点的路径。

当队列不为空时，队列前面的元素被出列。其堆栈中的顶部元素被窥视，因为该元素表示添加到路径的最后一个顶点。循环遍历最后一个顶点的相邻顶点，如果其中任何一个不在当前路径集中，则使用先前的路径 Stack 和路径 Set 创建一个新的 Combination 对象，并将新顶点添加到 Stack 和 Set 中。这个新的组合对象被添加到队列的后面以供以后分析。如果无法将另一个顶点添加到路径，则循环继续并且对此组合对象的引用丢失 - 组合被打折。

如果在出队时我们遇到一个具有与图中顶点数相同长度的 Stack 的 Combination 对象，那么我们返回该 Stack 的数组表示，因为它是哈密顿路径。

我正在针对这个Graph测试这个算法。

我的代码为此图生成的邻接列表如下：

[[1], [2, 3], [4], [4], [5], []]

矩阵索引和顶点值之间的键映射是：

{0=F, 1=A, 2=B, 3=D, 4=C, 5=E}

    public String[] getHamiltonianPath() {
        String hamiltonianPath[] = new String[adjacencyList.size()];
        Combination newCombination;
        for(int i = 0; i < adjacencyList.size(); i++) {
            LinkedList<Combination> combinations = new LinkedList<>();
            // create base case with paths of length 1 including only a single vertex.
            for(int j = 0; j < adjacencyList.size(); j++) {
                combinations.add(new Combination(j));
            }
            while(!combinations.isEmpty()) {
                Combination current = combinations.pollFirst();
                // If we've found a Hamiltonian Path return it.
                if(current.pathOrder.size()  == adjacencyList.size()) {
                    while(!current.pathOrder.isEmpty()) {

                        hamiltonianPath[current.pathOrder.size() - 1] = ids.get(current.pathOrder.pop());
                    }
                    return(hamiltonianPath);
                }
                // Select the last vertex added to the path
                int lastVertex = current.pathOrder.peek();
                // Get all the vertices adjacent to the last vertex added to the path
                HashSet<Integer> neighbours = adjacencyList.get(lastVertex);

                for(int neighbour : neighbours) {
                    // Create a new combination for each path that includes the previous path
                    // and is extended to one of the adjacent vertices to the last vertex added.
                    newCombination = new Combination(current.path, current.pathOrder);
                    // Check if the adjacent vertex is already on the path.
                    // If so do not add it to the path
                    if(!newCombination.path.contains(neighbour)) {
                        newCombination.path.add(neighbour);
                        newCombination.pathOrder.push(neighbour);
                        // Add the new combination to the combinations queue
                        // for further extension later
                        combinations.add(newCombination);
                    }
                }
            }
        }
        return(hamiltonianPath);
    }


    public class Combination {
        HashSet<Integer> path;
        Stack<Integer> pathOrder;


        public Combination(HashSet<Integer> path, Stack<Integer> pathOrder) {
            this.path = path;
            this.pathOrder = pathOrder;
        }

        public Combination(int origin) {
            path = new HashSet<>();
            pathOrder = new Stack<>();

            path.add(origin);
            pathOrder.push(origin);
        }
    }

ids HashMap 只是顶点的整数 ID 与其实际 String 值之间的映射。

由于该图不包含哈密顿路径，我希望输出是一个空字符串数组。但是我实际得到的输出是：

F -> A -> B -> D -> C -> E

这很奇怪，因为在图形或矩阵中 B 和 D 之间没有边。

4

0 回答 0