В 2D плоскости n точек. Робот хочет посетить их все, но может двигаться только горизонтально или вертикально. Как он должен посетить их всех, чтобы общее расстояние, которое он преодолевал, было минимальным?
Это задача коммивояжера , где расстояние между каждой парой точек равно | y2-y1 | + | x2-x1 | (называется прямолинейным расстоянием или Манхэттенским расстоянием ). Это NP-hard , что в основном означает, что не существует известного эффективного решения.
Методы ее решения в Википедии.
Простейшим алгоритмом является наивный поиск методом грубой силы, где вы вычисляете расстояние для каждой возможной перестановки точек и находите минимум. Это имеет время работы O (n!). Это будет работать примерно до 10 баллов, но очень быстро станет слишком медленным для большего количества баллов.