Заказ словаря для максимизации общих букв между смежными словами

Question

Предполагается, что это более конкретная, легко выражаемая форма моего предыдущего вопроса.

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

Пример 1:

AGNI, CIVA, DEVA, DEWA, KAMA, RAMA, SIVA, VAYU
reorders to:  
AGNI, CIVA, SIVA, DEVA, DEWA, KAMA, RAMA, VAYU  

Пример 2:

DEVI, KALI, SHRI, VACH
reorders to:
DEVI, SHRI, KALI, VACH

Кажется, что самый простой алгоритм: выбрать что-нибудь, а затем найти кратчайшее расстояние?
Однако DEVI-> KALI (1 общий) эквивалентен DEVI-> SHRI (1 общий)
Выбор первого совпадения приведет к уменьшению общих пар во всем списке (4 против 5).

Кажется, это должно быть проще, чем полный TSP?

Answer 1

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

Для вашего примера, график будет иметь ребра, взвешенные так:

     DEVI KALI SHRI VACH
DEVI   X    3    3    4
KALI   3    X    3    3
SHRI   3    3    X    4
VACH   4    3    4    X

Тогда вам просто нужно выбрать свой любимый Алгоритм решения TSP , и все готово.

Answer 2

Мой псевдокод:

• Создать граф узлов, где каждый узел представляет слово
• Создание соединений между всеми узлами (каждый узел соединяется с каждым другим узлом). Каждое соединение имеет «значение», которое представляет собой число общих символов.
• Отбросить соединения, где «значение» равно 0.
• Пройдите по графику, предпочитая соединения с самыми высокими значениями. Если у вас два соединения с одинаковым значением, попробуйте оба рекурсивно.
• Сохраните результат прогулки в списке вместе с суммой расстояния между словами в этом конкретном результате. Я не уверен на 100% в банкомате, если вы можете просто суммировать соединения, которые вы использовали. Смотрите сами.
• Из всех выходов выберите тот, который имеет наибольшее значение.

Эта проблема, вероятно, завершена NP, что означает, что время выполнения алгоритма станет невыносимым по мере роста словарей. Прямо сейчас я вижу только один способ оптимизировать его: разрезать график на несколько меньших графиков, запустить код для каждого и затем присоединиться к спискам. Результат не будет таким же идеальным, как при попытке каждой перестановки, но время выполнения будет намного лучше, а конечный результат может быть «достаточно хорошим».

[РЕДАКТИРОВАТЬ] Поскольку этот алгоритм не пробует каждую возможную комбинацию, вполне возможно пропустить идеальный результат. Возможно даже попасть в локальный максимум. Скажем, у вас есть пара со значением 7, но если вы выбрали эту пару, все остальные значения упадут до 1; если бы вы не взяли эту пару, большинство других значений были бы равны 2, что дало бы намного лучший общий конечный результат.

Этот алгоритм обменивает совершенство на скорость. При попытке каждой комбинации потребуются годы, даже с самым быстрым компьютером в мире, вы должны найти способ ограничить время выполнения.

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

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

Answer 3

У этой проблемы есть имя: n-арный код Грея. Поскольку вы используете английские буквы, n = 26. В статье Википедии о коде Грея описана проблема и приведен пример кода.

Answer 4

Возможно, вы захотите взглянуть на BK-Trees , которые делают поиск слов на определенном расстоянии друг от друга эффективным. Не полное решение, но, возможно, один компонент.

Answer 5

Это можно сделать с помощью рекурсивного подхода. Псевдо-код:

Start with one of the words, call it w
FindNext(w, l) // l = list of words without w
  Get a list l of the words near to w
  If only one word in list
    Return that word
  Else
    For every word w' in l do FindNext(w', l') //l' = l without w'

Вы можете добавить некоторое количество очков, чтобы подсчитать общие пары и предпочесть «лучшие» списки.