Как найти кратчайший путь между точками на плоскости

Question

Есть допустим сколь угодно точек на плоскости, и как понять, какой наикоротейший путь огнуть их всех? Просто идти к ближайшей раз за разом?

Answer 1

Самый прямой и топорный способ - такой: выписать все перестановки данных точек, за исключением симметричных, то есть, таких, для которых точки расположены в обратном относительно данной перестановки порядке (например, если даны четыре точки, то для перестановки ABCD симметричной ей будет перестановка DCBA, в данной задаче считается, что это - одна и та же перестановка) . Таким образом, всего таких перестановок для n точек будет n! /2 (для каждой перестановки существует одна, симметричная ей) . Затем найти длину каждой ломаной, узлы которой расположены в том порядке, как в данной перестановке (очевидно, симметричная перестановка будет иметь ту же длину) . Получится n! /2 чисел, среди которых нужно просто выбрать наименьше. Это и будет ответ.