Как согласованность подразумевает, что эвристика также допустима?

13

Эвристическая функция ...h(n)

  • Согласованно, если оценочная стоимость от узла до цели не превышает стоимость шага для его преемника плюс расчетную стоимость от преемника до цели.n ′nn′
  • Допустимо, если никогда не переоценивает истинную стоимость состояния цели.h(n)

В учебнике для моего курса по искусственному интеллекту говорится, что согласованность сильнее допустимости, но не доказывает это, и у меня возникают проблемы с математическим объяснением.

algorithms shortest-path heuristics user58348
источник
Взгляните на en.wikipedia.org/wiki/Consistent_heuristic
manlio

Ответы:

12

Чтобы доказать утверждение в вашем вопросе, давайте докажем, что согласованность подразумевает допустимость, тогда как обратное не обязательно верно. Это сделало бы согласованность более сильным условием, чем последнее.

Согласованность подразумевает допустимость:

Начнем с подчеркнуть , что , если эвристический функция является допустимой (где представляет собой цель) , так как краевые затраты предполагаются неотрицательным и , таким образом, стоимость оптимальной от одного узла к самому себе обязательно 0 Это, безусловно, имеет место, если эвристическая функция допустима, но мы хотим доказать, что согласованность обязательно подразумевает допустимость . Для этого предположим далее, что для любой цели - и этот факт будет использован в базовом случае ниже.h t h ( t ) = 0h(t)=0hth(t)=0

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

Базовый случай : взять любой предшественник целевого узла . Пусть обозначим его, так что является правопреемником . Если эвристическая функция согласована , то и, следовательно, ведет себя допустимо в этом случае ,n t n h ( n ) ≤ c ( n , t ) + h ( t ) = c ( n , t ) + 0 = c ( n , t ) htntnh(n)≤c(n,t)+h(t)=c(n,t)+0=c(n,t)h

Обратите внимание, что в базовом случае не предполагается, что ребро обязательно является оптимальным решением от до и, действительно, может быть другой путь от до с меньшими затратами. Важность базового случая заключается в том, что для всех предков узла ! Этот результат будет повторно использован на этапе индукции.п т п т ч ( п ) ≤ C ( п , т ) т⟨n,t⟩ntnth(n)≤c(n,t)t

Шаг индукции : рассмотрим узел . Оптимальная стоимость для достижения цели из , , рассчитывается как: , где - множество наследников узла . Поскольку согласованность предполагает гипотеза, то . Кроме того, поскольку предполагается шагом индукции, то и это верно для все наследники узла . Другими словами:ntnh∗(n)minm∈SCS(n){c(n,m)+h∗(m)}SCS(n)nh(n)≤c(n,n′)+h(n′)h(n′)≤h∗(n′)h(n)≤c(n,n′)+h∗(n′)n′nh(n)≤minm∈SCS(n){c(n,m)+h∗(m)}=h∗(n) , так что .h(n)≤h∗(n)

Приемлемость не обязательно подразумевает последовательность:

Для этого достаточно простого примера. Рассмотрим граф, который состоит из одного пути с 10 узлами: , где целью является . Будем считать , без потери общности , что все расходы края равны 1. Очевидно , и давайте , и . Понятно, что эвристическая функция допустима :⟨n0,n1,n2,...,n9⟩n9h∗(n0)=9h(n0)=8h(ni)=1,1≤i<9h(n9)=0

  1. h(t)=0
  2. h(ni)=1≤h∗(ni)=(9−i) , .∀i,1≤i<9
  3. Наконец, .h(n0)=8≤h∗(n0)=9

Однако не является согласованным и .h(n)h(n0)=8>c(n0,n1)+h(n1)=1+1=2

Надеюсь это поможет,

Карлос Линарес Лопес
источник