Процедура решения задач

Определим теперь понятия «задача», «решение», «алгоритм». Обозначим начальное состояние ПрО через S_H. Задача заключается в том, чтобы перевести предметную область из состояния S_H в некоторое заданное, определяемое как целевое 5_Ц. Очевидно, сделать это возможно, лишь применяя допустимые в данной предметной области действия из множества G = = (g_fg2, •••> gk) — Какие выбрать операции g и в какой последовательности их проводить — неизвестно. В этом как раз и состоит решение задачи. Схема решения, таким образом, выражается формулой.

Допустим, что к состоянию S_H был применен оператор gj. Его реализация перевела состояние 5_Н в S_lf но оно не совпало с S_w т. е. S_{ = g_{(S_u), Sj ф S_n. Для перевода в состояние S₂ поищем другой оператор. Пусть им будет оператор g₂ е G. Результатом его применения будет состояние S₂ = g₂(Sj), и если 5*2 снова не совпадет с 5*_ц, поищем следующий оператор, например, g*₃, чтобы получить состояние 5₃ и оценить его, сравнивая с 5_Ц. И т.д., пока не найдется такой g_;, что Sj = gj (Sj-) и Sj = S_n. Описанный путь поиска решения можно отобразить следующей цепочкой:

То же самое можно написать по-другому:

Последовательность (g_t, g₂, g₃,…, g_;) будет представлять собой алгоритм решения задачи, являющейся результатом синтеза на основе МПрО.

Отметим, что перевод S_u —" S_n возможен не единственным способом. В этом случае можно ставить задачу об оптимизации решения. Приведем примеры построения КМ ПрО.

Пример i.2

Об обезьяне и бананах Рассмотрим широко известную задачу об обезьяне и бананах. В комнате, где находятся обезьяна, имеются ящик и связка бананов, причем бананы подвешены к потолку так высоко, что обезьяна не может дотянуться до них, стоя на полу. Какую последовательность действий должна совершить обезьяна, чтобы достать эти бананы? (Предполагается, что она должна догадаться подтащить ящик к бананам, взобраться на него и дотянуться до них.).

Построим модель данной предметной области. Чтобы определить пзаницы нужного нам фрагмента внешнего мира, начнем с определения целей, которые должны быть достигнуты в результате построения модели. В нашем случае все просто. Обезьяна должна достать бананы с потолка. Но для этого ей придется сообразить, что нужно подтащить ящик под бананы и забраться на него. Таким образом, целевая структура модели задается действиями: подойти, перенести, забраться, схватить. Очевидно, что множество X будет ограничено теми объектами и предметами, которые станут аргументами действий. Тогда мы получаем:

• • подойти (О, Я) — g,(0, Я) — обезьяне подойти к ящику;
• • передвинуть (О, Я) — g₂(0, Я) — обезьяне передвинуть ящик;
• • взобраться (О, Я) — g₃(0, Я) — обезьяне взобраться на ящик;
• • схватить (О, Б) — g₄(0, Б) — обезьяне схватить бананы.

Объединяя аргументы действий, формируем множество X. Это — имена предметов и объектов МПрО: Обезьяна (далее О), Ящик (Я), Бананы (Б), Комната (К).

Начинаем строить множество С — имен свойств выделенных объектов, которые нам необходимо знать для решения задачи. У обезьяны — очень много свойств, например вид, рост, вес, иол, возраст и т. п. Нужны ли они нам для определения действия, которое она должна выполнить в той или иной ситуации? Нужно знать вес и рост, чтобы дотянуться до бананов. Но мы упростили задачу для большей ясности основных идей, поэтому это знание нам пока не понадобится. Договоримся, что у нас исходно обезьяна такого роста и веса, а ящик такого веса и высоты, что высоты Я и роста О будет достаточно для того, чтобы достать бананы. Очевидно, для выполнения всех этих действий мы пока должны знать лишь одно свойство О, Я, Б — в каких местах (точках) комнаты они находятся в начальной ситуации, т. е. их координаты. Возникает также вопрос: а какими свойствами нужно описывать комнату? Задав длину, ширину, высоту? Ясно, что это можно сделать по-разному. Итак, поскольку обезьяна может ходить по комнате, т. е. перемешаться из одной точки в другую, наиболее естественно каким-то образом перечислить эти точки, т. е. описать комнату как некоторое конечное (дискретное) множество точек, которое можно перечислить. Каждую их них можно задать как точки плоскости, но для простоты изложения назовем их точками я, /;, с, р. Таким образом, мы сможем совместить свойства комнаты со свойствами объектов, которые в ней могут находиться. В итоге множество С будет иметь всего одно свойство для всех объектов — координаты (Коорд.) О, Я, Б и точек комнаты. Не будем также выделять пока пространственную составляющую точки, в которой подвешены бананы.

Множество отношений — R между нашими объектами тоже достаточно очевидно. Это: Рядом (О, Я), т. е. обезьяна находится у ящика; На (О, Я) — обезьяна на ящике, наконец, У (О, Б) — бананы у обезьяны. Очевидно, что возможны отрицания этих отношений: He-Рядом (О, Я), Не-У (О, Б), Не-На (О, Я) или иначе: Рядом (О, Я), У (О, Б), На (0, Я).

Отметим также, что все действия имеют в качестве аргументов объекты МПрО, а субъект единственный — обезьяна.

Таким образом, кон центу альная модель нашей задачи и соответствующей ей предметной области ясна: X = (О, Я, Б, К), С = (Коорд. (О), Коорд. (Я), Коорд. (Б),.

Коорд. = (я, Ь_У Су…, р))у R = (Рядом (О, Я), На (О, Я), У (О, Б)), G = (g (0, Я), g₂(0> Я), ?₃(0,Я),&(0,Я)).

Теперь нам необходимо превратить эти фрагменты знания в целостную систему. С этой целью построим отображение F: (S (t) —> G) множества состояний на множество действий. Определим понятия начального — S_l{ и целевого — 5_Ц состояний МПрО. Допустим, Коорд. (О) = я, Коорд. (Я) = Ь, Коорд. (Б) = с, расположенная непосредственно под бананами. Тогда начальное состояние будет удобно описать в виде.

все объекты в начальных позициях, обезьяна Не-На ящике, бананы Не-У обезьяны. Каждое из отношений На и У может принимать лишь два значения Да («1») и Нет («О»): или обезьяна На ящике — Да («1»), или Нет («О»); или У нее бананы — Да («1»), или Нет («О»). Теперь мы можем упростить запись состояний (ср. с (1.8)):

(Все объекты — в одной точке, обезьяна — на ящике и схватила банан.).

Задача, как видим, сводится к тому, как с помощью вышеперечисленных операторов gj, g₂y g₃, g₄ из ситуации (1.9) перейти в ситуацию (1.10). Применяя к 5″ оператор gj — подойти, имеем:

(Обезьяна подошла к ящику, и их координаты совпали.).

Применяем g₂ — передвинуть'.

g₃ — взобраться'.

g₄ — схватить:

Весь процесс можно отобразить формулой.

Правила для описания ситуаций могут быть обобщены для случая, когда координаты нахождения обезьяны и ящика являются переменными. Обозначим их — как .г и у соответственно. Координаты связки бананов тоже можно сделать переменными, но пока для упрощения ситуации не будем этого делать. Тогда каждое правило будет описывать класс состояний, к которым применим тот или иной оператор. Эти правила будут выглядеть следующим образом:

Нетрудно подсчитать число состояний N (мощность подпространства состояний), описываемых каждым прототипом:

для (1.12): N_{ = 20 • 20 • 1? 1 • 1 = 400, для (1.13): N₂ = 20 1 1 — 1 — 1 = 20, для (1.14): N₃ = 1 -1−11*1 = 1, для (1.15): N4=1 -1−11−1 = 1.

Здесь х, у определены на множестве точек комнаты п = 20. А все пространство состояний имеет мощность, равную сумме мощностей подпространств, т.с. 422 состояния.

Данную модель можно сколько угодно усложнять: может меняться местоположение бананов, ящиков может быть несколько, в комнате могут находиться другие предметы и т. п., но смысл преобразований при этом не изменится.

Пример 1.3

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

Множество X: Робот (Р), Ведро (В), Кран (К), Пол (П), Раковина (РК). Множество С:

состояние Ведра — (Пусто, Полно), состояние Крана — (Открыт, Закрыт).

Множество R:

У (Р, Кран) — робот у крана,.

На (В, П) — ведро на полу,.

В (В, РК) — ведро в раковине.

Множество действий — G = (g, g₂, g3. g)> где: g’j — поставить (Р, В, РК) или (Р, В, П), g₂ — открыть (Р, К),.

?₃ — наполнить (Р, В, РК), g₄ — закрыть (Р, К).

Поскольку робот все время находится в одной точке, его можно исключить из рассмотрения. Тогда:

S_H = <�Пусто (В), Закрыт (К), На (В, П)>,.

5_Ц = <�Полно (В), Закрыт (К), На (В, П)>.

Рассмотрим отображение состояний в действия (решения):

• 1. (Пусто (В), Закрыт (К), На (В, II)) —>g_{ —> (Пусто (В), Закрыт (К), В (В, РК));
• 2. (Пусто (В), Закрыт (К), В (В, РК)) —>g₂—> (Пусто (В), Открыт (К), В (В, РК));
• 3. (Пусто (В), Открыт (К), В (В, РК)) —>g₃ —> (Полно (В), Открыт (К), В (В, РК));
• 4. (Полно (В), Открыт (К), В (В, РК) —>g_A —> (Полно (В), Закрыт (К), В (В, РК));
• 5. (Полно (В), Закрыт (К), В (В, РК)) —>gj —> (Полно (В), Закрыт (К), На (В, П)). Последняя ситуация является, как видим, целевой.

Решением задачи является алгоритм.

Примечание 1. Из определения МПрО следует, что отображение F описывает условия применения операторов из множества G к состояниям — предусловиям.

Примечание 2. Из примеров хорошо видно, как важно правильно (удачно) выбрать способ описания ПрО. От этого зависят наглядность представления и даже скорость поиска решения.