Приобретение знаний Извлечение знаний из данных Курс Интеллектуальные информационные системы Лекция 7 доклад по теме Информатика

Доклад раскрывает тему " Приобретение знаний Извлечение знаний из данных Курс Интеллектуальные информационные системы Лекция 7 ".
Презентация поможет подготовится к предмету Информатика, может быть полезна как ученикам и студентам, так и преподавателям.
Материал представлен на 43 страницах, оформлен в виде презентации, доступен для скачивания и просмотра онлайн.

Навигация по документу

Страница №1
Приобретение знаний. Извлечение знаний из данных. Курс «Интеллектуальные информационные системы» Лекция 7
Страница №2
Приобретением знаний
называется выявление знаний из источников и преобразование их в нужную форму, а также перенос в базу знаний интеллектуальной системы.
Приобретением знаний называется выявление знаний из источников и преобразование их в нужную форму, а также перенос в базу знаний интеллектуальной системы.
Страница №3
Источники знаний:
Книги, архивные документы, содержимое других баз знаний, т.е. некоторые объективизированные знания, приведенные к форме, которая делает их доступными для потребителя;
Экспертные знания, которые имеются у специалистов, но не зафиксированы во внешних по отношению к ним хранилищах (субъективные);
Эмпирические знания (субъективные), получающиеся путем наблюдения за окружающей средой (если у ИС есть средства наблюдения)
Источники знаний: Книги, архивные документы, содержимое других баз знаний, т.е. некоторые объективизированные знания, приведенные к форме, которая делает их доступными для потребителя; Экспертные знания, которые имеются у специалистов, но не зафиксированы во внешних по отношению к ним хранилищах (субъективные); Эмпирические знания (субъективные), получающиеся путем наблюдения за окружающей средой (если у ИС есть средства наблюдения)
Страница №4
Методология приобретения субъективных знаний
Две формы представления:
модели и формы хранения знаний у человека – эксперта
Модель, по которой инженер по знаниям (проектировщик ИИС), собирается их описывать
Методология приобретения субъективных знаний Две формы представления: модели и формы хранения знаний у человека – эксперта Модель, по которой инженер по знаниям (проектировщик ИИС), собирается их описывать
Страница №5
Схема приобретения знаний
Схема приобретения знаний
Страница №6
Когнитивные структуры знаний
Представление класса понятий через его элементы
Птица=<чайка, воробей, скворец,…>
Представление понятий класса с помощью базового прототипа
Птица=<нечто с крыльями, с клювом, летает, …>
Представление с помощью признаков
Птица=<крылья, клюв, две лапы, перья…>
Когнитивные структуры знаний Представление класса понятий через его элементы Птица=<чайка, воробей, скворец,…> Представление понятий класса с помощью базового прототипа Птица=<нечто с крыльями, с клювом, летает, …> Представление с помощью признаков Птица=<крылья, клюв, две лапы, перья…>
Страница №7
Представление когнитивной модели
Отношения между понятиями определяются процедурным способом
Отношения между оставляющими понятий – декларативным способом.
Представление когнитивной модели Отношения между понятиями определяются процедурным способом Отношения между оставляющими понятий – декларативным способом.
Страница №8
Формирование БЗ в ИИС
Переход от описания некоторой области в поле знаний аналогичен переходу от концептуальной модели БД к ее логической схеме
Формирование БЗ в ИИС Переход от описания некоторой области в поле знаний аналогичен переходу от концептуальной модели БД к ее логической схеме
Страница №9
Информация вложена в изображении слайда
Страница №10
Схема приобретения знаний
Носитель информации → Посредник → Модель знания


