[Tito]

Парни нужна помощь. Просто делфи только начали разбирать а курсачь уже поджимает(тупая учебная программа ). Мот кто сможет помочь?

Тема: Деление графа на куски по средствам итерационного алгоритма.

Препод сказал что мне повезло...тема не такая сложная...но я не втыкаю ни в графы, ни в куски ни в средства итерационного алгоритма

Мот кто делал что похожее... или может кто нить даст ссылки на инфу по этому поводу.

Plz....в армию жуть как не хочется

[AlexSku]

Итерационный алгоритм это не тупая программа. Изложи его, тогда запрограммируем.

[Tito]

Деление графа на куски по средствам итерационного алгоритма.


Задан мультиграф G(X,U). Требуется "разрезать" его на отдельные куски G1(X1,U1),G2(X2,U2)...Gn(Xn,Un) чтобы число ребер соеденяющих эти куски было минимальным.


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

Из книги Автоматизация конструирования РЭА Б.Н. Деньдобренько.

[AlexSku]

Ты бы разжевал, что такое X, U. Подозреваю, что множество узлов и рёбер. Но на догадках можно запрограммировать не тот алгоритм. Ты разбил задачу на куски, но каждый кусок нуждается в уточнении. Например, как задаётся начальное разрезание - произвольно или по какому-то принципу? Итерация идёт в каком-то направлении или это просто перебор всех вариантов? Какие такие "другие показатели качества" и ограничения?

[Tito]

В этой книге,Автоматизация конструирования РЭА Б.Н. Деньдобренько,много чего полезного по этому поводу...даже какая-то блоксхема есть...я отсканю и выложу.

[Tito]

Столько времени прошло...а я ничего и не добился..просто тяжело...с графами НИКОГДА не сталкивался...нарыл тольковот что


Итерационные алгоритмы компоновки


Сущность данной группы алгоритмов заключается в выборе некоторого начального «разрезания» исходного графа на куски (вручную или с помощью последовательного метода компоновки) и последующего его улучшения с помощью итерационного парного или группового обмена вершин из различных кусков. При этом для каждой итерации осуществляется перестановка тех вершин, которая
обеспечивает максимальное уменьшение числа связей между кусками графа или максимальное улучшение другого выбранного показателя качества с учетом используемых ограничений (например, на максимальное число внешних ребер любого отдельно взятого куска).
Рассмотрим основную идею итерационного алгоритма разбиения графа G, заданного матрицей смежности, с минимизацией числа соединительных ребер. Разбиение графа G = (X,U) на l подграфов G1 = (X1,U1), G2 = (X2,U2),…,Gl = (Xl,Ul) сведем к разбиению на два подграфа. С этой целью в матрице
смежности R выделим по главной диагонали две подматрицы R1 и R2. При этом порядок подматрицы R1 равен числу вершин, которые должны находится в G1, а порядок подматрицы R2 – числу всех оставшихся вершин графа. Необходимо так переставить строки и столбцы матрицы R, чтобы число ребер между G1 и оставшейся частью графа G было минимальным. После этого подматрицу R1 из матрицы R исключаем, вычеркнув из R строки и столбцы, соответствующие
элементам R1. Далее подматрицу R1’ разбиваем снова на две подматрицы R2 и R2’, причем порядок R2 соответствует числу вершин второго выделяемого подграфа, а порядок R2 – числу оставшихся вершин графа. Переставляем строки и столбцы R1’ с целью минимизации числа соединительных ребер. После этого подматрица R2’ исключается и процесс повторяется до тех пор, пока не будет
выполнено разбиение графа G на l подграфов.
Основная идея алгоритма заключается в выборе таких строк и столбцов, перестановка которых приводит к сосредоточению в диагональных клетках матрицы R максимального числа элементов. Построим прямоугольную матрицу W = ||wi,j||nix(n-ni), в которой строки определяются вершинами из множества
I, а столбцы – из множества V, [pic]. На пересечении k строки ([pic]и q столбца [pic] находится элемент [pic],где rk,q – элемент матрицы смежности R.
Элемент wk,q матрицы W характеризует изменение числа соединительных ребер между Gi и Gj при перестановке вершин [pic] и [pic]. Используя матрицу W , можно найти подстановку, которая увеличит число элементов в
подматрицах R1 и R1’ . Такой процесс повторяется до тех пор, пока в подматрице R1 не сосредоточится максимальное число единиц.
В итерационных алгоритмах предусмотрена возможность поиска оптимального варианта для различных начальных разбиений. Это связано с тем,
что при использовании итерационных алгоритмов оптимальность решения в значительной мере зависит от того, насколько удачно было произведено начальное разбиение графа G(X,U).
Итерационные алгоритмы компоновки обеспечивают высокое качество решения задачи, однако требуют больших затрат машинного времени, чем последовательные алгоритмы. Для сокращения числа итераций обмена вершин между кусками в смешанных алгоритмах для получения начального «разрезания»
графа применяют последовательные методы формирования его кусков. С этой целью в некоторых итерационных алгоритмах используют процесс групповой перестановки взаимно непересекающихся пар вершин.