Legjobbat először keresés

A legjobbat először keresés (best-first search) egy olyan keresőalgoritmus, amely feltérképezi a gráfot egy megadott szabály szerint kiválasztott legígéretesebb csomópont kiterjesztésével.

Judea Pearl a legjobbat először keresést úgy jellemezte, mint becslés az n csomópont ígéretességére egy „heurisztikus $f(n)$ kiértékelő függvénnyel, amely általában függhet az n tulajdonságaitól, a cél meghatározásától, az addig elvégzett keresési információktól, és elsősorban a problémakörrel kapcsolatos kiegészítő információktól.”^[1]^[2] Egyes szerzők a legjobbat először keresés meghatározással kifejezetten olyan keresésre utalnak, amelynek heurisztikája megpróbálja megjósolni, hogy a bejárási út vége mennyire közel van a céltól, és így azokat az utakat járják be először, amelyeket a célhoz közelebb állónak becsülnek. Ezt a konkrét keresést mohó legjobbat először keresésnek (greedy best-first search)^[2] vagy tisztán heurisztikus keresésnek (pure heuristic search) nevezik.^[2]

Az aktuálisan legjobb bővítési jelölt hatékony kiválasztása jellemzően egy prioritásos sor (priority queue) segítségével valósul meg.

Az A* algoritmus és a B* algoritmus a legjobbat először keresési algoritmusok példái. A legjobbat először algoritmusokat gyakran használják útvonalak megtalálására kombinatorikus keresések során. Sem az A*, sem a B* nem mohó legjobbat először keresés, mivel a célig vezető becsült távolságon túl a kiindulóponttól való távolságot is tartalmazzák.

Mohó LEK

Egy mohó algoritmus segítségével kiterjesztjük a szülő első utódját. Az utód meghatározása után:^[3]

Ha az utód heurisztikája jobb, mint a szülőé, akkor az utódot a prioritásos sor elejére állítják (a szülőt közvetlenül az utód mögé helyezve), és a ciklus újraindul.
Más esetben az utódod hozzáadják a sorhoz (a heurisztikus értéke által meghatározott helyre), majd az eljárás kiértékeli a szülő fennmaradó utódait (ha vannak ilyenek).

Alább látható ezen algoritmus pszeudokódként, ahol a Sor egy prioritásos sort jelöl, amely a csomópontokat a céltól való heurisztikus távolságuk alapján rendezi. Ez az implementáció nyomon követi a meglátogatott csomópontokat, ezért irányítatlan gráfok esetén is használható, és módosítható az útvonal lekérdezéséhez.

Függvény LEK(start, cél): Csomópont
  start.Feltárt ← Igaz;
  Sor.Hozzáad(start);
  Ciklus_Míg Sor.Elemszám != 0:
    aktuális_csomópont ← Sor.Kivesz(aktuális_csomópont);
    Ciklus I ← (1..aktuális_csomópont.Szomszédszám):
      szomszéd ← aktuális_csomópont.Szomszédok[I]
      Ha szomszéd.Feltárt = Hamis Akkor:
        Ha szomszéd = cél Akkor:
          LEK ← szomszéd;
        Különben:
          szomszéd.Feltárt ← Igaz;
          Sor.Hozzáad(szomszéd);
        Ha Vége
      Ha Vége
    Ciklus Vége
  Ciklus Vége
  LEK ← NULL;
Függvény Vége

Jegyzetek

↑ Pearl, J.. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 48.. o. (1984)
↑ ^a ^b ^c Russell, Stuart J., Norvig, Peter. Artificial Intelligence: A Modern Approach, 2, Upper Saddle River, New Jersey: Prentice Hall (2003). ISBN 0-13-790395-2
↑ Carnegie Mellon: Greedy Best-First Search when EHC Fails

Fordítás

Ez a szócikk részben vagy egészben a Best-first search című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

További információk

Wikibooks: Mesterséges intelligencia: Legjobbat először keresés

Kapcsolódó szócikkek

Read other articles:

Kerry Von Erich

Kerry Von ErichKerry Von Erich, c. 1987Nama lahirKerry Gene AdkissonLahir(1960-02-03)3 Februari 1960[1][2]Niagara Falls, New York, A.S.Meninggal18 Februari 1993(1993-02-18) (umur 33)[1][2][3]Denton, Texas, A.S.Sebab meninggalBunuh diri dengan tembakanPasanganCatherine Murray (m. 1983; c. 1992)Anak2, termasuk Lacey Von ErichKeluargaVon ErichKarier gulat profesionalNama ringCosmic Cowboy #2Ker...

Howard County, Missouri

County in Missouri, United States County in MissouriHoward CountyCountyThe Howard County Courthouse in FayetteNickname: Mother of CountiesLocation within the U.S. state of MissouriMissouri's location within the U.S.Coordinates: 39°08′N 92°42′W / 39.14°N 92.7°W / 39.14; -92.7Country United StatesState MissouriFoundedJanuary 23, 1816Named forBenjamin HowardSeatFayetteLargest cityFayetteArea • Total472 sq mi (1,220 km2)...