Посредник – человек, обладающий специфическими знаниями инженер по знаниям или когнитолог
Схема приобретения знаний Носитель информации → Посредник → Модель знания Посредник – человек, обладающий специфическими знаниями инженер по знаниям или когнитолог
Страница №11
Причины использования посредника
Эксперт владеет субъективными знаниями, которые не всегда можно выразить словами, упускает промежуточные звенья цепочки вывода.
Объясняющий в процессе объяснения сам начинает лучше понимать проблему
Посреднику, владеющему меньшим объемом знаний о ПО, проще постепенно строить целостную модель Предметной области (ПО)
Причины использования посредника Эксперт владеет субъективными знаниями, которые не всегда можно выразить словами, упускает промежуточные звенья цепочки вывода. Объясняющий в процессе объяснения сам начинает лучше понимать проблему Посреднику, владеющему меньшим объемом знаний о ПО, проще постепенно строить целостную модель Предметной области (ПО)
Страница №12
В качестве посредника могут использоваться
Инженер по знаниям (когнитолог)
Специальная программа
В качестве посредника могут использоваться Инженер по знаниям (когнитолог) Специальная программа
Страница №13
По отношению к носителю предметного знания посредник должен обладать метазнанием, к которому относится знание следующих научных областей
По отношению к носителю предметного знания посредник должен обладать метазнанием, к которому относится знание следующих научных областей
По отношению к носителю предметного знания посредник должен обладать метазнанием, к которому относится знание следующих научных областей По отношению к носителю предметного знания посредник должен обладать метазнанием, к которому относится знание следующих научных областей
Страница №14
Приобретением знаний
называют процесс получения знаний от эксперта или каких-либо других источников и передачи их в ИИС.
Применяют также термины извлечение  и формирование знаний
Приобретением знаний называют процесс получения знаний от эксперта или каких-либо других источников и передачи их в ИИС. Применяют также термины извлечение и формирование знаний
Страница №15
Правила использования терминов
Если при разработке ИИС процесс получения знаний от экспертов происходит без использования компьютерных средств путем непосредственного контакта – это извлечение знаний.
Если процесс осуществляется с использованием специальных программных средств – приобретение знаний.
Если процесс осуществляется с использованием программ обучения при наличии репрезентативной выборки примеров принятия решений в ПО – формирование знаний
Правила использования терминов Если при разработке ИИС процесс получения знаний от экспертов происходит без использования компьютерных средств путем непосредственного контакта – это извлечение знаний. Если процесс осуществляется с использованием специальных программных средств – приобретение знаний. Если процесс осуществляется с использованием программ обучения при наличии репрезентативной выборки примеров принятия решений в ПО – формирование знаний
Страница №16
Три стратегии получения знаний при разработке ИИС
Три стратегии получения знаний при разработке ИИС
Страница №17
Классификация методов извлечения знаний
Классификация методов извлечения знаний
Страница №18
Коммуникативные методы. Наблюдение
Используется в случаях, когда участие инженера по знаниям (ИЗ)в реальном процессе невозможно. («Чистый» метод) Может потребовать:
Техники стенографирования и хронометрирования
Серьезного предварительного знакомства с ПО
Коммуникативные методы. Наблюдение Используется в случаях, когда участие инженера по знаниям (ИЗ)в реальном процессе невозможно. («Чистый» метод) Может потребовать: Техники стенографирования и хронометрирования Серьезного предварительного знакомства с ПО
Страница №19
Коммуникативные методы. Анализ протоколов «мыслей вслух»
ИЗ протоколирует все слова эксперта
Лекции
ИЗ ведет конспекты, по ходу лекции задает вопросы.
Коммуникативные методы. Анализ протоколов «мыслей вслух» ИЗ протоколирует все слова эксперта Лекции ИЗ ведет конспекты, по ходу лекции задает вопросы.
Страница №20
Коммуникативные методы.
Анкетирование
Требования к анкете:
Она не должна быть монотонной
Должна быть приспособлена к языку экспертов
Должна быть продумана последовательность вопросов
Допускается избыточность вопросов для перепроверки ответов
Коммуникативные методы. Анкетирование Требования к анкете: Она не должна быть монотонной Должна быть приспособлена к языку экспертов Должна быть продумана последовательность вопросов Допускается избыточность вопросов для перепроверки ответов
Страница №21
Коммуникативные методы. Интервью
Серия заранее подготовленных вопросов. На качество интервью влияют:
Язык вопросов (понятность, лаконичность, терминология);
Порядок вопросов (логическая последовательность и немонотонность);
Уместность вопросов (этика, вежливость)
Коммуникативные методы. Интервью Серия заранее подготовленных вопросов. На качество интервью влияют: Язык вопросов (понятность, лаконичность, терминология); Порядок вопросов (логическая последовательность и немонотонность); Уместность вопросов (этика, вежливость)
Страница №22
Коммуникативные методы. Свободный диалог
Метод извлечения знаний в форме беседы ИЗ с экспертом, в которой нет жесткого регламентированного плана и вопросника. Следует выбрать правильный темп беседы, не утомляющий эксперта
Коммуникативные методы. Свободный диалог Метод извлечения знаний в форме беседы ИЗ с экспертом, в которой нет жесткого регламентированного плана и вопросника. Следует выбрать правильный темп беседы, не утомляющий эксперта
Страница №23
Коммуникативные методы. Игры с экспертом
Учитель и ученик – эксперт выявляет и исправляет ошибки ученика.
Медицина – ИЗ – врач , эксперт - консультант
Коммуникативные методы. Игры с экспертом Учитель и ученик – эксперт выявляет и исправляет ошибки ученика. Медицина – ИЗ – врач , эксперт - консультант
Страница №24
Коммуникативные методы. Круглый стол
Обсуждение проблем ПО в присутствии привлеченных экспертов, обладающих равными правами. Роль ИЗ – организация обсуждений
Коммуникативные методы. Круглый стол Обсуждение проблем ПО в присутствии привлеченных экспертов, обладающих равными правами. Роль ИЗ – организация обсуждений
Страница №25
Коммуникативные методы. «Мозговой штурм»
Участникам (до 10 чел.) предлагается высказывать любые идеи: чем больше идей, тем лучше. Идеи оцениваются группой экспертов, не участвовавших в их генерации. Эффективен для новых ПО.
Ролевые игры
Используются для обучения персонала. Эксперты сами распределяют роли между собой
Коммуникативные методы. «Мозговой штурм» Участникам (до 10 чел.) предлагается высказывать любые идеи: чем больше идей, тем лучше. Идеи оцениваются группой экспертов, не участвовавших в их генерации. Эффективен для новых ПО. Ролевые игры Используются для обучения персонала. Эксперты сами распределяют роли между собой
Страница №26
Текстологические методы.
Данная группа методов объединяет методы извлечения знаний, основанные на изучении специальных текстов з учебников, монографий, статей, методик и других носителей профессиональных знаний
Текстологические методы. Данная группа методов объединяет методы извлечения знаний, основанные на изучении специальных текстов з учебников, монографий, статей, методик и других носителей профессиональных знаний
Страница №27
Схема извлечения знаний
М1 → Вербализация → Текст→ Понимание → М2
М1 – модель мира автора текста;
М2 – модель, возникающая при чтении текста (модель ИЗ)
Модели М1 и М2 не могут совпадать в силу искажения смысла при вербализации М1 и интерпретации М2
Схема извлечения знаний М1 → Вербализация → Текст→ Понимание → М2 М1 – модель мира автора текста; М2 – модель, возникающая при чтении текста (модель ИЗ) Модели М1 и М2 не могут совпадать в силу искажения смысла при вербализации М1 и интерпретации М2
Страница №28
Научный текст строится из следующих компонент:
Научный текст строится из следующих компонент:
Наблюдения объективной информации;
Системы научных понятий;
Взгляды и опыт автора;
Общие места
Заимствования (материалы из других источников)
	Модель автора: М1=<a, b, c, d, e>
