Ханойские башни

Тип работы: Курсовая работа
Бесплатно: Антиплагиат
Объем: 17 страниц
В избранное:

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ
РЕСПУБЛИКИ КАЗАХСТАН

Казахский национальный технический университет
им. Каныша Сатпаева

Институт информатики и информационных технологий
Кафедра информатики

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту

Тема: Ханойские башни

Дисциплина – экспертные и интеллектуальные системы

Руководитель

преподаватель________

____Ахметова М. А.____

"___"____________20__г.

Нормоконтроллер

______________________
"___"____________20__г.
Студент Шигаева К.А.__
Специальность 3704 ___
Группа ПОС-98-5______

Алматы 2002

Задание

Название: "Ханойские башни".

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

Дата получения задания: 10.10.02.

Дата выполнения задания: 20.11.02.

Дата защиты КП: __________.

Содержание

Введение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 3
1 Основная часть ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 4
1.1 Методы поиска в пространстве состояний ... ... ... ... ... ... 5
1.1.1 Метод перебора в глубину ... ... ... ... ... ... ... ... ... 5
1.1.2 Метод полного перебора ... ... ... ... ... ... ... ... ... ... 5
1.1.3 Метод оценки вершин ... ... ... ... ... ... ... ... ... ... . 6
1.2 Метод сведения задач к подзадачам ... ... ... ... ... ... ... .. 7
1.2.1 Постановка задачи ... ... ... ... ... ... ... ... ... ... ... ... 7
1.2.2 Описание метода ... ... ... ... ... ... ... ... ... ... ... ... .. 7
1.3 "ИИЛИ" графы ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 10
2 Описание алгоритма ... ... ... ... ... ... ... ... ... ... ... ... ... ... 13
Заключение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 14
Список литературы. ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 15
Приложение А. Тестирование ... ... ... ... ... ... ... ... ... ... ... .. 16
Приложение Б. Листинг программы ... ... ... ... ... ... ... ... ... .. 17

Введение

Курсовой проект посвящен изучению методов разработки интеллектуальных
игр на примере игры Ханойские башни.

Работа по игровым программам развивалась не зависимо от
математических исследований в области теории игр. Эти два направления имеют
различные цели. Математический анализ игр изучает стратегии, которым должен
следовать идеализированный совершенный игрок, а при программировании же
действие игрока проходит при определенных ограничениях на использование
ресурсов.

Для того, чтобы написать игровую программу, надо решить проблемы
представления структуры игр. Эта структура будет связана с методом поиска
решения. Человек не задумываясь, использует метод проб и ошибок. Обычно при
решении человеком той или иной задачи, он использует в первую очередь, не
метод поиска, а ясную точку зрения на рассматриваемую проблему. Поэтому
имеется два аспекта решения задач: представление и поиск.

Пока, к сожалению, в исследованиях по искусственному интеллекту еще
не выработан универсальный метод для нахождения (искусственных)
великолепных формулировок задач. Остается рассмотреть различные методы
поиска. Но прежде чем такой процесс поиска начат, сама задача должна быть
поставлена в рамках следующих подходов:

- подход, основанный на пространстве состояний,

- подход, основанный на редукциях подзадач,

- подход, как теорема, подлежащая доказательству (исчисление предикатов).

В качестве постановки задачи мы исследуем подход к решению задач,
основанный на сведении задачи к подзадачам.

Чтобы проиллюстрировать этот метод, рассмотрим хорошо известную
головоломку "Ханойские башни". Имеются три стержня А, В и С. Вначале на
стержень А нанизываем несколько дисков: диск наибольшего диаметра находится
внизу, а выше - диски последовательно уменьшающегося диаметра. Цель
головоломки - перемещать диски по одному со стержня на стержень так, чтобы
диск большего диаметра никогда не размещался выше диска меньшего диаметра и
чтобы в конце концов все диски были нанизаны на стержень С.

Данный алгоритм реализован на объектно-ориентированном языке Borland
Delphi 6.0.

1 Основная часть

1.1 Методы поиска в пространстве состояний

1.1.1 Метод перебора в глубину
В методах перебора в глубину прежде всего раскрываются те вершины,
которые были построены последними. Определим глубину вершины дерева
следующим образом:
- глубина корня дерева равна нулю;
- глубина любой последующей вершины равна единице плюс глубина
вершин, которая непосредственно ей предшествует.
Таким образом, вершиной, имеющей наибольшую глубину в дереве
перебора, в данный момент служит та, которая должна в этот момент быть
раскрыта.
Такой подход может привести к процессу, разворачивающегося вдоль
некоторого бесконечного пути, поэтому нужно ввести некоторую процедуру
возвращения. После того как в ходе процесса строится вершина с глубиной,
превышающей некоторую граничную глубину, мы раскрываем вершины наибольшей
глубины, не превышающей этой границы и т.д.
Метод перебора в глубину определяется следующей
последовательности шагов:
1) Поместить начальную вершину в список, называемый ОТКРЫТ.
2) Если список ОТКРЫТ – пуст, то на выход подается сигнал о неудаче поиска,
в противном случае перейти к шагу (3).
3) Взять первую вершину из списка ОТКРЫТ, и перенести ее в список ЗАКРЫТ.
Дать этой вершине название n.
4) Если глубина вершины n равна граничной глубине, то переход в (2), в
противном случае к (5).
5) Раскрыть вершину n, построив все непосредственно следующие за ней
вершины. Поместить их (в произвольном порядке) в начало списка ОТКРЫТ и
построить указатели идущие от них к n.
6) Если одна из этих вершин целевая, то на выход выдать решение,
просматривая для этого соответствующие указатели, в противном случае к
(2).
В алгоритме поиска в глубину сначала идет перебор вдоль одного пути,
пока не будет достигнута максимальная глубина, затем рассматриваются
альтернативные пути той же или меньшей глубины, которые отличаются от него
лишь последнем шагом, после чего рассматриваются пути, отмечающиеся
последними двумя шагами, и т.д.

