Защо допустимите евристики гарантират оптималност?

Имаме списък с кандидати, нали?

И всеки от тях има ETC (очаквани общи разходи) за достигане на целта от началния възел (т.е. цената за достигане на този възел + очакваните оставащи разходи до целта (евристика)).

Сега, ако очакваната цена е идентична с действителната цена, ние буквално просто ще изберем възлите по най-краткия път (е, всеки от най-кратките пътища) и нищо друго. Тъй като избираме най-ниския ETC, трябва да е доста очевидно защо избираме само възли от най-краткия път - всичко, което не е по най-краткия път, ще има по-висок ETC.

Какво ще стане, ако ETC е по-малко от действителната цена? Винаги избираме най-ниския ETC, така че в крайна сметка може да изберем възли, които не са по най-краткия път. Но никога не можем да достигнем целта по път, който не е най-краткият, защото:

• Най-краткият път има по-ниска действителна цена от всеки не-кратък път
• ETC на целта е същата като цената за достигане на целта по този път (тъй като вече сме на целта, очакваната оставаща цена е 0)
• ETC винаги е по-малък или равен на действителните общи разходи по всеки път
• По този начин ETC на най-краткия път е строго по-малък от ETC на целта, която е достигната по не-късия път.

As an example, let's say we have costs as follows: (the cost above / below a node is the expected remaining cost, the cost at an edge is the actual cost)

  0    10  0  100   0
START ---- O ------ GOAL
0 |                 | 100
  O ------ O ------ O
 100  1   100  1   100

Така че ясно ще започнем с посещение на горния среден възел, тъй като ETC е 10 (10+0).

Тогава целта ще бъде кандидат с ETC 110 (10+100+0).

След това ясно бихме избрали долните възли един след друг, последвани от актуализираната цел, тъй като всички те имат ETC по-ниски от ETC на текущата цел, т.е. техните ETC са: 100, 101, 102, 102.

Така че, въпреки че целта беше кандидат, не можахме да я изберем, защото все още имаше по-добър път.

Според тази статия в Уикипедия:

С недопустима евристика, алгоритъмът A* може да пренебрегне оптималното решение на проблем с търсенето...

Добър пример е даден в статията: Проблем с 15 пъзела.

За този конкретен проблем вземете евристична функция, която връща броя на грешно поставените плочки (за преместване) като цена за достигане на целта (където целият пъзел е сортиран). Това е възможно най-малкият брой ходове, въпреки че не може да бъде действително решение.

Вземете това като текущия възел:

Целеви възел:

15 и 14 плочки се разменят.

За възела, представен на фигурата по-горе, той ще върне 2 (две плочки са неправилно поставени: 15 и 14). Тази евристична функция е допустима, тъй като не пренебрегва най-оптималното решение (сортиране на пъзела с 2 хода – преместване на 15 и 14 на правилните им места).

Следователно евристиката гарантира оптималност.