Конференции ИВТ СО РАН

VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

27 - 29 ноября 2007 года, Новосибирск

Тезисы докладов

Информационные технологии

Применение метода "столб Штейнера" в САПР СКС

Гарбар С.П.

ОмГУ (Омск)

Целью работы является создание САПР (системы автоматизированного проектирования) СКС. В конечном итоге должен получится программный продукт, способный выдавать комплект проектной документации, соответствующий действующим международным и российским стандартам в этой области.

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

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

В основе программы лежит алгоритм построения минимального связывающего дерева методом «столб Штейнера». Метод «Столб Штейнера» применим для плоскости прямоугольной формы. Для плоскости, отличающейся от прямоугольной, необходима модификация и усовершенствование алгоритма.

Метод "Столб Штейнера" является одним из наиболее эффективных по времени реализации эвристических алгоритмов построения ДШ и предусматривает следующий порядок действия.
1. Все вершины проецируются на ось S.
2. Расстояние от наименьшей до наибольшей координаты делится пополам, и из этой точки проводится перпендикуляр (столб Штейнера).
3. Из каждой вершины опускается перпендикуляр до пересечения со столбом Штейнера.

Возможна модификация метода – построение столба по весовому коэффициенту вершин.

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]