Литература
Различные реализации Пролога используют разные синтаксические соглашения. В данной книге мы применяем так называемый Эдинбургский синтаксис (его называют также синтаксисом DEC-10, поскольку он принят в известной реализации Пролога для машины DEC-10; см. Pereira и др. 1978), он используется во многих популярных пролог-системах, таких как Quintus Prolog, Poplog, CProlog, Arity/ Prolog, Prolog-2 и т.д.
Bowen D. L. (1981). DECsystem-10 Prolog User's Manual. University of Edinburgh: Department of Artificial Intelligence.
Mellish С. and Hardy S. (1984). Integrating Prolog in the POPLOG environment. Implementations of Prolog (J. A. Campbell, ed.). Ellis Horwood.
Pereira F. (1982). C-Prolog User's Manual. University of Edinburgh: Department of Computer-Aided Architectural Design.
Pereira L. M., Pereira F., Warren D. H. D. (1978). User's Guide to DECsystem-10 Prolog. University of Edinburgh: Department of Artificial Intelligence.
Quintus Prolog User's Guide and Reference Manual. Palo Alto: Quintus Computer System Inc. (1985).
The Arity/Prolog Programming Language. Concord, Massachusetts: Arity Corporation (1986).
2-3 деревья детально описаны, например, в Aho, Hopcroft and Ullman (1974, 1983). В книге этих авторов, вышедшей в 1983 г., дается также реализация соответствующих алгоритмов на языке Паскаль. Н.Вирт (см. Wirth (1976)) приводит программу на Паскале для работы с AVL-деревьями. 2-3 деревья являются частным случаем более общего понятия В-деревьев. В-деревья, а также несколько других вариантов структур данных, имеющих отношение к 2-3 деревьям в AVL-деревьям, рассматриваются в книге Gonnet (1984). В этой книге, кроме того, даны результаты анализа поведения этих структур.
Программа вставления элемента в AVL-дерево, использующая только величину "перекоса" дерева (т.е. значение разности глубин поддеревьев, равной -1, 0 или 1, вместо самой глубины) опубликована ван Эмденом (1981).
Aho А. V., Hopcroft J. Е. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. - М.: Мир, 1979.]
Aho А. V., Hopcroft J. Е. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.
Gonnet G. H. (1984). Handbook of Algorithms + Data Structures. Addison-Wesley.
van Emden M. (1981). Logic Programming Newsletter 2.
Wirth N. (1976). Algorithms + Data Structures = Programs. Prentice-Hall. [Имеется перевод: Вирт H. Алгоритмы + структуры данных = программы. - M.: Мир, 1985.]
Назад | Содержание | Вперёд
Поиск в глубину и поиск в ширину - базовые стратегии поиска, они описаны в любом учебнике по искусственному интеллекту, см., например, Nilsson (1971, 1980) или Winston (1984). Р. Ковальский в своей книге 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.]
Назад | Содержание | Вперёд
Программа поиска с предпочтением, представленная в настоящей главе, - это один из многих вариантов похожих друг на друга программ, из которых А*-алгоритм наиболее популярен. Общее описание А*-алгоритма можно найти в книгах 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.
И / ИЛИ-графы и связанные с ними алгоритмы поиска являются частью классических механизмов искусственного интеллекта для решения задач и реализации машинных игр. Ранним примером прикладной задачи, использующей эти методы, может служить программа символического интегрирования (Slagle 1963). И / ИЛИ-поиск используется в самой пролог-системе. Общее описание И / ИЛИ-графов и алгоритма можно найти в учебниках по искусственному интеллекту (Nilsson 1971; Nilsson 1980). Наша программа поиска с предпочтением - это один из вариантов алгоритма, известного под названием АО* . Формальные свойства АО* -алгоритма (включая его допустимость) изучались несколькими авторами. Подробный обзор полученных результатов можно найти в книге Pearl (1984).
Nilsson N.J. (1971). Problem-Solving Methods in Artificial Intelligence. McGraw-Hill.
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.
Slagle J.R. (1963). A heuristic program that solves symbolic integration problems in freshman calculus. In: Computers and Thought (E. Feigenbaum, J. Feldman, eds.). McGraw-Hill.
Назад | Содержание | Вперёд
Книга Michie (1979) - это сборник статей, относящихся к различным аспектам экспертных систем и инженерии знаний. Две ранние экспертные системы, оказавшие большое влияние на развитие этой области, MYCIN и Prospector, описаны в Shortliffe (1976) и Duda et al (1979). Книга Buchanan and Shortliffe (1984) является хорошим сборником статей, посвященных результатам экспериментов с системой MYCIN. Weiss and Kulikowski (1984) описывают свой практический опыт разработки экспертных систем. Вопрос о работе в условиях неопределенности еще нельзя считать вполне решенным: в статье Quinlan (1983) сравниваются различные подходы к этой проблеме. Способ разработки нашей экспертной системы до некоторой степени аналогичен описанному в Hammond (1984). Некоторые примеры, использовавшиеся в тексте, заимствованы из Winston (1984), Shortliffe (1976), Duda et al (1979), Bratko (1982) и Reiter (1980).
Bratko I. (1982). Knowledge-based problem-solving in AL3. In: Machine Intelligence 10 (J.E. Hayes, D. Michie, Y.H. Pao, eds.). Ellis Horwood.
Buchanan B.G. and Shortliffe E.H. (1984, eds.). Rule-based Expert Systems: The МYСIN Experiments of the Stanford Heuristic Programming Project. Addison-Wesley.
Duda R., Gasschnig J. and Hart P. (1979). Model design in the Prospector consultant system for mineral exploration. In: Expert Systems in the Microelectronic Age (D. Michie, ed.). Edinburgh University Press.
Hammond P. (1984). vMicro-PROLOG for Expert Systems. In: Micro-PROLOG: Programming in Logic (K.L. Clark, F.G. McCabe, eds.). Prentice-Hall.
Michie D. (1979, ed.). Expert Systems in the Microelectronic Age. Edinburgh University Press.
Quinlan J.R. (1983). Inferno: a cautious approach to uncertain reasoning. The Computer Journal 26: 255-270.
Reiter J. (1980). AL/X: An Expert System Using Plausible Inference. Oxford: Intelligent Terminals Ltd.
Shortliffe E. (1976). Computer-based Medical Consultations: MYCIN. Elsevier.
Weiss S.M. and Kulikowski CA. (1984). A Practical Guide to Designing Expert Systems. Chapman and Hall.
Winston P. H. (1984). Artificial Intelligence (second edition). Addison-Wesley. [Имеется перевод первого издания: Уинстон П. Искусственный интеллект. - М.: Мир, 1980.]
Назад | Содержание | Вперёд
Минимаксный принцип, реализованный в форме альфа-бета алгоритма, - это наиболее популярный метод в игровом программировании. Особенно часто он применяется в шахматных программах. Минимаксный принцип был впервые предложен Шенноном (Shannon 1950). Возникновение и становление альфа-бета алгоритма имеет довольно запутанную историю. Несколько исследователей независимо друг от друга открыли либо реализовали этот метод полностью или частично. Эта интересная история описана в статье Knuth and Moore (1978). Там же приводится более компактная формулировка альфа-бета алгоритма, использующая вместо минимаксного принципа принцип "него-макса" ("neg-max" principle), и приводится математический анализ производительности алгоритма. Наиболее полный обзор различных минимаксных алгоритмов вместе с их теоретическим анализом содержится в книге Pearl (1984). Существует еще один интересный вопрос, относящийся к минимаксному принципу. Мы знаем, что статическим оценкам следует доверять только до некоторой степени. Можно ли считать, что рабочие оценки являются более надежными, чем исходные статические оценки, из которых они получены? В книге Pearl (1984) собран ряд математических результатов, имеющих отношение к ответу на этот вопрос. Приведенные в этой книге результаты, касающиеся распространения ошибок по минимаксному дереву, объясняют, в каких случаях и почему минимаксный принцип оказывается полезным.
Сборник статей Bramer (1983) охватывает несколько аспектов игрового программирования. Frey (1983) - хороший сборник статей по шахматным программам. Текущие разработки в области машинных шахмат регулярно освещаются в серии Advances in Computer Chess и в журнале ICCA.
Метод Языка Советов, позволяющий использовать знания о типовых ситуациях, был предложен Д. Мики. Дальнейшее развитие этого метода отражено в Bratko and Michi (1980 a, b) и Bratko (1982, 1984, 1985). Программа для игры в эндшпиле "король и ладья против короля", описанная в этой главе, совпадает с точностью до незначительных модификаций с таблицей советов, корректность которой была математически доказана в статье Bratko (1978).
Waterman and Hayes-Roth (1978) - классическая книга по системам, управляемым образцами. В книге Nilsson (1980) можно найти фундаментальные понятия, относящиеся к задаче автоматического доказательства теорем, включая алгоритм преобразования логических формул в конъюнктивную нормальную форму. Прологовская программа для выполнения этого преобразования приведена в Clocksin and Mellish (1981).
Clocksin F. W. and Mellish С S. (1981). Programming in Prolog. Springer- Verlag. [Имеется перевод: Клоксин У., Мелиш К. Программирование на языке Пролог. - М.: Мир, 1987.]
Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; Springer-Verlag.
Waterman D. A. and Hayes-Roth F. (1978, eds). Pattern-Directed Inference Systems. Academic Press.
Назад | Содержание | Вперёд
Clocksin W. F. and Mellish С. S. (1981). Programming in Prolog. Springer-Verlag. [Имеется перевод: Клоксин У., Меллиш К. Программирование на языке Пролог. - М.: Мир, 1987.]
Lloyd J. W. (1984). Foundations of Logic Programming. Springer-Verlag.
Nilsson N. J. (1981). Principies of Artificial Intelligence. Tioga; Springer-Verlag.
Robinson A. J. (1965). A machine-oriented logic based on the resolution principle. JACM 12: 23-41. [Имеется перевод: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции.- В кн. Кибернетический сборник, вып. 7, 1970, с. 194-218.]
Назад | Содержание | Вперёд
Различать "зеленые и "красные" отсечения предложил ван Эмден (1982).
van Emden M. (1982). Red and green cuts. Logic Programming Newsletter: 2.
Назад | Содержание | Вперёд
В этой главе мы занимались такими важными темами, как сортировка и работа со структурами данных для представления множеств. Общее описание структур данных, а также алгоритмов, запрограммированных в данной главе, можно найти, например, в Aho, Hopcroft and Ullman (1974, 1983) или Baase (1978). В литературе рассматривается также поведение этих алгоритмов, особенно их временная сложность. Хороший и краткий обзор соответствующих алгоритмов и результатов их математического анализа можно найти в Gonnet (1984).
Прологовская программа для внесения нового элемента на произвольный уровень дерева (раздел 9.3) была впервые показана автору М. Ван Эмденом (при личном общении).
Aho А. V., Hopcroft J. Е. and Ullman J. D. (1974). The Design and Analysis of Computer Algorithms. Addison-Wesley. [Имеется перевод: Ахо А., Хопкрофт Дж. Построение и анализ вычислительных алгоритмов. Пер. с англ. - М-: Мир, 1979.]
Aho А. V., Hopcroft J. Е. and Ullman J. D. (1983). Data Structures and Algorithms. Addison-Wesley.
Baase S. (1978). Computer Algorithms. Addison-Wesley.
Gonnet G. H. (1984). Handbook of Algorithms and Data Structures. Addison-Wesley.
Назад | Содержание | Вперёд
