Tarvitsen esimerkin penetanssin laskemisesta ja hakupuun haarautumistekijä tilatila-heuristisessa haussa. Määritelmät ovat seuraavat. Penetranssi $ P $ on määritelty
$ \ qquad \ displaystyle P = \ frac {L} {T} $
ja haarautumistekijä $ B $ määritellään seuraavasti:
$ \ qquad \ displaystyle \ frac {B} {(B-1)} \ cdot (B ^ L – 1) = T $
missä $ L $ on polun pituus juuresta ratkaisuun ja $ T $ laajennettujen solmujen kokonaismäärä.
Vastaa
Harkitse seuraavaa hakupuuta. Heuristinen hakualgoritmisi aloittaa haun juurisolmusta. Laajentamattomat solmut on merkitty harmaalla.
Heuristiikkaa ohjataan jostain syystä kohti vasemmanpuoleista alipuuta, kun itse asiassa maalisolmu on oikeanpuoleisimmassa alipuussa, merkitty vihreällä.
Solmut, joilla on laajennetut on merkitty punaisella. Kun houkutteleva vasemmanpuoleisin osa-alue on osoittautunut umpikujaksi, heuristia ohjataan nyt onneksi suoraan kohti maalia. Edellisen kuvan tilanteesta ”laajennamme kaikkiaan kolme uutta solmua ennen kuin saavut tavoitteeseen.
Yllä olevasta kuvasta tavoitteen polun pituus on $ 3 $. Laajennettuja solmuja on $ 17 $. Siksi tunkeutuminen on $ 3/17 \ noin 0,43 $.
Haarautumistekijä on enimmäismäärä minkä tahansa solmun seuraajia. Esimerkiksi binääripuun haarautumistekijä on $ 2 $, koska jokaisessa solmussa on enintään kaksi lasta. Samoin yllä olevassa hakupuussa haarautumistekijä on $ 3 $.
Mitä näyttää siltä, että olet kiinnostunut haarautumistekijästä, mutta tehokas haarautumistekijä $ B ^ * $, joka on tapa kuvaamaan heuristisen kuvan laatua. Jos laajennettujen solmujen kokonaismäärä on $ T $ ja tavoitteen polun pituus on $ L $ (tämä tunnetaan yleisemmin a s syvyys ), niin $ B ^ * $ on haarautumistekijä, joka yhtenäisellä syvyyspuulla $ L $ olisi, jotta se sisältäisi $ T + 1 $ -solmua. Siksi
$$ T + 1 = 1 + B ^ * + (B ^ *) ^ 2 + \ cdots + (B ^ *) ^ L. $ $
Jos liität arvot, jotka saimme haulla, eli $ T = 17 $ ja $ L = 3 $, saat $ B ^ * \ noin 2,165 $. Tämä on täsmälleen sama arvo, jonka saat käyttämällä yhtälöäsi; se on vain vain erilainen esitys saman asian suhteen.
Tehokas haarautumistekijä voi vaihdella esiintymien välillä, mutta on melko vakaa tarpeeksi kovien ongelmien varalta. Hyvin suunnitellun heuristisen arvon arvo on B ^ * $ lähellä $ 1 $, mikä sallii melko suurten ongelmien ratkaisemisen kohtuullisen halvalla.
Kommentit
- Ratkaisemalla kaavan $ B $, sinä saat $ B \ noin 2,165 $. Ihmettelen, mikä on kyseisen arvon tulkinta. Se ' on lähellä kaikkien sisäisten solmujen keskimääräistä haarautumiskerrointa, mutta ei sama.
- @MAcad Itse asiassa, mikä sinua kiinnostaa, ei ole haarautumistekijä, vaan tehokas haarautumistekijä, joka ei kuvaa heuristisen kuvan laatua. I ' päivitän vastaukseni.
- @Juho Luulen, että jos käytän haarautumiskerroinkaavaa, testaan monia lukuja LHS: ssä, lasken sen ja tarkistan, että yhtälö RHS: n kanssa seuraavasti: B = 1 == > 1 + 1 + 1 ^ 2 + 1 ^ 3 = 4 ei ole yhtä suuri kuin T = 17, joten meidän on testattava B = 2 == > 1 + 2 + 2 ^ 2 + 2 ^ 3 = 15 Tulos lähellä T: tä, jotta voimme testata B = 2,1 ja niin edelleen, kunnes saavutetaan tulos T !!!! Luulen, että tätä kaavaa voidaan käyttää näin :))))