Минимаксная процедура, альфа-бета отсечение.

Планирование «организация пространства поиска».

Другим способом планирования поиска является организация пространства поиска. Суть планирования в этом случае заключается в использовании классического принципа «разделяй и властвуй», который применяется во всех иерархических организациях. Видовой особенностью таких пространств обычно служит организация горизонтальных и вертикальных отношений между предками и потомками. В этом случае каждый потомок конкретизирует свойства уровня предков за счет собственной видовой особенности.

Например, необходимо организовать пространство состояний, включающее состояния: s ₁(k_i, k_j, k_a, k_b), s ₂(k_i, k_j, k_a, k_с) и s ₃(k_i, k_j,k_c, k_b). При условии, что состояния обладают конечным набором признаков, пространство состояний может быть разбито соответственно на конечное число подпространств и состояний путем обобщения признаков состояний.

Так, состояния потомки: s ₁, s ₂ и s ₃ обладают общими признаками k_i и k_j или родовыми признаками пространства состояний (класса). Кроме этого состояния s ₁ и s ₂ имеют общий признак k_a, состояния s ₂ и s ₃ общий признак k_c и s ₁, s ₃ – признак k_b, которые обобщаются в собственные подпространства или подклассы класса. Видовые признаки подклассов k_a, k_c и k_b представляют собой обобщение свойств соответствующих состояний. Можно сказать, что свойства состояний (потомков) на уровне предков представлены абстрактно, соответственно свойства предков уточняются на уровне потомков.

Также можно отметить, что обычно мощность уровня предков снижается в соответствии с уровнем обобщения свойств состояний потомков. В таком случае поиск логично начать на относительно абстрактном уровне. Соответственно в результате получаются абстрактные решения, по виду которых можно определить приведут ли онРешением задачи является путь из состояния №0 (1111) правого берега в состояние №15 (0000). td/subи к цели. При необходимости решения могут быть конкретизированы на более детальных уровнях вплоть до уровня состояний.

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

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

Классическим примером использования такого подхода при планировании поиска в иерархическом пространстве является задача поиска пути на картах некоторой местности различного масштаба.

Пусть требуется переехать из центра одного города в центр другого. Разумнее это сделать в два приёма: выезд из первого города и въезд во второй спланировать на детальной карте, а переезд из города в город – на относительно крупномасштабной. В этом случае планирование на крупномасштабной карте является относительно более абстрактным. При этом планирование всего маршрута на более детальной карте было бы соответственно более ресурсоемким, т.е. в соответствии с выбранным уровнем детализации.

. 7. Планирование на основе оценочной функции, алгоритм А* (достоинства и недостатки).

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

Использование оценочной функции должно позволить решить третью задачу поиска, т.е. выделение оптимального пути L_i до состояния с заданными видовыми свойствами K^V = { k ₁ , k ₂ , …, k _n }.

Наиболее яркими представителями класса эвристических методов поиска на основе оценочной функции являются алгоритмы Харта-Нильсона или алгоритм А* и минимаксная процедура [2].

Методы реализуются в следующих условиях:

1. Задано одно начальное и целевое состояние.

2. Оценочная функция f (x) определена для всех состояний пространства поиска.

3. Относительно оценочной функции пространство поиска должно быть монотонно.

4. Состояния в пространстве поиска связны.

Предварительно до начала поиска задается оценочная функция вида:

f (x) = g (x) + h (x),

где: g (x) – расстояние от начального до текущего состояния, h (x) – оценка, представляющая отличие свойств текущего и целевого состояния.

Алгоритм поиска А* включает следующие этапы:

1. Раскрыть очередное состояние: s_{i- 1} ⊕ F_j =S_i.

2. Если ∃ s_j ∈ S_i, ≡ s^t, то задача решена, иначе п.3.

3. Выбрать из S_i состояния s_i , для которых оценка f (x) _min , а операторы, образовавшие данные состояния, записать в цепочку L_i = { f ₁, f ₂, … f _{i - 1} , f _i ,…}. Далее перейти к п. 1 для s _i.

При применении алгоритма А* в задаче «в восемь» возможна ситуация, в которой некоторое подмножество состояний фронта будет иметь тождественные оценки f (x) _min (свойства состояний в пространстве поиска распределены немонотонно относительно принятой системы оценок).

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

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

L_i ={ f ₁, f ₂,…, F_{i- 1}, F_i, F_{i+ 1}, … f_n },

где ∀ | F_i | > 1.

8. Модернизированный алгоритм А*.

В результате алгоритм поиска примет следующий вид:

1. Раскрыть очередное состояние: s_{i- 1} ⊕ F_j =S _i.

2. Если ∃ s_i ∈ S_i, ≡ s^t, то задача решена, иначе п.3.

3. Для всех s _i ∈ S _i определить значение оценки f (x) и записать в память M^{F (x)} , перейти к п. 4.

В памяти M^{F (x)} хранятся оценки f (x) всех ранее раскрытых состояний в ранжированном виде. При записи новых состояний в M^{F (x)}их оценки ранжируются вместе с ранее раскрытыми состояниями. Причем ранее раскрытые состояния должны быть помечены.

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

Отличие M^{F (x)} в отношении M^S, применяемой в методе Мура, заключается в том, что оригинальные состояния ранжируются на основе оценки f (x), а не на основе порядка поступления.

4. Выбрать из M^{F (x)} любое состояние s _i, которое ранее не раскрывалось, для которого оценка f (x) _min, если таких нет, то выбрать любое состояние для которого f (x) _min.

5. Оператор f _i, образовавший очередное состояние, записать в цепочку L _i = { f ₁, f ₂, … f _{i - 1}, f _i, …}, далее перейти к п. 1 для состояния s _i.

