2. Семейство операций поиска теоретико-графовой окрестности указываемого sc-элемента

Ключевые понятия: поиск теоретико-графовой окрестности.

В рассматриваемое семейство операций навигационно-поисковой графодинамической ассоциативной машины входят следующие операции:

• операция поиска теоретико-графовой окрестности указываемого sc‑элемента по выходящим или входящим парам принадлежности указываемого типа. Указываемый тип может быть составлен из комбинации “константный – переменный – метапеременный” и “позитивная – негативная – нечеткая”;

• операция поиска теоретико-графовой окрестности указываемого sc‑элемента по связкам указываемого отношения с указанием атрибута, который должен быть помечен в искомых связках;

• операция поиска теоретико-графовой окрестности указываемого sc‑элемента в рамках всей памяти или в рамках указываемой формальной теории и семейства указываемых формальных теорий.

Рассмотрим в качестве примера операцию поиска теоретико-графовой окрестности указываемого sc‑элемента по выходящим парам принадлежности константного позитивного типа.

Условием выполненияоперации поиска теоретико-графовой окрестности указываемого sc-элемента по выходящим парам принадлежности константного позитивного типа является наличие конструкции следующего вида:

Здесь sc-узел viявляется sc-узлом, относительно которого осуществляется поиск теоретико-графовой окрестности указываемого sc-элемента по выходящим парам принадлежности константного позитивного типа. Ключевой sc-узелsearchAllуказывает, что необходимо найтивсеэлементы.

Результатом выполненияоперации поиска теоретико-графовой окрестности указываемого sc-элемента по выходящим парам принадлежности константного позитивного типа является сформированное следующие множество:

Здесь результат rsiцелиgliвключает sc-узелvi, который является аргументом поиска, и sc-узлыv1,v2,v3, которые связаны с sc-узломviконстантными позитивными парами принадлежности.

3. Семейство операций поиска в рамках указываемой формальной теории всех истинных высказываний, релевантных указываемой высказывательной форме (заданному образцу)

Ключевые понятия:высказывание;изоморфный поиск.

Напомним, что в языке SCLвысказывание, релевантное заданной высказывательной форме, и сама эта высказывательная форма являются изоморфными логическими формулами. При этом в рамках указанного изоморфизма:

• свободным переменным высказывательной формы ставятся в соответствие константы релевантного высказывания;

• константы высказывательной формы ставятся в соответствие самим себе;

• знаки логических формул, входящих в состав высказывательной формы, ставятся в соответствие знакам логических формул, входящих в состав релевантного высказывания.

Очевидно, что если высказывательная форма является атомарной логической формулой, то релевантное высказывание представляет собой подграф (фрагмент структуры) sc-конструкции, являющейся представлением той предметной области, которая описывается указанной выше формальной теорией.

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

Рассмотрим операцию изоморфного поиска по заданному образцу.

Условием выполненияоперации изоморфного поиска является наличие конструкции следующего вида:

Здесь sc-узел gliявляется множеством, которое содержит образец для изоморфного поиска.

Результатом выполнения операции изоморфного поиска является сформированное множество результатов. Связь цели с результатом осуществляется с помощью отношенияresult(смscg-текст 7.1.1.5)

Микрограммаоперации изоморфного поиска имеет следующий вид.

1. Проверить условие выполнения операции, т.е. найти конструкцию вида:

   

2. Если такой конструкции не найдено, то перейти к шагу 1. Это означает, что в текущем состоянии навигационно-поисковой графодинамической ассоциативной машины нет активного запроса на поиск изоморфного подграфа.

3. Создать множество выполняемых вариантов (обозначим его s_vars). Под вариантом будем понимать кортеж, в состав которого входят множества: помеченное атрибутомFront_,которое содержит такие элементы, от которых можно осуществлять поиск соседних элементов, помеченное атрибутомAnalArc_, которое содержит лишь те дуги, которые еще не имеют соответствий в рамках текущего варианта, а все остальные, – знаки соответствий. Включить в него начальный выполняемый вариантvar_init:

   

4. Просмотреть все элементы шаблона. Все константные элементы поместить в множество front, установить соответствие константного элемента самому себе - сгенерировать конструкцию следующего вида:

   

5. Все переменные дуги поместить в множество analArcs.

6. Просмотреть все элементы множества front. Исключить те элементы, в которыене входятдуги принадлежащие множествуanalArcs. Т.е. удалить те элементы, от которых невозможно вести поиск, т.к. их окрестность уже найдена.

7. Если множество  frontпусто, то перейти к шагу 10.

8. Начало цикла по элементам var_anyмножестваs_vars.

9. Если множество analArcsвариантаvar_anyпусто, то удалить множествоfrontиanalArcs, исключитьvar_anyизs_varsи занести его во множество результатовs_result. Перейти к шагу 8.

10. Иначе выбрать элемент множества frontтекущего вариантаvar_any- sc-элементel_fr. Среди sc-дуг, входящих в этот элемент или выходящих из него и принадлежащих множествуanalArcsвариантаvar_anyвыбрать одну из них - sc-дугуd_an.

    

11. Если el_adjпринадлежит множествуfront вариантаvar_any, т.е. ему уже присвоено соответствие в составе вариантаvar_any, то

12. Найти элемент el_adj_c, являющийся соответствием элементаel_adjв рамках вариантаvar_any.

13. Если между элементами el_adj_сиel_fr_cсуществует sc-дугаd_an_c, "ориентированная" относительноel_fr_cточно таким же образом, какd_an- относительноel_fr(т.е. обе эти дуги - либо входящие, либо выходящие), и не проведенная в вариантеvar_anyникакой sc-дуге, то

