#algorithm #recursion #dynamic-programming #greedy
#алгоритм #рекурсия #динамическое программирование #жадный
Вопрос:
Учитывая массив из пары точек, например
[19, 11], [11,44] ,[ 98,101], [44,98], [12,32],[44,12],[44,98],[98,101],[33,39]
Расположите массив так, чтобы конечная точка была равна началу следующей точки. Если оно не равно, то есть стоимость = 1. Мы должны минимизировать затраты. например, мы можем организовать вышесказанное следующим образом
[19,11],[11,44],[44,12],[12,32],[44,98],[98,101],[44,98],[98,101],[33,39]
итак, здесь стоимость [12,32],[44,98] = 1 [98,101],[44,98] = 1 [98,101],[33,39] = 1, так что итого = 3.
Я пробовал некоторое решение, которое сначала сопоставляет точные пары, а затем пытается сопоставить неточные пары, но я чувствую, что мой жадный подход не является оптимальным, и динамическое программирование может быть использовано для поиска некоторого оптимального решения.
Другой способ, который я считаю, состоит в том, чтобы подсчитать все возможные последовательности, но сложность очень высока n !.
Может ли кто-нибудь помочь мне придумать решение для динамического программирования
Ответ №1:
Я полагаю, что на самом деле это пример известной задачи коммивояжера. Это означает, что ваше решение не является оптимальным, а также не существует возможного оптимального решения за полиномиальное время. Хотя динамическое программирование, кажется, немного снижает временную сложность, оно по-прежнему NP-сложно.
Чтобы понять почему, нам нужно переформулировать эту проблему, используя теорию графов. Здесь каждая точка является узлом. Каждый узел (т. Е. точка) связан со всеми остальными через направленное взвешенное ребро стоимостью 1. За исключением случаев, когда конечное значение исходного узла совпадает с начальным значением соседнего узла, тогда вес ребра равен 0. Теперь создайте фиктивный начальный узел, который имеет прямое реберное соединение от него к каждому узлу, а также от каждого узла к нему.
Теперь, если вы запустите TSP с начального узла, вы получите желаемую последовательность с минимальными затратами.
Ответ №2:
Если бы мы должны были сформировать ориентированный граф, тогда проблема выглядела бы как проблема разбиения графа: найдите подходящее удаление ребер, чтобы оставить в каждой вершине не более одного входящего ребра и одного исходящего ребра, минимизируя при этом количество результирующих компонентов графа.
[19,11], [11,44], [98,101], [44,98], [12,32],
[44,12], [44,98], [98,101], [33,39]
33,39
44,98
⇗ ⇙ ⇘
⇗ 98,101 98,101
↑ ⇖ ⇗
19,11 -> 11,44 --> 44,98
↓
44,12 -> 12,32
Тогда результат был бы на единицу меньше, чем количество компонентов.
Может быть, поиск с обратным отслеживанием?
Комментарии:
1. Вы не возражаете написать какой-нибудь псевдокод или какой-нибудь реальный код для демонстрации вашей идеи?
2. @darksky представьте на текущем примере: допустим, мы поворачиваем направо (вниз) от 11,44; это разделило бы большой компонент на две части. Юго-восточный компонент был бы допустимым. Затем северо-западный компонент также разделился бы. Аналогичный результат по мощности был бы получен, если бы мы вернулись назад и сделали другой ход на 11,44. В общем случае, однако, компоненты, которые начинаются отдельно, будут иметь независимые поиски и решения; и если бы мы записали решения конкретных компонентов (подграфов), нам не нужно было бы повторять эти поиски (перекрывающиеся подзадачи).
3. @darksky почему ..? 🙂
4. Это сделало бы ваш аргумент более строгим, ясным и недвусмысленным и позволило бы всем следовать ему и анализировать его сложность во время выполнения. Не обязательно должен быть готовый к работе код, подойдет любой псевдокод. Это хорошее упражнение для вас, а также для углубления вашего собственного понимания.
5. @darksky Я серьезно рассмотрю вашу просьбу «пожалуйста, воплотите мое воображение в код», когда закончу рассматривать интересные способы решения проблемы разбиения графа, которую я описал. Тем не менее, я не думаю, что вы представили достаточно убедительный аргумент, чтобы я мог предложить код (или псевдокод). Формулировка разделения понятна. Способы подхода к этому разнообразны, и этот аспект ответа я оставил в некоторой степени совместным на данном этапе, закончив вопросительным знаком. Я буду рад ответить на вопросы, которые у вас могут возникнуть.