Учитывая набор точек в 2d системе координат, как рассчитать минимальное расстояние и путь, если мы посетим все точки только один раз?

Question

Предельные условия являются следующими:

1. Устанавливается фиксированный порог, при котором расстояние, превышающее порог, рассчитывается самим расстоянием, а расстояние, меньшее или равное расстоянию, рассматривается какпостоянное значение;

2. Лучше, чтобы путь увеличивался с координатами x (то есть p1.x <= p2.x <= ... <= pn.x), но сначала рассматривается условие.1, затем условие.2; </p>

3. Мы можем посетить каждую точку только один раз.

Answer 1

Примечание для оптимизации: Итак, в основном это кратчайший гамильтонов путь с 2 поворотами (условие 1 и 2). Учитывая, что кратчайшее HP можно решить с помощью алгоритма Traveling Salesman (с фиктивным городом с нулевым расстоянием от всех остальных), для лучшего оптимизированного решения вы можете попробовать манипулировать вашей матрицей расстояний в соответствии с условием 1, прежде чем подавать ее в алгоритм TSP. Подробнее о том, как использовать TSP для этого кратчайшего HP здесь .

Метод грубой силы

Я собираюсь назвать ваши очки [A, B, ... C] для удобства чтения. Давайте представим наши точки следующим образом:

+---+---+---+
|   | X | Y |
+---+---+---+
| A | 0 | 0 |
| B | 4 | 3 |
| C | 0 | 3 |
+---+---+---+

Затем создайте матрицу расстояний с помощью теоремы Пифагора:

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 5.00 | 3.00 |
| B | 5.00 | 0.00 | 4.00 |
| C | 3.00 | 4.00 | 0.00 |
+---+------+------+------+

Мое понимание вашего первого состояния (фиксированного порога) заключается в том, что любое расстояние ниже определенного значения считается нулевым. Примените это условие к матрице расстояний (скажем, в нашем случае это 3,50).

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 5.00 | 0.00 |
| B | 5.00 | 0.00 | 4.00 |
| C | 0.00 | 4.00 | 0.00 |
+---+------+------+------+

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

+------+-----------+--------------+
| Path | Distances | Total Length |
+------+-----------+--------------+
| ABC  | 5+4       |            9 |
| ACB  | 0+4       |            4 |
| BAC  | 5+0       |            5 |
| BCA  | 4+0       |            4 |
| CAB  | 0+5       |            5 |
| CBA  | 4+5       |            9 |
+------+-----------+--------------+

Удалить те же маршруты, но обратные.

+------+-----------+--------------+
| Path | Distances | Total Length |
+------+-----------+--------------+
| ABC  | 5+4       |            9 |
| ACB  | 0+4       |            4 |
| BAC  | 5+0       |            5 |
+------+-----------+--------------+

Возьмите самую короткую по общей длине, и это ваше решение.

2-е условие - расстояние, пройденное по X, предпочтительнее, чем расстояние, пройденное по Y

Насколько я понял, это условие активируется только при наличии связи в общей длине. В этом случае создайте матрицу расстояний, используя абсолютное значение разницы в координатах X точек:

+---+------+------+------+
|   |  A   |  B   |  C   |
+---+------+------+------+
| A | 0.00 | 4.00 | 0.00 |
| B | 4.00 | 0.00 | 4.00 |
| C | 0.00 | 4.00 | 0.00 |
+---+------+------+------+

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