Модель ИЗ формируется из  экстракта <a, b, c, e>’ прочитанного текста и индивидуальных свойств ИЗ.
Научный текст строится из следующих компонент: Научный текст строится из следующих компонент: Наблюдения объективной информации; Системы научных понятий; Взгляды и опыт автора; Общие места Заимствования (материалы из других источников) Модель автора: М1=<a, b, c, d, e> Модель ИЗ формируется из экстракта <a, b, c, e>’ прочитанного текста и индивидуальных свойств ИЗ.
Страница №29
Индивидуальные свойства ИЗ характеризуются:
Индивидуальные свойства ИЗ характеризуются:
Личным опытом
Общенаучной эрудицией
Предварительными сведениями о ПО.
Модель ИЗ имеет вид
	М2=[<a, b, c, e>’, <f, g, h>]
Индивидуальные свойства ИЗ характеризуются: Индивидуальные свойства ИЗ характеризуются: Личным опытом Общенаучной эрудицией Предварительными сведениями о ПО. Модель ИЗ имеет вид М2=[<a, b, c, e>’, <f, g, h>]
Страница №30
Методы поиска решений в пространстве
Задача. Три миссионера и три людоеда находятся на левом берегу реки и им нужно переправиться на правый берег, однако у них имеется только одна лодка, в которую могут сесть лишь 2 человека. Поэтому необходимо определить план, соблюдая который и курсируя несколько раз туда и обратно, можно переправить всех шестерых. Однако если на любом берегу реки число миссионеров будет меньше, чем число людоедов, то миссионеры будут съедены. Решения принимают миссионеры, людоеды их выполняют.
Методы поиска решений в пространстве Задача. Три миссионера и три людоеда находятся на левом берегу реки и им нужно переправиться на правый берег, однако у них имеется только одна лодка, в которую могут сесть лишь 2 человека. Поэтому необходимо определить план, соблюдая который и курсируя несколько раз туда и обратно, можно переправить всех шестерых. Однако если на любом берегу реки число миссионеров будет меньше, чем число людоедов, то миссионеры будут съедены. Решения принимают миссионеры, людоеды их выполняют.
Страница №31
Основой метода являются следующие этапы:
Определяется конечное число состояний, одно из состояний принимается за начальное и одно или несколько состояний определяются как искомое (конечное, или терминальное). Обозначим состояние S тройкой S=(x,y,z), где x и y - число миссионеров и людоедов на левом берегу, z= {L,R} - положение лодки на левом (L) или правом (R) берегах. Итак, начальное состояние S0=(3,3, L ) и конечное (терминальное) состояние Sk=(0,0, R ). 
Заданы правила перехода между группами состояний. Введем понятие действия M:[u, v]w, где u - число миссионеров в лодке, v - число людоедов в лодке,w - направление движения лодки (R или L). 
Для каждого состояния заданы определенные условия допустимости (оценки) состояний: x≥y; 3-x≥3-y ; u+v ≤ 2. 
После этого из текущего (исходного) состояния строятся переходы в новые состояния, показанные на рисунке.  Два новых состояния следует сразу же вычеркнуть, так как они ведут к нарушению условий допустимости (миссионеры будут съедены). 
При каждом переходе в новое состояние производится оценка на допустимость состояний и если при использовании правила перехода для текущего состояния получается недопустимое состояние, то производится возврат к тому предыдущему состоянию, из которого было достигнуто это текущее состояние. Эта процедура получила название бэктрекинг (bac tracing или BACKTRACK).
Основой метода являются следующие этапы: Определяется конечное число состояний, одно из состояний принимается за начальное и одно или несколько состояний определяются как искомое (конечное, или терминальное). Обозначим состояние S тройкой S=(x,y,z), где x и y - число миссионеров и людоедов на левом берегу, z= {L,R} - положение лодки на левом (L) или правом (R) берегах. Итак, начальное состояние S0=(3,3, L ) и конечное (терминальное) состояние Sk=(0,0, R ). Заданы правила перехода между группами состояний. Введем понятие действия M:[u, v]w, где u - число миссионеров в лодке, v - число людоедов в лодке,w - направление движения лодки (R или L). Для каждого состояния заданы определенные условия допустимости (оценки) состояний: x≥y; 3-x≥3-y ; u+v ≤ 2. После этого из текущего (исходного) состояния строятся переходы в новые состояния, показанные на рисунке. Два новых состояния следует сразу же вычеркнуть, так как они ведут к нарушению условий допустимости (миссионеры будут съедены). При каждом переходе в новое состояние производится оценка на допустимость состояний и если при использовании правила перехода для текущего состояния получается недопустимое состояние, то производится возврат к тому предыдущему состоянию, из которого было достигнуто это текущее состояние. Эта процедура получила название бэктрекинг (bac tracing или BACKTRACK).
Страница №32
Метод поиска в пространстве состояний
Теперь мы можем проанализировать полностью алгоритм простейшего поиска решений в проблемном пространстве, описанный группами состояний и переходами между состояниями на рисунке. Решение задачи выделено жирными стрелками. Такой метод поиска S0  Sk называется прямым методом поиска. Поиск Sk  S0 называют обратным поиском. Поиск в двух направлениях одновременно называют двунаправленным поиском.
Метод поиска в пространстве состояний Теперь мы можем проанализировать полностью алгоритм простейшего поиска решений в проблемном пространстве, описанный группами состояний и переходами между состояниями на рисунке. Решение задачи выделено жирными стрелками. Такой метод поиска S0 Sk называется прямым методом поиска. Поиск Sk S0 называют обратным поиском. Поиск в двух направлениях одновременно называют двунаправленным поиском.
Страница №33
фундаментальным понятием в методах поиска в ИС является идея рекурсии и процедура BACKTRACK. В качестве примера многоуровневого возвращения рассмотрим задачу размещения на доске 8 x 8 восьми ферзей так, чтобы они не смогли "съесть" друг друга.
фундаментальным понятием в методах поиска в ИС является идея рекурсии и процедура BACKTRACK. В качестве примера многоуровневого возвращения рассмотрим задачу размещения на доске 8 x 8 восьми ферзей так, чтобы они не смогли "съесть" друг друга.
Допустим, мы находимся на шаге размещения ферзя в 6 ряду и видим, что это невозможно. Процедура BACKTRACK пытается переместить ферзя в 5 строке и в 6 строке опять неудача. Только возврат к 4 строке и нахождение в ней нового варианта размещения приведет к решению задачи.
фундаментальным понятием в методах поиска в ИС является идея рекурсии и процедура BACKTRACK. В качестве примера многоуровневого возвращения рассмотрим задачу размещения на доске 8 x 8 восьми ферзей так, чтобы они не смогли "съесть" друг друга. фундаментальным понятием в методах поиска в ИС является идея рекурсии и процедура BACKTRACK. В качестве примера многоуровневого возвращения рассмотрим задачу размещения на доске 8 x 8 восьми ферзей так, чтобы они не смогли "съесть" друг друга. Допустим, мы находимся на шаге размещения ферзя в 6 ряду и видим, что это невозможно. Процедура BACKTRACK пытается переместить ферзя в 5 строке и в 6 строке опять неудача. Только возврат к 4 строке и нахождение в ней нового варианта размещения приведет к решению задачи.
Страница №34
Алгоритмы эвристического поиска

