Искусственный интеллект. Алгоритмы эвристического поиска (учебное пособие) [Е. И. Большакова] (doc) читать постранично
Книга в формате doc! Изображения и текст могут не отображаться!
[Настройки текста] [Cбросить фильтры]
- 1
- 2
- 3
- . . .
- последняя (15) »
Московский государственный университет
им. М.В. Ломоносова
Факультет вычислительной математики и кибернетики
Е.И. Большакова, М.Г. Мальковский, В.Н. Пильщиков
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ.
АЛГОРИТМЫ ЭВРИСТИЧЕСКОГО ПОИСКА
(Учебное пособие)
Москва
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) подвижных фишек, расположенных в клетках квадрата 44. Одна клетка этого квадрата всегда остается пустой, так что одну из соседних с ней фишек можно передвинуть на место этой пустой клетки, изменив тем самым местоположение пустой клетки. Заметим, что более простым вариантом этой головоломки является игра в восемь (квадрат 33 и восемь фишек) – пример соответствующей задачи показан на рис.1(б).
На рис.1(а) изображены две конфигурации фишек. В головоломке требуется преобразовать первую, или начальную, конфигурацию во вторую, или целевую конфигурацию. Решением этой задачи будет подходящая последовательность сдвигов фишек, например: передвинуть фишку 8 вверх, фишку 6 влево и т.д.
Рис. 1. Игра в пятнадцать и игра в восемь фишек
Важной особенностью класса задач, к которому принадлежит игра в пятнадцать (восемь) фишек, является наличие в задаче точно определенной начальной ситуации и точно определенной цели. Имеется также некоторое множество операций, или ходов, переводящих одну конфигурацию в другую. Именно из таких ходов состоит искомое решение задачи, которое можно в принципе получить методом проб и ошибок. Действительно, отправляясь от начальной ситуации, можно построить конфигурации, возникающие в результате выполнения возможных в этой ситуации ходов, затем построить множество конфигураций, получающихся после применения следующего хода, и так далее – пока не будет достигнута целевая конфигурация.
Введем теперь основные
- 1
- 2
- 3
- . . .
- последняя (15) »
Последние комментарии
3 часов 56 минут назад
4 часов 16 минут назад
4 часов 41 минут назад
4 часов 45 минут назад
14 часов 15 минут назад
14 часов 19 минут назад