Получите самый длинный маршрут в графике

Question

У меня есть массив узлов, которые связаны друг с другом

У меня есть сеть узлов ниже.Здесь 0 - отправная точка, я хочу проехать как можно больше узлов, причем узел путешествовал только один раз.Также во время поездки от 0 до узла назначения я хочу иметь только один нечетный узел (например, 1, 3, 5, 7).Теперь мне нужно найти самый длинный маршрут, который я могу пройти из моей начальной позиции 0.

Пример:

int[] array = { 0, 9, 0, 2, 6, 8, 0, 8, 3, 0 };

На приведенном выше графике ниже представлены возможности:

0 -> 6 -> 4 (valid path, length = 3 nodes)
0 -> 9 -> 1 (Not valid path, length as we have 2 odd numbers here 1 & 9)
0 -> 2 -> 3 -> 8 (valid path, length = 4 nodes)
0 -> 2 -> 3 -> 8 -> 5 (Not valid path as we have 2 odd numbers here 3 & 5)
0 -> 2 -> 3 -> 8 -> 7 (Not valid path as we have 2 odd numbers here 3 & 7)

So the answer is 4 for this input.

Ниже приводится программа, которую я пробую.

public int process(int[] array) {
    int count = array.length;
    ArrayList<Integer>[] branches = new ArrayList[count];
    for (int i = 0; i < count; i++) {
        branches[i] = new ArrayList<>();
    }
    int begin = 0;

    for (int i = 0; i < count; i++) {
        if (array[i] != i) {
            branches[i].add(array[i]);
            branches[array[i]].add(i);
        }
    }

    Arrays.stream(branches).forEach(System.out::println);

    Queue<Network> networkQueue = new LinkedList<Network>();
    ArrayList<Integer> networkList = branches[begin];
    networkList.forEach(value -> {
        Network net = new Network(0, value);
        networkQueue.add(net);
    });

    System.out.println("printing starting nodes.......");
    List<Network> nodes = new ArrayList<>();
    for (Network n : networkQueue) {
        nodes.add(n);
        System.out.println(n.value + " : " + n.road);
    }

    int result = 0;
    return result;
}

class Network {
    int road, value;

    public Network(int road, int value) {
        this.road = road;
        this.value= value;
    }

}

Программа печатает ветви и узлы для начальной точки, т. Е. 0:

[2, 6, 9]
[9]
[0, 3]
[2, 8]
[6]
[8]
[4, 0]
[8]
[5, 7, 3]
[1, 0]
printing starting nodes.......
2 : 0
6 : 0
9 : 0

Я застрял в поиске самого длинного маршрута, как продолжить эту программу, пожалуйста, помогите мне здесь.

Answer 1

Это классический поиск в глубину с обратным отслеживанием.

Суть этого алгоритма заключается в следующем. Начиная с начального узла, посетите всех его соседей, которые не были посещены, и не нарушайте узел максимального нечетного числа с 1 ограничением. Добавьте текущий узел к текущему пути и увеличьте счетчик узлов нечетного числа, если номер текущего узла нечетный. Делайте это рекурсивно, пока не исчерпаете все допустимые пути для одного соседа, затем вернитесь назад для остальных соседей.

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

import java.util.*;

public class LongestRoute {
    private static int maxLen = 0;
    private static List<List<Integer>> res = new ArrayList<>();

    public static int longestRouteWithRestrictions(Map<Integer, List<Integer>> graph, int startNode) {
        Set<Integer> visited = new HashSet<>();
        visited.add(startNode);
        List<Integer> path = new ArrayList<>();
        path.add(startNode);

        dfs(graph, startNode, visited, startNode % 2 == 1 ? 1 : 0, path);
        return maxLen;
    }

