Резюме

Резюме

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

• Эвристический принцип поиска с предпочтением направляет процесс поиска таким образом, что для продолжения поиска всегда выбирается вершина, наиболее перспективная с точки зрения эвристической оценки.

• В этой главе был запрограммирован алгоритм поиска, основанный на указанном принципе и известный в литературе как А*-алгоритм.

• Для того, чтобы решить конкретную задачу при помощи А*-алгоритма, необходимо определить пространство состояний и эвристическую функцию. Для сложных задач наиболее трудным моментом является подбор хорошей эвристической функции.

• Теорема о допустимости помогает установить, всегда ли А*-алгоритм, использующий некоторую конкретную эвристическую функцию, находит оптимальное решение.

Литература

Программа поиска с предпочтением, представленная в настоящей главе, — это один из многих вариантов похожих друг на друга программ, из которых А*-алгоритм наиболее популярен. Общее описание А*-алгоритма можно найти в книгах Nillson (1971, 1980) или Winston (1984). Теорема о допустимости впервые доказана авторами статьи Hart, Nilsson, and Raphael (1968). Превосходное и строгое изложение многих разновидностей алгоритмов поиска с предпочтением и связанных с ними математических результатов дано в книге Pearl (1984). В статье Doran and Michie (1966) впервые изложен поиск с предпочтением, управляемый оценкой расстояния до цели.

Головоломка "игра в восемь" использовалась многими исследователями в области искусственного интеллекта в качестве тестовой задачи при изучении эвристических принципов (см., например, Doran and Michie (1966), Michie and Ross (1970) и Gaschnig (1979)).

Задача планирования, рассмотренная в настоящей главе, также как и многие ее разновидности, возникает во многих прикладных областях в ситуации, когда необходимо спланировать обслуживание запросов на ресурсы. Один из примеров — операционные системы вычислительных машин. Задача планирования со ссылкой на это конкретное приложение изложена в книге Coffman and Denning (1973).

Найти хорошую эвристику — дело важное и трудное, поэтому изучение эвристик — одна из центральных тем в искусственном интеллекте. Существуют, однако, некоторые границы, за которые невозможно выйти, двигаясь в направлении улучшения качества эвристик. Казалось бы, все, что необходимо для эффективного решения комбинаторной задачи — это найти мощную эвристику. Однако есть задачи (в том числе многие задачи планирования), для которых не существует универсальной эвристики, обеспечивающей во всех случаях как эффективность, так и допустимость. Многие теоретические результаты, имеющие отношение к этому ограничению, собраны в работе Garey and Johnson (1979).

Coffman E.G. and Denning P.J. (1973). Operating Systems Theory. Prentice-Hall.

Doran J. and Michie D. (1966). Experiments with the graph traverser program. Proc. Royal Socieiy of London 294(A): 235-259.

Garey M. R. and Johnson D. S. (1979). Computers and Intractability. W. H. Freeman. [Имеется перевод: Гэри M., Джонсон Д. С- Вычислительные машины и труднорешаемые задачи. — M.: Мир, 1982.]

Gaschnig J. (1979). Performance measurement and analysis of certain search algorithms. Carnegie-Mellon University: Computer Science Department-Technical Report CMU-CS-79-124 (Ph. D. Thesis).

Hart P.E., Nilsson N.J. and Raphael B. (1968). A formal basis for the heuristic determination of minimum cost paths. IEEE Transactions on Systems Sciences and Cybernetics SSC-4(2):100-107

Michie D. and Ross R. (1970). Experiments with the adaptive graph traverser. Machine Intelligence 5: 301–308.

Nilsson N.J. (1971). Problem — Solving Methods in Artificial Intelligence. McGraw-Hill. [Имеется перевод: Нильсон H. Искусственный интеллект. Методы поиска решений. — M: Мир, 1973.]

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

Pearl J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley.

Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. — M.: Мир, 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. Теперь для вас не составит труда очистить перезаписываемый диск от ненужных записей, настроить скорость вращения диска в приводе. В этой главе мы также рассмотрели работу новых


Резюме

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

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