Сложность поиска всех простых путей с использованием поиска в глубину?

Question

Спасибо всем, кто ответил идеями и альтернативными решениями.Всегда приветствуются более эффективные способы решения проблем, а также напоминания о необходимости подвергнуть сомнению мои предположения.Тем не менее, я бы хотел, чтобы вы на мгновение проигнорировали проблему, которую я пытаюсь решить с помощью алгоритма, и просто помогли мне проанализировать огромную сложность моего алгоритма в том виде, в котором я его написал, — все простые пути. на графике с использованием поиска с ограниченной глубиной, как описано здесь, и реализован здесь.Спасибо!

Редактировать:Это домашнее задание, но я уже отправил это задание и мне просто хотелось бы знать, правильный ли мой ответ.Меня немного смущает сложность Big-O, когда задействована рекурсия.

---

Оригинальный вопрос ниже:

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

Я знаю, что временная сложность DFS равна O(V+E), а пространственная сложность — O(V), и моя интуиция подсказывает, что сложность поиска по всем путям будет больше, но я не могу определить, что это будет.

Связанные вопросы SO здесь и здесь.

Обновление (в ответ на комментарий ниже):

Я пытаюсь решить шесть степеней Кевина Бэкона проблема.Обычно для этого требуется найти наименьшую степень разделения между парой актеров, но мне нужно найти ВСЕ степени разделения (на данный момент меньше 6, но это может измениться).

Answer 1

Отвечая на мой собственный вопрос с моим анализом, пожалуйста, прокомментируйте/исправьте!

The algorithm is simplified and analyzed as follows: 
(Note: here MAXDEPTH is the maximum degrees of separation to search for, default 6)
1. For the current vertex, get neighbors (amortized O(1))
2. For every neighbor, do the following [O(b), where b is the branching factor, or the avg. number of neighbors of a vertex]
2.1.    Check if already visited [O(MAXDEPTH), since it’s a linked list of max size MAXDEPTH)
2.2.    Append path to paths list [amortized O(1)]
3. End for 
4. Do the following MAXDEPTH times [O(MAXDEPTH)]
4.1.    For every neighbor do the following [O(b)]
4.1.1.      Check if already visited [O(MAXDEPTH)]
4.1.2.      Add to visited list [O(1)]
4.1.3.      Recursively call search again [becomes O(MAXDEPTH*b)]
4.1.4.      Delete from visited list [O(1)]
4.2 End for /* Neighbor */
5. End loop /* MAXDEPTH */

Thus, the complexity becomes O((MAXDEPTH*b)^MAXDEPTH).

Answer 2

Наихудшим сценарием является (я думаю) полный график на н вершины.Этот график имеет н!простые пути, и для каждого из них ваш алгоритм делает как минимум н^2 вычислительных шага — для каждой вершины, смежной с последней на пути, выполняется линейное сканирование связанного списка ранее посещенных узлов.(Это не считая всех промежуточных этапов поиска.) Значит сложность не меньше O(н^2 * н!), возможно, хуже.

Какую большую проблему вы пытаетесь решить?

Answer 3

6 градусов — это хорошо, потому что это дает вам ограничение.Я понимаю, что цифра 6 может измениться, но думаю, что этот подход по-прежнему применим.Везде, где я говорю «6», просто замените «# градусов».

Если вы хотите, вы можете использовать поиск в ширину (BFS).Если я правильно понимаю, вам дана начальная точка (актер/актриса), и вам нужно найти все пути к конечной точке (Кевин Бэкон), которые находятся на расстоянии менее 6 ребер.Вы можете разбить эту задачу на подзадачи, сказав: сначала найдите все соединения, находящиеся на расстоянии 1 ребра, затем все пути на расстоянии 2 ребер,...и, наконец, найдите все пути, расположенные на расстоянии шести ребер.Именно так будет работать BFS... сначала исследуйте все узлы на расстоянии одного ребра, затем двух и т. д.

В качестве альтернативы вы также можете использовать модифицированный поиск в глубину (DFS), выполнив обычный DFS и следуя по каждому пути настолько далеко, насколько сможете, но сохраняя счетчик и не позволяя ему идти более чем на 6 ребер вглубь любого конкретного пути.

Я думаю, что ваше решение, вероятно, будет намного лучше, чем обычное O(V + E), просто потому, что вы, вероятно, не посещаете все вершины и не путешествуете по всем ребрам (при условии, что наш график представляет собой отношения между большим количеством актеров), но скорее вы ограничены подграфом общего графа.Вы начинаете свой алгоритм поиска, действуя так, как будто вы собираетесь посетить все вершины/ребра, но независимо от того, используете ли вы BFS или DFS, вы остановитесь на 6 ребрах от начальной вершины, а не просматриваете весь граф. .

Учтите, что что-то вроде DFS можно представить как O(V+E), но его также можно представить как O(b^d), где b — коэффициент ветвления, а d — глубина графа (см. Википедия_DFS для получения дополнительной информации ).Итак, учитывая, сколько актеров там будет, каким будет b?Учитывая ограничения, которые вы знаете о задаче (6 градусов и другие), каким будет d?

Думаю, я, наверное, сказал достаточно.Надеюсь, это послужит для вас толчком.Я должен добавить оговорку: на самом деле я не знаю наверняка ответа, просто проблема меня поражает;)

Answer 4

Я думал об использовании O((n^2)*глубина) алгоритм

1. Для каждого актера найдите всех актеров, с которыми он работал.(Пространственная и временная сложность O(n^2), но обе зависят от фактического количества соединений и для большинства актеров не превышают 500 или 5-кратного количества ваших друзей на Facebook). Это дает 500*n временную и пространственную сложность.

2. Соберите целых три, охватывая всех людей на одной глубине, и добавьте все эти связи.O(n^2*глубина)

Если вы используете двусвязное дерево для хранения соединений, вы можете найти все соединения по глубине*n сложности.