Я пытаюсь создать программу, которая будет определять кратчайшее возможное общее расстояние между несколькими строками, включая сами строки. Я ранее сделал программу для этого, но понял, что вычисление с помощью грубой силы нереально c для любого значительного количества строк. Надеюсь, что приведенный ниже снимок экрана иллюстрирует то, что я пытаюсь сделать. Черные линии - это элементы пути, которые необходимо включить в самый быстрый путь. Красная линия - это самый быстрый маршрут между ними.
Я возился с созданием собственных алгоритмов, но я не могу увеличить производительность программы намного больше, чем показано ниже. Есть ли у кого-нибудь предложения по пакету, который мне следует изучить? Я видел много разговоров о таких вещах, как A *, но, судя по всему, я не думаю, что это вполне подходит для этой задачи.
Тем не менее, я задумался о создании своего рода лабиринта, где прямо Паяные линии состоят из трех точек и окружены препятствиями, так что единственный способ их припаять - также go через две другие точки. Но это все равно будет включать в себя несколько пунктов назначения, что, на мой взгляд, не подходит для A *.
С этой точки зрения это больше похоже на задачу коммивояжера, но ответы на этот вопрос, которые я видел, не включают необходимость проезда по определенным маршрутам.
Как видите судя по изображению, я сделал подходы, основанные на грубой силе, ближайшем соседе (что не очень хорошо решает проблему) и попытался разработать вероятностный метод c, но он все еще очень ограничен.
