Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

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

Читайте также:
  1. Алгоритм поиска литературы в электронном каталоге
  2. Алгоритм поиска литературы и др. документов
  3. Армия Спасения открыла первый центр поиска пропавших людей, чтобы помочь семьям найти близких.
  4. В поисках затерянного города
  5. В поисках зомби
  6. В поисках истины
  7. В поисках Конгамато

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

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

B) "xi, xj X1 [((xi, xj) O)→((xi, xj) O1)] (если две вершины, присутствующие в подсети соединены ребром в сети, то это ребро присутствует и в подсети);

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

D) "(xi, xj) O1 g1((xi, xj))=g((xi, xj)) (в подсети сохраняется разметка ребер).

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

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

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

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

Сеть.

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

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

//запрос (17)

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

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

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

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

Отображение hY: X1→X2 называется частичным изоморфизмом семантической сети ((X1, O1), A1, R1, f1, g1) на семантическую сеть ((X, O), A, R, f, g) с критериальным множеством Y X, если для "xi, xj X1 выполняются следующие условия:

A) (xi, xj) O1 => (hY(xi), hY(xj)) O (каждому ребру в исходной сети должно соответствовать ребро в образе);

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

С) g1(xi, xj) g(hY(xi), hY(xj)) (если в исходной сети ребро помечено некими метками, то соответствующее ребро в образе должно содержать, по крайней мере, те же метки);

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

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

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

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

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

//пример (18)

маршрут

1 -4 – 6 + 4 + z

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

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

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

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

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

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

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

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

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

Пример.

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

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

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

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

 


Дата добавления: 2015-09-06; просмотров: 113 | Нарушение авторских прав


Читайте в этой же книге: Логический вывод на хорновских дизъюнктах. | Понятие экспертной системы и применение логического вывода при построении экспертных систем. | Запросы класса C. | Понятие о нечетком выводе | Модальные логики. | Многозначные логики. | Понятие о нечетком выводе на продукциях | Понятие об ИПС. | Линейная модель работы ИПС. | Понятие синтагматических цепей. |
<== предыдущая страница | следующая страница ==>
Понятие семантической сети.| Понятие о логическом выводе на семантических сетях.

mybiblioteka.su - 2015-2024 год. (0.007 сек.)