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

Question

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

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

---

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

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

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

Смежные вопросы SO здесь и здесь .

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

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

Answer 1

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

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

Answer 2

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

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 3

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

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

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

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

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

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

Answer 4

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

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

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

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