Выбор подходящего алгоритма для создания и расчета перестановок пар совместного использования элементов

Question

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

С учетом списка кортежей, таких как [(A, B), (B, C), (C), D), (DE), (A, D), (E, A), (A, C)], найдите последовательности, такие как [ A , B, C, D, E, A ] или [ A , D, C, B, A ], которые начинаются и заканчиваются одной и той же буквой и образуютсяобъединение пар, которые разделяют хотя бы один элемент кортежа. Примечание: (A, B) считается таким же, как (B, A), точно так же, как (A, C) такое же, как (C, A), поэтому его можно использовать для создания обеих пар ( C , B, A, C ) или ( A , B, C, A )

Важным ограничением являетсяимея ограничение по длине. Например, убедитесь, что последовательность не длиннее 7 элементов.

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

Answer 1

Сложность времени

(В худшем случае) временная сложность любого алгоритма для решения этой задачи будет иметь нижнюю границу O (n) , где n количество ребер (т. е. кортежей) графа:

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

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

Алгоритмы

По сути, есть две стратегии: поиск в ширину или поиск в глубину. Оба имеют временную сложность O (n) .

Алгоритм, который вы, похоже, пытались использовать, - это поиск в ширину. Это лучший выбор, когда вам нужно найти кратчайший цикл, потому что тогда вы можете выйти из алгоритма, как только найдете цикл (A-to-A).

A глубина-Первый поиск также является жизнеспособным вариантом, конечно, когда есть ограничение, установленное для длины цикла. В этом случае сложность space равна O (m) , где m - максимальная длина цикла. В зависимости от графика (его размер, средний коэффициент ветвления) это может быть намного дешевле, чем пространство O (n) , необходимое для поиска в ширину.

Кроме того, ширинаПри первом поиске необходимо постоянно переключать состояния, в то время как переходы, которые происходят во время рекурсии и обратного отслеживания (характерные для поиска в глубину), часто легче иметь дело.

Подготовка

Какую бы стратегию вы ни выбралииспользуйте, убедитесь, что сначала создали эффективную структуру данных для графа.

Простая структура данных, состоящая из массива пар (как показано в вашем вопросе), недостаточно хороша. Для достижения оптимальной временной сложности вам необходимо создать список смежности (или что-то подобное), чтобы вы могли найти соседей узла (достижимых через один кортеж) за постоянное время.