* comm - идентификатор группы

* color - признак разделения на группы

* key - параметр, определяющий нумерацию в новых группах

* OUT newcomm - идентификатор новой группы

Данная процедура разбивает все множество процессов, входящих в группу comm, на непересекающиеся подгруппы - одну подгруппу на каждое значение параметра color (неотрицательное число). Каждая новая подгруппа содержит все процессы одного цвета. Если в качестве color указано значение MPI_UNDEFINED, то в newcomm будет возвращено значение MPI_COMM_NULL.

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

Предопределенные константы

Предопределенные константы типа элементов сообщений

Константы MPI Тип в C

MPI_CHAR signed char

MPI_SHORT signed int

MPI_INT signed int

MPI_LONG signed long int

MPI_UNSIGNED_CHAR unsigned char

MPI_UNSIGNED_SHORT unsigned int

MPI_UNSIGNED unsigned int

MPI_UNSIGNED_LONG unsigned long int

MPI_FLOAT float

MPI_DOUBLE double

MPI_LONG_DOUBLE long double

Другие предопределенные типы

MPI_Status - структура; атрибуты сообщений; содержит три обязательных поля:

* MPI_Source (номер процесса отправителя)

* MPI_Tag (идентификатор сообщения)

* MPI_Error (код ошибки)

MPI_Request - системный тип; идентификатор операции посылки-приема сообщения

MPI_Comm - системный тип; идентификатор группы (коммуникатора)

MPI_COMM_WORLD - зарезервированный идентификатор группы, состоящей их всех процессов приложения

Константы-пустышки

* MPI_COMM_NULL

* MPI_DATATYPE_NULL

* MPI_REQUEST_NULL

Константа неопределенного значения

* MPI_UNDEFINED

Глобальные операции

MPI_MAX

MPI_MIN

MPI_SUM

MPI_PROD

Любой процесс/идентификатор

MPI_ANY_SOURCE

MPI_ANY_TAG

Код успешного завершения процедуры

MPI_SUCCESS

2. Задача о ранце

2.1 Постановка задачи о ранце

Задача о ранце -- одна из задач комбинаторной оптимизации. Название это получила от максимизационной задачи укладки как можно большего числа нужных вещей в рюкзак при условии, что общий объём (или вес) всех предметов ограничен. Подобные задачи часто возникают в экономике, прикладной математике, криптографии. В общем виде, задачу можно сформулировать так: из неограниченного множества предметов со свойствами «стоимость» и «вес», требуется отобрать некое число предметов таким образом, чтобы получить максимальную суммарную стоимость при одновременном соблюдении ограничения на суммарный вес.

2.2 Алгоритм задачи о ранце

Пусть имеется n предметов, каждый из которых имеет ценность >0 и вес >0, j = 1,2,3,…..,n. Имеется ранец, грузоподъемность которого есть R, при этом >R, т.е. все предметы в ранец положить невозможно. Необходимо положить в ранец набор предметов с максимальной суммарной ценностью. Введем n переменных:

={0,1},

0 = если предмет с номером j не кладется в ранец,

1 = если предмет с номером j кладется в ранец,

j = 1,2,…….,n.

После введения этих переменных суммарная ценность и грузоподъемность соответственна имеют вид:

= ,

= .

Поэтому задача о ранце имеет вид:

(3.2.1)

, (3.2.2)

(3.2.3)

Естественно предположить, что > 0, 0 < < R, j = 1,2,... ,n. Множество допустимых решений этой задачи -- это множество n -мерных булевых векторов х = (,,...,), удовлетворяющих условию (3.2.2). Вместе с задачей (3.2.1)-(3.2.3) будем рассматривать задачу линейного программирования, в которой вместо условий (3.2.3) вводятся условия

