Intel_Nils (526801), страница 10
Текст из файла (страница 10)
Основная литература по примерам задач Примеры задач, которые мы использовали для иллюстрации методов работы с пространством состояний, связаны с различными областямк, в каждой из котовых своитрадиционныеспециализированные методы решения. Многие из этих методов можно рассматривать как применение подхода, основанного на пространстве состояний. Читателю было бы весьма полезно попытаться в качестве упражнения перевести описания этих специа- Задачи лнзированных методов на обычный язык представления в пространстве состояний.
Задача о коммивояжере занимает важное место в теории исследования операций. Обзор результатов по ней можно найти у Беллмора и Немхозера (1968). Задачи синтаксического анализа обычны при исследовании языков. Фельдман и Грие (!968) дают всесторонний обзор методов синтаксического анализа, используемых трансляцион- ными системами для формальных вычислительных языков. Амарель (!965) обсуждает синтаксический анализ с позиции автоматического решения задач и предлагает процедуру, основанную на сведении задачи к подзадачам. Доступное изложение вопроса об использовании строк и символов и их продукционных систем как вычислительных моделей имеется в заключительных главах книги Минского (1967) по вычислениям.
Множество задач, таких, как распределение, потоки и очереди, может быть решено методом, связанным с пространством состояний. Они рассмотрены в книге Форда и Фалкерсона (1962). Теория управления — это большая специальная область с разнообразными приемами решения возникающих здесь задач. Книга Де Руссо, Роя и Клоуза (1965) может служить хорошим введением в современную георию управления. Проблема поиска хорошего представления Вопросы поиска хорошего представления рассматривали лишь немногие исследователи и, в частности, Амарель. Амарелем (1968) написана классическая работа на эту тему. В ней он последовательно показывает читателю ряд постепенно улучшающихся представлений для задачи о миссионерах и людоедах.
Интересная головоломка, подчеркивающая важность выбора хорошего представления, была отмечена Маккарти (1964). Задача об обезьяне и бананах — стандартный пример задачи о построении рассуждений на основе здравого смысла. Она детально рассмотрена Амарелем (!966). Отмечалось,что использование схем для описания сосгояпий служит мощным приемом представления задачи. В последнем варианте универсального решателя задач допускается использование схем объектов с переменными, как это делается в системе Файкса (1970) решения задач. В статье Ньюэлла (!965) исследуются некоторые возможные подходы (исвязанныес ними ограничения) к задаче получения хорошего представления. Задачи (Для региеиия задач, отмеченных звездочкой, может яотребоваться иесколько часов.
Некоторые из этик задач могли бы служить темой курсовой работы.) 50 Гл. 2. Представление задач и пространстве состояний 2.1. Локомотив Ь н вагоны стоят иа пути, показанном ниже, в порядке. (слева направо), который может быть представлен строкой ЕАВС0. Предположим, что локомотив можно произвольно отцеплять н сцеплять с отдельными вагонами, стрелии могут занимать произвольное положение и локомотив может тянуть и толкать тот вагон, к которому ои прицеплен. Укажите множество правил переписывания для строк, которое можно было бы использовать с целью создания представлений для всех возможных расположений вагонов и локомотива иа прямом отрезке пути. 2.2. Дуга между вершиной л; и вершиной ль следуюпгей за ней, называется невозвратной, если л, недостижима из пь Дайте два примера задач, для которых графы в пространстве состояний содержат невозвратные дуги. 2.3. Покажите, найдя соответствующий путь на графе, представляющем пространство состояний, что строка (((), ()), (), ((), ())) является предложением 8 в грамматике, определяемой следующими правилами перевнсываиия: а) Ю () Ь) А -8 с) А»-А,А б) 5»- (А).
В этих правилах переписывания считается, что символ, стопщий слева от стрелки, может быть подставлеи вместо подстроки символов, стоящей справа от стрелки, в любом месте строки, в котором эта подстрока встретилась. 2,4. Найдите форму описания состояний, операторы и критерии достижения цели для следующей задачи о кувшинах.
Даны кувшин с водой емкостью 5 галлонов н пустой кувшин емкостью 2 галлона. Квк получить ровно один галлон в кувшине емкостью в 2 галлона? Вод можно либо выливать, либо переливать из одного кувшина в другой. ачертите часть дерева перебора, соответствующего тем шагам, которые вы предпринимаете а поиске решения. 2.5. Для следующей задачи о восьми ферзях укажите форму описания состояний, операторы и критерий достижения цели. Разместить 8 ферзей иа обычной шахматной доске так, чтобы на иаждой горизонтали, вертикали и диагонали стоило ие более одного ферзя.
Начертнте часть графа состояний и снабдите его вершины и дуги соответствующими описаниями. 2.5. Наяншите программу для вычислительной машины, порождающую множество строк, которые могут быть получены заменой подстроки 81 подстрокой Ят во всех местах данной строки 5, где стоит подстрока Зь Задачи "2Л. Прочтите работу Амареля (19бб) по прелставленням.
Обратите вииманне на то, что Амарель начинает с весьма примитивного вредстаилеиия, работает немного с ним, а затем постепенно его улучшает. Проведите подробный анализ следуюшей задачи, упоминаемой Маккарти (1994): Удалнте нз доски, содержащей 2л Х 2л клеток, по одной клетке из двух ее противолежащих углов: Покажите, что теперь невозможно полностью покрыть эту искаженную доску фишкамн размером ! Х 2 так, чтобы они ие высовывались за край доски и ие накрывали друг друга. На некотором агаве исследования задачи Бы, возможно, захотите поработать с лаской 2 Х 2, затем с доской 4 Х 4 и т, д., чтобы найти понятна, удобные для предстанлення обшего случая. Напишите отчет о работе над этой задачей и в заключение укажите те наблюдения, которые, быть может, у Вас имеются относительно трудности этой задачи представления. Глава 3 МЕТОДЫ ПОИСКА В ПРОСТРАНСТВЕ СОСТОЯНИЙ ЗЛ.
ПРОЦЕССЫ ПОИСКА НА ГРАФЕ При формулировке задачи в пространстве состояний решение получается в результате применения операторов к описаниям состояний до тех пор, пака не будет получено выражение, описывающее состояние, которое соответствует достижению цели. На примерах, рассмотренных в предыдущей главе, мы видели, как для иллюстрации пространств состояний могут быть использованы графы.
Язык графов чрезвычайно полезен для описания эффективных стратегий перебора (поиска) в пространстве состояний. Все методы перебора в пространстве состояний, которые мы будем обсуждать, могут быть смоделированы с помощью следующего теоретико-графавого процесса: Начальная вершина соответствует описанию начального состояния. Вершины, непосредственно следующие за данной, получаются в результате использования операторов, которые применимы к описанию состояния, ассоциированного с этой вершиной. Пусть à — некоторый специальный оператор, который строит все вершины, непосредственно следующие за данной. Мы будем называть процесс применения оператора Г к вершине раскрытием вершины.
От каждой такой последующей вершины к породившей ее идут указатели, Эти указатели позволяют найти путь назад к начальной вершине, уже после того как обнаружена целевая вершина. Для вершин, следующих за данной, делается проверка, не являются ли они целевыми вершинами. (То есть проверка того, не определяют ли соответствующие описания такие состояния, которые соответствуют цели.) Если целевая вершина еще не найдена, то продолжается процесс раскрытия вершин (и установки указателей). Когда же целевая вершина найдена, эти указатели просматриваются в обратном направлении — от цели к началу, в результате чего выявляется путь решения. Тогда операторы над описаниями состояний, связанные с дугами этого пути, образуют решающую последовательность.
Этапы, указанные выше, описывают просто основные элементы процесса перебора подобно описанию, даваемому блок- д2. Методы полного переборе схемой недетерминираванной программы. При полном описании пронесена перебора нужна еще задать порядок, в котором следует раскрывать вершины. Если вершины раскрываются в том же порядке, в котором оии порождаются, то получается процесс, который называется полным перебором (Ьгеаб(Ь-Вгз( ргосезз). Если же сначала раскрывается всегда та вершина, которая была построена самой последней, то получается процесс перебора в глубину (бер(Ь4!гз( ргосезз).
Процессы полного перебора и перебора в глубину можно назвать также проиедурами слепого перебора, поскольку расположение цели не влияет на порядок, в котором раскрываются вершины. Возможно, однако, что у нас имеется некоторая эвристическая информация о глобальном характере графа и общем расположении цели поиска. (Слово эвристический означает «служащий открытию».) Такого рода информация часто может быть использована для того, чтобы «подтолкнуть» поиск в сторону цели, раскрывая в первую очередь наиболее перспективные вершины.
В этой главе мы опишем несколько эвристических методов перебора в терминах теории графов. Но прежде мы введем ряд основных идей, связанных с перебором, рассмотрев более подробно методы слепого перебора. Сущность этих методов станет понятнее, если мы ограничимся рассмотрением деревьев, а не произвольных графов. Деревом называется граф, каждая вершина которого имеет ровно. одну непосредственно предшествующую ей (родительскую) вершину,за исключением выделенной вершины, называемой корнем дерева, которая вовсе не имеет предшествующих ей вершин. Таким образом, корень дерева служит начальной вершиной.
Для перебора деревья проще графов прежде всего потому, что при построении новой вершины мы можем быть уверены, что она никогда раньше не строилась и' никогда не будет построена вновь. Таким образом, путь от корня до данной вершины единствен. После описания методов слепого поиска для деревьев мы покажем, как их следует модифицировать в случае произвольных графов. 3.2. метОды пОлнОГО пеРеБОРА В методе полного перебора вершины раскрываются в там порядке, в котором они строятся.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
