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

↑

⇐ ПредыдущаяСтр 3 из 5Следующая ⇒

Минимум функции T_k =max((Q_i  + R_i), где i=1, 2, …, k), ввиду её монотонности достигается при  np=n, номер класса эквивалентности разбиений, а n – число вершин в разделяемом графе. Пусть, как и прежде, задан неориентированный взвешенный граф G(V,E) с числом вершин равным n. Этот граф является математической моделью решения некоторой задачи. В памяти компьютера этот граф задаётся матрицей смежности вершин A[n][n], диагональные элементы которой представляют собой временную сложность подзадач, которые могут быть решены параллельно на нескольких процессорах или последовательно на однопроцессорной платформе, а все остальные элементы этой матрицы моделируют временные сложности коммуникационных операций. При решении задачи с использованием единственного процессора коммуникационные затраты отсутствуют. И временная сложность решения всей задачи T₁ определяется суммой диагональных элементов матрицы A[n][n]: mSA=A[0][0]; for(j1=1;j1<n;j1++)mSA+=A[j1][j1]; положить T₁= mSA. Если теперь T₁ разделить на заданный коэффициент ускорения S, то мы получим верхнюю границу для значений функции T_k, соответствующих искомым (допустимым) разбиениям. Добавим к этому ограничению условие «использовать минимальное число процессоров» и получим наиболее практически значимую постановку задачи оптимального разделения взвешенного графа: определить разбиение множества вершин графа P={V₁,…,V_k}, на минимальное число подмножеств k, такое для которого выполняются условия достижения заданного ускорения   (1.1).

Монотонное убывание значений функции T_k при возрастании числа подмножеств в разбиениях позволяет использовать базовый алгоритм Eq2_1 как в вычислительной схеме последовательного поиска (будем отождествлять её с алгоритмом Eq2_1), так и в алгоритме двоичного поиска минимального разбиения взвешенного графа, при котором обеспечивается выполнение условия (1.1) [3]. Ниже будем именовать вычислительную схему двоичного поиска алгоритмом Eq3_1. Сначала рассмотрим псевдокод алгоритма Eq2_1. Он состоит из следующих шагов:

1. Пусть задана матрица A[n][ n] и коэффициент ускорения kp.

2. Вычислить mSA=A[0][0]; for(j1=1;j1<n;j1++)mSA+=A[j1][j1]; mSA/=kp;

3. Установить значения вектора спецификации разбиения pPsi и характеристического вектора pChi в соответствии с разбиением множества X, состоящим из единственного класса, и: for(i=0;i<n;i++) Chi[i]=pPsi[i]=1. Положить ic=0; np= 1.

4. Для анализа первого класса эквивалентности выполнить 5-8:

    if(np < 2)

{

 5. Проверка, не достаточно ли одного процессора: увеличить значение счётчика и определить текущее (начальное) значение minmaxSA:  

ic1++;

for(i=0;i<n;i++) pChi[i]=pPsi[i]=1;

maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;

for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){

if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];

for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}

if(maxSA<SA[j1])maxSA=SA[j1];}

6. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата: if(mSA>=maxSA) goto m_result;

7. Выполнить minmaxSA=maxSA;

8. Увеличить текущий номер класса эквивалентности разбиений: np++;}

//************Начало основного цикла

9. Положить nf=n и выполнять 10— 30 для всех оставшихся классов эквивалентности разбиений (np=2, 3, …, n):

 while(np<=nf)

{

10. Определить вектор спецификаций для нового класса эквивалентностей разбиений и построить первый характеристический вектор разбиения в этом классе: ii=np; for (i=n-1; i>0; i--)

{if(ii>1){pChi[i]=pPsi[i]=ii; ii--;}else pChi[i]=pPsi[i]=1; }

11. Увеличить значение счётчика и определить minSA:

ic1++;if( ic1>999999999){ic2++;ic1=0;}

maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;

for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){

if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];

for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}

if(maxSA<SA[j1])maxSA=SA[j1];}

12. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата: if(mSA>=maxSA) goto m_result;

13. Выполнить: if(minmaxSA>maxSA)minmaxSA=maxSA;

// Переменная minmaxSA позволяет монотонное убывание maxSA

14. Положить :i=n-1;

15. Повторять 16 - 27 пока есть ещё не рассмотренные разбиения в текущем классе эквивалентности :разбиений: while(i>0){

//Change PS***************************

16. Изменить вектор спецификаций, выполнив действия 17-21:

for (i=n-1; i>0; i--) {

17. В текущем классе эквивалентности есть нерассмотренная спецификация?

if((pPsi[i]==pPsi[i-1])&&(pPsi[i]<np))

18. Да, тогда построить новый вектор pPsi:

{pPsi[i]++; pChi[i]=pPsi[i]; k=np;

           for(ii=n-1; ii>i; ii--) {pPsi[ii] =k; if(k>pPsi[i]) k--;}

19.  Для нового вектора pPsi построить первый характеристический вектор разбиения pCh:

 for(ii=1; ii<n; ii++)if(pPsi[ii]==pPsi[ii-1])pChi[ii]=1;else pChi[ii]=pPsi[ii];}

20. Увеличить значение счётчика и определить minSA:

ic1++;if( ic1>999999999){ic2++;ic1=0;}

maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;

for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){

if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];

for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}

    if(maxSA<SA[j1])maxSA=SA[j1];}

 21. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата: if(mSA>=maxSA) goto m_result;

