[koui]

Добрый день.
ни у кого нет случайно Лиспа, который, так скажем, решает задачу коммивояжера, а именно, обходит все блоки полилинией по кратчайшему пути? было бы здорово, если бы была опция ещё и выбора: с возвратом в исходную точку или без. нигде ничего подобного найти не смог.

[Сергей812]

прокладывать методом коммивояжёра трассы между устройствами - имхо, не самая лучшая идея)

[koui]

Сообщение от Сергей812 прокладывать методом коммивояжёра трассы между устройствами - имхо, не самая лучшая идея)

мне важно видеть решение, иногда оно вообще не очевидно. а уже по нему в голове проще складывается полная картина. это быстрее, чем сделать несколько вариантов прежде, чем понять, как всё-таки это сделать оптимально.

[Сергей812]

Сообщение от koui мне важно видеть решение, иногда оно вообще не очевидно. а уже по нему в голове проще складывается полная картина. это быстрее, чем сделать несколько вариантов прежде, чем понять, как всё-таки это сделать оптимально.

и как алгоритм коммивояжёра справится, например с цепью трасса + ответвления типа звезды либо трасса древовидного вида? Видел где-то попытки реализации автопрокладки с первоначальным заданием общих трасс-направлений - т.е. сразу накладываются ограничения на направления трасс от конечных устройств. А чтобы выделили блоки и программа сама нарисовала что-то похожее на тот же шлейф - если проектировщики с опытом не всегда сразу выбирают трассу, то чего ожидать от программы)

[SetQ]

А сколько блоков в схеме? От этого зависит алгоритм - итерационный или прямой.

[koui]

Сообщение от Сергей812 и как алгоритм коммивояжёра справится, например с цепью трасса + ответвления типа звезды либо трасса древовидного вида? Видел где-то попытки реализации автопрокладки с первоначальным заданием общих трасс-направлений - т.е. сразу накладываются ограничения на направления трасс от конечных устройств. А чтобы выделили блоки и программа сама нарисовала что-то похожее на тот же шлейф - если проектировщики с опытом не всегда сразу выбирают трассу, то чего ожидать от программы)

алгоритм не будет ничего решать, он просто покажет техническую информацию, которая поможет в принятии решения.

----- добавлено через 25 сек. -----

Сообщение от SetQ А сколько блоков в схеме? От этого зависит алгоритм - итерационный или прямой.

обычно от 20 до 100.

[Сергей812]

Сообщение от koui алгоритм не будет ничего решать, он просто покажет техническую информацию, которая поможет в принятии решения.

какую техническую информацию? Рисунок из отрезков, соединяющих геометрические центры блоков по кратчайшему пути? На какой-то части чертежа они совпадут с будущей трассой, конечно. Но учитывать строительные и иные конструкции не будут, просто потому что об них не знает алгоритм.

[SetQ]

Сообщение от koui обычно от 20 до 100.

Можно придумать, как провести замкнутую линию без самопересечений, не обязательно самую короткую из возможных, нужна?

[koui]

Сообщение от Сергей812 какую техническую информацию? Рисунок из отрезков, соединяющих геометрические центры блоков по кратчайшему пути? На какой-то части чертежа они совпадут с будущей трассой, конечно. Но учитывать строительные и иные конструкции не будут, просто потому что об них не знает алгоритм.

нет, даже частично они не совпадут с трассой по одной простой причине - трассу я в любом случае буду перечерчивать, потому как проще и быстрее начертить заново, чем поправить то, что есть.

----- добавлено через ~1 мин. -----

Сообщение от SetQ Можно придумать, как провести замкнутую линию без самопересечений, не обязательно самую короткую из возможных, нужна?

было бы интересно затестить. возможно, очень даже подойдёт, а если без пересечений, то и жуткого отклонения не будет.

[Сергей812]

Сообщение от koui нет, даже частично они не совпадут с трассой по одной простой причине - трассу я в любом случае буду перечерчивать, потому как проще и быстрее начертить заново, чем поправить то, что есть.

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

[SetQ]

Вот цикл Гамильтона, надо выбрать рамкой несколько блоков в чертеже. Программа попутно удаляет (из обработки) дубликаты - блоки с одинаковой точкой вставки и каждый раз перетасовывает список точек, поэтом результат при большом числе вершин каждый раз разный.

[koui]

Сообщение от SetQ Вот цикл Гамильтона, надо выбрать рамкой несколько блоков в чертеже. Программа попутно удаляет (из обработки) дубликаты - блоки с одинаковой точкой вставки и каждый раз перетасовывает список точек, поэтом результат при большом числе вершин каждый раз разный.

ого, лютая вещь! такое чувство, что иет максимальное расстояние ))) если зациклить на 10000 раз, а потом среди 10000 элементов найти кратчайший, может, тогда и прокатит))) но я не смогу такое реализовать. но всё равно, большое спасибо!

[kacugu]

Можно попробовать так:
1. Извлекаете данные блоков в excel
2. Решаете там задачу (рещения вроде находятся/гуглятся)
3. По полученным данным строите полилинию (лисп построения полилинии по координатам вроде был здесь на сайте)

[Сергей812]

Сообщение от koui если зациклить на 10000 раз, а потом среди 10000 элементов найти кратчайший, может, тогда и прокатит))) но я не смогу такое реализовать. но всё равно, большое спасибо!

в лоб: на отдельном вспомогательном слое построить 10000 полилиний (просто вызвав данный выше лисп как функцию), выгрести по фильтру в виде имени слоя все эти полилинии, найти среди них одну с минимальной длиной, а остальные удалить.

[zamtmn]

Если интересно решение не в автокаде, могу попробовать сделать в зкаде, уже с учетом трасс