[NEDIS]

Доброго времени суток коллеги.
Хочу поделиться наработками по программке.
Сразу хочу попросить сильно меня не пинать в плане грамотности написания кода, начал изучать LISP только с весны этого года, благодаря dwg.ru. Наверняка я наделал неподъемную кучу косяков, поэтому очень рад буду выслушать рекомендации по оптимизации и рад буду любой оказываемой помощи.
Хочу выразить благодарность всем чьи наработки я использовал в частности: Кулику Алексею (aka kpblc), VVA и hwd (и остальных участников форума, кого я забыл упомянуть в силу своей некомпетентности).

Алгоритм Флойда (Проба пера).
Немного о содержимом:
1. Два файла Lisp Команды и Функции
2. DWG файл с планировками и тестовыми закладными устройствами «скелетами» по которым выполняется трассировка полилиниями.
3. Команды:
a. NEDIS-input-system-for-tracing – Команда создает набор примитивов по которым будет выполняться трассировка, обрабатывает эти примитивы и выдает конечные матрицы для трассировки.
b. NEDIS-tracing-point-to-point - Трассировка точка-точка (выбор пользователя).
4. Функции:
a. NDS-start-finish-for-Floyd - Находит ближайший примитив, точку пересечения с ним и узлы для трассировки
b. NDS-manipulation-for-Floyd - Создает определенного вида списки для дальнейшей обработки функцией NDS-solution-matrix-Floyd (Работает только с LWPOLYLINE и LINE)
c. NDS-solution-matrix-Floyd - Создает и решает матрицу Флойда и матрицу маршрутов (алгоритм взят от сюда http://khpi-iip.mipk.kharkiv.edu/lib.../din_0124.html )
d. NDS-tracing - Выполняем трассировку (т.е. находим кротчайший путь по matrica-route-end, проверяя возможность такого пути по matrica-floyda-end (не должен рассматриваемый элемент быть равен "NO") получаем список узлов оптимального маршрута)
e. dwgru-geom-point-on-line - Проверяет принадлежность точки отрезку
f. pln - Создает полилинию по списку вершин lst, c - nil/T - разомкн/замкнт или '(с слой цвет)
5. Логику работы программ объяснять не буду, старался внутри все пояснять. По мере обсуждения буду «повествовать» почему делал так.
6. Основная проблема кроется в функции NDS-solution-matrix-Floyd шибко долго она решает Вариант 1 планировки. Вообщем-то это и понятно, так как чем больше точек для построения матрицы Флойда тем больше циклов оня будет проделовать (а их три и они все внутри друг друга). Над оптимизацией сам не работал, сильно загружен по работе.

Алгоритм Дейкстры (Проба пера-2).
Оказался наиболее шустрым.
Некоторые нюансы:
1. Иногда вылетает ошибка типа переменной (непосредственно уже при трассировке) – думаю где-то намутил с обработкой списков (не разбирался), надеюсь с помощью однофорумчан ее решить.
2. Полилиния не должна сама себя пересекать, функция не увидит такую точку пересечения и, как следствие, не будет создано корректное разрешение для этой точки
Отличая от предшественника:
1. Взамен NDS-manipulation-for-Floyd пришел NDS-manipulation-for-Dijkstra с соответствующими доработками, сильно его не менял – времени нету, но укоротить код можно прилично для быстродействия.
2. По замечаниям более опытных коллег убрал лишние setq.
3. NDS-solution-Dijkstra – создает разрешения для точек (от куда куда можно) все загоняет в одномерный массив (список).
4. NDS-tracing-all-in-one – функция определяет из 4-х вариантов трасс (1 – стартовая точка, ближайший узел справа от стартовой точки, … , ближайший узел справа от финишной точки, финишная точка; 2 - стартовая точка, ближайший узел слева от стартовой точки, … , ближайший узел справа от финишной точки, финишная точка; и т.д) наиболее короткую.

Ну вот такой винегрет получился .

[Дима_]

Сообщение от ShaggyDoc Вообще про "математические методы" забыть.

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

[ShaggyDoc]

Сообщение от Дима_ Вот с этим - рассматривая оптимизацию - согласиться трудно. Просто надо правильные использовать. По сути, то, что делает "тетка" тоже метод - вероятностный.

А я "математические" в кавычках написал. Часто сталкиваюсь, что под ними понимают то, что в учебниках написано. Просто "тетка" не знает названия того, что делает.

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

Использовать надо вычислительные методы. Для конкретных программных возможностей.

Поиск кратчайшего пути разными способами выполняется. Есть много отработанных алгоритмов. В том числе не "математических".

[NEDIS]

Сообщение от ShaggyDoc Вот в этом и "корень зла". Матрица ведь не сама "знает". Её надо заполнить - по большей части заведомо ненужными данными. А потом их анализировать. И всё это в многочисленных циклах...

На выходных постараюсь реализовать следующий метод http://inf.1september.ru/2000/7/art/danil.htm "3. Бектрекинг на графе, заданном перечислением вершин и ребер". Никаких вложенных циклов и матриц тем более, вроли комнат буду выступать имена примитивов вида <Имя объекта: 7ef54b70>. Надеюсь все будет шустро методом "Проб и ошибок", так сказать погуляем по "скелету". Единственное - это надо будет делать на каждой итерации трассировки.

P.S. Не помню ... есть какая-нибудь LISP-функция, которая находит все примитивы пересекаемые с заданным ?

[Дима_]

Сообщение от NEDIS P.S. Не помню ... есть какая-нибудь LISP-команда, которая находит все примитивы пересекаемые с заданным ?

в прямую нет, но можно взять границы примитива (vla-getboundingbox...) и по этим точкам отсечь рамкой, далее отфильтровать набор через (vla-intersectwidth...) но это только при условии нечастого использования - ибо если в цикле - каждая такая итерация - достоточна ресурсоемка.

[ShaggyDoc]

NEDIS, в дополнение к алгоритму стоит подумать о порядке ввода точек (комнат). Это математически они могут быть как угодно перемешаны, а в реальном объекте они группируются. Например, ответвление "коридора", или "этаж".

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

И конкретную задачу лучше бы уточнить. Все-таки "две больших разницы" поиск кратчайших маршрутов и

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

Здесь все проще. Трасса каналов задана. Её автоматически не проложишь - масса "непрограммируемых" условий. А вот нарисовать каждую линию от шкафа до каждого порта гораздо легче. Заодно длины рассчитать и прочее.

Я сам такое делал.

[NEDIS]

Сообщение от ShaggyDoc Трасса каналов задана. Её автоматически не проложишь - масса "непрограммируемых" условий.

Именно так трасса каналов задана и только после этого выполняется автоматическая трассировка "порт - шкаф"

[ShaggyDoc]

Сообщение от NEDIS Именно так трасса каналов задана и только после этого выполняется автоматическая трассировка "порт - шкаф"

Тогда зачем вся эта математика? Описываете геометрию трассы, как это принято во всяких гидравлических расчетах:

1. Обозначаете как-то все порты и точки "перекрестков" (можно, для простоты, целыми числами, хотя удобнее "по-человечески", прямо обозначениями портов).

2. Описываете топологию сети - какая точка с какой соединяется. Вот здесь простор для фантазии. Хотя, с учетом того, что в СКС не разветвлений, это легче - можно легко описать маршруты.

3. Вычисление координат каждого маршрута. Сначала, для простоты, берете осевую линию трассы. А потом для каждого кабеля с учетом смещения на некоторое расстояние, лучше на реальное - порядка 5 мм. Можно с учетом габарита канала, в несколько ярусов. Здесь можно и постараться избежать повторных расчетов участков с несколькими кабелями.

4. Рисование каждого кабеля полилинией. Если надо - присоединение информации (окуда, куда и прочее) в виде расширенных данных для каких-то других расчетов.

[zamtmn]

>>Тогда зачем вся эта математика? Описываете геометрию трассы, как это принято во всяких гидравлических расчетах:

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

[NEDIS]

Сообщение от zamtmn единственное место для полета фантазии - как представить граф средствами лиспа и нарисовать примитивами автокада.

Абсолютно согласен. Без построения графа (двумерной матрицы) и ее решения в поиске оптимального (наикротчайшего) пути не обойтись.

Сообщение от ShaggyDoc Тогда зачем вся эта математика? Описываете геометрию трассы, как это принято во всяких гидравлических расчетах:

Так я ее и описываю - графом которой потом решаю.

[zamtmn]

>>Без построения графа (двумерной матрицы) и ее решения в поиске оптимального (наикротчайшего) пути не обойтись.

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

[NEDIS]

Сообщение от zamtmn >>Без построения графа (двумерной матрицы) и ее решения в поиске оптимального (наикротчайшего) пути не обойтись. если я правильно понял двумерная матрица получится размера кол-во узлов X кол-во узлов? это очень неэкономично - связей мало, соответственно матрица почти вся заполнена нулями. лучше 2 одномерных массива, один узлы (+возможно примыкающие связи), другой связи с примыкающими узлами и весами

И как найти оптимальную (самую короткую) трассу без связей i-узла с j-узлом по двум одномерным массивам? Скорее всего методом перебора всех возможных трасс и выбора из них самого короткого, на это тоже (в случае сложного скелета) уйдет куча времени.

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

[Дима_]

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

Можно - по хорошему переменных быть не должно вообще - в твоем коде прослеживаеться "не правильный" подход - изменение переменной внутри цикла - по хорошему функция не должна обращаться ни к каким "внешним" переменным - тем более для их установки - есть аргументы, есть возврат. В автолиспе с рекурсией надо быть внимательным - т.к. не поддерживаеться т.н. "хвостовая рекурсия"; при начальном уровне для "многовложенных" функций, как правило, проще mapcar, хотя рекурсия безусловно более функциональна. Если есть сложность с построением - напиши разберем.

[Sleekka]

трассировка http://ru.wikipedia.org/wiki/%D0%A2%...D0%B8%D1%8F%29
достаточно общее понятие, можно вкратце объяснить, что в этой программе трассируется, для какой отрасли?

[zamtmn]

>>И как найти оптимальную (самую короткую)
>>трассу без связей i-узла с j-узлом по двум одномерным массивам?

это алгоритм Дейкстры - http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры. реализация данного алгоритма на паскале работает без видимых задержек на сложных трассах (в разумных пределах - проверено на разделах ОПС довольно сложных зданий).

[NEDIS]

Сообщение от Дима_ Если есть сложность с построением - напиши разберем.

Вот с чем основная загвостка:

Код:

[Выделить все]

(setq num1 0 num2 0 num3 0)
	(setq matrica-floyda-end matrica-floyda-start matrica-route-end matrica-route-start)
	; num1 - k, num2 - i, num3 - j 
	(while
		(<= num1 (- (length spisok-vershin+X) 1))
		(setq num2 0)
		(while
			(<= num2 (- (length spisok-vershin+X) 1))
			(setq num3 0)
			(while
				(<= num3 (- (length spisok-vershin+X) 1))
				(if
					(and (/= num1 num2) (/= num2 num3) (/= num1 num3))
					(if
						(or
							(and
								(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num1)) matrica-floyda-end)) "NO")
								(/= (cadr (assoc (strcat (itoa num1) "-" (itoa num3)) matrica-floyda-end)) "NO")
								(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num3)) matrica-floyda-end)) "NO")
								(>
									(cadr (assoc (strcat (itoa num2) "-" (itoa num3)) matrica-floyda-end))
									(+
										(cadr (assoc (strcat (itoa num2) "-" (itoa num1)) matrica-floyda-end))
										(cadr (assoc (strcat (itoa num1) "-" (itoa num3)) matrica-floyda-end))
									)
								)
							)
							(and
								(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num1)) matrica-floyda-end)) "NO")
								(/= (cadr (assoc (strcat (itoa num1) "-" (itoa num3)) matrica-floyda-end)) "NO")
								(= (cadr (assoc (strcat (itoa num2) "-" (itoa num3)) matrica-floyda-end)) "NO")
							)
						)
						(setq
							matrica-floyda-end
							(subst
								(list
									(strcat (itoa num2) "-" (itoa num3))
									(+
										(cadr (assoc (strcat (itoa num2) "-" (itoa num1)) matrica-floyda-end))
										(cadr (assoc (strcat (itoa num1) "-" (itoa num3)) matrica-floyda-end))
									)
								)
								(assoc (strcat (itoa num2) "-" (itoa num3)) matrica-floyda-end)
								matrica-floyda-end
							)
							matrica-route-end
							(subst
								(list
									(strcat (itoa num2) "-" (itoa num3))
									(itoa num1)
								)
								(assoc (strcat (itoa num2) "-" (itoa num3)) matrica-route-end)
								matrica-route-end
							)
						)
					)
				)
				(setq num3 (+ num3 1))
			)
			(setq num2 (+ num2 1))
		)
		(setq num1 (+ num1 1))
		(princ (strcat "\nПриступил к решению матриц Флойда и Маршрутов. Решено --> " (itoa (/ (* 100 (+ num1)) (- (length spisok-vershin+X) 1))) " %\n"))
	)

