В работе рассматривается алгоритм распределения соединений по слоям в задаче многослойной глобальной трассировки, базирующейся на биоинспирированных методах поиска. Решение задачи глобальной трассировки базируется на подходе, включающем две стадии. На первой стадии решается задача однослойной трассировки. На второй -выполняется «распределение соединений по слоям». Разработанные алгоритмы реализованы в виде двух программ: эвристического распределения соединений по слоям и разнесения соединений по слоям методом муравьиной колонии. Решения, полученные в процессе выполнения глобальной трассировки предложенным алгоритмом, на 2-5% лучше, в сравнении с достигнутыми результатами известных трассировщиков. Общая оценка временной сложности лежит в пределах О(n2)-О(n3).
На элементарном уровне изложены важнейшие понятия теории
графов, причем основной материал посвящен именно обыкно-
венным (не ориентированным) графам. Подробно рассмотрен ал-
горитм Дейкстры, позволяющий находить кратчайшие маршруты
во взвешенном графе, в общих чертах разобран так называемый му-
равьиный алгоритм, предназначенный для решения известной задачи
коммивояжера. Во втором издании исправлены замеченные неточно-
сти и опечатки, добавлен ряд новых задач, расширен материал, отно-
сящийся к свойствам многогранников.
Книжка адресована старшим школьникам, интересующимся мате-
матикой, а также студентам педвузов – будущим учителям математи-
ки и информатики.
На элементарном уровне изложены важнейшие понятия теории графов, причем основной материал посвящен именно обыкновенным (не ориентированным) графам. Подробно рассмотрен алгоритм Дейкстры, позволяющий находить кратчайшие маршруты во взвешенном графе, в общих чертах разобран так называемый муравьиный алгоритм, предназначенный для решения известной задачи коммивояжера. Во втором издании исправлены замеченные неточности и опечатки, добавлен ряд новых задач, расширен материал, относящийся к свойствам многогранников. Книжка адресована старшим школьникам, интересующимся математикой, а также студентам педвузов - будущим учителям математики и информатики.
В статье рассматривается задача построения туристического маршрута с заранее заданными точками начала и конца маршрута. Объекты делятся на два типа. Первые - обязательные, которые наверняка должны войти в результирующий маршрут. Вторые - дополнительные, посещение которых не является необходимым. Маршрут формируется с учетом приоритетов, заранее заданных для объектов туристом исходя из его интересов и предпочтений, при этом суммарное время посещения объектов не должно превышать заданного крайнего срока прибытия в конечную точку маршрута. Для решения поставленной задачи в статье предлагается подход, основанный на построении известными методами маршрута по основным объектам и дальнейшем его расширением с использованием муравьиных стратегий. С этой целью вводится понятие «сытости» муравья и вероятности возврата к основному маршруту, чтобы была возможность контроля оставшегося времени. В завершении статьи приводятся результаты вычислительного эксперимента, направленного на оценку влияния параметров муравьиного алгоритма на полученный маршрут и разработку рекомендаций по настройке этих параметров в зависимости от размерности задачи. Кроме того, проводится сравнительный анализ маршрутов, полученных предложенным алгоритмом и точным методом ветвей и границ по заданному набору объектов, по результатам которого сделан вывод об эффективности предложенного алгоритма.