Путешественник с направленным ограничением

Я пытаюсь упорядочить массив трехмерных координат по их порядку вдоль пути. Образец:

points = np.array([[ 0.81127451,  0.22794118,  0.52009804],
                   [ 0.62986425,  0.4546003 ,  0.12971342],
                   [ 0.50666667,  0.41137255,  0.65215686],
                   [ 0.79526144,  0.58186275,  0.04738562],
                   [ 0.55163399,  0.49803922,  0.24117647],
                   [ 0.47385621,  0.64084967,  0.10653595]])

Точки находятся в случайном порядке, но между ними всегда есть один путь. Я нахожу путь с адаптированной проблемой коммивояжера (TSP), используя LKH solver (Helsgaun 2009). Он включает в себя две модификации:

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

Обратите внимание, что TSP не включает положение, а только расстояния между узлами. Поэтому решатель "знает" (или заботится) о том, что я работаю в 3D. Я просто делаю матрицу расстояний следующим образом:

import numpy as np
from scipy.spatial.distance import pdist, squareform

# Add a point near the origin.
points = np.vstack([[[0.25, 0, 0.5]], points])
dists = squareform(pdist(points, 'euclidean'))

# Normalize to int16s because the solver likes it.
d = 32767 * dists / np.sqrt(3)
d = d.astype(np.int16)

# Add a point that is zero units from every other point.
row, col = d.shape
d = np.insert(d, row, 0, axis=0)
d = np.insert(d, col, 0, axis=1)

Я передаю это мою вилку pytsp, которая передает ее в решатель LKH. И все в порядке... кроме того, когда путь пересекает сам. Решения TSP не могут иметь замкнутые контуры, поэтому я всегда вижу открытый цикл, показанный здесь:

Обратите внимание, что это аналогичная 2D-версия моей ситуации. Заметим также, что точки неровно выровнены даже вдоль "прямых" бит.

Итак, мой вопрос: как я могу помочь решателю сохранить направление пути, когда это возможно? У меня две неправильные идеи, но до сих пор не удалось ничего реализовать:/p >

Используйте другую метрику вместо L2. Но я не думаю, что это может сработать, потому что на данном стыке нет ничего по-разному в отношении "неправильной" точки. Его неправильность зависит от предыдущей точки. И мы еще не знаем, что такое предыдущий момент (что мы пытаемся выяснить). Поэтому я думаю, что это нехорошо.
Оцените локальную коллинеарность каждого множества из трех точек (например, используя определитель каждой тройки). Модифицируйте локальный "3D-угол" (не уверен, что я имею в виду) благодаря этому коэффициенту коллинеарности. Дайте каждой точке другое измерение, выражающее это локальное выравнивание. Теперь норма будет отражать локальное выравнивание и (надеюсь) грубо говорящие коллинеарные вещи объединятся.

Я поставил эти файлы в Dropbox:

Спасибо за чтение; любые идеи оценили.

Ссылка

К. Helsgaun, General k-opt для подражания для эвристики TSP Lin-Kernighan. Математическое программирование, 2009, doi: 10.1007/s12532-009-0004-6.

Ссылка

Ответ 1