Одним из главных принципов уникальной «системы Физтеха», заложенной в основу образования в МФТИ, является тщательный отбор одаренных и склонных к творческой работе представителей молодежи. Абитуриентами Физтеха становятся самые талантливые и высокообразованные выпускники школ всей России и десятков стран мира.

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

Адрес e-mail:

Алгоритм построения минимальных связывающих деревьев с дополнительными вершинами (деревьев Штейнера) для случая прямоугольной метрики

Н.В. Рыженко, аспирант МФТИ

 

Для построения трасс в САПР электронной аппаратуры используются минимальные связывающие деревья с дополнительными вершинами (деревья Штейнера). Задача построения дерева Штейнера относится к так называемому классу NP-полных задач: все известные алгоритмы, дающие точное решение, не могут быть использованы в САПР из-за неприемлемой временной сложности. Это обстоятельство послужило стимулом для разработки многочисленных эвристических алгоритмов, наибольший практический интерес из которых представляет алгоритм последовательного введения дополнительных вершин в дерево Прима-Краскала (минимальное связывающее дерево без дополнительных вершин). Использование предложенного алгоритма позволяет строить деревья Штейнера, длина которых в среднем не превышает длину оптимального дерева Штейнера на 0.5%. Временные характеристики же позволяют успешно использовать его на этапе глобальной трассировки.

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

Основная идея алгоритма заключается в следующем. Для случая ортогональной метрики (а именно эта метрика используется в САПР электронной аппаратуры) доказано, что если через каждую точку из исходного множества точек на плоскости провести вертикальные и горизонтальные линии, то решение задачи Штейнера можно получить, рассматривая в качестве возможных дополнительных точек Штейнера только точки пересечения полученной сетки линий. Данный алгоритм последовательно вводит в текущее дерево Прима-Краскала каждую из n2 дополнительных вершин решеточного графа, строит новое дерево Прима и запоминает полученный выигрыш в длине. В настоящий момент существуют практически линейные, очень быстрые алгоритмы построения оптимального дерева Прима-Краскала. После оценки всех дополнительных точек в текущее дерево включается точка с максимальным выигрышем. Модификации данного алгоритма позволяют существенно сократить время его работы, но основная идея последовательного введения всех возможных дополнительных точек осталась неизменной.

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

Если вы заметили в тексте ошибку, выделите её и нажмите Ctrl+Enter.

© 2001-2016 Московский физико-технический институт
(государственный университет)

Техподдержка сайта

МФТИ в социальных сетях

soc-vk soc-fb soc-tw soc-li soc-li
Яндекс.Метрика