Преобразование неориентированного графа в оптимальные пути G-кода

Цитата комментария R.. GitHub STOP HELPING ICE по вопросу гласит:

Почти уверен, что это NP-полная задача (эквивалентная задаче коммивояжера), не так ли? –

Это правильно; это оптимизация маршрута в чистом виде и ни в коем случае не новая проблема. Вы хотите пройти кратчайшее общее расстояние между всеми вершинами того, что по сути является полностью взаимосвязанным графом; нет никаких врожденных ограничений на переход из любого места в любое место. TSP-это общая постановка этой задачи, на которой ваша задача специализируется лишь немного, предопределяя определенные движения вдоль ребер как необходимые в конечном пути (но эти ребра могут быть пройдены в любом направлении и в любом порядке.

Что делает этот комплекс на его лице, так это огромное количество возможностей, которые должно оценить исчерпывающее решение TSP, такое как Hold-Karp. У вас нет никаких реальных ограничений относительно того, между какими точками перемещаться; вы можете перемещаться из любого места, куда угодно. Только относительно небольшое количество ребер (ваши экструзионные линии) являются известными реквизитами, и они теоретически могут быть прослежены в любом порядке.

Если я читаю свой график правильно, вы начинаете в верхнем центре, а затем идите в левый верхний, затем в S-образной кривой, затем перейти к главному, и пересекая его с "правой рукой", поворачивая вниз через "тело" и "левая нога" Центрального форму, далее на "правое бедро", через ногу на ногу, потом обратно на "левое плечо", через "руки" и т. д.

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

Во всяком случае, ваш алгоритм довольно хорошо справлялся с выбором пути, пока не закончил рисовать "правую ногу". Наиболее эффективным движением оттуда было бы перейти к нижней части фигуры "Y" справа от главной фигуры и проследить через нее. Когда это будет сделано, ближайший непрорисованный отрезок линии вернется к левому плечу главной фигуры, что приведет вас к маленьким точкам, и вы закончите в этой области с относительно небольшими перемещениями. В целом, я думаю, что стратегия "ближайшей оставшейся конечной точки" будет почти оптимальной на каждом шагу; когда вы достигнете конца нарисованной линии, ищите конечную точку, которая ближе всего к вашему текущему местоположению. Он будет принимать большинство решений, которые принимает ваш существующий алгоритм, и несколько лучших. Это не всегда лучший выбор (например, точка в левом верхнем углу, которая никогда не находится ближе всего к концу любого другого хода и поэтому будет игнорироваться до тех пор, пока не останется последней), но чаще всего это так.

Мой опытный программист говорит, что у вас также есть рекурсивная трассировка пересечений ("хождение по деревьям"); алгоритм видит, что существует несколько путей для рисования из одной точки, запоминает эту точку и затем выбирает путь. Когда он достигает конца цепочки вытянутых линий, он возвращается к самому последнему встреченному пересечению, повторно оценивает доступные пути и выбирает следующий, пока не будут вычерчены все пути из этого пересечения. Затем вы переходите обратно к предыдущему перекрестку и так далее в рекурсивной манере LIFO.

Хотя это также, как правило, разумный способ приблизиться к нему, он делает пару явно неэффективных движений, например, от "правой ноги" главной фигуры обратно к "плечу" (которое является самым последним пересечением, посещенным, но не полностью нарисованным к этой точке). Более эффективный ход-это просто ближайшая оставшаяся конечная точка, нижняя часть шаткого на вид Y справа от главной фигуры.

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

Теперь, нарисовав "левую руку" главной фигуры, я совершенно не понимаю, почему ваш алгоритм решил пересечь график, чтобы нарисовать шаткий Y, а затем снова перейти на левую сторону. Это, безусловно, наименее эффективный ход, который он делает, и тот, который вы, вероятно, указываете на себя. Наиболее эффективный путь от конца левого плеча главной фигуры, учитывая то, что осталось нарисовать,-это прямая ближайшая конечная точка, заполняющая точки и линии с левой стороны, а затем делающая одно движение по графику к шаткому Y. Ближайшая конечная точка на самом деле уже заполнила бы этот Y, как описано ранее, и вы закончили бы свой обход графика в левой области точек и маленьких линий. У вас может быть один или два относительно неэффективных хода между углами этой области слева от графика в зависимости от вычисления ближайшей точки, но они незначительны по сравнению с ходами, сделанными поперек графика. Если ваш алгоритм выдает детерминированные результаты для этого графика, я бы отладил его, перешел бы к этой точке и выяснил, почему он считает эту последовательность предпочтительнее. Оптимизация этого решения вполне может быть ключом к почти оптимальной общей стратегии хождения по графам.