В рассмотренных примерах поиска решений число состояний невелико, поэтому перебор всех возможных состояний не вызвал затруднений. Однако при значительном числе состояний время поиска возрастает экспоненциально, и в этом случае могут помочь алгоритмы эвристического поиска, которые обладают высокой вероятностью правильного выбора решения. Рассмотрим некоторые из этих алгоритмов.
Алгоритмы эвристического поиска В рассмотренных примерах поиска решений число состояний невелико, поэтому перебор всех возможных состояний не вызвал затруднений. Однако при значительном числе состояний время поиска возрастает экспоненциально, и в этом случае могут помочь алгоритмы эвристического поиска, которые обладают высокой вероятностью правильного выбора решения. Рассмотрим некоторые из этих алгоритмов.
Страница №35
Алгоритм наискорейшего спуска по дереву решений
Пример построения более узкого дерева рассмотрим на примере задачи о коммивояжере. Торговец должен побывать в каждом из 5 городов, обозначенных на карте
Алгоритм наискорейшего спуска по дереву решений Пример построения более узкого дерева рассмотрим на примере задачи о коммивояжере. Торговец должен побывать в каждом из 5 городов, обозначенных на карте
Страница №36
Алгоритм оценочных (штрафных) функций
Умело подобранные оценочные функции (в некоторых источниках - штрафные функции) могут значительно сократить полный перебор и привести к решению достаточно быстро в сложных задачах. В нашей задаче о людоедах и миссионерах в качестве самой простой целевой функции при выборе очередного состояния можно взять число людоедов и миссионеров, находящихся "не на месте" по сравнению с их расположением в описании целевого состояния. Например, значение этой функции f=x+y для исходного состоянияf0=6, а значение для целевого состояния f1=0.
Алгоритм оценочных (штрафных) функций Умело подобранные оценочные функции (в некоторых источниках - штрафные функции) могут значительно сократить полный перебор и привести к решению достаточно быстро в сложных задачах. В нашей задаче о людоедах и миссионерах в качестве самой простой целевой функции при выборе очередного состояния можно взять число людоедов и миссионеров, находящихся "не на месте" по сравнению с их расположением в описании целевого состояния. Например, значение этой функции f=x+y для исходного состоянияf0=6, а значение для целевого состояния f1=0.
Страница №37
Эвристические процедуры поиска на графе стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска. Для задачи о людоедах введем оценочную функцию:
Эвристические процедуры поиска на графе стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска. Для задачи о людоедах введем оценочную функцию:
f(n) = d(n) + w(n)
где d(n) - глубина вершины n на дереве поиска и w(n) - число находящихся не на нужном месте миссионеров и людоедов. Эвристика заключается в выборе минимального значения f(n). Определяющим в эвристических процедурах является выбор оценочной функции.
Эвристические процедуры поиска на графе стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска. Для задачи о людоедах введем оценочную функцию: Эвристические процедуры поиска на графе стремятся к тому, чтобы минимизировать некоторую комбинацию стоимости пути к цели и стоимости поиска. Для задачи о людоедах введем оценочную функцию: f(n) = d(n) + w(n) где d(n) - глубина вершины n на дереве поиска и w(n) - число находящихся не на нужном месте миссионеров и людоедов. Эвристика заключается в выборе минимального значения f(n). Определяющим в эвристических процедурах является выбор оценочной функции.
Страница №38
Рассмотрим вопрос о сравнительных характеристиках оценочных целевых функций на примере функций для игры в "8" ("пятнашки"). Игра в "8" заключается в нахождении минимального числа перестановок при переходе из исходного состояния в конечное (терминальное, целевое). 
Рассмотрим вопрос о сравнительных характеристиках оценочных целевых функций на примере функций для игры в "8" ("пятнашки"). Игра в "8" заключается в нахождении минимального числа перестановок при переходе из исходного состояния в конечное (терминальное, целевое).
Рассмотрим вопрос о сравнительных характеристиках оценочных целевых функций на примере функций для игры в "8" ("пятнашки"). Игра в "8" заключается в нахождении минимального числа перестановок при переходе из исходного состояния в конечное (терминальное, целевое). Рассмотрим вопрос о сравнительных характеристиках оценочных целевых функций на примере функций для игры в "8" ("пятнашки"). Игра в "8" заключается в нахождении минимального числа перестановок при переходе из исходного состояния в конечное (терминальное, целевое).
Страница №39
Рассмотрим две оценочные функции:
Рассмотрим две оценочные функции:
h1(n) & = Q(n) 
h2(n) & = P(n) + 3S(n),
где Q(n) - число фишек не на месте; P(n) - сумма расстояний каждой фишки от места в ее целевой вершине; 
S(n) - учет последовательности нецентральных фишек (штраф +2 если за фишкой стоит не та, которая должна быть в правильной последовательности; штраф +1 за фишку в центре; штраф 0 в остальных случаях).
Рассмотрим две оценочные функции: Рассмотрим две оценочные функции: h1(n) & = Q(n) h2(n) & = P(n) + 3S(n), где Q(n) - число фишек не на месте; P(n) - сумма расстояний каждой фишки от места в ее целевой вершине; S(n) - учет последовательности нецентральных фишек (штраф +2 если за фишкой стоит не та, которая должна быть в правильной последовательности; штраф +1 за фишку в центре; штраф 0 в остальных случаях).
Страница №40
Сравнение этих оценочных функций приведено в таблице 
Сравнение этих оценочных функций приведено в таблице
Сравнение этих оценочных функций приведено в таблице Сравнение этих оценочных функций приведено в таблице
Страница №41
На основе сравнения этих двух оценочных функций можно сделать выводы.
Основу алгоритма поиска составляет выбор пути с минимальной оценочной функцией. 
Поиск в ширину, который дает функция h1, гарантирует, что какой-либо путь к цели будет найден. При поиске в ширину вершины раскрываются в том же порядке, в котором они порождаются. 
Поиск в глубину управляется эвристической компонентой 3S(n) в функции h2 и при удачном выборе оценочной функции позволяет найти решение по кратчайшему пути (по минимальному числу раскрываемых вершин). Поиск в глубину тем и характеризуется, что в нем первой раскрывается та вершина, которая была построена самой последней. 
Эффективность поиска возрастает, если при небольших глубинах он направляется в основном в глубь эвристической компонентой, а при возрастании глубины он больше похож на поиск вширь, чтобы гарантировать, что какой-либо путь к цели будет найден. Эффективность поиска можно определить как E=K/L*N*S, где K и S (трудоемкость) - зависят от оценочной функции, L - длина пути, N - число вершин, открытых при нахождении пути. Если договориться, что для оптимального пути E=1, то K=L0*N0*S0.
На основе сравнения этих двух оценочных функций можно сделать выводы. Основу алгоритма поиска составляет выбор пути с минимальной оценочной функцией. Поиск в ширину, который дает функция h1, гарантирует, что какой-либо путь к цели будет найден. При поиске в ширину вершины раскрываются в том же порядке, в котором они порождаются. Поиск в глубину управляется эвристической компонентой 3S(n) в функции h2 и при удачном выборе оценочной функции позволяет найти решение по кратчайшему пути (по минимальному числу раскрываемых вершин). Поиск в глубину тем и характеризуется, что в нем первой раскрывается та вершина, которая была построена самой последней. Эффективность поиска возрастает, если при небольших глубинах он направляется в основном в глубь эвристической компонентой, а при возрастании глубины он больше похож на поиск вширь, чтобы гарантировать, что какой-либо путь к цели будет найден. Эффективность поиска можно определить как E=K/L*N*S, где K и S (трудоемкость) - зависят от оценочной функции, L - длина пути, N - число вершин, открытых при нахождении пути. Если договориться, что для оптимального пути E=1, то K=L0*N0*S0.
Страница №42
Алгоритм минимакса
В 1945 году Оскар Моргенштерн и Джон фон Нейман предложили метод минимакса, нашедший широкое применение в теории игр. Предположим, что противник использует оценочную функцию (ОФ), совпадающую с нашей ОФ. Выбор хода с нашей стороны определяется максимальным значением ОФ для текущей позиции. Противник стремится сделать ход, который минимизирует ОФ. Поэтому этот метод и получил название минимакса. На рисунке приведен пример анализа дерева ходов с помощью метода минимакса (выбранный путь решения отмечен жирной линией).
Алгоритм минимакса В 1945 году Оскар Моргенштерн и Джон фон Нейман предложили метод минимакса, нашедший широкое применение в теории игр. Предположим, что противник использует оценочную функцию (ОФ), совпадающую с нашей ОФ. Выбор хода с нашей стороны определяется максимальным значением ОФ для текущей позиции. Противник стремится сделать ход, который минимизирует ОФ. Поэтому этот метод и получил название минимакса. На рисунке приведен пример анализа дерева ходов с помощью метода минимакса (выбранный путь решения отмечен жирной линией).
Страница №43
Развивая метод минимакса, назначим вероятности для выполняемых действий в задаче о миссионерах и людоедах:
Развивая метод минимакса, назначим вероятности для выполняемых действий в задаче о миссионерах и людоедах:
P([2 : 0]R) = 0,8;  P([1 : 1]R) = 0,5; 
P([0 : 2]R) = 0,9; 
P([1 : 0]R) = 0,3;  P([0 : 1]R) = 0, 3:
Интуитивно понятно, что посылать одного людоеда или одного миссионера менее эффективно, чем двух человек, особенно на начальных этапах. На каждом уровне мы будем выбирать состояние по критерию Pi. Даже такой простой подход позволит нам избежать части тупиковых состояний в процессе поиска и сократить время по сравнению с полным перебором. Кстати, этот подход достаточно распространен в экспертных продукционных системах.
Развивая метод минимакса, назначим вероятности для выполняемых действий в задаче о миссионерах и людоедах: Развивая метод минимакса, назначим вероятности для выполняемых действий в задаче о миссионерах и людоедах: P([2 : 0]R) = 0,8; P([1 : 1]R) = 0,5; P([0 : 2]R) = 0,9; P([1 : 0]R) = 0,3; P([0 : 1]R) = 0, 3: Интуитивно понятно, что посылать одного людоеда или одного миссионера менее эффективно, чем двух человек, особенно на начальных этапах. На каждом уровне мы будем выбирать состояние по критерию Pi. Даже такой простой подход позволит нам избежать части тупиковых состояний в процессе поиска и сократить время по сравнению с полным перебором. Кстати, этот подход достаточно распространен в экспертных продукционных системах.