Планирование «организация пространства поиска».

Другим способом планирования поиска является организация пространства поиска. Суть планирования в этом случае заключается в использовании классического принципа «разделяй и властвуй», который применяется во всех иерархических организациях. Видовой особенностью таких пространств обычно служит организация горизонтальных и вертикальных отношений между предками и потомками. В этом случае каждый потомок конкретизирует свойства уровня предков за счет собственной видовой особенности.

Например, необходимо организовать пространство состояний, включающее состояния: s ₁(k_i, k_j, k_a, k_b), s ₂(k_i, k_j, k_a, k_с) и s ₃(k_i, k_j,k_c, k_b). При условии, что состояния обладают конечным набором признаков, пространство состояний может быть разбито соответственно на конечное число подпространств и состояний путем обобщения признаков состояний.

Так, состояния потомки: s ₁, s ₂ и s ₃ обладают общими признаками k_i и k_j или родовыми признаками пространства состояний (класса). Кроме этого состояния s ₁ и s ₂ имеют общий признак k_a, состояния s ₂ и s ₃ общий признак k_c и s ₁, s ₃ – признак k_b, которые обобщаются в собственные подпространства или подклассы класса. Видовые признаки подклассов k_a, k_c и k_b представляют собой обобщение свойств соответствующих состояний. Можно сказать, что свойства состояний (потомков) на уровне предков представлены абстрактно, соответственно свойства предков уточняются на уровне потомков.

Также можно отметить, что обычно мощность уровня предков снижается в соответствии с уровнем обобщения свойств состояний потомков. В таком случае поиск логично начать на относительно абстрактном уровне. Соответственно в результате получаются абстрактные решения, по виду которых можно определить приведут ли онРешением задачи является путь из состояния №0 (1111) правого берега в состояние №15 (0000). td/subи к цели. При необходимости решения могут быть конкретизированы на более детальных уровнях вплоть до уровня состояний.

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

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

Классическим примером использования такого подхода при планировании поиска в иерархическом пространстве является задача поиска пути на картах некоторой местности различного масштаба.

Пусть требуется переехать из центра одного города в центр другого. Разумнее это сделать в два приёма: выезд из первого города и въезд во второй спланировать на детальной карте, а переезд из города в город – на относительно крупномасштабной. В этом случае планирование на крупномасштабной карте является относительно более абстрактным. При этом планирование всего маршрута на более детальной карте было бы соответственно более ресурсоемким, т.е. в соответствии с выбранным уровнем детализации.

. 7. Планирование на основе оценочной функции, алгоритм А* (достоинства и недостатки).

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

Использование оценочной функции должно позволить решить третью задачу поиска, т.е. выделение оптимального пути L_i до состояния с заданными видовыми свойствами K^V = { k ₁ , k ₂ , …, k _n }.

Наиболее яркими представителями класса эвристических методов поиска на основе оценочной функции являются алгоритмы Харта-Нильсона или алгоритм А* и минимаксная процедура [2].

Методы реализуются в следующих условиях:

1. Задано одно начальное и целевое состояние.

2. Оценочная функция f (x) определена для всех состояний пространства поиска.

3. Относительно оценочной функции пространство поиска должно быть монотонно.

4. Состояния в пространстве поиска связны.

Предварительно до начала поиска задается оценочная функция вида:

f (x) = g (x) + h (x),

где: g (x) – расстояние от начального до текущего состояния, h (x) – оценка, представляющая отличие свойств текущего и целевого состояния.

Алгоритм поиска А* включает следующие этапы:

1. Раскрыть очередное состояние: s_{i- 1} ⊕ F_j =S_i.

2. Если ∃ s_j ∈ S_i, ≡ s^t, то задача решена, иначе п.3.

3. Выбрать из S_i состояния s_i , для которых оценка f (x) _min , а операторы, образовавшие данные состояния, записать в цепочку L_i = { f ₁, f ₂, … f _{i - 1} , f _i ,…}. Далее перейти к п. 1 для s _i.

При применении алгоритма А* в задаче «в восемь» возможна ситуация, в которой некоторое подмножество состояний фронта будет иметь тождественные оценки f (x) _min (свойства состояний в пространстве поиска распределены немонотонно относительно принятой системы оценок).

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

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

L_i ={ f ₁, f ₂,…, F_{i- 1}, F_i, F_{i+ 1}, … f_n },

где ∀ | F_i | > 1.

8. Модернизированный алгоритм А*.

В результате алгоритм поиска примет следующий вид:

1. Раскрыть очередное состояние: s_{i- 1} ⊕ F_j =S _i.

2. Если ∃ s_i ∈ S_i, ≡ s^t, то задача решена, иначе п.3.

3. Для всех s _i ∈ S _i определить значение оценки f (x) и записать в память M^{F (x)} , перейти к п. 4.

В памяти M^{F (x)} хранятся оценки f (x) всех ранее раскрытых состояний в ранжированном виде. При записи новых состояний в M^{F (x)}их оценки ранжируются вместе с ранее раскрытыми состояниями. Причем ранее раскрытые состояния должны быть помечены.

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

Отличие M^{F (x)} в отношении M^S, применяемой в методе Мура, заключается в том, что оригинальные состояния ранжируются на основе оценки f (x), а не на основе порядка поступления.

4. Выбрать из M^{F (x)} любое состояние s _i, которое ранее не раскрывалось, для которого оценка f (x) _min, если таких нет, то выбрать любое состояние для которого f (x) _min.

5. Оператор f _i, образовавший очередное состояние, записать в цепочку L _i = { f ₁, f ₂, … f _{i - 1}, f _i, …}, далее перейти к п. 1 для состояния s _i.

минимаксная процедура, альфа-бета отсечение.

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

 

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