Задача поиска кратчайшего обхода образца в семантической сети.

Семантическая сеть ((X₁, O₁), A₁, R₁, f₁, g₁) называется подсетью семантической сети ((X, O), A, R, f, g), если

A) X₁ X, O₁ O (множества вершин и ребер подсети являются подмножествами соответствующих ребер сети);

B) "x_i, x_j X₁ [((x_i, x_j) O)→((x_i, x_j) O₁)] (если две вершины, присутствующие в подсети соединены ребром в сети, то это ребро присутствует и в подсети);

С) "x_i X₁ f₁(x_i)=f(x_i) (в подсети сохраняется разметка вершин);

D) "(x_i, x_j) O₁ g₁((x_i, x_j))=g((x_i, x_j)) (в подсети сохраняется разметка ребер).

Примечание. Из определения видно, что подсеть фактически можно задать подмножеством вершин, т.к. ребра и разметка сохраняются.

Запрос к семантической сети представляется также в виде семантической сети.

Пример. Изображение.

//изобр. аналогично примеру 2 в пункте 4.5.1 (15 – аналог 12)

Сеть.

//сеть аналогично примеру 2 в пункте 4.5.1 (16 – аналог 13)

Запрос. Какие фигуры находятся правее и касаются квадрата, находящегося, в свою очередь, правее и касающегося треугольника.

//запрос (17)

Формально вводится отображение φ(a):a - > P(A), которое задает множество суперпонятий, например

T→{МТ, БТ}, ГФ→{КВ, МТ, БТ},

т.е. понятию «Т» (треугольник) соответствуют понятия MT (малый треугольник) и БT (большой треугольник), все квадраты и треугольники соответствуют понятию «ГФ» (геометрическая фигура).

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

Отображение h_Y: X₁→X₂ называется частичным изоморфизмом семантической сети ((X₁, O₁), A₁, R₁, f₁, g₁) на семантическую сеть ((X, O), A, R, f, g) с критериальным множеством Y X, если для "x_i, x_j X₁ выполняются следующие условия:

A) (x_i, x_j) O₁ => (h_Y(x_i), h_Y(x_j)) O (каждому ребру в исходной сети должно соответствовать ребро в образе);

B) f₁(x_i)<>a₀ => f(h_Y(x_i)) φ(f₁(x_i)) (a₀ – это вершина, помеченная вопросом, остальные вершины должны задавать некие суперпонятия, которые должны содержать по крайней мере те понятия, которыми помечены их образы);

С) g₁(x_i, x_j) g(h_Y(x_i), h_Y(x_j)) (если в исходной сети ребро помечено некими метками, то соответствующее ребро в образе должно содержать, по крайней мере, те же метки);

D) Если x_i, x_j Y X1 => [(hy(x_i)=hy(x_j))→(x_i=x_j)]. (разные вершины исходной сети, принадлежащие критериальному множеству Y отображаются в разные образы).

Подсеть называется релевантной образцу по критерию h_Y, где h_Y – отображение образца на семантическую сеть, если h_Y является частичным изоморфизмом.

Однако иногда требуется не просто выделить релевантную образцу подсеть, а установить соответствие между маршрутами, которые могут описывать конкретные ситуации.

Неформально под маршрутом в семантической сети называется последовательность типа вершина-ребро-вершина и т.д., каждое из которых называется звеном, причем звенья могут быть как положительной, так и отрицательной ориентации. Изображением маршрута называется последовательность пометок вершин и ребер, входящих в маршрут. Поскольку на ребре может быть несколько пометок, то у одного и того же маршрута может быть несколько изображений. Для ребер отрицательной ориентации в изображении предусмотрена специальная пометка T.

Пример маршрута и изображения

//пример (18)

маршрут

1 -4 – 6 + 4 + z

изображение 1

МТ к^Т КВ п^Т КВ п КВ п БТ

изображение 2

МТ к^Т КВ в^Т КВ п КВ к БТ

Полным обходом образца называется маршрут в образце, проходящий по каждому ребру столько раз, сколько пометок на ребре. Изображением полного обхода образца называется изображение соответствующего ему маршрута такое, что для каждого ребра каждая пометка встречается хотя бы один раз.

//пример полного обхода образца, изображения полн обхда и изобр маршр полного обх полнм обх не явл (19)

2 + 3 – 2 + 1 – 2 - полный обход образца,

КВ к? п^Т КВ п Т к^Т КВ – изображение полного обхода образца.

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

Пример.

КВ к? к^Т КВ п Т п^Т КВ

//полный обход образца и покрываемый им маршрут

Доказана следующая теорема. Если некоторая подсеть релевантна образцу в соответствии с критерием h_p, то она релевантна ему и в соответствии с критерием h_Y, при пустом критериальном множестве (Y=ǿ (20)) .

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