Я пытаюсь создать одну непрерывную линию из набора линий, определенных двумя точками.
В настоящее время я генерирую подмножество случайных строк следующим образом:
[[0, 0] [2, 2], [2, 1] [0, 1], [0, 1] [2, 2], ...]
Затем я хочу провести вдоль этих линий, чтобы сделать максимально длинный непрерывный путь. Поскольку таких линий может быть от сотен до тысяч, некоторые в конечном итоге не будут подключены, и это нормально. Причина в том, что они могут иметь следующие свойства друг от друга:
- Та же отправная точка
- Та же самая конечная точка
- Одинаковая начальная и конечная точка
Полученный результат будет выглядеть как матрица, которая отслеживает оптимальный путь, который следует выбрать, например:
[[0, 0], [2, 2], [0, 1], [2, 1]]
Мне не важно оптимизировать длину пути (потому что длина уже будет предопределена общей длиной созданных линий), но я бы хотел минимизировать количество точек разрыва. Также непрерывная линия не должна начинаться и заканчиваться в одной и той же позиции.
Кодирование на python. Я изначально начал с руководства здесь Я могу использовать массив массивов в качестве моих "городов". Я не уверен, что это лучший метод, поскольку он пытается уменьшить расстояние. Поэтому я чувствую, что может быть аналогичная проблема для анализа данных генетического секвенирования; иметь много фрагментов, которые должны быть выровнены, чтобы сформировать непрерывный участок ДНК.
В конечном итоге я ищу любые предложения по выравниванию этих путей в одном непрерывном отрезке с использованием ранее опубликованных пакетов python. В конце концов, если я сам напишу это, я опубликую свои результаты здесь.