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

Question

Учитывая массив из пары точек, например,

[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!.

Может кто-нибудь помочь мне придумать решение для динамического программирования

Answer 1

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

[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

Результат будет тогда на единицу меньше, чем количество компонентов.

Может быть, поиск с возвратом?

Answer 2

Я полагаю, что это на самом деле пример известной проблемы с коммивояжером .Это означает, что ваше решение не является оптимальным, а также нет возможного оптимального решения за полиномиальное время.Хотя динамическое программирование , кажется, немного уменьшает временную сложность, оно все еще NP-Hard.

Чтобы понять почему, нам нужно переформулировать эту проблему с помощью теории графов.Здесь каждая точка является узлом.Каждый узел (т. Е. Точка) связан с любым другим через направленный взвешенный край со стоимостью 1. За исключением случаев, когда конечное значение исходного узла совпадает с началом соседнего узла, тогда вес края равен 0. Теперь создайте фиктивный начальный узел, который имеетпрямое граничное соединение от it до каждого узла, а также от каждого узла до it.

Теперь, если вы запустите TSP с начального узла, вы получите желаемую последовательность с минимальными затратами.