    private static void dfs(Map<Integer, List<Integer>> graph, int currentNode, Set<Integer> visited, int oddNumNodeCnt, List<Integer> path) {
        if(path.size() > maxLen) {
            maxLen = path.size();
            res.clear();
            res.add(new ArrayList<>(path));
        }
        else if(path.size() == maxLen) {
            res.add(new ArrayList<>(path));
        }
        for(int neighbor : graph.get(currentNode)) {
            if(visited.contains(neighbor) || oddNumNodeCnt == 1 && neighbor % 2 != 0) {
                continue;
            }
            path.add(neighbor);
            visited.add(neighbor);
            dfs(graph, neighbor, visited, oddNumNodeCnt + (neighbor % 2 != 0 ? 1 : 0), path);
            path.remove(path.size() - 1);
            visited.remove(neighbor);
        }
    }
    public static void main(String[] args) {
        //Init a test graph
        Map<Integer, List<Integer>> graph = new HashMap<>();
        Integer[] neighbors_0 = {2,6,9};
        List<Integer> list0 = Arrays.asList(neighbors_0);
        graph.put(0, list0);

        Integer[] neighbors_1 = {9};
        List<Integer> list1 = Arrays.asList(neighbors_1);
        graph.put(1, list1);

        Integer[] neighbors_2 = {0,3};
        List<Integer> list2 = Arrays.asList(neighbors_2);
        graph.put(2, list2);

        Integer[] neighbors_3 = {2,8};
        List<Integer> list3 = Arrays.asList(neighbors_3);
        graph.put(3, list3);

        Integer[] neighbors_4 = {6};
        List<Integer> list4 = Arrays.asList(neighbors_4);
        graph.put(4, list4);

        Integer[] neighbors_5 = {8};
        List<Integer> list5 = Arrays.asList(neighbors_5);
        graph.put(5, list5);

        Integer[] neighbors_6 = {0,4};
        List<Integer> list6 = Arrays.asList(neighbors_6);
        graph.put(6, list6);

        Integer[] neighbors_7 = {8};
        List<Integer> list7 = Arrays.asList(neighbors_7);
        graph.put(7, list7);

        Integer[] neighbors_8 = {5,7};
        List<Integer> list8 = Arrays.asList(neighbors_8);
        graph.put(8, list8);

        Integer[] neighbors_9 = {0,1};
        List<Integer> list9 = Arrays.asList(neighbors_9);
        graph.put(9, list9);

        System.out.println(longestRouteWithRestrictions(graph, 0));
        for(List<Integer> route : res) {
            System.out.println(route.toString());
        }
    }
}

Answer 2

Извините, у меня нет времени на его кодирование, но вот логика, которую я бы применил.

1. начиная с 0 программа генерирует связанные списки соседей.В нашем случае:

   [0->2]
   [0->9]
   [0->6]
   

2. проверка соседей (последние элементы в списках): если они нечетные, увеличьте счетчик, который ссылается на этот список путей.Если нечетный счетчик == 2, тогда сотрите этот список из дальнейшего анализа

3. для каждого списка, снова начните с 1., используя последний элемент в качестве входных данных.Если больше нельзя создать VALID списки, найдите список с самым длинным путем, считая элементы.

Просто обратите внимание, что допустимый сосед не может быть таким же, как предыдущий элемент в списке, чтобы избежатьбесконечные циклы: единственный действительный список, генерируемый [0->2], это [0->2->3], а не [0->2->0]

Answer 3

Решение может быть реализовано довольно чисто, используя идею, основанную на шаблоне Visitor .Основными элементами решения являются:

• A Node класс хранит индексный номер узла и список соседей;Он включает метод accept, который позволяет посещать его объекту посетителя.

• Объект посетителя пересекает график и отслеживает четыре элемента информации: длину путиот корня - уже увиденные узлы, максимальная длина, которую когда-либо видели, и сумма пути (сумма индекса каждого узла, увиденного на пути).Этот последний номер используется только для проверки, было ли обнаружено нечетное число на пути.

