3. Минимизация функции с численной процедуры минимизации на гиперкубах

Вариант № 4 (21) Т={0, 1, 2, 3, 4, 6, 8, 9, 10, 11, 12, 14, 17, 19, 21, 22, 25, 27}

1. Построение таблицы элементов функции.

Рассмотрим первую по списку вершину. Это вершина 0.

Для выбранной вершины 0 определим ближайших соседей по всем координатным осям.

J_j = J^* + (-1)^Xj 2^j-1,

где J_j - ближайший сосед по j-ой координате;

J^* - выбранная нами вершина.

Так как у нас задан пятимерный гиперкуб, то определять ближайших соседей будем по пяти осям:

J^* = 0 ~ 0 0 0 0 0

J₁ = J^* + (-1)⁰ 2⁰=0+1=1;

J₂ = J^* + (-1)⁰ 2¹=0+2=2;

J₃ = J^* + (-1)⁰ 2²=0+4=4;

J₄ = J^* + (-1)⁰ 2³=0+8=8;

J₅ = J^* + (-1)⁰ 2⁴=0+16=16.

J_∑ = { J_i : i=1,5}={ J₁, J₂, J₃, J₄, J₅}={1, 2, 4, 8, 16}.

J_∑ ∩ T = {1, 2, 4, 8}.

Получили множество вершин, на которых (в дополнение к вершине 0) исходная функция принимает единичное значение.

j₁= {0, 1};

j₂= {0, 2};

j₃= {0, 4};

j₄= {0, 8}.

Таким образом мы получили элементы функции размерности 1.

Найдем элементы функции размерности 2:

(j₁ , j₂) => J₁₂ = J₁ +J₂- J^*=1+2-0=3;

(j₁ , j₃) => J₁₃ = J₁ +J₃- J^*=1+4-0=5;

(j₁ , j₄) => J₁₄ = J₁ +J₄- J^*=1+8-0=9;

(j₂ , j₃) => J₂₃ = J₂ +J₃- J^*=2+4-0=6;

(j₂ , j₄) => J₂₄ = J₂ +J₄- J^*=2+8-0=10;

(j₃ , j₄) => J₃₄ = J₃ +J₄- J^*=4+8-0=12;

J_∑1={ J_12, , J_13, J₁₄, J₂₃, J₂₄, J₃₄} = {3; 5; 9; 6; 10; 12}.

Множество диагональных элементов.

J_∑1 ∩ T = {3, 9, 6, 10, 12}.

Элементы размерности 2:

j₁₂= {0, 1, 2, 3};

j₁₄= {0, 1, 8, 9};

j₂₃= {0, 2, 4, 6};

j₂₄= {0, 2, 8, 10};

j₃₄= {0, 4, 8, 12}.

Найдем элементы функции размерности 3:

J₁ = J^* + (-1)⁰ 2⁰=0+1=1;

J₂ = J^* + (-1)⁰ 2¹=0+2=2;

J₃ = J^* + (-1)⁰ 2²=0+4=4;

J₄ = J^* + (-1)⁰ 2³=0+8=8;

J₅ = J^* + (-1)⁰ 2⁴=0+16=16.

(j₁₂, j_14, j₂₄) => J₁₂₄ = J₁ + J₂ + J₄ - 2J^*=1+2+8-0=11;

(j₂₃, j_24, j₃₄) => J₂₃₄ = J₂ + J₃ + J₄ - 2J^*=2+4+8-0=14;

J_∑2 ={ J₁₂₄, J₂₃₄}={11, 14}.

J_∑2 ∩ T={11, 14}.

Элементы функции размерности 3:

j₁₂₄={0, 1, 2, 3, 8, 9, 10, 11};

j₂₃₄={0, 2, 4, 6, 8, 10, 12, 14}.

Элементов функции размерности 4 и 5 у данной функции нет.

Рассмотрим следующую непокрытую вершину. Это вершина 17.

J^* = 17 ~ 1 0 0 0 1

J₁ = J^* + (-1)¹ 2⁰=17-1=16;

J₂ = J^* + (-1)⁰ 2¹=17+2=19;

J₃ = J^* + (-1)⁰ 2²=17+4=21;

J₄ = J^* + (-1)⁰ 2³=17+8=25;

J₅ = J^* + (-1)¹ 2⁴=17-16=1.

J_∑ = { J_i : i=1,5}={ J₁, J₂, J₃, J₄, J₅}={16, 19, 21, 25, 1}.

J_∑ ∩ T = {19, 21, 25, 1}.

j₂ = {17, 19};

j₃ = {17, 21};

j₄ = {17, 25};

j₅ = {17, 1}.

Таким образом мы получили элементы функции размерности 1.

Найдем элементы функции размерности 2:

(j₂ , j₃) => J₂₃ = J₂ + J₃ - J^*=19+21-17=23;

(j₂ , j₄) => J₂₄ = J₂ + J₄ - J^*=19+25-17=27;

(j₂ , j₅) => J₂₅ = J₂ + J₅ - J^*=19+1-17=3;

(j₃ , j₄) => J₃₄ = J₃ + J₄ - J^*=21+25-17=29;

(j₃ , j₅) => J₃₅ = J₃ + J₅ - J^*=21+1-17=5;

(j₄ , j₅) => J₄₅ = J₄ + J₅ - J^*=25+1-17=9;

J_∑1 = {J₂₃, J₂₄, J₂₅, J_34, J_35, J₄₅} = {23, 27, 3, 29, 5, 9}.

Множество диагональных элементов.

J_∑1 ∩ T ={27, 3, 9}.

Элементы размерности 2:

j₂₄ = {17, 19, 25, 27};

j₂₅= {17, 19, 1, 3};

j₄₅= {17, 25, 1, 9}.

Найдем элементы функции размерности 3:

(j₂₄, j_25, j₄₅) => J₂₄₅ = J₂ + J₄ + J₅ - 2J^* =19+25+1-34=11;

J_∑2={ J₂₄₅}={11}.

J_∑2 ∩ T ={11}.

Элементы размерности 3:

j₂₄₅ = {17, 19, 25, 27, 1, 3, 9, 11}.

Элементов функции размерности 4 и 5 для данной функции для вершины 17 нет.

Рассмотрим следующую непокрытую вершину. Это вершина 22.

J^* = 22 ~ 0 1 1 0 1

J₁ = J^* + (-1)⁰ 2⁰=22+1=23;

J₂ = J^* + (-1)¹ 2¹=22-2=20;

J₃ = J^* + (-1)¹ 2²=22-4=18;

J₄ = J^* + (-1)⁰ 2³=22+8=30;

J₅ = J^* + (-1)¹ 2⁴=22-16=6.

J_∑ = { J_i : i=1,5}={ J₁, J₂, J₃, J₄, J₅}={23, 20, 18, 30, 6}.

J_∑ ∩ T ={6}.

j₅ = {22, 6};

Таким образом мы получили элементы функции размерности 1.

Элементов функции размерности 2, 3, 4 и 5 для данной функции для вершины 22 нет.

На основании полученных выше данных можем составить следующую таблицу:

Таблица элементов функции

		0	17	22
	0		-	-
	1	j1	j5	-
	2	j2	-	-
	3	j12	j25	-
	4	j3	-	-
	6	j23	-	j5
	8	j4	-	-
	9	j14	j45	-
	10	j24	-	-
	11	j124	j245	-
	12	j34	-	-
	14	j234	-	-
	17	-		-
	19	-	j2	-
	21	-	j3	-
	22	-	-
	25	-	j4	-
	27	-	j24	-