Здравствуйте 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>Какие-то идеи?
Точно говорю — должен быть человеческий алгоритим. Уж больно норма красивая. Так сходу в голову ничего не приходит, но попробую покумекать.
Чтобы обнадежить, могу рассказать байку про стандартную задачку, которую дают в НГУ математикам первого курса: дано множество точек на плоскости, надо построить окружность минимального радиуса, которая покрывает их все.
Классический подход: берем тройку точек, проводим окружность через них (очевидно, что искомая окружность будет проходить как минимум через три точки множества), проверяем, все ли внутри. полный перебор. Время работы ~N^4. Решения проверялисm на множествах в ~100 точек.
Мой друг, помогая человеку получить построил алгоритм, время работы которого ~N^N. Проверяли на множестве в 16000 точек.
Мораль: не все печальные теоремы бывают применимы в частном случае.В конкретной задаче могут найтись удачные ограничения, и решение будет намного эффективнее общего.
fAX>Заранее спасибо,
fAX>fAX.