Valerenic acid

Chemical compound Not to be confused with Valeric acid. Valerenic acid Names Preferred IUPAC name (2E)-3-[(4S,7R,7aR)-3,7-Dimethyl-2,4,5,6,7,7a-hexahydro-1H-inden-4-yl]-2-methylprop-2-enoic acid Identifiers CAS Number 3569-10-6 N 3D model (JSmol) Interactive image ChEBI CHEBI:9921 N ChemSpider 4788689 Y ECHA InfoCard 100.112.154 PubChem CID 6440940 UNII 34NDB285PM N CompTox Dashboard (EPA) DTXSID8034089 InChI InChI=1S/C15H22O2/c1-9-4-6-12(8-11(3)15(16)17)14-10(2)5-7-13(9)1...

Keprabon, Banjarsari, Surakarta

KeprabonKelurahanKantor Kelurahan Keprabon setelah renovasi 2012Peta lokasi Kelurahan KeprabonNegara IndonesiaProvinsiJawa TengahKotaSurakartaKecamatanBanjarsariKodepos57131Kode Kemendagri33.72.05.1006 Kode BPS3372050003 Jumlah penduduk3.122 jiwa (2020) Keprabon (Jawa: ꦏꦼꦥꦿꦧꦺꦴꦤ꧀, translit. Keprabon) merupakan sebuah kelurahan di kecamatan Banjarsari, Surakarta. Kelurahan ini memiliki kode pos 57131. Pada tahun 2020, kelurahan ini berpenduduk sebesar 3.122 jiwa....

2009 Saint Paul mayoral election

2009 Saint Paul mayoral election ← 2005 November 3, 2009 (2009-11-03) 2013 → Candidate Chris Coleman Eva Ng Party Democratic (DFL) Independent Popular vote 23,380 10,496 Percentage 68.67% 30.84% Mayor before election Chris Coleman Democratic (DFL) Elected Mayor Chris Coleman Democratic (DFL) The 2009 Saint Paul mayoral election in the U.S. state of Minnesota held a scheduled primary election on 15 September and a general election on 3 November...

Chris Berry (broadcaster)

American broadcaster Chris BerryBornDecatur, Illinois, United StatesNationalityAmericanAlma materUniversity of MississippiOccupation(s)Broadcaster, Journalist Chris Berry is an American broadcaster whose career has included newsroom and management roles for some of the largest communications firms in the United States.[1] As executive vice president of news, talk and sports programming for iHeartMedia he is responsible for overseeing the company's news, talk and sports brands. ...

Ding Yuan

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus. Cet article ne cite pas suffisamment ses sources (février 2014). Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ». En pratique : Quelles sources sont attendues ? ...

Nicolaus Bruhns

Danish-German organist, violinist, and composer Not to be confused with Friedrich Nicolaus Bruhns. Nicolaus Bruhns House in Schwabstedt Nicolaus Bruhns (also Nikolaus, Nicholas; late 1665 – 8 April [O.S. 29 March] 1697 in Husum) was a Danish-German organist, violinist, and composer. He was one of the most prominent organists and composers of his generation.[1] Biography Bruhns was born in Schwabstedt (Danish: Svavsted), a small settlement near Husum. He came from a...

Hari Rabies Sedunia

