Информационная система "Конференции"

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

Вычислительная математика

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

Реализация метода осуществляется в следующем порядке.

1. Исходный граф произвольно отобразить в одномерную координатную решётку, количество узлов которой соответствует количеству вершин графа.
2. Построить матрицу смежности графа и матрицу расстояний между узлами заданной координатной решётки. Шаг решётки, т.е. расстояние между двумя соседними позициями, в которых размещаются вершины графа, прини-мается равным единице.
3. По матрице смежности и матрице расстояний вычислить величины приращений суммарной длины связей для всех возможных парных перестановок. По результатам полученных вычислений построить матрицу приращений суммарной длины связей для всех возможных парных перестановок. Отрицательное значение приращений означает уменьшение суммарной длины связей между соответствующими парами вершин.
4. Из множества пар вершин, перестановка которых даёт отрицательные приращения суммарной длины связей, выбрать подмножество, обеспечивающее выполнение следующих условий:
   - выбранное подмножество перестановок максимально уменьшает суммарную длину связей;
   - любая пара вершин из выбранного подмножества не должна иметь связей с другими парами.
   Несоблюдение указанных условий может ухудшить результат размещения по сравнению с первоначальным на любой итерации. В [1] приводится ещё одно условие: любая вершина может менять свою позицию только один раз, однако автор в процессе чтения лекций, освещающих вопросы алгоритмизации размещения РЭС по курсу «Системы автоматизированного проектирования», неоднократно доказывал, в том числе и на примерах, что данное условие деструктивно. Недопустимой следует считать повторную перестановку одной и той же пары вершин. Такая перестановка свидетельствует о зацикливании программы для автоматизированного решения задачи размещения из-за текстовой ошибки при её написании. Повторная и, возможно неоднократная, перестановка одной вершины с вершиной (вершинами) из другой пары способствует минимизации суммарной длины связей между размещаемыми элементами любого иерархического уровня.
5. Выполнить перестановку выбранных подмножеств. В матрице смежности разрезаемого графа переставить строки и столбцы, соответствующие переставляемым вершинам.
6. Повторно вычислить величины приращений суммарной длины связей для всех возможных парных перестановок. Описанные действия повторяются до тех пор, пока в матрице приращений суммарной длины связей не останется ни одного отрицательного перестановочного коэффициента.
7. Провести сечения между всеми рядом расположенными узлами координатной сетки, отступив слева и справа то количество узлов, которое равно количеству вершин, заданному для минимального куска требуемого разрезания.
8. Подсчитать количество рёбер в каждом сечении.
9. Выбрать сечение с минимальным количеством находящихся в нём рёбер. Это сечение будем считать входным.
10. Выделить подмножество вершин с мощностью, равной количеству вершин, заданному для формируемого куска. Выделение такого подмножества следует осуществлять в направлении расположения выходного сечения с минимальным количеством содержащихся в нём рёбер. Выходным сечением будем считать сечение, расположенное до или после входного сечения на расстоянии ni шагов и содержащее наименьшее количество рёбер.
    Если граф разрезается на неравные по количеству вершин куски, то имеется возможность выбора количества выделяемых вершин по критерию минимума рёбер в сечении, что в конечном итоге обеспечит минимум внешних связей между полученными кусками.
11. Удалить из матрицы смежности строки и столбцы, соответствующие выбранным вершинам. В результате будет получена обновлённая матрица смежности.
12. Построить новую матрицу расстояний, размерность которой соответствует размерности обновлённой матрицы смежности.
13. Повторно выполнить действия 3-11. Описанные действия повторяются до тех пор, пока не будет получено заданное разрезание.

1. Конструирование и технология печатных плат : Учеб. пособие для ра-диотехнических специальностей вузов / А.Т. Жигалов, Е.П. Котов, К.Н. Шихаев [и др.]. – М. : Высш. шк., 1973. – 216 с. : ил.

Дополнительные материалы:

Полный текст доклада

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

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

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

© 1996-2000, Институт вычислительных технологий СО РАН, Новосибирск
© 1996-2000, Сибирское отделение Российской академии наук, Новосибирск
    Дата последней модификации: 06-Jul-2012 (11:48:14)