Вот что я набросал для внутреннего цикла num3 (типо рекурсивная функция) - естественно не работает :

Код:

[Выделить все]

(defun NDS-recursion-num3 (num1 num2 num3 spisok-vershin+X matrica-floyda-end)
	(if
		(= num3 0)
		matrica-floyda-end
		(if
			(or
				(and
					(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num1)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(/= (cadr (assoc (strcat (itoa num1) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(>
						(cadr (assoc (strcat (itoa num2) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
						(+
							(cadr (assoc (strcat (itoa num2) "-" (itoa num1)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
							(cadr (assoc (strcat (itoa num1) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
						)
					)
				)
				(and
					(/= (cadr (assoc (strcat (itoa num2) "-" (itoa num1)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(/= (cadr (assoc (strcat (itoa num1) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
					(= (cadr (assoc (strcat (itoa num2) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))) "NO")
				)
			)
			(subst
				(list
					(strcat (itoa num2) "-" (itoa num3))
					(+
						(cadr (assoc (strcat (itoa num2) "-" (itoa num1)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
						(cadr (assoc (strcat (itoa num1) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)))
					)
				)
				(assoc (strcat (itoa num2) "-" (itoa num3)) NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end))
				NDS-recursion-num3 (num1 num2 (- num3 1) matrica-floyda-end)
			)
		)
	)
 )

[Дима_]

Не вникая что такое матрица флойда - смотрю твой рекурсивный пример:
1. (= num3 0) -> (zerop num3);
2. (if (or (and много вычислений)
(and мало вычислений)
); конец or
я не вникал, но вначале надо проверять то, что более вероятно является условием выхода и если равновероятно - то начинать надо с меньшего кол-ва вычислений (быстрее).
3. NDS-recursion-num3 ..... -> забыт запуск функции - нет "(" она видимо перед num1
4. у функции 5 аргументов а вызываешь ты ее с 4 (даже если ошибку с "фуyкцией" num1 убрать - а вобще сейчас 1 получаеться).
5. если у тебя num1 и num2 внутри этой функции не меняются, то зачем на них все время одинаковые вычисления (itoa) делать одного раза будет достаточно.
6. зачем ты передаешь рекурсивно первичную матрицу - наверное там должен быть результат assoc.

[NEDIS]

Сообщение от zamtmn это алгоритм Дейкстры - http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры. реализация данного алгоритма на паскале работает без видимых задержек на сложных трассах (в разумных пределах - проверено на разделах ОПС довольно сложных зданий).

Честно говоря когда выбирал алгоритм, то как раз и рассматривал алгоритмы Флойда и Дейкстры . Выбрал Флойда (сработало Русское "Все и сразу" ). Сейчас поменял алгоритм трассировки с Флойда на Дейкстры.

Вывод: все считает шустро - таких проблем как с Флойдом, используя даже "неправильный" для LISP-а императивный подход, замечено не было. Спасибо Sleekka за наставление.

Обновил топик. Добавил новые функции.

В ближайшие дни скомпоную все в отдельные функции (для удобства), ну и соответственно переделаю команду NEDIS-tracing-point-to-point под новые функции.

[Eddicordo]

Прикольно. Авто трассировка Алгоритм Дейкстры мне напомнила Карту Украины или Киева.
Где указываешь точку А и точку В. (Указать кратчайший путь для проезда автомобилем по дороге от точки А до точки В. Плюс показать длину этого пути.)
Но с запуском вашей программы ничего не понятно.
Да еще Кад висит

[NEDIS]

Сообщение от Eddicordo Прикольно. Авто трассировка Алгоритм Дейкстры мне напомнила Карту Украины или Киева. Где указываешь точку А и точку В. (Указать кратчайший путь для проезда автомобилем по дороге от точки А до точки В. Плюс показать длину этого пути.) Но с запуском вашей программы ничего не понятно. Да еще Кад висит

Что именно не понятно?

P.S. На трех машинах разной кофигурации запускал - все считает шустро, проблем не замеченно.

[Eddicordo]

NEDIS, Все разобрался. Это я загрузил сразу 2 алгоритма. Вот и подвисло.
Но чет странно при команде NEDIS-tracing-point-to-point путь находит вроде бы правильно. А вот поллинию налаживает со сдвигом. То есть не точно по указанному скелету.
Это у тебя как пример показаны отрезки ну очень огромные. Ты начерти отрезки по 10-100 мм. и увидишь не точности.

Да и при команде NEDIS-input-system-for-tracing наши отрезки должны быть именно в том слое !!SS_zakl_gofra_25.
Неудобство в том что при указании наших отрезков они уже должны быть в нужном слое.
Был бы неплохо что бы при указании нашего скелета из отрезков все что мы выделяем само переносилось в нужный нам слой.
И выделение рамкой скелета ну очень не удобно. А выделить ВСЕ, по моему никому и не нужно.
Выделение должно быть указание конкретного отрезка клац, дольше клац., если надо, выделение стандартным методом рамкой справа на лево выделяется все что вошло в рамку ну и слево на права как у Вас сейчас.

Создал свои отрезки присвоил им твой слой !!SS_zakl_gofra_25.
Указываю NEDIS-input-system-for-tracing

Код:

[Выделить все]

Команда:
Активируйте способ выбора закладных устройств:
      1. Выбор всех устройств на активном листе Модель
      2. Выбор рамкой необходимых мне устройств
2
Выделите фрагмент в рамках которого будет выполняться трассировка
Restoring System variables
Application aborted: неверный тип аргумента: numberp: nil

Для выделение корректней использовать вот такой код

Код:

[Выделить все]

            ;(setq    pt1 (getpoint "\nВыделите фрагмент в рамках которого будет выполняться трассировка")
                ; getcorner - рисует "резиновую" рамку (стр. 89);


(if (null (setq pt1 (ssget '((0 . "INSERT") (66 . 1)))))
    (setq
      pt1 (ssget
           "_X"
           (list '(0 . "INSERT") '(66 . 1) (cons 410 (getvar "CTAB")))
         ) ;_ end of ssget
    ) ;_ end of setq
  ) ;_ end of if



                pt2 (getcorner pt1)
            ;)

Но почему то, так не находит наш скелет