Найдите возможный кратчайший путь между двумя вершинами

#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. Вы можете обобщить этот алгоритм на произвольный граф.

  1. Используя DFS или BFS, создайте список вершин, достижимых из версии V1.
  2. Повторите этот шаг для каждой вершины, достижимой из V1, пока не достигнете V7 (или V[Last]).

Что вам нужно, так это запустить короткую DFS (6-вершинные «прогоны») внутри длинной DFS (вершины, достижимые после каждого прогона).

Комментарии:

1. не могли бы вы, пожалуйста, объяснить, почему это номер 4?

2. @newToJava Все пути из 1 заканчиваются на 4 и 6. Пути из 7 заканчиваются на 2 и 4. Число 4 является общим элементом, доступным с обоих концов.

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

4. @newToJava Да, это единственный способ сделать это. Но на самом деле вам не обязательно двигаться с обоих концов. Вы можете просто запустить метод рекурсивно из каждой вершины, доступной с самого начала (из V1, затем из V2, затем из V4), пока не дойдете до конца. Я сделал это с обоих концов, просто чтобы сделать объяснение немного короче.