admissible heuristic

Angol

Főnév

admissible heuristic (tsz. admissible heuristics)

(informatika, mesterséges intelligencia) Az admissible heuristic (magyarul: engedélyezett heurisztika vagy megengedő becslés) egy kulcsfogalom a keresési algoritmusok, például az A* algoritmus esetén a mesterséges intelligenciában.

Mi az az admissible heuristic?

Olyan heurisztikus függvény, amely soha nem becsüli túl a tényleges legkisebb költséget egy adott állapottól a célállapotig.
Másképp: a heurisztika optimista becslést ad, azaz mindig kevesebbet vagy pontosan annyit jelez, mint a valós minimális költség.

Miért fontos?

Az A* algoritmusban az admissible heuristic garantálja, hogy a keresés optimális megoldást talál (a legkisebb költségű utat).
Ha a heurisztika túlbecsüli a költséget, akkor nem biztos, hogy az A* optimális lesz.

Példa

Útvonaltervezésnél, ha a heurisztika az egyenes vonalú távolság (Euclideszi távolság) a jelenlegi ponttól a célig, akkor ez egy admissible heuristic, mert a valós úthossz soha nem lehet kisebb, mint a légvonal.

Formalis definíció

Legyen ${\textstyle h(n)}$ a heurisztikus becslés az ${\textstyle n}$ állapottól a célhoz, és ${\textstyle h^{*}(n)}$ a valódi legkisebb költség ${\textstyle n}$ -ből a célhoz.

A ${\textstyle h}$ heurisztika akkor admissible, ha minden ${\textstyle n}$ -re:

$0\leq h(n)\leq h^{*}(n)$

Összefoglalás

Az admissible heuristic egy olyan becslő függvény, amely soha nem túlbecsüli a megoldáshoz szükséges költséget, így biztosítva a keresési algoritmusok optimális megoldását.

További információk

admissible heuristic - Szótár.net (en-hu)
admissible heuristic - Sztaki (en-hu)
admissible heuristic - Merriam–Webster
admissible heuristic - Cambridge
admissible heuristic - WordNet
admissible heuristic - Яндекс (en-ru)
admissible heuristic - Google (en-hu)
admissible heuristic - Wikidata
admissible heuristic - Wikipédia (angol)