Изменить порядок строк с помощью алгоритма оценки сходства

Переупорядочивает набор строк { buzz, fuzz, jazz, fizz..} так, чтобы сумма оценок сходства между каждой парой соседних строк была наименьшей.

buzz-> fuzz (1)
fuzz-> jazz (2)
jazz-> fizz (2)

сумма баллов равна 5. Если переупорядочить на основе самого низкого (4), окончательный результат будет

{ buzz, fuzz, fizz, jazz..}

buzz-> fuzz (1)
fuzz-> fizz (1)
fizz-> jazz (2) 

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

То, как вы моделируете проблему, дает вам в основном en.wikipedia.org/wiki/Travelling_salesman_problem. Таким образом, это будет иметь экспоненциальное время выполнения (следовательно: это решение неэффективно). Однако я не могу придумать более эффективного способа решить эту проблему.

SaiBot 10.08.2018 16:37

Я считаю, что вы ищете кратчайший гамильтонов путь в полном графе. Посетите каждое слово или вершину один раз -> Гамильтонов путь. Каждое слово связано с каждым другим словом (с переменным весом) -> Полный график. Хорошие новости. Эта проблема хорошо известна. :) Плохие новости. Это NP-Complete. :( researchgate.net/publication/…

Mark Wistrom 10.08.2018 16:39

@SaiBot дал аналогичную проблему на собеседовании по кодированию, которое нужно закончить за 1 час. Я не был уверен, что то, что у меня было, является оптимальным решением. Хотел услышать мысли других, если что-то упустил.

Kar 10.08.2018 18:11

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

Matt Timmermans 10.08.2018 18:47

@MattTimmermans Я не хотел упоминать, что это было дано как есть на собеседовании по кодированию. Теперь я только что это сделал.

Kar 11.08.2018 03:18

Как измерить «сходство». См. Например Фонетические алгоритмы

axelclk 11.08.2018 19:15
0
6
73
0

Другие вопросы по теме