Intel_Nils (526801), страница 25
Текст из файла (страница 25)
Задачи 4.1. (Для инженеров-электринов.) Покажите, как может быть использовано решающее «И/ИЛИ» дерево для представлении вычислений импеданса показанной ниже электрической цепи. За элементарные факты возьмите возможность вычислить импеданс одиночного звена ??, ь или С (соответствующие значения равны )?, /ыь, !/!мС). Операторы построения дочерних вершин должны быть основаны иа правилах комбинирования импедансов в параллельных н последовательных соединениях. 4.2. Представьте, по Вы студент высшего учебного заведения, изучаю„щий геометрию. Докажите следующую теорему: диагонали параллелограмма, пересекаясь, делятся пополам.
Воспользуйтесь «И/ИЛИ» деревом для изображения этапов, которые Вы прокодите в поиске доказательства. Проставьте в вершинах этого дерева предположения, ноторые были Вами рассмотрены при поиске доказательства. Были ли какие-нибудь из иих отброшены после обращения н модели? Укажите решающее поддерево, дающее доказательство теоремы. 4.3. (Длн программирующих на языке 1.!ЗР.) Напишите на языке ЫЬР прединат РАЗРЕШИМОЕ (ДЕРЕВО), имеющий значение Г, если корневая вершина этого дерева (графа типа «И/ИЛИ») разрешима, и значение г" в противном случае.
Воспользуйтесь любой удобной структурой данных для ДЕРЕВА. 4.4. Объясните, нак бы Вы построили систему решения задачи, основанную на сведении задачи к подзадачам, нредиазиаченную для разбиения любого английского слова иа составляющие его слоги. Предположите, что на каждом этапе сведения задачи к подзадачам строка символов расщепляется ровно иа две строки.
Я.б. История прогресса в развитии систем для автоматического символического интегрирования выдвигает интересный вопрос, касзющийсн определения искусственного интеллекта. Лишь немногие будут сомневаться в том, что программа ЬА1)ЧТ Слейджла является результатом исследования в области искусственного интеллекта. В программе $!Х Мозеса для символического интегрирования редко используется перебор, и по этой причине некоторые считают ее сильнее (разумнее?) программы ЗА!ОТ.
Риш (!969) разработал алгоритм для интегрирования многих типов выражений. Он считаете себя математиком, а не исследователем в области искусственного интеллекта. Как по Вашему мнению, следует ли относить алгоритм Риша к области искусственного интеллекта? При ответе дайте описание критерия для определения 128 Гд 4. Представления, донускаюитие сведение задач к иодзадачам того, что составляет искусственный интеллект. Если Вы исключите из искусственного интеллекта алгоритм Риша, то кзк Вы будете реагировать на заявление, что каждая программа из области искусственного интеллекта в конце концов будет превзойдена некоторым (более разумным?) алгоритмом ие из области искусственного интеллекта? Если же Вы относите алгоритм Риша к области искусственного интеллекта, то не включите ли Вы туда н алгоритм деления многочлена на миогочлен? Я.б. Игра, называемая «последний проигрывает», состоит в следующем: два игрока поочередно берут во одной, две илн три монеты из пучки, перво.
начально содержащей девять монет. Игрок, берущий последнюю монету, проигрывает. Нарисуйте решающее «И/ИЛИ» дерево, которое доказывает, что участник, играющий вторым, всегда может выиграть. Глава 5 МЕТОДЫ ПОИСКА ПРН СВЕДЕНИИ ЗАДАЧ К СОВОКУПНОСТИ ПОДЗАДАЧ вл. процессы перпнорл (поискл) ил грлфлх типл «и)или» После выбора описаний задач и операторов сведения задач к подзадачам можно построить «И~ИЛИ» граф, предназначенный для решения исходной задачи илн для демонстрации ее неразрешимости (при выбранном представлении).
Построение этого графа связано с процессом перебора, который успешно завершается, когда находится решающий граф. В этой главе мы опишем основные приемы ведения эффективного поиска решающих графов. Нахождение решающего графа основано на построении достаточно большой части «И/ИЛИ» графа, показывающей, что начальная вершина разрешима. Приведем здесь еще раз определения разрешимых и неразрешимых вершин, данные в предыдущей главе. Разрешимые вершины Заключительные вершины (соответствующие элементарным задачам) разрешимы. Вершина, не являющаяся заключительной и имеющая дочерние вершины типа «ИЛИ», разрешима тогда и только тогда, когда разрешима по крайней мере одна из ее дочерних вершин.
Вершина, не являющаяся заключительной и имеющая дочерние вершины типа «И», разрешима тогда и только тогда, когда разрешимы все ее дочерние вершины. Неразрешимые вершины Вершины, не являющиеся заключительными и не имеющие дочерних вершин, неразрешимы. Вершина, ие являющаяся заключительной и имеющая дочерние вершины типа «ИЛИ», неразрешима тогда и только тогда, когда неразрешимы все ее дочерние вершины. Вершина, не являющаяся заключительной и имеющая дочерние вершины типа «И», неразрешима тогда и только !30 Гм Б, Методы поиска лри сведении задач к лодеадачам тогда, когда неразрешима по крайней мере одна из ее дочерних вершин. Мы видим, что определения разрешимых и неразрешимых вершин носят рекурсивный характер. Эти определения можно использовать в простых рекурсивных или итеративных процедурах, действующих на «И~ИЛИ» графе, для того чтобы отметить все разрешимые и неразрешимые вершины.
Мы будем называть эти процедуры процедурами разметки разрешимых и неразрешимых вершин. Они применяются при контроле окончания в тех алгоритмах перебора, которые мы будем рассматривать. Перебор заканчивается успешно, если начальная вершина может быть отмечена как разрешимая. Перебор считается закончившимся безуспешно, если начальная вершина может быть отмечена как неразрешимая. В том случае, когда начальная вершина в конечном итоге может быть отмечена как разрешимая, решающим графом будет подграф (содержащий только разрешимые вершины), показывающий в соответствии с нашим определением, что начальная вершина разрешима.
Все процессы перебора, которые мы будем рассматривать, включают следующие этапы: (1) Начальная вершина ассоциируется с начальным описанием задачи. (2) Строятся множества дочерних вершин для начальной вершины с помощью тех операторов сведения задач к подзадачам, которые применимы. Пусть à — такой комбинированный оператор, применение которого дает нам все дочерние вершины для данной вершины. Мы снова назовем этот процесс применения Г к вершине раскрытием вершины. (Напомним, что если при этом строится более одного множества дочерних вершин типа «И», то каждое множество; содержащее более одного элемента, группируется под промежуточной вершиной типа «ИЛИ».) (3) От каждой дочерней вершины назад к ее родительским вершинам проводятся указатели.
Эти указатели используются, когда делается попытка разметить разрешимые и неразрешимые Вершины, а после окончания они дают решающий граф. (4) Процесс раскрытия вершин и установхн указателей продолжается до тех пор, пока начальная вершина не может быть помечена как разрешимая или как неразрешимая. Структура из вершин и указателей, порождаемая в процессе перебора, образует «И/ИЛИ» граф, т. е. подграф всего неявно определенного графа. Мы будем йазывать его гра4юм перв- бора.
В этой главе мы будем заниматься различными процессами перебора на графе типа «И/ИЛИ», в которых выбран эффектив- бл. Процесса перебора (поиска) иа гра4ах гила «И/ИЛИ» 131 ный порядок раскрытия вершин '). Эти процессы в некоторых отношенйях отличаются от процессов перебора в пространстве состояний. Основные различия возникают из-за того, что теперь контроль окончания и методы упорядочения вершин должны быть намного более сложными. Вместо поиска вершин, удовлетворяющих условию цели, мы теперь ведем поиск решающего графа. Таким образом, мы должны в соответствующие моменты времени делать проверку, чтобы убедиться в том, что начальная вершина разрешима.
Однако такую проверку имеет смысл делать лишь после того, как будут построены дочерние вершины, которые разрешимы (например, заключительные вершины). Для проведения такой проверки мы должны прежде всего применить процедуру разметки разрешимости вершин поискового «И/ИЛИ» графа, построенного к данному моменту. Если начальная вершина отмечена как разрешимая, то мы закончили проверку. В противном случае мы продолжаем раскрывать вершины (возможно, запоминая, какие из ранее раскрытых вершин отмечены как разрешимые, с тем чтобы уменьшить объем вычислений при следующей проверке).
Если вершина, выбранная для раскрытия, не является заключительной и не имеет дочерних вершин, то'она неразрешима. Тогда естественно применить процедуру разметки неразрешимости вершин с тем, чтобы проверить, не будет ли начальная вершина.неразрешимой.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
