Intel_Nils (526801), страница 18
Текст из файла (страница 18)
Прерывание хода процесса перебора этапами отсечения ветвей дерева (длв очищения требуемой памяти) было исследовано Дораном н Мичи (1966) и Дораном (1967). Критерии качества работы Доран и Мичи (!966) предложили целенаправленность как критерий эффективности данного поиска. Слейджл и Диксон '(1969) предложили иную меру, которую они назвали «глубинное Гл. 3. Методы поиска а пространстве состояний отношение». Наше «эффективное ветвление» было навеяно этими двумя введенными раньше мерами эффективности. Задачи 3.!. Рассмотрите представление в пространстве состояний дли задачи о коммивояжере, описанной в равд.
2.6. Предложите по крайней мере две функции а' (л' Ф О), являющиеси нижней границей для Ь. Какая из этих функций, по вашему мйению, приведет к более эффективному перебору? Примените алгоритм А* с такими функциями к задаче о коммивояжере для 5 городов, которая показана на рис.
2.4. 3.2. На рис. 2.4 укажите, пользуясь подходом, основанным на пространстве состояний, путь максимальной протяженности, который начинается в А, проходит через каждый другой город не более одного раза и возвращается в А. Выберите представление в пространстве состояний и изобразите часть графа в пространстве состояний с вершинами и стоимостями дуг, снабженными соответствующими пометками, и.укажите иа этом графе оптимальный путь от начальной вершины к целевой. З.З.
Рассмотрите возможные достоинства следующей стратегии перебора в пространстве состояний: любым удобным методом получить некоторый путь к цели и его стоимость С. Эта стоимость не обязательно минимальна, но она дает некоторую верхнюю границу для минимальной стоимости. Теперь' воспользуйтесь алгоритмом А* с некоторой функцией й, гарантирующей допусти. мость, В сразу же отбросьте те полученные Яткрытые вершины, значения ( для которых больше, чем С. Является ли эта модифицированная стратегия допустимой? Означает ли факт возможного отбрасывания некоторых из открытых вершин в этом алгоритме, что число вершин, которые будут раскрыты, может оказаться меньше? Уменьшаются ли прн этом требования к памяти в целом? 3.4. Предположим, что и — нижняя граница для й. Докажите. что если алгоритм А* когда-либо раскроет вершину, для которой г(л) = ((з), то или вершина л была на оптимальном пути, или непосредственно перед раскрытием в списке ОТКРЫТ и на оптимальном пути была такая вершина т, что ?(л) =((ш) = ((з).
3.3. Пусть ль лз, ..., ль — последовательность вершин, раскрытых алгоритмом А*. Докажите, что если й удовлетворяет предположению о непротиворечивости (равд. 3.9), то ((лг) ч= ((лгь~) для любого ! ~ ! < й — !. ч3.6. Используя наиболее развитые представления для задниц о миссионерах и людоедах, данные Амарелем (!963), напишите программу, которая находит решение с минимальным числом ходов дли любого числа л миссионеров н людоедов и для любой вместимости лодки й.
ь3.7. Напишите программу для вычислительной машины, в которой алго- нтм А* используется для преобразования произвольного расположения в за- Р даче о скользящих прямоугольниках в конфигурацию вида если такое преобразование возможно в принципе. Глава 4 ПРЕДСТАВЛЕНИЯ, ДОПУСКАКПДИЕ СВЕДЕНИЕ ЗАДАЧ К ПОДЗАДАЧАМ 4Л. ПРИМЕР ПРЕДСТАВЛЕНИЯ, ДАЮЩЕГО СВЕДЕНИЕ ЗАДАЧИ К ПОДЗАДАЧАМ В этой главе мы исследуем иной подход к решению задач, основанный на сведении задачи к подзадачам, Идея такого подхода состоит «в размышлении в обратном направлении» от задачи, которую предстоит решить, с тем чтобы выделить подзадачи, подподзадачн и т. д., пока, наконец, первоначальная задача не будет сведена к набору тривиальных элементарных задач. Для того чтобы показать, как можно решать задачу методом сведения к подзадачам, мы воспользуемся еще одной головоломкой.
Один из вариантов задачи о пирамидке (ханойской башне) можно сформулировать следующим образом: Имеется три колышка 1, 2 и 3 и три различных диска А, В и С. У дисков в центре имеется отверстие, так что их можно надевать на колышки. Сначала все 'диски расположены на первом 1 х 3 1 х 3 Р и с 4.Ь Задача о пирамидке (слева — начальное положение, справа — це- левое). колышке, больший диск С внизу, а меньший диск А — вверху.
Требуется переместить все диски на третий колышек, двигая нх ро очереди. Перемещать можно всегда только верхний диск, причем нельзя никакой диск помещать выше меньшего. Начальное и целевое расположерия показаны на рис. 4.!. Конечно, эта задача может быть решена методами, использующими пространство состояний. Действительно, на рис. 4.2 показано полное пространство состояний для этой задачи '). Граф имеет 27 вершин, каждая из которых представляет одно из допустимых расположений дисков на колышках.
Обозначение (()й) у каждой вершины графа описывает такое состояние, ') Этот граф был предложен Дж. Маккарти (частное сообщение). 92 Гл. 4. Предсгавленип, допускающие сведение задач к подзадачам когда диск С (наибольший) находится на колышке й диск В— на колышке 1, а диск А (самый маленький) — на колышке й. Если на одном и том же колышке находится более одного диска, то всегда предполагается, что самый большой находится внизу и т. д. Дуги, связывающие между собой пары вершин графа, означают, что некоторый диск может быть переложен так, что почила)аав варева)а (!!1) (222) (2 3) (213) (211) (311) (312) (332) (233) ((емиаи асрасиии )з и с.
4.2. Граф лли задачи о пирамидка конфигурация, представляемая одной из вершин пары, изменится на конфигурацию, представляемую другой вершиной. Например, дуга, идущая от (113) к (123), означает, что (113) можно изменить на (123) посредством перекладывания диска В с колышка 1 на колышек 2. Это действие отражается надписью «Переложить (В,!,2)» у этой, дуги. (Путь, выделенный жирными линиями на этом графе, представляет собой решение задачи.) Задачу о пирамидке можно решить также простым методом сведения задачи к подзадачам. Один из путей сведения исходной задачи о пирамидке, изображенной на рис. 4.1, к совокуп- дд. Пример ооедеиип задачи к подзадачам ностй более простых задач связан со следующей цепочкой рассуждений: 1.
Для того чтобы переложить все диски на колышек 3, мы, конечно, должны переложить на этот колышек диск С, причем в момент, непосредственно предшествующий перекладыванию диска С на колышек 3, последний должен быть свободным. ' 2. Теперь, рассматривая исходную конфигурацию, мы видим, что диск С вообще нельзя никуда переложить, пока с этого колышка не будут сняты диски А и В. Кроме того, диски А и В лучше не размещать на колышке 3, так как тогда у нас не будут возможности поместить там диск С. Таким образом, прежде всего мы должны перенести диски А и В на колышек 2.
3. Затем можно сделать наш основной шаг, переложив диск С с колышка 1' на 3, и перейти к решению оставшейся задапи. Мы видим, что эти рассуждения позволяют свести исходную задачу к следующим трем задачам: 1. Задача с двумя дисками о перемещении дисков А и В на колышек 2: е 2 3 и. 2 Л В221 2. Задача с одним диском о перемещении диска С на колышек 3: е 2 д / 2 Л 1е221 Р221 3. Задача с двумя дисками о перемещении дисков А и В на колышек 3: ч 2 д 2. 5 1згг) ' Й ы о й~ О х Я й Р ж Ф о Я о М М ы и О. ж Ф о Ф Й( о Р3 4.2. Оаисамие задач Каждая из этих трех полученных задач меньше, а следовательно, и должна быть легче, чем исходная задача. Действительно, задача 2 может рассматриваться как элементарная, так как ее решение состоит ровно из одного хода.
Используя подобную цепочку рассуждений, задачи ! и 3 также можно свести к элементарным, как это схематически изображено на рис. 4.3. (Точно такая же схема сведения задачи к совокупности подзадач может быть применена и в случае, когда начальная конфигурация содержит произвольное число дисков.) Графовая структура рис. 4.3 носит название «И!ИЛИ» графа (или графа подзадач); она полезна для иллюстрации решений, получаемых методом сведения задачи к подзадачам.
В этой н следующей главах мы подробно рассмотрим, различные применения метода сведения задачи к подзадачам. Методы сведения задачи к подзадачам нашли применение к широкому кругу проблем, включая задачу получения выражения, которое было бы интегралом от некоторой функции, н задачу доказательства теорем йланиметрии. Мы увидим также, что эти методы полностью аналогичны методам, используемым для вычисления наилучшего следующего хода в таких играх, как шашки илн шахматы. 4.2. ОПИСАНИЕ ЗАДАЧ В подходе, основанном на сведении задачи к подзадачам, используются операторы, которые преобразуют олисамия задач в описания подзадач. Имеется большое число форм описаний задачи. Для этой цели опять могут быть использованы списки, деревья, строки, векторы, массивы и другие формы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
