Þumalputtareglur
Þumalputtareglur, eða eins og það kallast á ensku heuristic, eru reglur sem gera okkur og tölvum kleift að taka "styttri leiðir" í ákvarðanatöku.
Efnisyfirlit |
Kynning
Manneskjur nota þumalputtareglur oft í sinni ákvörðunartöku. Dæmi um þetta er til dæmis þegar maður er að leita að einhverju, eins og t.d. bíllyklunum sínum, þá byrjar maður að leita kannski í fötunum sem maður var í seinast því það er líkleg staðsetning fyrir lyklana. Tölvuforrit nota svipaðar reglur í ýmsum aðgerðum, t.d. leit. Ef við ímyndum okkur róbót sem er forritaður til að leita eftir bíllyklum manns, þá myndi hann innihalda einhvers konar leitarforrit. Ef að leitarforritið myndi ekki nota þumalputtareglur þá myndi það einfaldlega leita alls staðar og ekki sjá neinn mun á því að leita að bíllyklunum í eldhúsinu eða í bílskúrnum. Ef forritið hins vegar innihéldi góðar þumalputtareglur myndi það byrja að leita á þeim stöðum sem eigandinn væri vanur að skilja eftir lyklana, t.d. á sófaborðinu eða í veski eigandans.
Þumalputtareglur í leit
Þumalputtareglur eru mikið notaðar í leitarforritum og má í raun segja að rannsóknir í leit gangi út á að búa til betri og betri þumalputtareglur. Með því að nota þumalputtareglur verður leit hraðari og leitarrýmið er minnkað. Þumalputtareglur geta verið statískar eða dýnamískar. Statískar þumalputtareglur eru forritaðar einu sinni og breytast ekki. Dýnamískar þumalputtareglur breytast á keyrslutíma og kemur þar lærdómur við sögu. Þumalputtareglur eru notaðar í leit til að gefa stöðu einhvers konar einkunn þannig að forritið geti leitað í líklegri stöðum en ella.
Block World
Til að skoða dæmi um þumalputtareglur getum við notað Block World heiminn. Block World heimurinn samanstendur af borði, númeramerktum kubbum og armi til að taka upp og setja niður kubbana. Heimurinn byrjar í einhverri upphafsstöðu og svo er tilgreind einhver lokastaða sem leitarforrit á að komast í. Því færri skref sem það tekur að komast í lokastöðu, því betra. Fyrir hverja aðgerð sem hægt er að framkvæma kemst forritið í nýja stöðu. Þetta byggir upp tré þar sem hver hnútur táknar stöðu og hver leggur táknar aðgerð.
Ef við skoðum t.d. eftirfarandi upphafsstöðu:
_
_ |4|
|5| |3|
Hér er kubbar nr. 5 og 3 ofan á borðinu og kubbur 4 er ofan á kubb 3. Gerum ráð fyrir að lokastaðan sem við viljum komast í sé sú að allir kubbar eiga að vera á borðinu með engan kubb ofan á sér. Ef enginn kubbur er í arminum eru tvær aðgerðir mögulegar: Að taka upp kubb 5 eða kubb 4. Báðar þessar aðgerðir færa heiminn í mismunandi stöður. Við sjáum að stysta leiðin í lokastöðu er að taka upp kubb 4 og leggja hann á borðið.
Engar þumalputtareglur
Gerum ráð fyrir að leitarforritið okkar hafi engar þumalputtareglur. Ef það notar einföldu leitarregluna dýptin fyrst þá mun það taka fyrstu aðgerðina sem býðst þar til það lendir í stöðu sem er lokastaða eða á einhvern hátt er ekki hægt að komast neitt úr. Í upphafsstöðunni myndi það velja að taka upp kubb 5. Í næstu stöðu myndi það velja að setja niður kubb 5. Í næstu stöðu myndi það velja að taka kubb upp. Þetta myndi það endurtaka endalaust og væri komið í endalausa lykkju og myndi því aldrei ná lokastöðu sinni. Því er leit á dýptina fyrst ekki góður kostur. Ef við myndum leita á breiddina fyrst myndum við prófa allar aðgerðir á hverri hæð í trénu áður en við færum í þá næstu þar til við myndum finna lokastöðuna. Leit á breiddina fyrst er góð vegna þess að hún tryggir að lokastaðan finnst ef hægt er að komast í hana. Í leit á breiddina fyrst myndi forritið fyrst prófa að taka upp kubb 5 og athuga hvort það væri komið í lokastöðu. Það myndi síðan fara aftur í upphafsstöðuna og prófa að taka upp kubb 4 og athuga hvort það væri komið í lokastöðu. Þá væri það lokið með fyrstu hæðina í trénu og myndi þá prófa þá næstu sem fæli í sér að framkvæma tvær aðgerðir eins og að taka upp kubb 5 og setja hann aftur niður. Í okkar tilviki myndi leit á breiddina fyrst skoða á bilinu 4 til 8 stöður, eftir því í hvaða röð það myndi leita.
Með þumalputtareglum
Ef við myndum hins vegar nota þumalputtareglur gætum við aukið þennan leitarhraða mikið án mikillar fyrirhafnar. Einföld þumalputtaregla fyrir leitarvandamálið okkar væri að gefa hverri stöðu einkunn m.v. fjölda kubba sem eru ofan á borðinu og hafa enga ofan á sér. Þannig myndi upphafsstaðan fá einkunnina 1 því kubbur 5 er eini kubburinn sem er á borðinu og ekki með neinn kubb ofan á sér.
Þegar forritið tekur svo ákvörðun um hvað það ætlar að gera í upphafsstöðunni skoðar það hvaða einkunnir stöðurnar, sem hægt er að fara í, fá. Aðgerðin að taka upp kubb 5 gefur stöðu sem fær einkunnina 0. Aðgerðin að taka upp kubb 4 gefur stöðu með einkunnina 2, því þá eru kubbar 5 og 3 á borðinu og ekki með neina kubba ofan á sér. Seinni aðgerðin lítur því betur út og er valin. Þá fer forritið í stöðu þar sem kubbar 5 og 3 eru á borðinu og kubbur 4 er í arminum. 3 aðgerðir eru mögulegar:
- Að setja kubb 4 ofan á kubb 5, einkunn: 1
- Að setja kubb 4 ofan á kubb 3, einkunn: 1
- Að setja kubb 4 ofan á borðið, einkunn: 3
Því velur forritið að setja kubbinn ofan á borðið og er þá komið í lokastöðu. Með því að nota þumalputtareglu skoðar það einungis 6 stöður. Þótt að leit á breiddina fyrst gæti skilað betri niðurstöðum mun leitarforritið með þumalputtareglunni standa sig mun betur í flóknari uppsetningum.
Algengar leitaraðferðir sem nýta sér þumalputtareglur eru: astjarna, hrein þumalputtaleit, rauntímaleit,
