Алгоритм гамильтонова пути на направленном невзвешенном графе использует несуществующие ребра - PullRequest
Новая
       27

Алгоритм гамильтонова пути на направленном невзвешенном графе использует несуществующие ребра

1 голос
/ 28 мая 2019

Я пытаюсь реализовать алгоритм Хелда-Карпа для нахождения гамильтонова пути на невзвешенном ориентированном графе.Для этого я создал внутренний класс Combination, в котором хранится стек, представляющий порядок выбранного пути, и набор, в котором хранятся элементы, находящиеся в данный момент на пути.

Определение гамильтонова пути - это путь, который посещает каждую вершину графа только один раз

Я также использую очередь для хранения путей, которые еще не былибыл полностью исследован или обесценен алгоритмом.

Первоначально эта очередь заполняется комбинациями, каждая из которых содержит одну вершину в графе.Это соответствует базовому случаю для Хелд-Карпа, где тривиальный гамильтонов путь - это путь, который проходит через одну вершину.

Пока очередь не пуста, элемент из передней части очереди исключен.Верхний элемент из его стека просматривается, так как этот элемент представляет последнюю вершину, добавленную к пути.Смежные вершины последней вершины проходят через петлю, и если какая-либо из них не находится в текущем наборе пути, создается новый объект Combination с предыдущим путем Stack и путем Set, и новая вершина добавляется в Stack и Set.Этот новый объект комбинации добавляется в конец очереди для последующего анализа.Если невозможно добавить еще одну вершину к пути, цикл продолжается и ссылка на этот объект комбинации теряется - комбинация сбрасывается.

Если при снятии очереди мы сталкиваемся с комбинированным объектом со стеком, длина которого равна числу вершин в графе, то мы возвращаем представление массива этого стека, поскольку он является гамильтоновым путем.

Я проверяю этот алгоритм на этом Графике .

Ниже приведен список смежности, сгенерированный моим кодом для этого графа: 

[[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);
        }
    }

HashMap идентификаторов - это просто отображение между целочисленными идентификаторами вершин и их фактическими значениями String.

Поскольку в этом графе нет гамильтонова пути, я ожидаю, что на выходе будет массив нулевых строк.Однако вывод, который я на самом деле получаю:

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

, что очень странно, поскольку между B и D нет грани вграфик или матрица.

...