!7.Эвристические алгоритмы поиска. Алгоритм поиска оптимального решения а*.

Эвристический алгоритм — это алгоритм решения задачи, правильность которого для всех возможных случаев не доказана, но про который известно, что он даёт достаточно хорошее решение в большинстве случаев. В действительности может быть даже известно (то есть доказано) то, что эвристический алгоритм формально неверен. Его всё равно можно применять, если при этом он даёт неверный результат только в отдельных, достаточно редких и хорошо выделяемых случаях, или же даёт неточный, но всё же приемлемый результат.

Важно понимать, что эвристика, в отличие от корректного алгоритма решения задачи, обладает следующими особенностями:

•Она не гарантирует нахождение лучшего решения.

•Она не гарантирует нахождение решения, даже если оно заведомо существует (возможен «пропуск цели»).

•Она может дать неверное решение в некоторых случаях.

Эвристические алгоритмы широко применяются для решения задач высокой вычислительной сложности (задачи, принадлежащие классу NP), то есть вместо полного перебора вариантов, занимающего существенное время, а иногда технически невозможного, применяется значительно более быстрый, но недостаточно обоснованный теоретически, алгоритм. В областях искусственного интеллекта, таких, как распознавание образов, эвристические алгоритмы широко применяются также и по причине отсутствия общего решения поставленной задачи.

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

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

Поиск в ширину. Вершины раскрываются в последовательности их порождения. Поиск идет по ширине дерева, т.к. раскрытие вершины происходит вдоль одного уровня. Целевая вершина выбирается сразу же после порождения. При поиске в ширину возможно нахождение наиболее короткого пути к целевой вершине, если такой путь есть.

!8. Сравнительная характеристика методов извлечения знаний

Показатели	Наблюдения	«Мысли вслух»	Лекции
Достоинства	Отсутствие влияния аналитика и его субъективной позиции. Максимальное приближение аналитика к предметной области.	Свобода самовыражения для эксперта. Вербализация рассуждений. Отсутствие влияния аналитика и его субъективной позиции.	Свобода самовыражения для эксперта. Структурированное изложение. Высокая концентрация. Отсутствие влияния аналитика и его субъективной позиции.
Недостатки	Отсутствие обратной связи Фрагментарность полученных комментариев.	Отсутствие обратной связи Возможность ухода «в сторону» в рассуждениях эксперта	«Зашумленность» деталями. Слабая обратная связь. Недостаток хороших лекторов среди экспертов-практиков.
Требования к эксперту (типы и основные качества)	Собеседник или мыслитель (способность к вербализации мыслей, аналитический склад ума, открытость, рефлексивность)		Мыслитель (лекторские способности)
Требования к аналитику {типы и основные качества)	Мыслитель (наблюдатель­ность, поленезависи­мость)	Мыслитель или собеседник (поленезависимост, способность к общению)	Мыслитель (поленезависимость, способность к общению)
Характерис-тика предметной области	Слабо- и среднеструктурированные, слабо- и среднедокументированные		Слабоструктурированны, слабодокументирован­ные

Сравнение активных индивидуальных методов

Показатели	Анкетирование	Интервьюирование	Свободный диалог
Достоинства	Возможность стандартизированного опроса нескольких экспертов. Не требует особенного напря­же­ния от аналитика во время процедуры анкетирования.	Наличие обратной связи (возможность уточнения контекста и разрешения противоречий)	Гибкость Обратная связь. Возможность изменения сценария и формы сеанса
Недостатки	Требует умения и опыта составления анкет. Отсутствие контекста и обратной связи. Вопросы анкеты могут быть неправильно поняты экспертом.	Требует значительного времени на подготовку вопросов интервью	Требует от аналитика высочайшего напряжения Отсутствие формальных методик проведения. Трудность протоколирования результатов
Требования к эксперту	Практик и мыслитель	Собеседник и мыслитель
Требования к аналитику	Мыслитель (педантизм в составлении анкет, внимательность)	Собеседник (журналистские навыки, умение слушать)	Собеседник (наблюдательность, умение слушать, обаяние)
Характе­ристика предметной области	Слабоструктурированные, слабо- и среднедокументированные.

Сравнение активных групповых методов извлечения знаний

Показатели	«Мозговой штурм»	Дискуссия за круглым столом
Достоинства	Позволяет выявлять глубинные пласты знаний (на уровне бессознательного). Активизирует экспертов. Позволяет получать новые знания	Позволяет получать более объективные фрагменты знаний. Оживляет процедуру извлечения знаний. Позволяет участникам обмениваться знаниями.
Недостатки	Возможен только ДЛЯ новых интересных исследовательских проблем. Не всегда эффективен (довольно низкий процент продуктивных идей)	Требует больших организационных затрат. Отличается сложностью проведения.
Требования к эксперту	Мыслитель (способность к творчеству)	Собеседник или мыслитель (искусство полемики)
Требования к аналитику	Собеседник или мыслитель (быстрая реакция и чувство юмора)	Собеседник (дипломатические способности)
Характеристика предметной области	Слабоструктурированные и слабодокументированные с наличием перспективных «белых пятен»	Слабоструктурированные и слабодокументированные с наличием спорных проблем