Здравствуйте fAX, Вы писали:
fAX>Нужен алгоритм.
fAX>Вход — двухмерный массив точек.
fAX>Выход — порядок обхода этих точек, исходя из следующих критериев:
fAX>
fAX> Минимальное расстояние. Под "расстоянием" имеется в виду "манхэттенское расстояние", т.е. dist (x, y, x1, y1) = abs(x — x1) + abs (y — y1). Ещё лучше, если расстояние по у будет в 2 (например) раза больше реального, или, в общем виде, dist (x, y, x1, y1) = M * abs(x — x1) + N * abs (y — y1).
fAX> Строго горизонтальное или строго вертикальное направление является приоритетным, сохраняя приоритет M:N.
fAX> Стараться избегать возвращения в точку, возле которой уже были после большого кол-ва шагов. (Это требование весьма низкоприоритетно и вытекает из того, что точность девайса не бесконечна и может быть погрешность, которая будет особенно заметна на замкнутых фигурах).
fAX>
fAX>Самое непонятное тут, как изначально организовать точки. Если какой-нибудь алгоритм (Форда, если не ошибаюсь) из теории графов для нахождения минимальных расстояний между всеми точками, то ему нужно O(n^3), а при входе O(10^5) это очень дорого, но в крайнем случае, подойдёт. Кроме того, как эффективно построить граф из массива точек.
fAX>Какие-то идеи?
fAX>Заранее спасибо,
fAX>fAX.
Очень похоже на задачу коммивояжера. Для решения этой задачи используется симплекс-метод.
Алгоритм Форда же предназначен для поиска кратчайших путей между всеми вершинами графа. Причем эти не обязательно проходят через все вершины.
Или я неправильно понял постановку?
