Intel_Nils (526801), страница 22
Текст из файла (страница 22)
Читатель мог бы посмотреть, к чему привело бы добавление еще нескольких элементарных задач, таких, как Л Х1ХгХз ~ с-'з У|Угуз Х Хг = У~1 м ~ Х~Х»Хз = ~ Узугуз Х,Х» = У,Уз (сторона-угол-сторона). Важным средством контроля числа порождаемых вершин в «И/ИЛИ» графах служит использование моделей. Под моделью мы здесь понимаем некоторую конкретную интерпретацию общего логического утверждения. Утверждения, которые нам предстоит доказать, часто представляют собой общие чтверждения, охватывающие большое число частных случаев. Любой из этих частных случаев мог бы использоваться в качестве модели общего утверждения. Если это общее утверждение в действительности можно доказать, то тем более любой частный случай, очевидно, будет истинным в соответствующей модели.
В качестве примера рассмотрим только что доказанную тео- рему: АР= СР ~ ОВА= ~ РВС, АР .) ВА, СР .). ВС, РВ, Л ВСР, зз, ВАР. 1!2 Гл. 4. Представления, допускающие сведение задач к иодзадачая Эту задачу можно представлять себе как задачу, содержазцую определенное утверждение, которое может быть формально доказано посредством некоторого абстрактного процесса манипулирования с символами, использующего чисто синтаксические правила сведения задачи к совокупности подзадач. В то же время мы можем интерпретировать ее как некоторое осмысленное утверждение о реальных точках, отрезках и т, п.
на плоскости. С точки зрения семантики в этом утверждении говорится, частный слтчий РЬ частный случай РБ Р я с. 4.11. «И/11ЛИ» решающий граф для рассматраваеиого доказательства теоремы. что независимо от действительного расположения этих точек на плоскости, до тех пор пока справедливы указанные посылки, длина отрезка АР всегда будет равна длине отрезка СР. То есть мы на самом деле могли бы измерить длины этих отрезков и убедиться, что они равны. Конечно, прежде чем мы получим возможность что-то измерять, мы должны взять некоторый частный случай этих посылок и указать реальное расположение этих точек и отрезков так, как это было сделано при построении рис.
4.10. Такой частный пример и служит моделью нашего утверждения. Конечно, если утверждение вообще доказуемо, то его интерпретация на данной модели должна быть истинной. И обратно, если будет установлено, что некоторая интерпретация в некоторой лгодели не является истинной, то очевидно, что это утвер- 4 7. Примеры сведении задачи к совокупности подзадач ыз ждсние не может быто доказано. Использование модели как «мерыж недоказуемости тех нли иных возможных утверждений часто может привести к исключению из рассмотрения большого числа бесполезных порождаемых вершин графа.
Проиллюстрируем использование модели для задачи АВ=ВС ВР=АВ, ~ ВРС= ~ РСВ, ВС, РС СР, АР, Л РАВ, Ь РВС. Мы предполагаем, что программа доказательства теорем имеет доступ к чертежу на рнс. 4.12. Эту задачу следовало бы решать прямым путем посредством введения посылки ВС = ВР В Р и с. 4АХ Чертеж ддн геометрической задачи. Дано; ВП= АВ, к. ВПС = е РСВ. сз ПАВ, Ы)ВС. Доказаты АВ=ВС. и формулировки подзадачи доказательства этой посылки. Но прежде чем будет получено решение, в простом устройстве доказательства теорем будет введена также посылка тХРАВжЬРВС и сформулирована задача ее доказательства.
Очевидно, что равенство сзРАВ ~ ЛРВС не может быть доказано из этих посылок. Проводя несложные подсчеты на этом чертеже (рнс. 4.12), решатель этой задачи мог бы легко установить, что треугольники сзРАВ и ЛРВС модели не равны друг другу, и таким путем выяснить, что подзадача сч,РАВ ж,п РВС неразрешима. После этого данную подзадачу можно было бы изъять нз списка «перспективных» вершин. Обычно программу доказательства теорем нетрудно снабдить моделью.
Для геометрических теорем такой моделью мог бы быть чертеж, построенный по имеющимся посылкам и соответствующим образом представленный в виде списка координат, линий, отрезков и т. д., на основании которого могли быть 114 Гэ. 4. Вредстаеэениа, допускающие сведение задач к аодэадачам сделаны измерения с привлечением, скажем, аналитической геометрии.
При этом нужно позаботиться о том, чтобы расположение выбранных точек было наиболее общим, не допускающим появления случайных совпадений, параллельностей и т. д. Заметим, что если совладения все же имеются или оказались неточными измерения, произведенные на чертеже, то нужно, чтобы устройство доказательства теорем, использующее этот чертеж, не могло бы даже и тогда получить доказательство для недоказуемого утверждения. (Чертежные ошибки могли бы привести к попыткам доказать недоказуемые утверждения. Однако, онн, очевидно, будут безуспешными.) Ошибки могут привести также В С Р н с.
4.1З. Пример, требующий построения вспомогательного отрезка. Дано: ВС 11 АВ, ВС АВ. Доказать: АВ = СВ. к отбрасыванию ключевых доказуемых утверждений, в результате чего доказательство может получиться более длинным, а может и не быть найдено вовсе. Обычно эти осложнения удается предусмотреть и в резуль'- тате получить значительное возрастание эффективности поиска решения при использовании чертежа.
Гелернтер и др. (1960) показали, что использование чертежа в программе .доказательства геометрических теорем уменьшает в среднем число дочерних вершин с 1000 до 5 на одну родительскую вершину. В программе Гелернтера имелась также возможность добавлять некоторые вспомогательные линии к имеющемуся чертежу. Рассмотрим, например, следующую задачу: АВ=С0 АВС0 — четырехугольник, отрезок ВС параллелен отрезку А0, ВС= А0, АВ, С0.
Устройство доказательства теорем может обращаться к чертежу на рис. 4.13. При попытке построить вершины, следующие за начальной вершиной, путем добавления посылок, наше устройство доказательства теорем не может, к сожалению, сделать попытку применить такую элементарную задачу, как АВ = С0~ ЛАВОЙ гм сзВ0С, поскольку треугольники ЬАВ0 и с."ьВ0С не упоми- 4.8. Меланизмы аланирования нри сведении задач к подзадачам !15 наются в наших посылках. Предположим, что вообще не уда-- ется найти никаких последую!цих вершин. Тогда при отсутствии альтернативных подзадач, с которыми в этом случае можно работать, наше устройство вновь обратится к тем элементарным задачам, относительно которых прежде было принято считать, что они неприменимы, поскольку они содержат элементы, не упомянутые в посылках. В случае использования АВ = : С0~ с~,АВ0 ы ЬВ0С порождается следующая «И/ИЛИ» графовая структура ниже начальной вершины: Задачи ГгАВ0) и т.
д. и ллВОС'! и т. д. берутся в качестве элементарных (три точки определяют треугольник). результат этой операции равносилен построению на чертеже отрезка В0, образующего на нем два треугольника. После такого построения доказательство может быть продолжено обычным образом. 48. МЕХАНИЗМЫ ПЛАНИРОВАНИЯ ПРИ СВЕДЕНИИ ЗАДАЧ К ПОДЗАДАЧАМ В настоящем разделе мы опишем один метод сведения задачи к совокупности подзадач, при котором задачи поиска в пространстве состояний сводятся последовательно к все более и более простым, которые могут быть решены тривиально.
Кроме того, этот процесс сведения задач направляется одним из типов механизма планирования, играющим весьма важную роль в искусственном интеллекте. Предположим, что задачу поиска в пространстве состояний, определяемую тройкой (5, г, 6), нам нужно свести к совокупности более простых задач поиска в пространстве состояний. Если бы мы могли выделить последовательность соответствующих «основных промежуточных состояний»' ) и» дл, ..., Пн, то мы получили бы возможность свести первоначальную задачу к множествУ задач, опРеделЯемых тРойками (Я, г', (Дг)), ')' В оригинале пп1ез!опез — «кклоыетроеые столбы».— Прим. рвд. !1З Гл. 4.
Представления, допускающие сведение задач к подзадачам ((ЕД, Е, (Атя)), ..., ((Ен), Р, 6). Решение всех этих задач эквавалентио решению первоначальйой задачи. Если эти основные промежуточные состояния ят, яг, ..., дм определяются явно, то безразлично, в каком порядке решаются результирующие задачи. Иногда, однако, нам удается определить множество 6, состояний, каждое из которых могло бы служить в качестве первого основного промежуточного состояния, множество 6з состояний, каждое из которых могло бы служить в качестве второго, и т. д.
Тогда задача, описываемая тройкой (5, Г', 6т), должна быть решена в первую очередь, чтобы можно было найти конкретное состояние ят ~ 6, прежде, чем будет сформулирована следующая задача ((я1),Р,6з), и т. д.,В следующем разделе мы опишем интересный прием нахождения этих множестн основных промежуточных состояний. 4.9. КЛЮЧЕВЫЕ ОПЕРАТОРЫ Во многих задачах поиска в пространстве состояний нетрудно сообразить, как выделить по крайней мере один оператор в пространстве состояний, который будет находиться где-то в решающей цепочке операторов. То есть, хотя задача нахождения всей цепочки операторов в решении достаточно трудна, задача выделения одного из них часто оказывается легкой.
С возможностью выделения одного такого оператора мы сталкиваемся тогда, когда по характеру задачи применение одного из операторов рассматривается как необходимый шаг решения задачи. (На графах в пространстве состояний применение такого оператора соответствует проведению дуги, связывающей две практически отдельные части графа.) Например, в рассмотренной задаче,о пирамидке оператор «переложить диск С на колышек 3» может быть выделен как оператор, совершенно необходимый при решении задачи (см. рис.
4.2). Мы будем называть операторы такого рода ключевыми операторами. Когда удается найти ключевой оператор, его можно использовать для определения некоторого основного промежуточного состояния в нашем процессе сведения задачи. Предположим, что некоторый ) из Р— ключевой оператор для задачи, задаваемой тройкой (5, Р, 6). Так как мы предполагаем, что оператор Г должен быть применен, то первой задачей, следующей из (5, Г, 6), будет задача поиска пути к некоторому состоянию, к которому 1 применим.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