2.2. Выполнить: if(minmaxSA>maxSA)minmaxSA=maxSA;

23. Прервать цикл  «for i »: break;} // if(pPsi[i]==pPsi[i-1])&&pPsi[i]<np)

          } //end for i

24. Если цикл «for i» был прерван (был построен новый вектор pPsi), то выполнить построение нового характеристического вектора pChi (действия 25 - 29): if(i>0) {

25. Выполнить: ii=n-1;  

 while(ii>0) { if(pChi[ii]<pPsi[ii]) {pChi[ii]++; k=ii; k++;

while(k<n)  { if(pPsi[k]==pPsi[k-1]) {pChi[k]=1; }  k++;}

               ii=n-1;

26. Увеличить значение счётчика и определить minSA:

ic1++;if( ic1>999999999){ic2++;ic1=0;}

maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;

for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){

if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];

for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}

if(maxSA<SA[j1])maxSA=SA[j1];}

27. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:  if(mSA>=maxSA) goto m_result;

28. if(minmaxSA>maxSA)minmaxSA=maxSA;

           }//end if(pChi[j]<pPsi[j])

29. Выполнить:        else ii--;

        }// end while(ii>0)

// Конец изменений pChi

    }// end if(i>0)

} //end while(i>0)

30. Выполнить:np++;

}//end while(np<=n)

//*********************Конец основного цикла

m_result: 31. Выполнить:

finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;

32.  Вывести номер экспериментальной точки " N= jj ", число просмотренных вариантов  " NN= ic2* ic1”, время поиска минимального разбиения множества вершин "duration", номер класса эквивалентности "np", в котором найдено решение, значение функции   "T_k= maxSA", характеристический вектор разбиения множества вершин "pChi", который представляет собой найденное решение.

33. Стоп.//Конец описания алгоритма.

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

1. Пусть задана матрица A[n][ n] и коэффициент ускорения kp.

2. Вычислить mSA=A[0][0]; for(j1=1;j1<n;j1++)mSA+=A[j1][j1]; mSA/=kp;

3. Выполнить: ic1=ic2=0;np=1;

4. Вывести " mSA=”, inSA ;

5. Выполнить: start = clock();

6. Выполнить генерацию первого разбиения: for(i=0;i<n;i++) pChi[i]=pPsi[i]=1;

7. Обработать первое разбиение, выполнив действия 8 - 10:

    if(np < 2)

{

 8. Выполнить:  for(i=0;i<n;i++) pChi[i]=pPsi[i]=1;

ic1++;

9. Вычислить значение функции S= maxSA для первого разбиения: maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;

for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){

if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];

for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}

if(maxSA<SA[j1])maxSA=SA[j1];}

10. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:

 if(minSA>=maxSA){ minmaxSA=maxSA;minnp=np;

for(j1=0; j1<n; j1++) minpChi[j1]= pChi[j1];

goto m3_result;}

} // if(np < 2)

//************Начало основного цикла

11. Вычислить np : nn1=2; nn2=n; np=(nn1+nn2)/2;

12. Выполнить:

while(nn2>nn1)

{// Изменить pPsi*****************************

13. Определить вектор спецификаций для нового класса эквивалентностей разбиений и построить первый характеристический вектор разбиения в этом классе: ii=np; for (i=n-1; i>0; i--){ if(ii>1){pChi[i]=pPsi[i]=ii; ii--;}else pChi[i]=pPsi[i]=1; }

14. Увеличить значение счётчика и определить minSA:

ic1++;if( ic1>999999999){ic2++;ic1=0;}

maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;

for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){

if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];

for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}

if(maxSA<SA[j1])maxSA=SA[j1];}

15. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:

if(mSA>=maxSA){ minmaxSA=maxSA;minnp=np;

for(j1=0; j1<n; j1++) minpChi[j1]= pChi[j1]; goto m2_result;}

16. Положить: i=n-1;

17. Повторять 18 - 27 пока есть ещё не рассмотренные разбиения в текущем классе эквивалентности:

 while(i>0)

