Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

1. алгоритмы, использующие методы целочисленного программирования.

2. последовательные алгоритмы

3. итерационные алгоритмы

4. смешанные алгоритмы

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

Последовательные алгоритмыкомпоновки

В последовательных алгоритмах компоновки «разрезание» исходного графа
G(X,U) на куски G1(X1,U1), G2(X2,U2),…, Gk(Xk,Uk) сводится к следующему. В графе G(X,U) находят вершину xi [pic] X с минимальной локальной степенью
[pic].

Если таких вершин несколько, то предпочтение отдают вершине с максимальным числом кратных ребер. Из множества вершин, смежных с вершинами формируемого куска графа G1(X1,U1), выбирают ту, которая обеспечивает минимальное приращение связей куска с еще нераспределенными вершинами.
Данную вершину xi [pic] X X1 включают в G1(X1,U1), если не происходит нарушения ограничения по числу внешних связей куска, т.е.
[pic], где ?j? – элемент матрицы смежности исходно графа G(X,U); ?(xg) – относительный вес вершины xg, , равный приращению числа внешних ребер куска
G1(X1,U1) при включении вершины xg во множество X1; E – множество индексов вершин, включенных в формируемый кусок графа на предыдущих шагах алгоритма; m – максимально допустимое число внешних связей отдельно взятого куска со всеми оставшимися.

Указанный процесс продолжается до тех пор, пока множество X1 не будет содержать n элементов либо присоединение очередной нераспределенной вершины xj к куску G1(X1,U1) не приведет к нарушению ограничения по числу внешних соединений куска, равному

[pic]

Следует отметить, что величина [pic] не является монотонной функцией
|X1|, поэтому, для того чтобы убедится в невозможности дальнейшего формирования куска вследствие нарушения последнего ограничения, необходимо проверить его невыполнимость на последующих шагах увеличения множества X1 вплоть до n. В качестве окончательного варианта выбирают кусок
G10(X10,U10), содержащий максимально возможное число вершин графа G(X,U), для которого выполняются ограничения на число внешних связей и входящих в него вершин (nmin-nmax).

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

Сформулируем алгоритм последовательной компоновки конструктивных элементов.

1) t:0

2) Xf = Xt = Ш; t=t+1; ?=1; ?=nmax,

Где t, ? – порядковые номера формируемого куска и присоединяемой вершины; ? – ограничение на число вершин в куске.

3) По матрице смежности исходного графа | ?hp|NxN, где N – число вершин исходного графа (при большом значении N для сокращения объема оперативной памяти ЭВМ используем не саму матрицу смежности, а её кодовую реализацию), определяем локальные степени вершин

[pic].

4) Из множества нераспределенных вершин X выбираем вершину xj с ?(xj)

= [pic]. Переходим к п.6. Если таких вершин несколько, то переходим к п.5

5) Из подмножества вершин Xl с одинаковой локальной степенью выбирают вершину xj с максимальным числом кратных ребер (минимальным числом смежных вершин), т.е. |Гxj| = [pic].

6) Запоминаем исходную вершину формируемого куска графа [pic].

Переходим к п.10

7) По матрице смежности [pic] строим множество Xs = [pic] и определяем относительные веса вершин [pic]:

[pic].

Рекомендуем скачать другие рефераты по теме: реферат вещество, недвижимость реферат, отчет по практике.



Предыдущая страница реферата | 1  2  3  4  5  6 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки