Sisältö

• Vertailutaulukko
• Määritelmä tietoiselle haulle
• Heuristinen syvyys Ensimmäinen haku
• Määritelmä epävirallinen haku
• Syvyys ensimmäinen haku
• johtopäätös

Haku on prosessi, jolla etsitään vaiheita, joita tarvitaan minkä tahansa ongelman ratkaisemiseksi. Aikaisempi ero tietoisen ja tietämättömän haun välillä on se, että tietoon perustuva haku tarjoaa ohjeita siitä, missä ja miten löytää ratkaisu. Sitä vastoin tietämätön haku ei anna lisätietoja ongelmasta, paitsi sen määrittelyä.

Sekä tietoisen että tietämättömän hakutekniikan välillä tietoinen haku on kuitenkin tehokkaampaa ja kustannustehokkaampaa.

1. 1. Vertailutaulukko
   2. Määritelmä
   3. Keskeiset erot
   4. johtopäätös

Vertailutaulukko

Vertailun perusteet	Tietoinen haku	Ei tietoa
perustiedot	Käytä tietoa ratkaisun löytämiseen.	Ei tiedon käyttöä
tehokkuus	Erittäin tehokas, koska vie vähemmän aikaa ja kustannuksia.	Tehokkuus on välittävää
Kustannus	Matala	Suhteellisen korkea
Esitys	Löytää ratkaisun nopeammin	Nopeus on hitaampaa kuin tietoinen haku
algoritmit	Heuristinen syvyys ensimmäinen ja leveys ensin ja A * -haku	Syvyys ensimmäinen haku, leveys ensin haku ja edullisin ensimmäinen haku

Määritelmä tietoiselle haulle

Tietoon perustuvalla hakutekniikalla hyödynnetään ongelmakohtaista tietoa antamaan vihje ongelman ratkaisulle. Tämäntyyppinen hakustrategia estää algoritmeja kompastumasta tavoitteesta ja suunnasta ratkaisuun. Tietoon perustuva haku voi olla edullista kustannusten suhteen, kun optimaalisuus saavutetaan alhaisemmilla hakukustannuksilla.

Jotta optimaalisen polun kustannuksia haettaisiin kuvaajasta toteuttamalla tietoinen hakustrategia, lupaavimmat solmut n lisätään heuristiseen funktioon h (n). Sitten funktio palauttaa ei-negatiivisen todellisen numeron, joka on likimääräinen polun hinta laskettuna solmusta n kohdesolmuun.

Tärkein osa tietoon perustuvaa tekniikkaa on heuristinen toiminto, joka helpottaa lisätietoa ongelmasta algoritmille. Seurauksena on, että se auttaa löytämään tien päähän erilaisten naapurisolmujen kautta. Tietoon perustuvaan hakuun perustuvia algoritmeja on useita, kuten heuristinen syvyys ensin -haku, heuristinen leveys-ensimmäinen haku, A * -haku, jne. Ymmärretään nyt heuristinen perusteellisin haku.

Heuristinen syvyys Ensimmäinen haku

Samanlainen kuin heuristinen syvyyshaku jäljempänä esitetyllä syvyyshakutoiminnolla, ensin haku valitaan polku, mutta kulkee kaikki polut valitusta polusta ennen toisen polun valitsemista. Se valitsee kuitenkin parhaan reitin paikallisesti. Tapauksissa, joissa pienin heuristinen arvo on rajan prioriteetti, se tunnetaan parhaana ensimmäisenä hauna.

Toinen tietoon perustuva hakualgoritmi on A * -haku, joka yhdistää alhaisimman kustannuksen ensimmäisen ja parhaan ensimmäisen haun käsitteen. Tämä menetelmä ottaa huomioon sekä polun kustannukset että heuristisen tiedon etsittäessä ja valittaessa laajennettavaa polkua. Arvioitu kokonaiskuljetuskustannus kullekin polulle, joka sijaitsee rajalla lähtökohdasta kohdesolmuun. Siksi se käyttää kahta funktiota samanaikaisesti - kustannukset (p) ovat löydetyn polun kustannukset ja h (p) on arvioidut arvot polun kustannuksista aloitussolmusta maalisolmuun.

Määritelmä epävirallinen haku

Tietoinen haku eroaa tietoon perustuvasta hausta siinä mielessä, että se vain antaa ongelman määritelmän, mutta ei enää askelta ratkaisun löytämiselle ongelmaan. Epävirallisen etsinnän ensisijainen tavoite on erottaa kohde- ja ei-kohdetila, ja se jättää täysin huomioimatta määränpään, jota kohti se kulkee, kunnes se löytää tavoitteen ja raportoi seuraajalle. Tätä strategiaa kutsutaan myös sokeaksi hakuksi.

Tässä kategoriassa on useita hakualgoritmeja, kuten ensin syvyyshaku, yhtenäinen kustannushaku, leveys ensin ja niin edelleen. Ymmärtäkäämme nyt tietämättömän haun taustan käsite syvä-ensin -haun avulla.

Syvyys ensimmäinen haku

Perusteellisessa ensimmäisessä haussa viimeisenä ensimmäisenä pinoa käytetään solmujen lisäämiseen ja poistamiseen. Vain yksi solmu lisätään tai poistetaan kerrallaan ja ensimmäinen elementti, joka poistetaan pinon rajalta, olisi viimeinen pinoon lisätty elementti. Käyttämällä pinoa rajalla johtaa polkujen etsimiseen ensin syvällisesti. Kun etsitään lyhyintä ja optimaalista polkua ensin syvyyshaun avulla, vierekkäisten solmujen luoma polku suoritetaan ensin, vaikka se ei olisi haluttu. Sitten vaihtoehtoista polkua etsitään jälkiseurannan kautta.

Toisin sanoen algoritmi valitsee ensimmäisen vaihtoehdon jokaisessa solmussa ja palaa sitten takaisin toiseen vaihtoehtoon, kunnes se on kulkenut kaikki polut ensimmäisestä valinnasta. Tämä herättää myös ongelman, jossa haku voi lakata lopettamasta kuvaajassa olevien äärettömien silmukoiden (jaksojen) vuoksi.

1. Entinen tietoinen hakutekniikka käyttää tietämystä ratkaisun löytämiseen. Toisaalta jälkimmäinen tietämätön hakutekniikka ei käytä tietoa. Yksinkertaistettuna ratkaisusta ei ole annettu lisätietoja.
2. Tietoon perustuvan haun tehokkuus on parempi kuin tietämättömän haun.
3. Ohjaamaton haku vie enemmän aikaa ja kustannuksia, koska ratkaisulla ei ole aavistustakaan tietoon perustuvaan hakuun verrattuna.
4. Ensimmäinen syvyyshaku, leveys ensimmäinen haku ja alimman hinnan ensimmäinen haku ovat algoritmeja tietämättömän haun luokassa. Toisin kuin tietoinen haku kattaa algoritmit, kuten heuristinen syvyys ensin, heuristinen leveys ensin ja A * -haku.

johtopäätös

Tietoon perustuva haku tarjoaa suunnan ratkaisun suhteen, kun tietämättömässä haussa ratkaisua koskevaa ehdotusta ei anneta. Tämä tekee tietämättömästä hausta pitempää, kun algoritmi toteutetaan.