Rekursiivinen haku ensimmäisen parhaan osuman perusteella

RPPNS-
algoritmit kaavioiden etsimiseen
Nimetty Hae ensimmäisen parhaan osuman perusteella
Tekijä Richard E. Korf [d]
Tietorakenne kaavio
pahin aika

Rekursiivinen paras ensimmäinen haku (RBFS ) on yksinkertainen rekursiivinen algoritmi , joka yrittää jäljitellä tavallisen ensimmäisen parhaan haun toimintaa , mutta käyttäävain lineaarista  tilaa .

Yleiset määräykset

Esimerkki algoritmin toteutuksesta pseudokoodissa

Funktio Rekursiivinen-Paras-Ensimmäinen-Haku(ongelma) palauttaa ratkaisutuloksen tai vikailmaisimen vika RBFS ( ongelma , merkkisolmu (alkutila[ ongelma ] ) , ∞) funktio RBFS(ongelma, solmu, f_raja) palauttaa ratkaisutuloksen tai vikailmaisin ja uusi f-kustannusraja f_limit if Goal-Test[ ongelma ](Tila[ solmu ]) sitten palauta solmun seuraajat ← Laajenna( solmu , ongelma ) jos seuraavien solmujen joukko on tyhjä , palauta epäonnistuminen, ∞ seuraajien jokaiselle s :lle tee f[s] ← max ( g (s)+h(s) , f[ solmu ] ) toista parhaiten ← solmu, jolla on pienin f-arvo seuraajajoukossa , jos f[paras] > f_raja sitten palauttaa epäonnistumisen , f[ paras ] vaihtoehto ← toiseksi pienin f-arvo seuraajien joukossa tulos, f[paras] ← RBFS(ongelma, paras, min{f_raja, vaihtoehto)) jos tulos ≠ epäonnistui , palauta tulos

Sillä on samanlainen rakenne kuin rekursiivisella syvyys-ensimmäisellä haulla , mutta sen sijaan, että se kulkisi loputtomasti nykyistä polkua pitkin, tämä algoritmi ohjaa parhaan vaihtoehtoisen polun f-arvoa, joka on saatavilla miltä tahansa nykyisen solmun esi-isältä. Jos nykyinen solmu ylittää annetun rajan, rekursion nykyinen vaihe lopetetaan ja rekursio jatkuu vaihtoehtoista polkua pitkin. Tämän RPPN - algoritmin rekursiovaiheen päätyttyä kunkin solmun f-arvo tietyllä polulla korvataan sen lapsisolmun parhaalla f -arvolla. Tästä johtuen unohdetun alipuun parhaan lehtisolmun f-arvo jää muistiin RPPN- algoritmiin, joten jossain seuraavassa vaiheessa voidaan tehdä päätös laajentaako tätä alipuuta uudelleen [1] .

Edut ja haitat

RPPNS- algoritmi on hieman tehokkaampi kuin IDA* , mutta sen haittana on kuitenkin se, että solmut uusiutuvat liian usein [2] . Nämä päätösmuutokset tapahtuvat, koska joka kerta kun nykyinen paras polku rullataan auki, on hyvä mahdollisuus, että sen f-arvo kasvaa, koska h - funktiosta tulee yleensä vähemmän optimistinen, kun kohdetta lähempänä olevia solmuja puretaan. Kun tämä tilanne tapahtuu, varsinkin suurissa hakutiloissa, toiseksi paras polku voi itse tulla parhaaksi poluksi, joten hakualgoritmin on suoritettava paluu seuratakseen sitä. Jokainen päätösmuutos vastaa yhtä IDA* -algoritmin iteraatiota ja saattaa vaatia useita unohdettujen solmujen uudelleenlaajennuksia parhaan polun toistamiseksi ja polun laajentamiseksi yhteen solmuun.

Kuten hakualgoritmi A* , RPPN on optimaalinen algoritmi, jos heuristinen funktio h(n) on sallittu. Sen avaruuden monimutkaisuus on 0(bd) , mutta aikamonimutkaisuutta on melko vaikea luonnehtia : se riippuu sekä heuristisen funktion tarkkuudesta että siitä, kuinka usein paras polku muuttui solmujen käyttöönoton yhteydessä. Sekä IDA* - että RPPN- algoritmi ovat alttiita kaaviohakuihin liittyvän monimutkaisuuden mahdolliselle eksponentiaaliselle lisääntymiselle, koska nämä algoritmit eivät pysty havaitsemaan muita toistuvia tiloja kuin nykyisellä polulla olevia. Siksi nämä algoritmit pystyvät toistuvasti tutkimaan samaa tilaa.

IDA*- ja RPPNS-algoritmien haittana on, että ne käyttävät liian vähän muistia. Iteraatioiden välillä IDA* -algoritmi tallentaa vain yhden numeron, nykyisen f-kustannusrajan . RPPN- algoritmi tallentaa enemmän tietoa muistiin, mutta siinä käytetyn muistin määrä mitataan vain arvolla 0(bd) : vaikka muistia olisi enemmän, RPPN- algoritmi ei pysty käyttämään sitä.

Muistiinpanot

  1. ↑ Sovellusosio ei ole kokonaan kirjoitettu alkuperäisessä artikkelissa, joten sen sisällyttäminen tähän artikkeliin ei ole vielä järkevää.
  2. ↑ Tässä pitäisi olla katkelma

    Kuvassa esitetyssä esimerkissä 1, 2 ja 3, RPPNS- algoritmi seuraa ensin polkua RimnicuVilcea- solmun läpi , sitten "muuttaa mielensä" ja yrittää kulkea Fagaras -solmun läpi , minkä jälkeen se palaa aiemmin hylättyyn ratkaisuun,

    mutta hän viittaa alkuperäisen artikkelin keskeneräiseen Sovellusosaan .

Kirjallisuus

 Kaavion hakualgoritmit
Tietämättömät menetelmät
Tietoon perustuvat menetelmät
Pikanäppäimet
Vähintään ulottuva puu
Muut