Это вариация проблемы коммивояжера?

Question

Меня интересует функция из двух списков слов, которая бы возвращала расстояние редактирования без учета порядка.

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

Расстояние между "cat rat bat" и "rat bat cat" будет равно 0. Расстояние между "cat rat bat" и "fat had bad" будет таким же, как расстояние между "rat bat cat" и "had fat bad", 4. В случае количество слов в списки не совпадают, более короткий список будет дополнен словами 0 длины.

Моя интуиция (которая не воспитывалась на уроках информатики) не находит другого решения, кроме как использовать грубую силу:

   |had|fat|bad|   a solution
---+---+---+---+ +---+---+---+
cat| 2 | 1 | 2 | |   | 1 |   |
---+---+---+---+ +---+---+---+
rat| 2 | 1 | 2 | | 3 |   |   |
---+---+---+---+ +---+---+---+
bat| 2 | 1 | 1 | |   |   | 4 |
---+---+---+---+ +---+---+---+

Начиная с первого ряда, выберите столбец и перейдите к следующим строкам, даже не посещая уже посещенный столбец. Делайте это снова и снова, пока не перепробуете все комбинации.

Для меня это звучит немного похоже на проблему коммивояжера. И как бы вы решили мою конкретную проблему?

Answer 1

Как вы уже показали в сетке слева, вы можете начать с вычисления расстояний редактирования для каждой пары слов. Это легко сделать за полиномиальное время (n ^ 2 отредактировать вычисления расстояния).

Тогда ваша проблема может быть описана как «минимально взвешенное двустороннее соответствие» или, что эквивалентно, «максимально взвешенное двустороннее соответствие» Это также можно сделать за полиномиальное время (быстрее, чем коммивояжер). Смотри http://en.wikipedia.org/wiki/Matching_%28graph_theory%29#Maximum_matchings_in_bipartite_graphs

Answer 2

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