Класс Node (здесь ничего особенного):

public class Node implements Iterable<Node> {
    private final int index;
    private List<Node> neighbors = new ArrayList<>();

    public Node( int index ) {
        this.index = index;
    }

    public void setNeighbors( Node... neighbors ) {
        this.neighbors = Arrays.asList(neighbors);
    }

    public int getIndex() {
        return index;
    }

    public void accept(Visitor v) {
        v.visitNode(this);
    }

    @Override
    public Iterator<Node> iterator() {
        return neighbors.iterator();
    }
}

Класс Visitor, который накапливает состояние текущего пути, но с возможностью отменить это состояние после завершения посещения:

class Visitor {

    private int pathLength = 0;
    private int maxLength = 0;
    private int currentSum = 0;
    private List<Node> visited = new ArrayList<Node>();

    public void visitNode(Node n) {
        if( visited.contains(n)) {
            return;
        }
        visited.add(n);
        if( canBeIncluded(n) ) {
            pathLength++;
            maxLength = Math.max(maxLength, pathLength);
            currentSum += n.getIndex();
            for( Node neighbour : n ) {
                neighbour.accept(this);
            }
            currentSum -= n.getIndex();
            pathLength--;
        }   
    }

    public int getMaxLength() {
        return maxLength;
    }

    /* A node cannot be included if the current sum is odd and the 
     * index of the node is odd, because this means there would be
     * two odd nodes on the path.
     */
    private boolean canBeIncluded(Node node) {
        return !(currentSum % 2 == 1 && node.getIndex() % 2 == 1);
    }
}

С этим на месте, и предполагая, что Node экземпляры имеютправильно инициализированы, получение результата - это всего лишь инициализация посетителя и вставка его в график через корневой узел, а затем получение результата:

Node n0 = new Node(0);
// Create all nodes
n0.setNeighbors(n2,n6,n9); 
// and so on, presumably done by a dedicated method
Visitor visitor = new Visitor();
n0.accept(visitor);
System.out.println(visitor.getMaxLength());

(Кстати, технически, чтобы это было правильное приложениешаблона Visitor, Visitor должен быть интерфейсом, реализованным конкретным классом посетителей. Чтобы свести к минимуму все, я пропустил эту часть структуры.)

Answer 4

Вы можете попробовать следующий подход, который должен быть относительно простым для реализации и отслеживания.Во-первых, вам нужно сформировать класс Node, который будет иметь информацию о 3 вещах:

1. Максимальная длина пути, пройденного до сих пор, при посещении всех узлов до этого узла от узла 0, посещая каждыйузел только один раз.
2. Переменная с именем oddCounter, которая подсчитывает количество нечетных узлов, обнаруженных до сих пор в этом пути.
3. Логическая переменная isVisited, чтобы узнать, посещался ли уже этот узел.или нет.

Теперь просто внедрите BFS с узлами, которые являются экземпляром этого типа класса, определенного выше, и при выполнении BFS вам просто необходимо соответствующим образом обновить переменные каждого узла.

Обратите внимание, что вам нужно сделать BFS для всех узлов, начиная с узла 0, каждый раз сбрасывая значения выше 3 переменных, чтобы вы могли отслеживать дальнейшие пути в этом маршруте через этот узел.Вы можете завершить цикл за определенными узлами, если вы уже нашли один нечетный узел.Таким образом, в будущем это будет более гибким, если вы захотите включить в свой путь, возможно, 2 или 3 нечетных узла по сравнению с одним узлом в настоящее время.

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

Я уверен, что этот подход может быть оптимизирован с помощью динамического программирования.Поскольку вы знаете длину маршрута и количество нечетных узлов до тех пор, пока данный узел не скажет i, вы можете просто сделать BFS сейчас из ith узла и использовать memoization для отслеживания предыдущей длины маршрута и нечетных узлов, которыемы уже отслеживаем, используя созданный выше класс.