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

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

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 (Helsgaun 2009). Он включает в себя две модификации:

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

Обратите внимание, что 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 это своей вилке pytsp , которая передает ее решателю LKH. И все в порядке … кроме того, когда путь пересекает сам. Решения TSP не могут иметь замкнутые контуры, поэтому я всегда вижу открытый цикл справа:

Пути торговых продавцов

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

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

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

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

  • Необработанный файл данных NumPy
  • Упорядоченные данные Файл NumPy

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

Справка

К. Хельгаун, генерал k-opt, подготавливающий для эвристики TSP Лин-Кернигана. Математическое программирование, 2009, doi: 10.1007 / s12532-009-0004-6 .

One Solution collect form web for “Путешественник с направленным ограничением”

Судя по документации на pytsp, матрица расстояний не должна быть симметричной. Это означает, что вы можете изменить норму L2, чтобы включить информацию в предпочтительном направлении в эту матрицу. Скажем, у вас есть предпочтительное направление для некоторых пар точек (i, j), то для каждой из этих точек вы можете разделить dists[i,j] на (1+a) и умножить dists[j,i] на (1+a) сделать это направление более благоприятным. Это означает, что если ваш алгоритм обязательно найдет глобальный оптимум, вы можете заставить его удовлетворить свое предпочтительное направление, взяв a достаточно большим.

Кроме того, я не уверен, что невозможно иметь замкнутые контуры в решении, где матрица расстояний взята из трехмерных данных. Мне кажется, что «нет замкнутых циклов» является результатом (неравенства треугольника), специфичным для 2D.

 
Interesting Posts for Van-Lav

Интроспекция вложенных (локальных) функций данной функции в Python

Юникод печати Python не отображает правильные символы

python работает на бесконечном процессе

Python PyQt на macOS Sierra

Печать значений (весов) для всех dtype = float32 в Tensorflow

Как вызвать методы на объектах дескриптора класса Python?

Как я узнаю, что раньше я даю научиться sci-kit? (Классификаторы наивных заливов).

Модуль трассировки и файловые пути Python

Как создать экспоненциально увеличивающийся диапазон в Python

UnicodeDecodeError: кодек 'utf8' не может декодировать байт 0xa5 в позиции 0: недопустимый стартовый байт

Можно ли использовать Lisp / Scheme в качестве языка сценариев?

Преобразование объекта Pandas GroupBy в DataFrame

Matplotlib boxplot с использованием предварительно рассчитанной (сводной) статистики

Пользователи @Rails: вы пробовали web2py? Плюсы? Минусы?

Подклассификация Tkinter для создания пользовательского виджета

Python - лучший язык программирования в мире.