Каков наиболее эффективный алгоритм поиска самой длинной цепочки из набора упорядоченных пар (x, y)?

Question

У меня есть набор упорядоченных пар (x, y), где x! = Y, но в остальном произвольно.
Как найти самую длинную цепочку, не повторяя упорядоченные пары?

Например пусть

S = {(-1, 1.2), (4, 2), (1,2, 3), (3, 5,2), (4,2, -1), (5.2 , 1), (3, 2)}.
Самая длинная цепь образована (-1, 1.2), (1.2, 3), (3, 5.2), (5.2, 1).
Существует еще одна цепочка (-1, 1.2), (1.2, 3), (3, 2), но она не самая длинная.

Итерация по всему набору - это одно решение, но оно неэффективно.

Answer 1

Я не собираюсь вводить код. Но это может вам помочь.

Вы должны посмотреть на алгоритмы графа. Думайте, что ваша пара - это узел со стороной входа и выхода. Затем подумайте обо всех краях, которые вы можете нарисовать. затем упростите график и используйте некоторые алгоритмы поиска длинного пути для графиков. https://en.wikipedia.org/wiki/Longest_path_problem