1.1.2 Метод полного перебора

В методе полного перебора, вершины раскрываются в том порядке, в
котором они строятся. Простой алгоритм полного перебора на дереве состоит
из следующей последовательности шагов:
1) Поместить вершину в список, называемый ОТКРЫТ.
2) Если список ОТКРЫТ – пуст, то на выход подается сигнал о неудаче поиска,
в противном случае перейти к шагу (3).
3) Взять первую вершину из списка ОТКРЫТ, и перенести ее в список ЗАКРЫТ.
Дать этой вершине название n.
4) Раскрыть вершину n, образовав все вершины, непосредственно следующие за
n. Если непосредственно следующих вершин нет, то переход к (2). Поместить
имеющиеся непосредственно следующие за n вершины в конец списка ОТКРЫТ, и
построить указатели, ведущие от них назад к вершине n.
5) Если какие-нибудь из этих непосредственно следующих за n вершин являются
целевыми вершинами, то на выход выдать решение, получающееся просмотром
вдоль указателя; в противном случае переход к (2).
В этом алгоритме предполагается, что начальная вершина не
удовлетворяет поставленной цели, хотя нетрудно ввести этап проверки такой
возможности.
В методе полного перебора непременно будет найден самый короткий путь
к целевой вершине при условии, что такой путь вообще существует.

1.1.3 Метод оценки вершин

Присваивание дугам деревьев определенных цен (с последующим
нахождением решающего пути, имеющего минимальную стоимость) соответствует
многим из таких обещанных критериев. Более общий вариант метода полного
перебора, называемый методом равных цен, позволяет во всех случаях найти
некоторый путь от начальной вершины к целевой, стоимость которой
минимальна.
В этом методе для каждой вершины n в дереве перебора нам нужно
помнить стоимости пути, построенного от начальной вершины s к вершине n.
Пусть g(n) – стоимость от вершины s к вершине n в дереве перебора. В случае
деревьев перебора, мы можем быть уверены, что g(n) является к тому же
стоимостью того пути, который имеет минимальную стоимость (т.к. этот путь
единственный).
В методе равных цен вершины раскрываются в порядке возрастания
стоимости g(n) .
Этот метод характеризуется такой последовательностью шагов:
1) Поместить начальную вершину s в список, называемый ОТКРЫТ. Положить
g(n)=0.
2) Если список ОТКРЫТ пуст, то на выход подается сигнал о неудаче поиска, в
противном случае переходить к следующему шагу.
3) Взять из списка ОТКРЫТ ту вершину, для которой величина g имеет
наименьшее значение, и поместить ее в список ЗАКРЫТ. Дать этой вершине
название n. (В случае совпадения значений выбирать вершину с минимальными
g произвольно, но всегда отдавая предпочтение целевой вершине.)
4) Если n есть целевая вершина, то на выход выдать решающий путь,
получаемый путем просмотра назад в соответствие с указателями; в
противном случае переходить к следующему шагу.
5) Раскрыть вершину n, построив все непосредственно следующие за ней
вершины. (Если таковых нет, переходить к шагу (2).) Для каждой из такой
непосредственно следующей (дочерней) вершины ni вычислить стоимость g(n),
положив g(ni)=g(n)+c(n, ni). Построить эти вершины вмести с
соответствующими им только что найденными значениями g в список ОТКРЫТ и
построить указатели, идущие назад к n.
6) Перейти к шагу (2).

1.2 Метод сведения задач к подзадачам