0<<1, j = l,2,...,n. (3.2.3')

2.3 Задача о многомерном ранце

(3.2.4)

(3.2.5)

(3.2.6)

Предполагаем, что > 0, 0 < <, i= 1, 2,..., n, j = 1, 2,...,n.

В этой задаче каждый предмет имеет т свойств (кроме ценности). Эти свойства описываются количественно с помощью элементов столбца с номером j матрицы . Множество допустимых решений этой задачи -- это множество булевых векторов , удовлетворяющих условиям (3.2.5). Вместе с задачей (3.2.4)-(3.2.6) будем рассматривать задачу линейного программирования, в которой вместо условий (3.2.6) вводятся условия

0<<1, j = l,2,...,n. (3.2.6')

Экономическая интерпретация. Пусть имеется п проектов, и для их реализации задан вектор ресурсов b , > 0. Обозначим через > 0 количество единиц ресурса типа i, необходимое для реализации проекта с номером j, при этом для любого ресурса s выполнено условие , т.е. реализация всех проектов невозможна. Пусть > 0, j = 1, 2,...,n -- прибыль, полученная при реализации проекта j. Требуется выбрать для реализации набор проектов с максимальной суммарной прибылью. Введем п булевых переменных:

=0 (если проект j не реализуется),

=1 (если проект j реализуется),

j=1,2,3,…..,n.

Получим задачу о многомерном ранце (3.2.4)-(3.2.6).

Общие свойства задач о ранце

Существование допустимого решения. В задачах (3.2.1)-(3.2.3) и (3.2.4)-(3.2.6) допустимое решение всегда существует (например, нулевое). Если решить задачи линейного программирования (3.2.1)- (3.2.3^;) и (3.2.4)-(3.2.6^/) и в полученных оптимальных решениях заменить дробные значения нулевыми, то получим допустимые решения задач (3.2.1)-(3.2.3) и (3.2.4)-(3.2.6). Число дробных значений в оптимальных решениях линейных задач не превосходит т.

Отсев подмножеств булевых векторов, не содержащих оптимальных решений. Рассмотрим вектор, имеющий к единиц и n -- к нулей. Если вектор х является допустимым (т.е. условия (3.2.2) или (3.2.5) выполнены), то можно исключить из дальнейшего рассмотрения 2к векторов, получающихся из х заменой любого числа единиц нулями, так как для любого такого вектора х значение функции f(x) будет меньше, чем . Если вектор х не является допустимым (т.е. условия (2.2.2) или (2.2.5) не выполняются), то можно исключить из дальнейшего рассмотрения векторов, которые получаются из х заменой любого числа нулей единицами, так как все эти векторы недопустимы.

Оценка точности приближенных булевых решений. Пусть -- допустимое булево решение задачи (3.2.1)-(3.2.3) или (3.2.4)--(3.2.6); -- оптимальное булево решение; -- оптимальное решение задачи (3.2.1)- (3.2.3') или (3.2.4)-(3.2.6^/). Тогда имеет место следующее неравенство:

(3.2.7)

Величина есть гарантированная оценка отклонения приближенного решения от оптимума . Нахождение вектора связано с решением задачи линейного программирования. Далее в п. 3.2.4 показано, что задача (3.2.1)-(3.2.3^/) решается просто. Для решения задачи (3.2.4)-(3.2.6^/) необходимо применение симплексного алгоритма, что не всегда удобно. Для задачи (3.2.4)-(3.2.6) можно получить более грубую оценку, решив последовательность из т задач вида (3.2.1)-(3.2.3^/). Пусть -- значение целевой функции для оптимального решения линейной задачи, полученной из задачи (3.2.4)-(3.2.6^/) с учетом лишь одного ограничения с номером i. Тогда вместо неравенства (3.2.7) получим

 (2.2.8)

В этом случае гарантированная оценка отклонения приближенного решения от оптимума имеет вид:

.

Алгоритм динамического программирования решения задачи о ранце

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

j = 1,2,…….,n ; i = 1,2,……., max.

Решение задачи о ранце на С++

Пусть уравнение имеется вид,

Получается 6 предметов(obj), и максималный вес(max_w) имеет ценность 15.

Решением является вектор из нулей и единиц, задающий значения переменных.

Прямой ход алгоритма динамического программирования решения задачи о ранце

В таблице столбцы обозначают вес от нуля до максимального значения (т.е Грузоподъемность), а строки обозначают количество предметов. Прямой ход алгоритма динамического программирования решения задачи о ранце использует уравнение Беллмана для вычисления очередного значения в ячейке таблицы.

Заполняется столбец сверху вниз.

В данном случае сравнивается 16 и 16 + 9 = 25. Т.к. как 25 больше чем 16, то в ячейку записывается 25.

Максимальное значение целевой функции оказывается в правом нижнем углу.

Обратный ход алгоритма динамического программирования решения задачи о ранце

Обратный ход позволяет восстановить значения переменных найденного решения по таблице.

Проверка результата

Проверяем, что полученное решение удовлетворяет ограничению по весу: суммарный вес предметов равен 14, что меньше 15. Суммарная стоимость предметов 34, что соответствует значению в таблице. Таким образом ответ верен.

Программный код на С + +

1. #include<iostream>

2. #include<conio.h>

16. for(int i=0;i<max_w+1;i++)

17. {

18. if(i<w[j])

19. {

20. if(i==0 || (j-1)<0)a[i][j]=0;

21. else a[i][j]=a[i][j-1];

22. }

23. if(i>=w[j])

24. {

25. if((j-1)<0)a[i][j]=p[j];

26. else

27. {

28. if(a[i][j-1]>(a[k][j-32.1]+p[j]))a[i][j]=a[i][j-1];

29. else a[i][j]=a[k][j-1]+p[j];

30. k++;

31. }

32. }

33. }

34. k=0;

35. }

36. for(int i=0;i<max_w+1;i++)

37. {

38. for(int j=0;j<obj;j++)

39. {

40. cout<<setw(4)<<a[i][j]<<" ";

41. }

42. cout<<endl;

43. }

44. k=max_w;

45. cout<<"\nThe Answer is = ";

46. for(int i=obj-1;i>=0;i--)

47. {

48. if(a[k][i]!=a[k][i-1])

49. {

50. x[i]=1;k=k-w[i];

51. }

52. else if(i==0 && a[k][i]!=0)x[i]=1;

53. else

54. x[i]=0;

55. }

56. for(int i=0;i<obj;i++)cout<<x[i]<<" ";

57. cout<<"\n\nThe maximum value is = "<<a[max_w][obj-1];

58. _getch();

59. }

if(i<w[j]){

if(i==0 || (j-1)<0)a[i][j]=0;

else a[i][j]=a[i][j-1];

}

if(i>=w[j]){

if((j-1)<0)a[i][j]=p[j];

else{

if(a[i][j-1]>(a[k][j-1]+p[j]))a[i][j]=a[i][j-1];

else a[i][j]=a[k][j-1]+p[j];

}

}

}

{

if(a[k][i]!=a[k][i-1])

{

x[i]=1;k=k-w[i];

}

else if(i==0 && a[k][i]!=0)x[i]=1;

else

02. #include<iostream>

03. #include<stdlib.h>

04. #include<stdio.h>

05. #include<math.h>

06. #include<fstream>

07. #include<iomanip>

08. using namespace std;

09. class KnapSolver

10. {