Tillåten heuristik

Inom datavetenskap , särskilt i algoritmer relaterade till pathfinding , sägs en heuristisk funktion vara tillåten om den aldrig överskattar kostnaden för att nå målet, dvs kostnaden den uppskattar för att nå målet är inte högre än den lägsta möjliga kostnaden från den nuvarande punkt i vägen.

Det är relaterat till begreppet konsekvent heuristik . Även om alla konsekventa heuristiker är tillåtna, är inte alla tillåtna heuristiker konsekventa.

Sökalgoritmer

En tillåten heuristik används för att uppskatta kostnaden för att nå måltillståndet i en informerad sökalgoritm . För att en heuristik ska vara tillåtlig för sökproblemet måste den uppskattade kostnaden alltid vara lägre än eller lika med den faktiska kostnaden för att nå måltillståndet. Sökalgoritmen använder den tillåtna heuristiken för att hitta en uppskattad optimal väg till måltillståndet från den aktuella noden. Till exempel, i A*-sökning är utvärderingsfunktionen (där $n$ är den aktuella noden):

$f(n)=g(n)+h(n)$

var

$f(n)$ = utvärderingsfunktionen.

$g(n)$ = kostnaden från startnoden till den aktuella noden

$h(n)$ = beräknad kostnad från nuvarande nod till mål.

$h(n)$ beräknas med hjälp av heuristisk funktion. Med en icke-tillåten heuristik kan A*-algoritmen förbise den optimala lösningen på ett sökproblem på grund av en överskattning i $f(n)$ .

Formulering

$n$ är en nod

$h$ är en heuristisk

$h(n)$ är kostnaden indikerad av $h$ för att nå ett mål från $n$

$h^{*}(n)$ är den optimala kostnaden för att nå ett mål från $n$

$h(n)$ är tillåtet om, $\forall n$

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

Konstruktion

En tillåten heuristik kan härledas från en avslappnad version av problemet, eller genom information från mönsterdatabaser som lagrar exakta lösningar på delproblem av problemet, eller genom att använda induktiva inlärningsmetoder .

Exempel

Två olika exempel på tillåten heuristik gäller för problemet med femton pussel :

• Hamming avstånd
• Manhattan avstånd

Hamming -avståndet är det totala antalet felplacerade brickor. Det är tydligt att denna heuristik är tillåten eftersom det totala antalet drag för att beställa brickorna korrekt är åtminstone antalet felplacerade brickor (varje bricka som inte är på plats måste flyttas minst en gång). Kostnaden (antal drag) till målet (ett beställt pussel) är åtminstone pusslets Hamming-avstånd .

Manhattan-avståndet för ett pussel definieras som:

$h(n)=\summa _{\text{alla brickor}}{\mathit {avstånd}}({ \text{bricka, korrekt position}})$

Tänk på pusslet nedan där spelaren vill flytta varje bricka så att siffrorna ordnas. Manhattan-avståndet är en tillåten heuristik i det här fallet eftersom varje bricka måste flyttas åtminstone antalet fläckar mellan sig och dess korrekta position.

4 3	6 1	30	8 1
7 2	12 3	9 3	14 4
15 3	13 2	1 4	5 4
2 4	10 1	11 1

Underskrifterna visar Manhattan-avståndet för varje bricka. Det totala Manhattanavståndet för det visade pusslet är:

$h(n)=3+1+0+1 +2+3+3+4+3+2+4+4+4+1+1=36$

Optimalitet bevis

Om en tillåten heuristik används i en algoritm som, per iteration, endast går vägen för lägsta utvärdering (nuvarande kostnad + heuristik) av flera kandidatvägar, avslutas i det ögonblick dess utforskning når målet och, avgörande, aldrig stänger alla optimala vägar innan terminating (något som är möjligt med A* sökalgoritm om man inte är särskilt försiktig), då kan denna algoritm bara avslutas på en optimal väg. För att se varför, överväg följande bevis genom motsägelse :

Antag att en sådan algoritm lyckades avslutas på en väg T med en sann kostnad T _sann större än den optimala vägen S med sann kostnad S _sann . Detta innebär att före uppsägningen var den utvärderade kostnaden för T mindre än eller lika med den utvärderade kostnaden för S (annars skulle S ha valts). Beteckna dessa utvärderade kostnader T _eval respektive S _eval . Ovanstående kan sammanfattas enligt följande,

S _sant < T _sant

T _eval ≤ S _eval

Om vår heuristik är tillåtlig följer det att vid detta näst sista steg T _eval = T _sant eftersom varje ökning av den verkliga kostnaden med heuristiken på T skulle vara otillåten och heuristiken kan inte vara negativ. Å andra sidan skulle en tillåten heuristik kräva att S _eval ≤ S _sant vilket i kombination med ovanstående ojämlikheter ger oss T _eval < T _sant och mer specifikt T _eval ≠ T _sant . Eftersom T _eval och T _sant inte kan vara både lika och ojämlika måste vårt antagande ha varit falskt och därför måste det vara omöjligt att avsluta på en mer kostsam än optimal väg.

Som ett exempel, låt oss säga att vi har kostnader enligt följande: (kostnaden över/under en nod är heuristiken, kostnaden vid en kant är den faktiska kostnaden)

0 10 0 100 0 START ---- O ----- MÅL | | 0| |100 | | O ------- O ------ O 100 1 100 1 100

Så tydligt skulle vi börja med att besöka den övre mittnoden, eftersom den förväntade totala kostnaden, dvs ${\displaystyle f(n)} ,$ är $10+0=10$ . Då skulle målet vara en kandidat, med $f(n)$ lika med $10+100+0=110$ . Då skulle vi tydligt välja de nedre noderna efter varandra, följt av det uppdaterade målet, eftersom de alla har $f(n)$ lägre än $f(n)$ av det aktuella målet, dvs deras $f(n)$ är $100,101,102,102$ . Så även om målet var en kandidat kunde vi inte välja det eftersom det fortfarande fanns bättre vägar där ute. På så sätt kan en tillåten heuristik säkerställa optimalitet.

Observera dock att även om en tillåten heuristik kan garantera slutlig optimalitet, är den inte nödvändigtvis effektiv.

Se även

• Konsekvent heuristik
• Heuristisk funktion
• Sökalgoritm