Нахождение самого длинного пути в загадке "Бегущий по лезвию стропа"

Question

Я уже несколько дней пытаюсь решить заархивированную головоломку Software ITA Software, известную как Sling Blade Runner. Суть головоломки заключается в следующем:

"Как долго вы можете найти цепочку перекрывающихся названий фильмов, таких как Sling Blade Runner?"

Используйте следующий список названий фильмов: MOVIES.TXT. Допускается наложение нескольких слов, как в "Лицензии на убийство пересмешника". Один и тот же заголовок не может быть использован более одного раза в решении. Будут приняты эвристические решения, которые не всегда дают наибольшее количество названий: ищите разумный компромисс между эффективностью и оптимальностью.

Файл MOVIES.TXT содержит 6561 заголовок фильма в алфавитном порядке.

Моя попытка найти решение состоит из нескольких частей.

Построение графика:

Что я сделал, так это сопоставил название каждого фильма с каждым другим названием фильма, к которому он мог привязаться (справа). То, что я в конечном итоге, как мой график Map[String, List[String]], Вы можете увидеть график, который был построен с использованием этого процесса здесь.

Обход графика:

Я выполнил поиск в глубину, используя каждый узел (каждый ключ на карте) в качестве начального узла поиска. Я отслеживал глубину, с которой каждый узел посещался во время поиска, и это было помечено в узлах, возвращаемых DFS. То, что я закончил, было List[List[Node]] где каждый List[Node] в списке было дерево DFS из определенного поиска.

Нахождение самой длинной цепочки:

Я взял результаты всех обходов графов на предыдущем шаге, и для каждого List[Node] Я отсортировал список по значениям глубины, с которыми я ранее помечал узлы, в порядке убывания. Затем, начиная с заголовка списка (который дает мне самый глубокий узел, посещаемый в DFS), я возвращаюсь назад через узлы, чтобы построить цепочку. Это дало мне List[List[String]] где каждый List[String] в списке была самая длинная цепочка для этой конкретной DFS. Сортировка List[List[String]] по размеру каждого List[String] и, схватив голову, дал мне самую большую цепь.

Результаты:

Самая длинная цепочка, найденная по моему алгоритму, имела длину 217 названий. Вывод можно посмотреть здесь.

Я только смог найти несколько других попыток Google, и кажется, что каждая другая попытка привела к более длинным цепям, чем я смог сделать. Например, в этом сообщении говорится, что Эрик Берк обнаружил цепочку длиной 245 заголовков, а пользователь с именем icefox в Reddit обнаружил цепочку длиной 312 заголовков.

Я не могу думать о том, где мой алгоритм не может найти самую длинную цепочку, учитывая, что другие люди нашли более длинные цепочки. Любая помощь / руководство очень ценится. Если вы хотите просмотреть мой код, его можно найти здесь (он написан на Scala, и я только начал изучать Scala, так что простите меня, если я сделал несколько ошибок noob).

Обновить:

Я внес некоторые изменения в свой алгоритм, который теперь находит цепочки длиной 240+. Смотрите здесь

Answer 1

Проблема в том, что, поскольку граф фильма (я предполагаю) имеет циклы, независимо от того, как вы назначаете глубины вершинам цикла, существует подпуть, который не является монотонным по глубине и, следовательно, не рассматривается вашим алгоритмом, Sling Blade Runner сложен для NP, так как мы не хотим, поэтому ни одна из известных стратегий полиномиального времени не даст оптимальных решений для каждого входа.

(Sling Blade Runner не совсем NP-трудная проблема длинных путей, которая задает пути без повторяющихся вершин вместо повторяющихся дуг, но есть простое сокращение за полиномиальное время от последних к первым. Разделите каждую вершину v в v_in -> v_outперемещение головки дуги к входящей вершине и хвосты дуги к выходной вершине. Сделайте дополнительные дуги из исходной вершины в другую исходную вершину для каждой в вершине и из каждой выходной вершины в вершину-приемник в другую вершину-приемник.

Чтобы найти самый длинный путь на графике a->b, b->c, c->a, c->dвход для Sling Blade Runner будет

s1->s2,
s2->a_in, s2->b_in, s2->c_in, s2->d_in,
a_in->a_out, b_in->b_out, c_in->c_out, d_in->d_out,
a_out->b_in, b_out->c_in, c_out->a_in, c_out->d_in,
a_out->t1, b_out->t1, c_out->t1, d_out->t1,
t1->t2.

Задача с самым длинным путем запрещает повторяющиеся вершины, поэтому оптимальное решение a->b->c->d скорее, чем c->a->b->c->d, Соответствующая цепь в Sling Blade Runner s1->s2->a_in->a_out->b_in->b_out->c_in->c_out->d_in->d_out->t1->t2, Соответствующее преобразование пути с повторяющейся вершиной будет повторять дугу c_in->c_out и, следовательно, быть недосягаемым для Sling Blade Runner.)

Предположим, что названия фильмов

S A
S B
A B
A E
B C
C D
D A
E F

так, чтобы график выглядел как

    F
    ^
    |
    E
    ^
    |
S-->A-->B<--
|   ^   |   \
|   |   v   |
|   D<--C   |
\___________/

Мы начинаем DFS с S и получить следующее дерево (потому что я так сказал; это не единственно возможное дерево DFS).

S-->A-->B-->C-->D
     \
      ->E-->F

, Глубины

S 0
A 1
B 2
C 3
D 4
E 2
F 3

Таким образом, самая длинная глубина-монотонный путь S A B C D, Самый длинный путь S B C D A E F, Если вы запустите DFS в другом месте, вы даже не назначите S глубина

Более простой пример

A B
B C
C D
D A

где, где бы вы ни начинали, оптимальный путь, который проходит весь цикл, не является монотонным по глубине: A B C D A или же B C D A B или же C D A B C или же D A B C D,