Статья

Название статьи АДАПТИВНЫЙ АЛГОРИТМ ПОСТРОЕНИЯ ДЕРЕВА ШТЕЙНЕРА
Автор В.А. Литвиненко, С.А. Ховансков, Д.Ю. Максюта
Рубрика РАЗДЕЛ III. ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ И НЕЧЕТКИЕ СИСТЕМЫ
Месяц, год 07, 2014
Индекс УДК 621.3.06
DOI
Аннотация Предлагается адаптивный алгоритм построения дерева Штейнера на основе построения кратчайшего связывающего дерева Прима и его ортогонализации с использованием решетки Ханана. Для выбора ортогональной реализации ребер дерева Прима используется генетический алгоритм. В разработанном адаптивном алгоритме построения дерева Штейнера используется параметрическая адаптация, которая заключается в выборе значения параметра адаптации на основе анализа внешних условий решения задачи и информации, хранящейся в базе данных. В качестве внешних условий решения задачи построения дерева Штейнера предложено использовать: размерность задачи; ресурс времени, отведенный на решение задачи, и производительность компьютера, на котором решается задача. В качестве параметра адаптации предложено использовать количество итераций в генетическом алгоритме при применении операций кроссинговера над вариантами реализации ребра дерева Прима. Разработанный адаптивный алгоритм построения дерева Штейнера реализован на языке высокого уровня Java 7.0. Проведены экспериментальные исследования разработанного алгоритма.

Скачать в PDF

Ключевые слова Адаптивные алгоритмы; дерево Штейнера; решетка Ханана; параметр адаптации; точность решения; размерность задачи; ресурс времени; производительность компьютера; база данных; управление точностью.
Библиографический список 1. Gilbert E.N., Pollak H.О. Steiner Minimal Trees // SIAM Journal on Applied Mathematics. – 1968. – Vol. 16, No 1. – P. 1-29. http://epubs.siam.org.
2. Кристофидес Н. Теория графов. Алгоритмический подход. – М.: Мир, 1978. – 432 с.
3. Курейчик В.В., Курейчик В.М., Родзин С.И. Теория эволюционных вычислений. – М.: Физматлит, 2013. – 260 с.
4. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Гибридный алгоритм разбиения на основе природных механизмов принятия решений // Искусственный интеллект и принятие решений. – 2012. – С. 3-15.
5. Курейчик В.М., Лебедев Б.К., Лебедев В.Б. Планирование сверхбольших интегральных схем на основе интеграции моделей адаптивного поиска // Известия РАН. Теория и системы управления. – 2013. – № 1. – С. 84-101.
6. Лебедев Б.К. Процедуры сужения пространства решений при построении дерева Штейнера // Известия ТРТУ. – 2004. – № 3 (38). – С. 55-60.
7. Лебедев Б.К. Интеллектуальная процедура построения дерева Штейнера на основе процедур отсечки и сужения // Известия ТРТУ. – 2000. – № 1 (15). – С. 89.
8. Чернышев Ю.О., Венцов Н.Н. К вопросу о построении деревьев Штейнера с различной шириной ветвей для связывания элементов трехмерных СБИС // Известия ЮФУ. Технические науки. – 2009. – № 4 (93). – С. 72-76.
9. Чернышев Ю.О., Литвиненко В.А., Ховансков С.А., Литвиненко Е.В. Методы управления точностью решения экстремальных задач на графах // Известия ЮФУ. Технические науки. – 2010. – № 7 (108). – C. 84-91.
10. Литвиненко В.А. Применение адаптивных алгоритмов определения экстремальных множеств графов при решении оптимизационных задач автоматизированного проектирования ЭВА // Известия ТРТУ. – 2001. – № 4 (22). – C. 361-362.
11. Литвиненко В.А. Адаптивные алгоритмы определения экстремальных множеств графов // Известия ТРТУ. – 2000. – № 2 (16). – С. 186-189.
12. Litvinenko V.A. Adaptive algorithms of definition of extreme sets of graphs // Proceeding of the International Scientific Conferences «Intelligent System (IEEE AIS’03)» and «Intelligent CAD’s (CAD-2003)». Scientific publication in 3 volumes. – 2003. – Vol. 3. – C. 52-59.
13. Литвиненко В.А., Ховансков С.А., Литвиненко Е.В. Применение методов искусственного интеллекта для управления точностью решения задач на графах // Известия ЮФУ. Технические науки. – 2011. – № 7 (120). – C. 153-159.
14. Растригин Л.А. Адаптация сложных систем. – Рига: Зинатне, 1981. – 375 с.
15. Курейчик В.М., Лебедев Б.К., Лебедев О.Б., Чернышев Ю.О. Адаптация на основе самообучения: Mонография. – Ростов-на-Дону: Изд-во РГАСХМ ГОУ, 2005.
16. Курейчик В.М., Лебедев Б.К., Лебедев О.Б. Поисковая адаптация. Теория и практика: Монография. – М.: Физматлит, 2006.
17. Орлов Н.Н. Новый подход к решению задачи Штейнера на основе решения Евклидовой задачи // Труды международных научных конференций IEEE AIS 04, CAD 04. – М.: Физматлит, 2004.
18. Hanan M. On Steiner's problem with rectilinear distance // J. SIAM Appl. – Math. 14, 1966. – P. 255-265.
19. Martin Zachariasen. A Catalog of Hanan Grid Problems Networks, 2000. – Vol. 38. – P. 200-221.

Comments are closed.