{

//Change PS***************************

18. Изменить вектор спецификаций, выполнив действия 19-23:

 for (i=n-1; i>0; i--)

{

 19. В текущем классе эквивалентности есть нерассмотренная спецификация?

if((pPsi[i]==pPsi[i-1])&&(pPsi[i]<np))

20. Да, тогда. Построить новый вектор pPsi:

{pPsi[i]++; pChi[i]=pPsi[i]; k=np;

         for(ii=n-1; ii>i; ii--) {pPsi[ii] =k; if(k>pPsi[i]) k--;}

21.  Для нового вектора pPsi построить первый характеристический вектор разбиения pCh:

for(ii=1; ii<n; ii++){if(pPsi[ii]==pPsi[ii-1])pChi[ii]=1;else pChi[ii]=pPsi[ii];}           22. Увеличить значение счётчика и определить minSA:

ic1++;if( ic1>999999999){ic2++;ic1=0;}

maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;

for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){

if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];

for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}

if(maxSA<SA[j1])maxSA=SA[j1];}

23. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:

 if(mSA>=maxSA){ minmaxSA=maxSA;minnp=np;

for(j1=0; j1<n; j1++) minpChi[j1]= pChi[j1];

goto m2_result;}

24.  Выполнить: break; } // if(pPsi[i]==pPsi[i-1])&&pPsi[i]<np)

          } //end for i

25. Если цикл «for i» был прерван (был построен новый вектор pPsi), то выполнить построение нового характеристического вектора pChi (действия 26 – 29): if(i>0)

{

26. Выполнить ii=n-1; while(ii>0)

      { if(pChi[ii]<pPsi[ii]) {pChi[ii]++; k=ii; k++;

                while(k<n){if(pPsi[k]==pPsi[k-1]) {pChi[k]=1; }k++;}

               ii=n-1;

27. Увеличить значение счётчика и определить minSA:

 ic1++;if( ic1>999999999){ic2++;ic1=0;}

maxSA=0; for(j1=0; j1<np; j1++)SA[j1]=0;

for(j1=0; j1<np; j1++){for(j2=0; j2<n; j2++){

if((j1+1)==pChi[j2]){SA[j1]+=A[j2][j2];

for(j3=0; j3<n; j3++)if(pChi[j3]!=(j1+1))SA[j1]+= A[j2][j3];}}

if(maxSA<SA[j1])maxSA=SA[j1];}

28. Если найдено разбиение, обеспечивающее требуемое ускорение, то перейти к обработке результата:

if(mSA>=maxSA){ minmaxSA=maxSA;minnp=np;

for(j1=0; j1<n; j1++) minpChi[j1]= pChi[j1];

goto m2_result;}

           }//end if(pChi[j]<pPsi[j])

29. Выполнить:        else ii--;

        }// end while(ii>0)

//Конец изменений pChi**************************

     }// end if(i>0)

} //end while(i>0)

30. Вычислить новое значение np: m2_result:if(mSA>=maxSA)nn2=np; else nn1=np+1; np=(nn1+nn2)/2;

}//end while(nn2>nn1)

//*********************End main cycle

31. Выполнить: m3_result:finish = clock();duration = (double)(finish - start) / CLOCKS_PER_SEC;

32.  Вывести номер экспериментальной точки " N= jj ", число просмотренных вариантов  " NN= ic2* ic1”, время поиска минимального разбиения множества вершин "duration", номер класса эквивалентности "np", в котором найдено решение, значение функции   "S= maxSA", характеристический вектор разбиения множества вершин " minpChi ", который представляет собой найденное решение.

33. Стоп.//Конец описания алгоритма

Описанные в данном разделе алгоритмы были реализованы в виде консольных программ, которые обеспечили их экспериментальное исследование. Результаты этого исследования рассматриваются в следующем разделе.

Для проведения вычислительного эксперимента с алгоритмами Eq2_1, Eq3_1, их программные реализации были объединены в специальную тест-программу. Это позволило выполнять обработку этими алгоритмами одних и тех же матриц смежности взвешенных графов, которые генерировались с использованием равномерно распредел1нных псевдослучайных чисел. Основные результаты вычислительного эксперимента с указанной тест-программой представлены в таблице 3

Таблица 3.  Сравнение алгоритмов Eq2_1, Eq3_1 при  n= 12 , kf=10, kp=3

N

mSA

Последовательный поиск

Двоичный поиск (Eq3_1)

np

maxSA

 Время, с

np

maxSA

Время, с

455,691

451,529

10,469

451,529

1,828

524,902

523,995

5,141

523,995

5,25

477,854

471,153

10,187

471,153

2,11

518,264

517,727

4,765

517,727

4,672

493,197

492,011

8,266

492,011

4,984

501,415

498,243

8,141

498,243

8,141

518,372

517,691

517,691

504,544

501,87

5,422

501,87

5,609

480,443

472,134

10,171

472,134

2,094

501,598

501,512

8,156

501,512

4,968

Среднее время поиска =

Познавательные статьи:



Как правильно слушать собеседника

Типичные ошибки при выполнении бросков в баскетболе

Принятие христианства на Руси и его значение

Средства массовой информации США