#java #algorithm #graph #computer-science
#java #алгоритм #График #информатика-наука
Вопрос:
Итак, допустим, у меня есть такой график, я могу посещать только 6 вершин одновременно, например, я могу посетить, возможно, 123654 в первый раз, и когда я снова перемещаюсь, мне нужно начать с конечной вершины, которую я посетил в прошлый раз, поэтому для приведенного примера я должен начать с 4, тогда я могу сделать 432567. Цель состоит в том, чтобы начать с 1 и закончить ровно на 7 для моего последнего элемента любых ходов.
Есть ли какой-нибудь способ добиться этого? Я застрял на этой проблеме уже несколько недель, пока моя идея состоит в том, чтобы продолжать изучать все возможные маршруты, которые я могу найти, но я не думаю, что это правильный алгоритм, есть ли идея получше?
Комментарии:
1. Скриншот … Краски? Почему? 🙂
2. Вам всегда нужно посещать ровно 6 вершин? Или до 6?
3. всегда 6 и скриншот просто дают вам пример, lol
Ответ №1:
Шаг 1. Найдите все пути длиной 6 из вершины 1 (V1). Для этого вы можете использовать DFS:
123456
123654
125436
125634
Я предполагаю, что вы не можете посетить одну и ту же вершину дважды за один и тот же «прогон». Если вы сможете, вы получите больший список.
Шаг 2. Найдите все пути длиной 6 из версии 7:
765432
765234
763452
763254
Шаг 3. Найдите вершину, которую вы можете достичь за один запуск как из V1, так и из V7
Это вершина номер 4. Затем вы можете построить два прогона, которые позволят вам перейти от версии V1 к версии V7:
123654
432567
Шаг 4. Вы можете обобщить этот алгоритм на произвольный граф.
- Используя DFS или BFS, создайте список вершин, достижимых из версии V1.
- Повторите этот шаг для каждой вершины, достижимой из V1, пока не достигнете V7 (или V[Last]).
Что вам нужно, так это запустить короткую DFS (6-вершинные «прогоны») внутри длинной DFS (вершины, достижимые после каждого прогона).
Комментарии:
1. не могли бы вы, пожалуйста, объяснить, почему это номер 4?
2. @newToJava Все пути из 1 заканчиваются на 4 и 6. Пути из 7 заканчиваются на 2 и 4. Число 4 является общим элементом, доступным с обоих концов.
3. итак, если нет общего элемента из начальной вершины и конечной вершины, он будет просто продолжать рекурсивно запускать метод до тех пор, пока не появится общий элемент?
4. @newToJava Да, это единственный способ сделать это. Но на самом деле вам не обязательно двигаться с обоих концов. Вы можете просто запустить метод рекурсивно из каждой вершины, доступной с самого начала (из V1, затем из V2, затем из V4), пока не дойдете до конца. Я сделал это с обоих концов, просто чтобы сделать объяснение немного короче.