14. Фиксируем, что дуге d_anв рамках вариантаvar_anyсоответствует дугаd_an_cи исключаем её из множестваanalArcs.

15. Если множество analArcsвариантаvar_anyстановится пустым, то следует перейти к шагу 9 (вариант завершается успешно).

16. Если элемент el_frбольше не инцидентен ни одной sc-дуге, принадлежащей множествуanalArcsвариантаvar_any, тоel_frисключается из множестваfrontвариантаvar_any, как элемент, от которого невозможно осуществить поиск соседей, т.к. всем инцидентным ему дугам уже найдены соответствия.

17. Если элемент el_adjбольше не инцидентен ни одной sc-дуге, принадлежащей множествуanalArcsвариантаvar_any, тоel_frисключается из множестваfrontвариантаvar_any.

18. Если в sc-дугу d_anвходят sc-дуги, являющиеся элементами множестваanalArcsвариантаvar_any, то занестиd_anв множествоfrontвариантаvar_any.

19. Перейти к шагу 10.

20. Иначе sc-дуге d_anневозможно присвоить соответствие.

21. Удалить множества frontиanalArcs, удалить все найденные соответствия, вариантvar_anyисключить из множестваs_vars, (фиксируется его безуспешное завершение). Перейти к шагу 8.

22. Сформировать множество m_el_adj_cэлементов, которые могут быть поставлены в соответствие элементуel_adjи которые не были поставлены другим элементам шаблона в рамках вариантаvar_any. В это множество не могут быть включены элементы, которые уже были поставлены в соответствие некоторому элементу шаблона в рамках текущего варианта.

23. Если множество m_el_adj_cпусто, то перейти к шагу 22 (вариантvar_anyявляется неудачным и его следует исключить из множества вариантов).

24. Иначе sc-дуга d_anисключается из множестваfrontвариантаvar_any.

25. Если в sc-дугу d_anвходят sc-дуги, являющиеся элементами множестваanalArcsвариантаvar_any, то занестиd_anво множествоfrontвариантаvar_any.

26. Если в sc-элементel_adjвходят sc-дуги, являющиеся элементами множестваanalArcsвариантаvar_any, то занестиel_adjво множествоfrontвариантаvar_any.

27. Если элемент el_frбольше не инцидентен ни одной sc-дуге, принадлежащей множествуanalArcsвариантаvar_any, тоel_frисключить изfrontвариантаvar_any.

28. Начало цикла по элементам el_adj_cмножестваm_el_adj_c.

29. Завести новый вариант var_new, множестваfrontиanalArcsвариантаvar_anyкопировать в соответствующие им множества в вариантеvar_new, также в новый вариант копировать все найденные соответствия.

    

30. Еще раньше, при занесении элемента el_adj_cво множествоm_el_adj_cдолжна была быть зафиксирована sc-дугаd_an_a, связывающая sc-элементыel_fr_cиel_adj_cсвязью соответствующего направления. Теперь устанавливаем соответствие между элементамиd_anиd_an_a, а также междуel_adjиel_adj_cв рамках вариантаvar_new,т.е. присваиваем соответствия элементамd_anиel_adjв рамках вариантаvar_new.

31. Если множество analArcsвариантаvar_newпусто, то удаляется множестваfront иanalArcs в рамках вариантаvar_new, вариантvar_newисключается из множестваs_varsи заносится в результирующее множествоs_result. Перейти к шагу 39. (Зафиксировать успешное завершение вариантаvar_new).

32. Если el_adj- sc-узел, то перейти к шагу 43.

33. Считаем, что значением daявляетсяel_adj.

34. Зафиксировать da_beg- начало sc-дугиda;da_end- конец sc-дугиda.

35. Находим sc-дугуda_c, соответствующуюsc-дугеda. Зафиксировать:da_c_beg- начало sc‑дугиda_c;da_c_end- конецsc-дугиda_c.

36. Если элемент, являющийся соответствием элемента da_beg в рамках вариантаvar_new определенине равенda_c_begилиесли элемент, являющийся соответствием элементаda_end в рамках вариантаvar_new определенине равенda_c_end, то зафиксировать безуспешное завершение вариантаvar_new(уничтожаются множестваfrontиanalArcs варианта var_new, уничтожаются все найденные соответствия, вариантvar_newисключается из множестваs_vars). Перейти к шагу 43.

37. Если элемент, являющийся соответствием элемента da_beg в рамках вариантаvar_newне определен, то  назначаем соответствующим ему в рамках вариантаvar_newэлементомda_c_beg.

38. Если элемент, являющийся соответствием элемента da_endв рамках вариантаvar_newне определен, то  назначаем соответствующим ему в рамках вариантаvar_newэлементомda_c_end.

39. Исключить sc-дугу daиз множестваanalArcs варианта var_new.

40. Если множество analArcsвариантаvar_newпусто, то перейти к шагу 32. (зафиксировать успешное завершение вариантаvar_new).

41. Если da_end- sc-дуга, принадлежащая множествуanalArcsвариантаvar_new, то  Считаем, что значениемdaявляетсяda_end; Перейти к шагу 37.

42. Конец цикла по элементам  el_adj_cмножестваm_el_adj_c.

43. Исключить вариант var_anyиз множества выполняемых вариантовs_vars.

44. Конец цикла по элементам var_anyмножестваs_vars.

45. Пометить исходную цель как достигнутую, что сводится к формированию следующей sc‑конструкции:

Конец микропрограммы.

Пример выполненияоперации изоморфного поиска приведен в подразделе 7.2.

Реализацияоперации изоморфного поиска на языкеSCPприведена в [411] (ПрогрВАМ-2001кн)