Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие) [Е. И. Большакова] (doc) читать постранично




Московский государственный университет
им. М.В. Ломоносова

​ Факультет вычислительной математики и кибернетики








​ Е.И. Большакова, М.Г. Мальковский, В.Н. Пильщиков



ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ.
АЛГОРИТМЫ ЭВРИСТИЧЕСКОГО ПОИСКА
(Учебное пособие)











Москва

2002
УДК 519.68+681.142
ББК 22.18



Большакова Е. И., Мальковский М. Г., Пильщиков В. Н. Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие)  М.: Издательский отдел факультета ВМК МГУ (лицензия ИД № 05899 от 24.09.01), 2002.83 с.

В пособии излагаются основные понятия и алгоритмы теории эвристического поиска, представляющей одно из классических направлений исследований в области искусственного интеллекта. Пособие предназначено для студентов факультета ВМК МГУ в поддержку основного курса «Искусственный интеллект», а также для студентов и аспирантов программистских специальностей.
Авторы благодарят Н.Э. Васильеву за помощь в подготовке пособия.



​ Рецензенты: доцент В.Г. Баула
доцент Л.С. Корухова






Печатается по решению Редакционно-издательского Совета факультета вычисли­тельной математики и кибернетики МГУ им. М.В. Ломоносова.





ISBN 5-89407-150-X  Издательский отдел
факультета вычислительной
математики и кибернетики
МГУ им. М.В. Ломоносова,
2002
 Большакова Е.И., Мальковский М.Г.,
Пильщиков В.Н. 2002
Данное пособие представляет собой введение в теорию эвристического поиска – один из наиболее разработанных разделов области исследований, известной под названием «искусственный интеллект».
Как и в других учебниках, в данном пособии основные понятия и методы этой теории иллюстрируются примерами известных игр, головоломок и математических задач. У этой традиции, сложившейся почти за 30 лет существования теории эвристического поиска, существует важная причина. Как пишет один из создателей теории Н. Нильсон, «Игры и математические задачи берутся не потому, что они просты и ясны, а потому, что они при минимальных структурах дают нам наибольшую сложность... В игровых задачах и решениях головоломок возникли и отшлифовались многие идеи, которые оказались по-настоящему полезными для менее легкомысленных задач» [Нильсон73, с.13].
Двумя составными элементами процесса решения задач в теории эвристического поиска является представление (формализация) задач и собственно решение – поиск. В пособии рассматриваются два подхода к решению задач и, соответственно, два способа представления – подход с использованием пространства состояний и подход, основанный на редукции задач. Для обоих подходов описываются используемые алгоритмы поиска решения. Важной особенностью большинства этих алгоритмов является исполь­зование эвристической информации. Эвристикой обычно принято называть любое правило, стратегию, прием, существенно помогающий решению некоторой задачи. В области искусственного интеллекта и теории поиска под эвристической информацией понимается все то, что относится к конкретной решаемой задаче и служит более эффективному ее решению.
​ Глава 1. Подходы к решению задач
​ 1.1. Представление задач в пространстве состояний
​ 1.1.1 Основные понятия
Типичным представителем класса задач, для которых подходит представление в пространстве состояний, является головоломка, известная как игра в пятнадцать – см. рис.1(а). В ней используется пятнадцать пронумерован­ных (от 1 до 15) подвижных фишек, расположенных в клетках квадрата 44. Одна клетка этого квадрата всегда остается пустой, так что одну из соседних с ней фишек можно передвинуть на место этой пустой клетки, изменив тем самым местоположение пустой клетки. Заметим, что более простым вариантом этой головоломки является игра в восемь (квадрат 33 и восемь фишек) – пример соответствующей задачи показан на рис.1(б).
На рис.1(а) изображены две конфигурации фишек. В головоломке требуется преобразовать первую, или начальную, конфигурацию во вторую, или целевую конфигурацию. Решением этой задачи будет подходящая последовательность сдвигов фишек, например: передвинуть фишку 8 вверх, фишку 6 влево и т.д.


Рис. 1. Игра в пятнадцать и игра в восемь фишек
Важной особенностью класса задач, к которому принадлежит игра в пятнадцать (восемь) фишек, является наличие в задаче точно определенной начальной ситуации и точно определенной цели. Имеется также некоторое множество операций, или ходов, переводящих одну конфигурацию в другую. Именно из таких ходов состоит искомое решение задачи, которое можно в принципе получить методом проб и ошибок. Действительно, отправляясь от начальной ситуации, можно построить конфигурации, возникающие в результате выполнения возможных в этой ситуации ходов, затем построить множество конфигураций, получающихся после применения следующего хода, и так далее – пока не будет достигнута целевая конфигурация.
Введем теперь основные