Определение ИИ (стр. 5 )

Поиск A* - Наиболее широко известная разновидность поиска по первому наилучшему совпадению называется поиском А* (читается как «А звездочка»). В нем применяется оценка узлов, объединяющая в себе g(n), стоимость достижения данного узла, и h(n), стоимость прохождения от данного узла до цели: f(n)=g(n)+h(n). Поскольку функция g(n) позволяет определить стоимость пути от начального узла до узла n, а функция h(n) определяет оценку стоимости наименее дорогостоящего пути от узла п до цели, то справедлива следующая формула: f(n) = оценка стоимости наименее дорогостоящего пути решения, проходящего через узел n Таким образом, при осуществлении попытки найти наименее дорогостоящее решение, по-видимому, разумнее всего вначале попытаться проверить узел с наименьшим значением g(n) + h(n). Как оказалось, данная стратегия является больше чем просто разумной: если эвристическая функция h(n) удовлетворяет некоторым условиям, то поиск А* становится и полным, и оптимальным.

Поиск в оперативном режиме - В действительности сам поиск с восхождением к вершине уже можно считать алгоритмом поиска в оперативном режиме, поскольку предусматривает хранение в памяти только одного текущего состояния! К сожалению, в своей простейшей форме этот алгоритм не очень полезен, так как оставляет агента в таком положении, что последний не может покинуть локальный максимум и отправиться куда-то еще. Более того, в этом алгоритме не может использоваться перезапуск случайным образом, поскольку агент не способен перенести самого себя в новое состояние.

Поиск с удовлетворением ограничений - Формально говоря, любая задача удовлетворения ограничений (Constraint Satisfaction Problem— CSP) определена множеством переменных, X1, X2,…, Xn, и множеством ограничений, C1, C2,…, Cm. Каждая переменная Xi имеет непустую область определения Di возможных значений. Каждое ограничение Ci включает некоторое подмножество переменных и задает допустимые комбинации значений для этого подмножества. Состояние задачи определяется путем присваивания значений некоторым или всем этим переменным, {Xi = vi, Xj = vj,...}. Присваивание, которое не нарушает никаких ограничений, называется совместимым, или допустимым присваиванием. Полным называется такое присваивание, в котором участвует аждая переменная, а решением задачи CSP является полное присваивание, которое довлетворяет всем ограничениям. Кроме того, для некоторых задач CSP требуется найти решение, которое максимизирует целевую функцию.

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

Например: “Альфа-бета-отсечение” – Лучшее враг хорошего. Общий случай: Если для Игрока узел m лучше чем п, то узел п никогда не встретится в игре.

Характеристика языка Пролог.

Пролог (англ. Prolog) — язык и система логического программирования, основанные на языке предикатов математической логики дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка.

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

История

Разработка языка Prolog началась в 1970 г. Аланом Кулмероэ и Филиппом Русселом. Они хотели создать язык, который мог бы делать логические заключения на основе заданного текста. Название Prolog является сокращением от "PROgramming in LOGic". Этот язык был разработан в Марселе в 1972 г. Принцип резолюции Ковальского, сотрудника Эдинбургского университета, казался подходящей моделью, на основе которой можно было разработать механизм логических выводов. С ограничением резолюции на дизъюнкты Хорна унификация привела к эффективной системе, где неустранимый недетерминизм обрабатывался с помощью процесса отката, который мог быть легко реализован. Алгоритм резолюции позволял создать выполняемую последовательность, необходимую для реализации спецификаций, подобных приведенному выше отношению flight.

Первая реализация языка Prolog с использованием компилятора Вирта ALGOL-W была закончена в 1972 г., а основы современного языка были заложены в 1973 г. Использование языка Prolog постепенно распространялось среди тех, кто занимался логическим программированием, в основном благодаря личным контактам, а не через коммерциализацию продукта. В настоящее время существует несколько различных, но довольно похожих между собой версий. Хотя стандарта языка Prolog не существует, однако версия, разработанная в Эдинбургском университете, стала наиболее широко используемым вариантом. Недостаток разработок эффективных приложений Prolog сдерживал его распространение вплоть до 1980 г.

