самый длинный список слов с соответствующими начальными и конечными буквами

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

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

Например, если вам дали слова «кошка», «собака», «тот», самая длинная строка, которую вы могли бы сделать, была бы «кошка -> та». Если бы вам дали слова «мышь», «лось», «единорог», самая длинная строка, которую вы могли бы сделать, была бы просто одним словом (поскольку ни одно из этих слов не связывалось). Если вам дали слова «птица», «блюдо», «гавань», самая длинная строка, которую вы могли бы сделать, была бы «harb -> bird -> dish» (или «dish -> harb -> bird» или «bird -»). > блюдо -> гавань ").

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

+-------+         \ +------+
|  cat  |-----------| that |
+-------+         / +------+
    |                  |
   \|/                 |
+-------+ /            |
|  the  |--------------+
+-------+ \

Эта проблема, кажется, самый длинный путь поиска , который является NP-Hard.

Есть ли лучший способ сделать это? Или даже какой-то алгоритм приближения, который можно использовать? Или каким-то образом использовать качества английского языка для сокращения пространства поиска?

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

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

1. Для каждого слова в списке подсчитайте возможные соединения и соединения.
2. Откажитесь от любых слов, которые имеют 0 входов и 0 выходов.
3. Определите начальный набор «начальных слов» с наименьшим числом входов и выходов, и выходы должны быть больше 0.
4. Каждое начальное слово получает свою собственную рабочую копию числа соединений входов / выходов. Это формирует голову цепи.
5. Для каждой цепочки определите список «следующих слов» на основе:
   
   • последняя буква стартера или предыдущего слова
   • наименьшее количество входов и выходов (опять же, выходы должны быть больше 0)
6. Для каждого next wordповторите шаг 5, пока цепь не прекратится.

Имейте в виду, что:

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

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

• В какой-то момент ваша цепочка будет прервана, и вам придется выбрать слово с нулевым числом соединений.

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

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

Например:

{dog, gopher, alpha, cube, elegant, this, that, bart}

dog     0, 1
gopher  1, 0
alpha   0, 0
cube    0, 1
elegant 1, 2
this    3, 0
that    2, 1
bart    0, 2

//alpha is dropped with 0 in and 0 out.
//two candidates found: dog, cube

//chain 1
dog => gopher
//chain 2
cube => elegant => that => this

//Note 1: the following chain won't occur due to selection rules
//that takes priority over this because of output count
cube => elegant => this

//Note 2: this chain won't occur either due to selection rules
bart => that => this

Если вы сделаете матрицу 26X26 для представления ориентированного графа вершины в виде каждого алфавита и слов в качестве ребра. Например, слово - APPLE соединяет вершины A и E с ребром, направленным от A к E. Теперь задача сводится к поиску наибольшего эйлерова следа (путь, который включает в себя максимальное число ребер, посещение каждого ребра один раз с возможным повторением вершин) в графе. Один из алгоритмов O (E) должен был бы начать случайным образом с пары вершин. Найдите путь между ними. Затем продолжайте расслаблять путь, пока это не станет возможным.

update @ GlenH7 Недавно я решил аналогичный вопрос на сайте www.hackerearth / jda, были отмечены относительные оценки в отношении наилучшего решения, и я набрал наивысшие оценки со следующим подходом:

Приведен список слов. Найдите самую длинную цепь, которую они могут сформировать. Цепочка действительна, если каждое слово начинается с буквы *, заканчивающейся в конце последнего слова.

Подход =

1) сделать граф алфавитов вершинами, а слова - ребрами. Вместо использования нескольких ребер используйте один с весом, равным количеству ребер.

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

3) Для каждой вершины сделать ее степень равной ее степени.

4) Теперь существует их эйлерова схема в графе. Найди это.

5) Теперь в оставшемся графе (относительно графа сигнала найдите самый длинный след с первой вершиной в выбранном сильно связанном компоненте. Я думаю, что это сложно из NP.

6) Включите вышеупомянутый след в элерийскую цепь, преобразуя эйлерову цепь в след.

Почему - я принимаю, что этот вопрос, скорее всего, сложный для NP (угадайте, не говоря математически). Но вышеприведенный подход работает лучше всего, когда имеется длинный список (более 1000) равномерно распределенных слов (т. Е. Он не предназначен для использования в вышеописанном подходе). Предположим, что после преобразования указанного списка в граф, упомянутый выше, он, к счастью, оказывается эйлеровым графом (см. Условия http://en.wikipedia.org/wiki/Eulerian_path ), и, без сомнения, мы можем сказать, что ответ к вышеприведенному вопросу относится P и фактически является эйлеровым путем в графе (см. http://www.graph-magics.com/articles/euler.php для очень простого подхода и посмотрите, чтобы убедиться, что ваш граф имеет сингл http://www.geeksforgeeks.org/strongly-connected-components/и если нет, то временно очистите другой маленький scc, потому что эйлерова траектория существует для одного scc). Таким образом, для не счастливых случаев (которые являются почти всеми случаями) я пытаюсь преобразовать их в счастливые случаи (то есть условие эйлеровых следов выполнено). Как это сделать? Я попытался сделать поиск по глубине для нерелевантных ребер (набор ребер в пути, начинающийся с вершины со степенью больше, чем степень и заканчивающийся в вершине со степенью больше, чем степень). Увеличение глубины поиска означает, что сначала я искал весь такой набор одного ребра в пути, чем два ребра в пути и так далее. На первый взгляд может показаться, что i-й поиск глубины будет занимать O (узлы ^ i), таким образом, общая сложность времени O (узлы + узлы ^ 2 + узлы ^ 3 + ....), пока это не удачный случай. Но амортизированный анализ получит удовольствие - это O (ребра). Как только это уменьшится, повезет найти эйлерову схему.

До этого было все полиномиальное время. Это дало бы почти лучшее решение. Но чтобы еще больше увеличить ваше решение (идеальное решение - трудная задача NP), попробуйте какой-то жадный подход в оставшемся графе, чтобы найти длинный след, начинающийся с одной из вершин в выбранном scc. Теперь добавьте это к найденному выше эйлерову следу, чтобы еще больше увеличить его.

Идея:

Сначала создайте две карты (хэши), скажем, S и E, от букв алфавита до слов; первый, S, отображает начальные буквы в слова, второй, E, делает то же самое с конечными буквами.

Например, если словарь состоит из:

птица, блюдо, собака, гавань

у нас есть:

S:

a -> [ ]
b -> [ bird ]
c -> [ ]
d -> [ dish, dog ]
...
h -> [ harb ]
...

и,

E:

a -> [ ]
b -> [ harb ]
c -> [ ]
d -> [ bird ]
...
g -> [ dog ]
h -> [ dish ]
...

Затем, используя S и E для быстрого поиска, создайте лес (набор деревьев) того же размера, что и словарь, с корнями в каждом слове и не позволяйте слову появляться в дереве более одного раза - кэшируйте Глубины деревьев, как вы их строите:

bird (depth: 2)
   dish
      harb
   dog

dish (depth: 3)
   harb
      bird
         dog

dog (depth: 0)

harb (depth: 2)
   bird
      dish
      dog

Наконец, переберите лес и найдите дерево (а) наибольшей глубины.

Решение (я) будет на оси-потомке этих деревьев.

Например,

dish / harb / bird / dog

над.