Методы и алгоритмы автоматизированного проектирования проводных телекоммуникационных сетей минимальной стоимости
Диссертация
В существующих на данный момент алгоритмах построения сетей минимальной стоимости заданной топологии стоимость затрат на прокладку линий связи между узлами телекоммуникационной сети определяется либо экспертным путем, либо не учитывает неоднородность среды, по которой будет прокладываться трасса: предполагается, что стоимость прокладки единицы длины линии связи по всей территории является… Читать ещё >
Содержание
- Стр
- Общая характеристика работы
- Глава 1. Анализ существующих методов и алгоритмов построения телекоммуникационных сетей минимальной стоимости
- 1. 1. Описание алгоритмов построения сетей минимальной стоимости
- 1. 1. 1. Алгоритмы построения минимальных остовных деревьев. 1.1.2 Алгоритмы построения деревьев Штейнера
- 1. 1. 3. Алгоритмы построения минимальных гамильтоновых контуров
- 1. 1. 4. Анализ предложенных алгоритмов
- 1. 2. Алгоритмы определения маршрута трассы
- 1. 2. 1. Конструкторская трассировка
- 1. 1. Описание алгоритмов построения сетей минимальной стоимости
- 1. 2. 3. Анализ алгоритмов трассировки
- 1. 3. Анализ близких задач
- Глава 2. Разработка математического аппарата соединения двух точек на взвешенной плоскости
- 2. 1. Соединение точек, расположенных в соседних полуплоскостях с различной стоимостью прокладки
- 2. 1. 1. Решение уравнений третьей степени (метод Кардано)
- 2. 1. 2. Решение уравнений четвертой степени (метод Феррари)
- 2. 2. Соединение точек, расположенных в полуплоскости с высокой стоимостью прокладки
- 2. 3. Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных произвольной кривой
- 2. 4. Соединение точек, расположенных в удаленных областях взвешенной плоскости, границами которых являются параллельные прямые
- 2. 5. Соединение точек, расположенных в удаленных областях взвешенной плоскости, границами которых являются две непараллельные прямые
- 2. 6. Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных тремя прямыми, сходящимися в одной точке
- 2. 7. Соединение точек, расположенных в соседних областях взвешенной плоскости, разделенных двумя прямыми, сходящимися в одной точке
- Глава 3. Разработка алгоритмов соединения точек на взвешенной плоскости и объединение п точек в сеть заданной топологии
- 3. 1. Разработка алгоритма соединения двух точек на взвешенной плоскости
- 3. 1. 1. Предварительный этап соединения двух точек на взвешенной плоскости
- 3. 1. 2. Улучшение пути, соединяющего две точки на взвешенной плоскости
- 3. 2. Разработка алгоритма объединения точек на взвешенной плоскости в сеть заданной топологии
- 3. 3. Разработка алгоритма построения телекоммуникационной ^ сети заданной топологии без вычисления всех расстояний между каждой парой узлов на взвешенной плоскости
- Глава 4. Экспериментальная проверка работы разработанных алгоритмов
- 4. 1. Разработка автоматизированной системы построения сети заданной топологии на взвешенной плоскости
- 4. 2. Описание вычислительного эксперимента
- 1. 4.3 Анализ полученных результатов
Список литературы
- Алексеев В.Б. Теорема Абеля в задачах и решениях М.: МЦНМО, 2001.- 192 е.: ил.
- Архангельский А.Я. Программирование в C++Builder 5. М.: ЗАО «Издательство БИНОМ», 2000 г. — 1152 е.: ил.
- Артамонов Г. Т. Топология регулярных вычислительных сетей и сред. -М.: Радио и связь, 1985. 192 с.
- Аттеков А.В., Галкин С. В., Зарубин B.C. Методы оптимизации: Учеб. для вузов / Под ред. B.C. Зарубина, А. П. Крищенко. М.: Изд-во МГТУ им. Баумана, 2001.440 е.: ил.
- Бермант А.Ф., Араманович И. Г. Краткий курс математического анализа.-М.: Наука, 1973.-736 с.
- Бет Верити. Кабельные системы: проектирование, монтаж и обслуживание. М.: КУДИЦ-ОБРАЗ, 2004. — 400 е.: ил.
- Бондарев В.М., Рублинецкий В. И., Качко Е. Г. Основы программирования- Ростов н/Д: Феникс, 1998. 368 е.: ил.
- Бондарев В.М., Рублинецкий В. И., Сигалов B.JI. Точное решение задачи строительной трассировки ДАН УССР, 1988, № 6, сер. «А», с. 67−70.
- Грин Д., Кнут Д. Математические методы анализа алгоритмов. М.: Мир, 1987.- 120 е.: ил.
- Дейтел Харви, Дейтел Пол. Как программировать на С++: Пер. с англ. -М.: ЗАО «Издательство БИНОМ», 1999. 1024 е.: ил.
- М.Ерзин А. И. Задачи проектирования оптимальной сети сбора нефти // Труды школы-семинара «Физика нефтяного пласта», Новосибирск, 2002. -с. 101−104.
- Инструкция по проектированию линейно-кабельных сооружений связи -М.: Гипросвязь, 1993.
- Калверт Ч., Рейсдорф К. Borland C++Builder 5. Энциклопедия программиста: Пер. с англ. К.: Издательство «ДиаСофт», 2001. — 944 е.: ил.
- Каляев А.В., Мелихов А. Н., Курейчик В. М., Гузик В. Ф., Калашников В. А. Автоматизация проектирования вычислительных структур. Издательство Ростовского университета, 1983. 224с.: ил.
- Карманов В.Г. Математическое программирование 2-е изд., перераб. -М.: Наука, 1980. — 256 е.: ил.
- Киржнер В.М., Рублинецкий В. И. О процедуре «иди в ближайший» в задаче коммивояжера. Выч. мат. и выч. техн., Харьков, 1973, вып. IV, с.40−41.
- Кнут Д. Искусство программирования, том 1. Основные алгоритмы, 3-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2002. — 720 е.: ил.
- Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. Алгоритмы: построение и анализ, 2-е изд.: Пер. с англ. М.: Издательский дом «Вильяме», 2005. -1296 е.: ил.
- Корн Г. и Корн Т. Справочник по математике для научных работников и инженеров. М.: Наука, 1970.- 720 с.
- Корячко В.П., Курейчик В. М., Норенков И. П. Теоретические основы САПР. Учебник для ВУЗов М.: «Энергоатомиздат», 1987 г. — 400с.: ил.
- Корячко В.П., Митрошин А. А., Читаев И. В. Алгоритм проектирования кластерной системы узлов телекоммуникационной сети // Известия Белорусской инженерной академии. Минск, 2003 г, № 1(15)/1. с.255−259.
- Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978.-432 с.
- Кудрявцев П.С. Курс истории физики. М.: Просвещение, 1982. — 448 с.
- Кульгин М.В. Компьютерные сети: практика построения. 2-е изд. -СПб.: Питер, 2003. — 462 е.: ил.
- ЗЬЛипский В. Комбинаторика для программистов М.: Мир, 1988 — 319 с.
- Литтл Дж., Мурти К., Суини Д., Кэрел К. Алгоритм решения задачи коммивояжера. Экономика и мат. методы, 1965, № 1, с. 13−22.
- Макконнелл Дж. Основы современных алгоритмов. 2-е дополненное издание — М.: Техносфера, 2004. — 368 е.: ил.
- Зб.Оре О. Теория графов. М.: Наука, 1968. 352 е.: ил.
- Палмер М., Синклер Р. Б. Проектирование и внедрение компьютерных сетей. Учебный курс. 2-е изд., перераб. и доп.: Пер. с англ. — СПб.: БХВ-Петербург, 2004. — 752 е.: ил.
- Попков В.К., Кауль С. Б., Нечепуренко М. И. и др. Методы оптимизации структур зоновых сетей связи. Отв. ред. Алексеев А. С. Новосибирск, 1983.-181 с.
- Препарата Ф., Шеймос М. Вычислительная геометрия: Введение: Пер. с англ. М.: Мир, 1989. — 478 с.
- Прим Р.К. Кратчайшие связывающие сети и некоторые обобщения. -Кибернетич. сб., М.: Мир, 1961, вып. 2, с. 95−107.
- Псиола В.В. Об одном эвристическом параллельном алгоритме решения задачи Штейнера. Изв. вузов, М.: Приборостроение, 1997. — с. 53−60.
- Техническое зрение роботов / Под ред. Пью А.- Пер. с англ. Миронова Д.Ф.- Под ред. Катыса Г. П.- М.: Машиностроение, 1987. 320 е.: ил.
- Руководство по строительству линейных сооружений магистральных и внутризоновых кабельных линий связи М.: «Радио и связь», 1986.
- Семенов А.Б. Проектирование и расчет структурированных кабельных систем и их компонентов. М.: Компания АйТи- ДМК Пресс, 2005. — 416 е.: ил.
- Структурированные кабельные системы / Семенов А. Б., Стрижаков С. К., Сунчелей И. Р. 5-е изд. — М.: Компания АйТи- ДМК Пресс, 2004. -640+16 е.: ил.
- Сигал И.Х., Иванова А. П. Введение в прикладное дискретное программирование: модели и вычислительные алгоритмы: Учебное пособие. Изд. 2-е, испр. — М.: ФИЗМАТЛИТ, 2003. — 240 е.: ил.
- Скворцов А.В. Обзор алгоритмов построения триангуляции Делоне. // Вычислительные методы и программирование. Т. З, 2002. с. 14−39.
- Скворцов В.А. Примеры метрических пространств. М.: МЦНМО, 2002. -24с.: ил.
- Советов Б. Я. Яковлев С.А. Построение сетей интегрального обслуживания. Л.: Машиностроение. Ленингр. отд-ние, 1990. — 332 е.: ил.
- Компьютерные сети. 4-е издание / Таненбаум Э. СПб.: Питер, 2003. -992 е.: ил. — (Серия «Классика computer science»)
- Тужилин А.А., Фоменко А. Т. Элементы геометрии и топологии минимальных поверхностей. М., Наука, 1991. 176 е.: ил.
- Уилсон Р. Введение в теорию графов. М.: Мир, 1977. — 207 с.
- Фень Юань Программирование графики для Windows. СПб.: Питер, 2002. — 1072 е.: ил.
- Филипс Д., Гарсиа-Диас А. Методы анализа сетей: Пер. с англ. М.: Мир, 1984.-496 е.: ил.
- Франка П. С++: учебный курс СПб: ЗАО «Издательство «Питер», 1999. — 528 с: ил.
- Харари Ф. Теория графов. М.: Мир, 1973. — 300 с.
- Харари Ф., Пальмер Э. Перечисление графов. М.: Мир, 1977. — 324 с.
- Холингвэрт Д., Баттерфилд Д., Сворт Б. C++Builder 5. Руководство разработчика, том 1. Основы: Пер. с англ. М.: Издательский дом «Вильяме», 2001. — 880 е.: ил.
- Холингвэрт Д., Баттерфилд Д., Сворт Б. C++Builder 5. Руководство разработчика, том 2. Сложные вопросы программирования: Пер. с англ. -М.: Издательский дом «Вильяме», 2001. 832 е.: ил.
- Читаев И.В., Жошкин А. С. Разработка программного обеспечения соединения двух точек на взвешенной дискретной плоскости // Новыеинформационные технологии, Межвузовский сборник научных трудов, Рязань, 2006 г. с. 123−126.
- Читаев И.В. Построение линии связи минимальной стоимости между двумя узлами на взвешенных регионах, разделенных прямыми линиями // Новые информационные технологии, Межвузовский сборник научных трудов, Рязань, 2006 г. с. 120−123.
- Петербурга- Ряз. филиал Санкт-Петербургской академии управления и экономики. Рязань, 2005 г., с. 79−80.
- Якобсон А., Буч Г., Рамбо Дж. Унифицированный процесс разработки программного обеспечения. СПб.: Питер, 2002. — 496 е.: ил.
- Alexander, R. S. 1989 (September). Construction of optimal-path maps for homogeneous-cost-region path-planning problems. Ph.D. thesis, Dept. of Computer Science, U.S. Naval Postgraduate School, Monterey, CA, USA.
- Chung S., Condon A. Parallel implementation of Boruvka’s minimum spanning tree algorithm. In Proc. 10th Int’l Parallel Processing Symp. (IPPS'96), pages 302−315, April 1996.
- Chazelle B. A Minimum Spanning Tree Algorithm with Inverse-Ackermann Type Complexity. Journal of the ACM, 47 (2000), 1028−1047.
- Dixon В., Rauch M. and Tarjan R. E. 1992. Verification and sensitivity analysis of minimum spanning trees in linear time. SIAM J. Comput. 21, 1184 -1192.
- Hakimi. S. L. Steiner’s Problem in Graphs and Its Implications. // Networks. 1971. V. l.P. 113−133.
- Jeff Erickson. Minimum spanning trees. Lecture notes: Fall 2002 — CS 373: Combinatorial Algorithms.
- Graham R. L. and Hell P. On the history of the minimum spanning tree problem. Annals of the History of Computing, 7(1): 43−57, 1985.
- Kindl R., Rowe C. and Shing Man-Tak A Stochastic Approach to the Weighted-Region Problem: Design and Testing of a Path Annealing Algorithm, Monterey, 1991.
- Lucena A. and Beasley J. E. A Branch and Cut Algorithm for the Steiner Problem in Graphs. // Networks. 1998. V. 31. P. 39 59.
- Melzak Z.A. On the problem of Steiner //Canad. Math. Bull. 1960. V.4 P. 143 148
- Mitchell J. S. B. and Keirsey D. Planning Strategic Paths Through Variable Terrain Data, SPIE, Applications of Artificial Intelligence, volume 485, 172 179, 1984.
- Mitchell J. S. B. and Papadimitriou С. H. The weighted region problem, to appear in Journal of the ACM, 1990.
- Parodi A. M. Multi-goal real-time global path planning for an autonomous land vehicle using a high-speed graph search processor, Proceedings of the 1985 IEEE Conference on Robotics and Automation, 161−167, 1985.
- Rowe N. C. Roads, rivers, and rocks: optimal two-dimensional route planning around linear features for a mobile agent. To appear in International Journal of Robotics Research, 1990.
- Rowe N. C. and Richbourg R. F. An Efficient Snell’s-Law Method for Optimal-Path Planning Across Multiple Homogeneous-Cost Regions, accepted to International Journal of Robotics Research, to appear 1990.
- Rowe N. C. and Richbourg R. F. An efficient Snell’s-law method for optimal-path planning across multiple two-dimensional irregular homogeneous-cost regions. To appear in International Journal of Robotics Research, 1990.
- Rowe N. C. and Ross R. S. Optimal grid-free path planning across arbitrarily-contoured terrain with anisotropic friction and gravity effects. Accepted to IEEE Transactions on Robotics and Automation, January 1990.
- Warme D.M. Spanning Trees in Hypergraphs with Applications to Steiner Trees. // Ph.D. Thesis, Computer Science Dept., The University of Virginia, 1998.