Резюме

Резюме

• Пространство состояний есть формализм для представления задач.

• Пространство состояний — это направленный граф, вершины которого соответствуют проблемным ситуациям, а дуги — возможным ходам. Конкретная задача определяется стартовой вершиной и целевым условием. Решению задачи соответствует путь в графе. Таким образом, решение задачи сводится к поиску пути в графе.

• Оптимизационные задачи моделируются приписыванием каждой дуге пространства состояний некоторой стоимости.

• Имеются две основных стратегии поиска в пространстве состояний — поиск в глубину и поиск в ширину.

• Поиск в глубину программируется наиболее легко, однако подвержен зацикливаниям. Существуют два простых метода предотвращения зацикливания: ограничить глубину поиска и не допускать дублирования вершин.

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

• Поиск в ширину всегда первым обнаруживает самое короткое решение, что не верно в отношении стратегии поиска в глубину.

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

• В этой главе были введены следующие понятия:

  пространство состояний

  стартовая вершина, целевое условие,

  решающий путь

  стратегия поиска

  поиск в глубину, поиск в ширину

  эвристический поиск.

Литература

Поиск в глубину и поиск в ширину — базовые стратегии поиска, они описаны в любом учебнике по искусственному интеллекту, см., например, Nilsson (1971, 1980) или Winston (1984). P. Ковальский в своей книге Kowalski (1980) показывает, как можно использовать аппарат математической логики для реализации этих принципов.

Kowalski R. (1980). Logic for Problem Solving. North-Holland.

Nilsson N. J. (1971). Problem Solving Methods in Artificial Intelligence. McGraw-Hill.

Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; also Springer-Verlag, 1981.

Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. — М.: Мир, 1980.]

Поделитесь на страничке

Следующая глава >

Похожие главы из других книг:

Резюме

Из книги автора

Резюме В этой главе предлагается обсуждение сервисов сериализации. Вы могли убедиться в том. что платформа .NET для корректного учета всего множества связанных объектов, подлежащих сохранению в потоке, использует объектные графы. Когда каждый член объектного графа


Резюме

Из книги автора

Резюме В этой главе были рассмотрены варианты конфигурации компоновочных блоков .NET, позволяющие совместное использование типов за рамками одного приложения. Вы увидели, что удаленный объект можно сконфигурировать, как MBV-или MBR-тип. Именно от этого, в конечном счете,


Резюме

Из книги автора

Резюме Эта глава рассказывает об основах построения графического интерфейса с помощью типов, содержащихся в пространстве имен System.Windows.Forms. Сначала вам предлагается создать несколько приложений вручную, и в процессе этого выясняется, что GUI-приложение, как минимум,


Резюме

Из книги автора

Резюме Аббревиатура GDI+ используется для обозначения ряда связанных пространств имен .NET, используемых для визуализации графических образов на поверхности производных от Control типов. Значительная часть этой главы была посвящена выяснению того, как работать с базовыми


РЕЗЮМЕ

Из книги автора

РЕЗЮМЕ Основной темой данной главы было обсуждение возможностей управления ходом выполнения программы. Язык Си предоставляет много средств для структурирования программ. С помощью операторов while и for реализуются циклы с предусловием. Второй оператор особенно подходит


РЕЗЮМЕ

Из книги автора

РЕЗЮМЕ     Для создания больших программ вы должны использовать функции в качестве "строительных блоков". Каждая функция должна выполнять одну вполне определенную задачу. Используйте аргументы для передачи значений функции и ключевое слово return для передачи


Резюме

Из книги автора

Резюме Итак, в этой главе вы познакомились с основами технологий оптических дисков и теперь, вооружившись знаниями, можете приступить к освоению самой программы Nero. По своей мощности и эффективности она не знает себе равных, но и требования, которые она предъявляет к


Резюме

Из книги автора

Резюме В этой главе вы научились устанавливать пакет программ Nero 8 Premium Reloaded, познакомились со средствами запуска приложений пакета с помощью панели StartSmart, узнали, как работать со справочной системой приложений Nero 8 Premium. С помощью Start Smart пользователь пакета сможет


Резюме

Из книги автора

Резюме В этой главе вы узнали, как создавать слайд-шоу. Для этого были использованы средства входящего в пакет Nero 8 приложения Nero Vision. Теперь вы знаете, как поместить фотографии в цифровой фотоальбом, сделать к ним звуковое сопровождение, создать красивое и понятное меню


Резюме

Из книги автора

Резюме В этой главе вы узнали, что можно делать со звуковыми файлами при помощи встроенных в пакет Nero 8 приложений.Как записать файлы формата Audio CD на жесткий диск, как декодировать звуковые файлы в компактный MP3-формат, как с его помощью создать и сохранить на дисках свою


Резюме

Из книги автора

Резюме Подведем краткий итог тому, что вы узнали из этой главы. Прежде всего, вы познакомились с новым приложением Nero Vision, входящим в состав пакета Nero 8. Вы научились создавать диски формата Video CD, используя два приложения – Nero Vision и Nero Burning ROM. Вы узнали, как выбрать


Резюме

Из книги автора

Резюме Итак, подведем итог. Копирование дисков может осуществляться при помощи двух приводов, либо виртуального устройства. Копирование либо с помощью двух приводов осуществляется «на лету» с привода-источника на привод-приемник. А копирование посредством виртуального


Резюме

Из книги автора

Резюме В этой главе мы рассмотрели две очень интересные программы пакета Nero 8 Premium – Nero Vision и Nero Recode, которые позволяют создавать DVD-Video либо из собственных видеоматериалов, либо из уже имеющихся дисков DVD-Video. Теперь вы знаете, как можно, пользуясь Nero Vision, получить


Резюме

Из книги автора

Резюме Мы рассмотрели возможности пакета Nero 8 по архивированию и восстановлению данных средствами приложения Nero BackItUp. Теперь сохранение важной информации в виде резервных копий не будет представлять для вас трудностей. Воспользовавшись информацией из этой главы, вы


Резюме

Из книги автора

Резюме В этой главе вы познакомились со вспомогательными инструментами пакета Nero 8. Теперь для вас не составит труда очистить перезаписываемый диск от ненужных записей, настроить скорость вращения диска в приводе. В этой главе мы также рассмотрели работу новых


Резюме

Из книги автора

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