Краткий обзор языка.

Программа на языке Prolog состоит из набора фактов, определенных отношений между объектами данных (фактами) и набором правил (образцами отношений между объектами базы данных). Эти факты и правила вводятся в базу данных через операцию consult. Для работы программы пользователь должен ввести запрос - набор термов, которые все должны быть истинны. Факты и правила из базы данных используются для определения того, какие подстановки для переменных в запросе (называемые унификацией) согласуются с информацией в базе данных.

Язык Prolog, как интерпретатор, приглашает пользователя вводить информацию. Пользователь набирает запрос или имя функции. Выводится значение (истина - yes, или ложь - по) этого запроса, а также возможные значения переменных запроса, присвоение которых делает запрос истинным (то есть унифицирует запрос). Если ввести символ ";", тогда отображается следующий набор значений переменных, унифицирующий запрос, и так до тех пор, пока не исчерпается весь набор возможных подстановок, после чего Prolog печатает no и ждет следующего запроса. Возврат каретки воспринимается как прекращение поиска дополнительных решений.

Хотя выполнение программы на языке Prolog основывается на спецификации предикатов, оно напоминает выполнение программ на аппликативных языках LISP или ML Разработка правил языка Prolog требует того же рекурсивного мышления, что и разработка программ на этих аппликативных языках.

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

Декларативный, процедурный подход языка Пролог.

Пролог (Prolog) — язык логического программирования, основанный на логике дизъюнктов Хорна, представляющей собой подмножество логики предикатов первого порядка. Начало истории языка относится к 70-м годам XX века. Будучи декларативным языком программирования, Пролог воспринимает в качестве программы некоторое описание задачи, и сам производит поиск решения, пользуясь механизмом бэктрекинга и унификацией. Пролог относится к так называемым декларативным языкам, требующим от автора умения составить формальное описание ситуации. Поэтому программа на Прологе не является таковой в традиционном понимании, так как не содержит управляющих конструкций типа if … then, while … do; нет даже оператора присваивания. В Прологе задействованы другие механизмы. Задача описывается в терминах фактов и правил, а поиск решения Пролог берет на себя посредством встроенного механизма логического вывода.

Декларативный подход: B-> PQ

Процедурный подход: Что бы получить В нужно решить P, а затем решить Q.

Основные положения пропорциональной логики и логики 1-го порядка.

Пропозициональная логика — это формальная теория, основным объектом которой служит понятие логического высказывания. С точки зрения выразительности, её можно охарактеризовать как классическую логику нулевого порядка. Логика высказываний является простейшей логикой, максимально близкой к человеческой логике неформальных рассуждений и известна ещё со времён античности. Знаки и (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.

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

Возьмем рассуждение «Каждый человек смертен. Конфуций — человек. Следовательно, Конфуций смертен». Обозначим «x есть человек» через ЧЕЛОВЕК(x) и «x смертен» через СМЕРТЕН(x). Тогда утверждение «каждый человек смертен» может быть представлено формулой: x(ЧЕЛОВЕК(x) → СМЕРТЕН(x)) утверждение «Конфуций — человек» формулой ЧЕЛОВЕК(Конфуций), и «Конфуций смертен» формулой СМЕРТЕН(Конфуций). Утверждение в целом теперь может быть записано формулой:

(x(ЧЕЛОВЕК(x) → СМЕРТЕН(x)) ЧЕЛОВЕК(Конфуций) ) → СМЕРТЕН(Конфуций)

Экспертные системы. Модели представления знаний. Архитектура экспертной системы.

Экспертная система — компьютерная программа, способная частично заменить специалиста-эксперта в разрешении проблемной ситуации. ЭС начали разрабатываться исследователями искусственного интеллекта в 1970-х годах, а в 1980-х получили коммерческое подкрепление. В информатике экспертные системы рассматриваются совместно с базами знаний как модели поведения экспертов в определенной области знаний с использованием процедур логического вывода и принятия решений, а базы знаний — как совокупность фактов и правил логического вывода в выбранной предметной области деятельности.