Hari Rabies SeduniaLogo Hari Rabies SeduniaNama resmiWorld Rabies DayTanggal28 SeptemberPertama kali2007Terkait denganRabies Hari Rabies Sedunia (bahasa Inggris: World Rabies Day, sering disingkat WRD) adalah sebuah kampanye global yang diselenggarakan pada tanggal 28 September setiap tahun. Peringatan Hari Rabies Sedunia dilakukan untuk meningkatkan kesadaran masyarakat akan pencegahan dan pengendalian penyakit rabies.[1] Hari Rabies Sedunia mulai diselenggarakan pada tahun 2007.[...

趙家驤

追晉陸軍二級上將趙家驤將軍个人资料出生1910年大清河南省衛輝府汲縣逝世1958年8月23日(1958歲—08—23)（47—48歲） † 中華民國福建省金門縣国籍中華民國政党中國國民黨获奖青天白日勳章（追贈）军事背景效忠中華民國服役國民革命軍中華民國陸軍服役时间1924年－1958年军衔二級上將（追晉）部队四十七師指挥東北剿匪總司令部參謀長陸軍�...

Piala Raja Spanyol 2019–2020

Piala Raja Spanyol 2019–2020Negara SpanyolJumlah peserta125Juara bertahanValenciaJuaraReal SociedadTempat keduaAthletic BilbaoJumlah pertandingan123Jumlah gol345 (2.8 per pertandingan)Pencetak gol terbanyak Alexander Isak(Real Sociedad)(5 gol)← 2018–2019 2020–2021 → Seluruh statistik akurat per 13 Februari 2020. Piala Raja Spanyol 2019–2020 adalah edisi ke-116 dari penyelenggaraan Piala Raja Spanyol, turnamen sepak bola di Spanyol dengan sistem piala. Final Artikel utama: Fin...

Brigate Rosse

Brigate RosseSimbolo delle Brigate Rosse.Attiva1970-1988 Nazione Italia ContestoAnni di piombo IdeologiaComunismoMarxismo-leninismo Affinità politicheNuclei Armati ProletariPrima LineaRote Armee Fraktion ComponentiFondatoriRenato CurcioMara CagolAlberto Franceschini Componenti principaliRenato CurcioMara CagolAlberto FranceschiniMario MorettiProspero GallinariFranco BonisoliRocco MicalettoLauro AzzoliniBarbara BalzeraniMaurizio IannelliValerio MorucciAdriana FarandaRiccardo DuraGiovanni...

Alseroxylon

Pharmaceutical drug AlseroxylonReserpine, the major component of alseroxylonClinical dataATC codeC02AA03 (WHO) IdentifiersCAS Number8001-95-4 Yactive moiety: 8063-17-0 YDrugBankDB00386 NChemSpiderNoneUNIIH192N84N1Gactive moiety: H192N84N1G YChEMBLChEMBL1201454 NChemical and physical dataFormulaVaries NY (what is this?) (verify) Alseroxylon (Rautensin, Rauwiloid) is a norepinephrine reuptake inhibitor that has been investigated ...

Tina Fey

Pour les articles homonymes, voir Fey. Tina Fey Tina Fey à l'avant première d'Opération Muppetsà Los Angeles, en Californie, le 11 mars 2014. Données clés Nom de naissance Elizabeth Stamatina Fey Surnom Tina Fey Naissance 18 mai 1970 (53 ans)Upper Darby Township, (Pennsylvanie), États-Unis Nationalité Américaine Profession ActriceScénaristeProductriceHumoriste Films notables Lolita malgré moiCrazy NightMegamindOpération MuppetsWhiskey Tango Foxtrot Séries notables Saturday ...

Clube Municipal Ananindeua

Brazilian association football club based in Ananindeua, Pará, Brazil Soccer clubAnanindeuaFull nameClube Municipal AnanindeuaNickname(s)Tartaruga (Turtle)Founded3 January 1978; 46 years ago (1978-01-03) Home colors Away colors Clube Municipal Ananindeua, commonly referred to as Ananindeua, was a Brazilian professional club based in Ananindeua, Pará. The club was founded on 3 January 1978. History The town of Ananindeua is in the metropolitan area of Belém. It has approx...

1913 Pittsburgh mayoral election

Election for Mayor of Pittsburgh 1913 Pittsburgh mayoral election ← 1909 November 4, 1913 1917 → Nominee Joseph G. Armstrong Stephen G. Porter Popular vote 39,912 37,472 Percentage 51.6% 48.4% Mayor before election William A. Magee Republican Elected Mayor Joseph G. Armstrong Elections in Pennsylvania Federal government U.S. President 1789 1792 1796 1800 1804 1808 1812 1816 1820 1824 1828 1832 1836 1840 1844 1848 1852 1856 1860 1864 1868 1872 1876 1880 1884 1...

Kingdom of Croatia (925–1102)

Medieval Kingdom Kingdom of CroatiaKraljevina Hrvatska (Croatian)Regnum Croatiæ (Latin)c. 925a–1102 Depiction of the Crown of Zvonimir Croatia during the reign of King Tomislav in purple and vassal states in light purpleCapitalVaried through timeNinBiogradSolinKninCommon languagesOld CroatianOld Church SlavonicLatinReligion Roman CatholicDemonym(s)Croatian, CroatGovernmentFeudal MonarchyKing • 925–928 (first) Tomislava• 1093–1097 (last) Petar Sna...

Syncom

1960s and 80s NASA program to develop communications satellites This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (July 2011) (Learn how and when to remove this message) Syncom (for synchronous communication satellite) started as a 1961 NASA program for active geosynchronous communication satellites, all of which were developed and manufactured by the Space and ...

Kompleks piramida kembar

Kompleks piramida kembar Q di Tikal Kompleks piramida kembar atau kelompok piramida kembar adalah terobosan arsitektur yang diciptakan oleh peradaban Maya di Mesoamerika kuno.[1] Kompleks piramida kembar dibangun di kota Tikal di Cekungan Petén tengah, Guatemala, setiap 20 tahun sekali untuk menandai siklus k'atun dalam Kalender Hitung Panjang Maya.[2] Kompleks piramida kembar juga telah ditemukan di Yaxha, sebuah kota besar yang terletak sejauh 30 km di sebelah tenggara...

琵琶

この項目では、楽器のビワについて説明しています。その他の用法については「びわ」をご覧ください。この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: 琵琶 – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL...