#algorithm #hashtable #doubly-linked-list #np-hard
#алгоритм #хеш-таблица #двусвязный список #np-жесткий
Вопрос:
Я хотел бы обнаружить «полный цикл». Предположим, что списки подключаемы, если первое значение списка равно конечному значению другого списка. Например, у нас может быть 5 списков, как показано ниже.
a1 = [1, 14, 0]
a2 = [2, 14, 3]
a3 = [0, 14, 2]
a4 = [3, 14, 1]
a5 = [0, 14, 3]
где a1, a3, a2 и a4 могут быть соединены друг с другом, образуя «полный цикл», поскольку a4 и a1 также могут быть соединены. Таким образом, результат должен быть [a1, a3, a2, a4].
(Это выглядело так, как если бы это была NP-сложная задача, но я думаю, что я ошибался!) Я пробовал такие решения, как двусвязный список или хеш-таблица, но это каким-то образом оказалось рекурсивным программированием, в котором я ужасен и не очень успешен.
Конечно, я могу просто сгенерировать все перестановки и проверять одну за другой. Может ли быть более красивый способ?
Комментарии:
1. Это совсем не сложно. Найдите «обнаружение цикла в ориентированном графе». Ваши ребра — это просто списки, например
a1 = [1, 14, 0]. указывает ребро от узла 1 до узла 0.2. @orlp Спасибо за ваш ответ. Я должен был спросить здесь раньше. Это выглядело как NP-hard, я думаю, я был неправ.
Ответ №1:
Это не NP-сложно. Концептуально эта проблема известна как «обнаружение цикла» и является частью теории графов.
Если вы хотите увидеть кодовые подходы к обнаружению цикла, вот достойный учебник для начинающих:
https://www.tutorialspoint.com/Detect-Cycle-in-a-an-Undirected-Graph
https://www.techiedelight.com/check-undirected-graph-contains-cycle-not
Если бы эта проблема была NP-сложной, мы не смогли бы выполнять множество относительно важных вещей, таких как вычисления зависимостей и обнаружение циклических ссылок.
Комментарии:
1. Спасибо за ваш ответ и ссылку. Я должен был спросить здесь раньше! Мне пришлось потратить на это уже два дня. Это выглядело так, как будто это было NP-сложно, я думаю, что я ошибаюсь.