Претрага по најбољим особинама

Претрага по најбољим особинама је алгоритам за претраживање који истражује граф тако што шири претрагу на следећи најбољи чвор који је изабран помоћу неког наведеног правила.

Јуде Перл је описао овај алгоритам као процену обећавања једног чвора n помоћу „хеуристичне функције процене Ф(n) која у општем случају може да зависи од описа n, описа циља, информација које су прикупљене помоћу претраге до тог тренутка и најважније, зависе од било ког додатног знања о домену проблема“. 

Неки аутори користе овај алгоритам да би дефинисали претагу са хеуристиком која покушава да предвиди колико је близу крај путање од решења, тако да би се путање за које се процени да су ближе  и прве продужене. Овај специфични тип претраге се назива и похлепна претрага по најбољим особинама или чиста хеуристичка претрага.

Ефикасно одређивање најбољег кандидата за придуживање путањи је обично имплементирано преко реда са чекањем.

А* алгоритам је пример претрага по најбољим особинама, као што је и Б* алгоритам . Ови алгоритми се најчешће користе за проналазак путање у комбинаториалним претрагама. (Напомена: Ни А* ни Б* нису жељна претрага по најбољим особинама јер они урачунавају удаљеност од почетка као и процену дистанце до циља).

Алгоритам

Алгоритам који имплементира претрагу по најбољим особинама изгледа овако:

OPEN = [initial state]
while OPEN is not empty or until a goal is found
do
 1. Remove the best node from OPEN, call it n.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. Evaluate each successor, add it to OPEN, and record its parent.

done

Напомена: Ова верзија алгоритма није завршена, тј. не налази увек најбољу путању између два чвора, чак иако таква путања постоји. На пример, улази у бесконачну петљу ако дође до чвора који је понор (нема излазних грана). Онда би се вратио назад, додао наследника у листу опет и тако даље.

Следећа верзија проширује алгоритам да користи још једну листу, која садржи све чворове који су процењени и неће бити прелажени опет. Пошто неће гледати исти чвор више пута неће улазити и у бесконачну петљу.

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n's successors.
 4. For each successor do:
       a. If it is not in CLOSED and it is not in OPEN: evaluate it, add it to OPEN, and record its parent.
       b. Otherwise, if this new path is better than previous one, change its recorded parent.
          i.  If it is not in OPEN add it to OPEN.
          ii. Otherwise, adjust its priority in OPEN using this new evaluation.

done

Такође треба напоменути да се псеудо код оба алгоритма завршава када није у стању да нађе било какву путању. Стварна имплементација у неком програмском језику би захтевала и обраћање овој ситуацији.

Похлепна претрага по најбољим особинама

Користећи похлепни алгоритам, прошири првох наследника родитеља. Пошто је наследник генерисан:

1. Ако је хеуристика наследника боља од родитељеве, наследник се ставља на почетак реда са чекањем (са родитељем поново убаченим у ред одмах иза њега), и петља се обавља испочетка.
2. У супротном, наследник се убацује у ред (на локацију која одређује његова хеуристика). Процедура ће затим проверити и остале наследнике ако постоје.

Види још

• Претрага бима
• A* algoritam
• Дајкстрин алгоритам