Идея такого подхода состоит в размышлении в обратном направлении от
задачи, которую предстоит решить, с тем чтобы выделить подзадачи,
подподзадачи и т. д., пока, наконец, первоначальная задача не будет сведена
к набору тривиальных элементарных задач. В подходе, основанном на сведении
задачи к подзадачам, используются операторы, которые преобразуют описания
задач в описания подзадач. Имеется большое число форм описаний задачи. Для
этой цели могут быть использованы списки, деревья, строки, векторы, массивы
и другие формы.
Часто удобно описывать задачу на языке элементов представления в
пространстве состояний. Любая задача поиска в пространстве состояний может
быть представлена как совокупность трех составляющих:
- Множество S начальных состояний.
- Множество F операторов, отображающих описания состояний в описания
состояний.
- Множество G целевых состояний.
Тогда тройка (S, F, G) определяет задачу, и она может быть
использована как описание задачи. В задаче о пирамидке мы использовали
именно это обозначение, хотя, поскольку множество F операторов в
пространстве состояний предполагалось одним и тем же для всех задач, в
описаниях задачи оно в явном виде не присутствовало.
После того как задачи и подзадачи описаны в виде троек (S, F, G),
естественно рассматривать эти подзадачи как задачи нахождения пути между
определенными состояниями-вехами в пространстве состояний.
То обстоятельство, что в подходе, связанном с сведением задачи к
подзадачам, используются понятия состояний, операторов и целей при описании
подзадач, само по себе еще не означает, что этот подход и подход с
использованием пространства состояний по существу совпадают. На самом деле,
как мы уже отмечали, последовательный перебор в пространстве состояний —
это тривиальный случай сведения задачи к подзадачам; по этой причине
подход, связанный со сведением задачи к совокупности подзадач, можно
рассматривать как более общий метод решения, чем последовательный перебор в
пространстве состояний. Можно было бы также рассматривать подход,
основанный на сведении задачи к подзадачам, просто как способ перечисления
отдельных этапов поиска подпутей между предполагаемыми состояниями-вехами в
пространстве состояний и управления процессом компоновки подпутей в полные
решения.

1.2.1 Постановка задачи

Для того чтобы показать, как можно решать задачу методом сведения к
подзадачам, мы воспользуемся головоломкой. Один из вариантов задачи о
пирамидке (ханойской башне) можно сформулировать следующим образом:
Имеется три колышка 1, 2 и 3 и три различных диска А, В и С. У дисков
в центре имеется отверстие, так что их можно надевать на колышки. Сначала
все диски расположены на первом колышке, больший диск С внизу,

Рисунок 1. Задача о "Ханойских башнях"
(слева — начальное состояние, справа — конечное)
а меньший диск А — вверху. Требуется переместить все диски на третий
колышек, двигая их по очереди. Перемещать можно всегда только верхний диск,
причем нельзя никакой диск помещать выше меньшего. Начальное и целевое
расположения, показаны на рисунке 1.

1.2.2 Описание метода

Конечно, эта задача может быть решена методами, использующими
пространство состояний. Действительно, на рисунке 2 показано полное
пространство состояний для этой задачи[1]. Граф имеет 27 вершин, каждая из
которых представляет одно из допустимых расположений дисков на колышках.
Обозначение (ijk) у каждой вершины графа описывает такое состояние, когда
диск С (наибольший) находится на колышке i, диск В — на колышке j, а диск А
(самый маленький)—на колышке k. Если на одном и том же колышке находится
более одного диска, то всегда предполагается, что самый большой находится
внизу и т. д. Дуги, связывающие между собой пары вершин графа, означают,
что некоторый диск может быть переложен так, что конфигурация,
представляемая одной из вершин пары, изменится на конфигурацию,
представляемую другой вершиной. Например, дуга, идущая от (113) к (123),
означает, что (113) можно изменить на (123) посредством перекладывания
диска В с колышка 1 на колышек 2. Это действие отражается надписью
Переложить (В,1,2) у этой, дуги. (Путь, выделенный жирными линиями на
этом графе, представляет собой решение задачи.)
Задачу о пирамидке можно решить также простым методом сведения задачи
к подзадачам. Один из путей сведения исходной задачи о пирамидке,
изображенной на рисунке 1, к совокупности более простых задач связан со
следующей цепочкой рассуждений:

Рисунок 2. Граф для задачи о "Ханойских башнях"
1. Для того чтобы переложить все диски на колышек 3, мы, конечно,
должны переложить на этот колышек диск С, причем в момент, непосредственно
предшествующий перекладыванию диска С на колышек 3, последний должен быть
свободным.
2. Теперь, рассматривая исходную конфигурацию, мы видим, что диск С
вообще нельзя никуда переложить, пока с этого колышка не будут сняты диски
А и В. Кроме того, диски А и В лучше не размещать на колышке 3, так как
тогда у нас не будет возможности поместить там диск С. Таким образом,
прежде всего мы должны перенести диски А и В на колышек 2.
3. Затем можно сделать наш основной шаг, переложив диск С с колышка
1 на 3, и перейти к решению оставшейся задачи.
Мы видим, что эти рассуждения позволяют свести исходную задачу к
следующим трем задачам:
1. Задача с двумя дисками о перемещении дисков А и В на колышек 2:

2. Задача с одним диском о перемещении диска С на колышек 3:
3. Задача с двумя дисками о перемещении дисков А и В на колышек 3:

Рисунок 3. Граф подзадач, сводящий задачу о "Ханойских башнях" к
совокупности элементарных одношаговых задач

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

Вы можете абсолютно на бесплатной основе полностью просмотреть эту работу через наше приложение.