Методологические основы моделирования
 Скачать 2.94 Mb.
|
Рис. 6. Матрицы смежностей А,В и С.Первоначальное заполнение матрицы возможных подстановок (С) производится путем анализа полустепеней исхода и захода исходных графов по правилу: “1”, еслиs(B,bi) ≤ s(A, ai) and s(B,bj) ≤ s(A, aj) Сij= “ “, в остальных случах Выполнена процедура Prov_0_str. Pr_0 = 0 переход на Prov_1_str. Prov_1_str => Pr_1 = 0 переходнаPrioritet. Prioritet (c наименьшим числом подстановок две строки (1-я и 2-я).Выбор первой строки и присвоение ей первого приоритета).PrTab[1] = 1; Mirage =’2’; PrEnd = 0; переход на Mirage1; Mirage1. Определена активная ячейка C[1,2], т.е. выдвинута гипотеза, что B1↔A2. На основании этой гипотезы получаем: C[1,3],C[4,2],C[5,2] = ‘2’; PrExit = 0; Pr_0 = 0. Переход на Mirage3. Mirage3. В связи с тем, что B1 имеет исходы в B3,B4,B6 (B1B3,B4,B6), а A2 A3,A6,A8, то, следовательно, и вершинам B3,B4,B6 могут соответствовать только вершины из множества A3,A6,A8. В таком случае в матрице С получаем: C[3,4],C[3,7],C[4,2],C[4,5],C[6,4],C[6,7] = ‘2’; аналогично для BB5 и для A2A1, т.е. B5↔A1, а C[5,3],C[5,5] = ‘2’; переход на Mirage2. Mirage2. C[2,6],C[6,6] = ‘2’. Переходна Prov_1_str =>ZapolnMatrCM =>ProvEnd. PrExit = 1. (Найденная перестановочная матрица оказалась неверной) =>Nvar = 0 =>ExitToHome (восстановление матрицы С в прежнем виде) => Mirage1; Mirage1. Определена активная ячейка C[1,3], т.е. выдвинута гипотеза, что B1↔A3. На основании этой гипотезы получаем: C[1,2],C[4,3],C[5,3] = ‘2’; PrExit = 0; Pr_0 = 0. Переход на Mirage3. Mirage3. В связи с тем, что B1 B3,B4,B6, а A3 A4,A5,A7, то, следовательно, и вершинам B3,B4,B6 могут соответствовать только вершины из множества A4,A5,A7. В таком случае в матрице С получаем: C[3,6],C[4,2],C[6,6],C[6,8] = ‘2’; аналогично для B1B5 и для A3A2, т.е. B5↔A2, а C[5,1],C[5,5] = ‘2’; переход на Mirage2. Mirage2. Изменений матрицы С не происходит, переход на Prioritet. Prioritet. Активной выбирается строка 4. Pr = 2; (PrTab[4]=2); Mirage = ‘3’. Переход на Mirage1; Mirage1. Определена активная ячейка C[4,5], т.е. выдвинута гипотеза, что B4↔A5. … Переход на Mirage3. Mirage3. В связи с тем, что B4 B2,B3, а A5 A4,A6, то, следовательно, и вершинам B2,B3 могут соответствовать только вершины из множества A4,A6. В таком случае в матрице С получаем: C[2,7],C[3,7] = ‘3’; аналогично для B4B1 и для A5A3, т.е. B1↔A3, изменений матрицы не происходит; переход на Mirage2. 13.Mirage2. C[6,4] = ‘3’. Переходна Prov_1_str =>ZapolnMatrCM =>ProvEnd. PrExit = 1. (решение найдено) =>Nvar = 1 =>Prioritet (попытка поиска автоморфизмов) =>ProvEnd = 1 => конец. Из приведённого описания видно, что все корректировки производились на основе выдвинутых трёх гипотез соответствия пар вершин (одна из которых оказалась ложной, а третья – единственно возможной), и заключались лишь в «подгонке» матрицы возможных подстановок под требования системы ограничений для конкретной гипотезы. Для каждой гипотезы проводится полный цикл проверок, матрицы С (результаты корректировок по циклам показаны на рис.7.(а,б)
|