Теоретико-игровые методы принятия решений (Еремеев А

Общие замечания

Дерево игры может быть построено, используя известные методы полного перебора («в глубину», «в ширину», комбинированный) или сокращенного перебора, выполняемого с использованием некоторой оценочной функции (точной или приближенной, эвристической) [7, 8].

Определение 2.2.Алгоритм поиска решения называетсядопустимым, если он оканчивает свою работу построением оптимального решения (оптимального пути к цели).

Определение 2.3. Допустимый алгоритм поиска решения называетсяоптимальным, если он при поиске решения анализирует (раскрывает) минимальное число вершин.

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

Нильсон Н. (NilssonN.) в своей классической работе по искусственному интеллекту [7] доказал теорему, определяющую требования к эвристической функции, чтобы алгоритм поиска решения, построенный на ее основе, был допустимым. К сожалению, проверка выполнимости этого требования, в свою очередь, является сложной и обычно практически нереализуемой задачей.

Рассмотрим два универсальных метода сокращенного перебора на дереве игры – метод максимина (максиминный метод) и метод -отсечений.

Содержание