Efect orizont
Efectul L 'horizon (Horizon Effect în engleză) este o problemă care apare cu algoritmii de căutare în profunzime cu întrerupere programată. [1]
Problemă
Un algoritm de căutare aprofundată este în general implementat pe o structură de date, cum ar fi graficul . Scopul său este de a căuta folosind tehnica recursivă în mod obișnuit, căutând toate soluțiile posibile. [2] Acești algoritmi sunt, de asemenea, implementați în programele de șah, dar din moment ce există o mare varietate de soluții posibile în șah și având calculatoare cu memorie limitată disponibilă, este adoptat un algoritm de căutare în profunzime cu întrerupere, adică este introdus un număr dincolo de care cercetările nu continuă. Acest număr corespunde adâncimii maxime pe care o poate atinge recursiunea; creșterea acestui număr crește adâncimea recursiunii. [3]
Problema care se creează astfel este efectul orizontului: neputând examina toate soluțiile, rămânem în întuneric despre o serie de cazuri care ar putea fi favorabile soluției problemei noastre. De exemplu, să presupunem că un computer programat să joace șah face o căutare profundă. La începutul jocului, albul are ocazia să facă 16 mișcări de pion și 4 mișcări de cal pentru un total de 20 de mișcări. Aceeași situație este neagră. Având în vedere o profunzime a analizei 2 la începutul jocului, obținem cât mai mult de 400 de mișcări posibile (20 de alb pentru 20 de negru); cu cât crește adâncimea, cu atât crește timpul de procesare. Cu toate acestea, mai puțină analiză în profunzime este echivalentă cu o viziune mai restrânsă a mișcărilor posibile, pierzând astfel soluții care ar putea duce la o victorie sau care ar putea evita o înfrângere (efect de orizont). [4]
În imaginea prezentată aici puteți vedea o structură de copac pe care este posibil să se producă efectul orizontului. Un algoritm generic de căutare a adâncimii cu tăiere (pauză) după două recursiuni; va ignora cea mai optimă soluție corespunzătoare nodului etichetat „A”, deoarece nu poate să o vadă, este dincolo de orizontul său maxim.
Soluții
Pentru a depăși problema efectului orizont, se adoptă diverse soluții care variază în funcție de aplicația pe care este implementat algoritmul. Aici sunt ilustrate câteva soluții, adoptate în principal în programele de șah.
Adâncime crescută
Alegeți să petreceți mai mult timp și mai multe resurse pentru a obține un rezultat satisfăcător, crescând numărul adâncimii maxime, care în orice caz din motive fizice nu poate fi infinită. [1]
Cercetare liniștită
Cercetarea în repaus sau metoda selectivă este un sistem de cercetare care exclude de la cercetarea aprofundată soluțiile care nu au legătură cu soluția finală, definită ca fiind aruncată. Prin includerea doar a celor mai probabile și / sau cele mai reușite, timpul de procesare este redus. [1] [4]
Bază de date
Unele dintre cele mai plauzibile și adoptabile soluții într-o anumită stare de căutare sunt stocate într-o bază de date și pot fi reutilizate pentru a reduce timpul de căutare. [1] [4]
Extensie unică
Soluțiile clar mai bune sunt salvate în timpul căutării (dar nu sunt analizate), pentru o revizuire ulterioară dincolo de limita maximă de adâncime. Dacă soluția nu este validă odată ce orizontul este depășit, adică numărul maxim de adâncimi, se adoptă o altă soluție (urmărind algoritmul utilizat) poate dezavantajat inițial, dar care ar putea duce la o situație mai bună, chiar dacă nu este posibil să se știe , deoarece nu se efectuează din nou o căutare aprofundată. Extensia unică este similară cu o căutare în repaus: soluțiile care cu siguranță nu sunt optime sunt aruncate, soluțiile care ar putea fi optime sunt analizate, soluțiile care sunt imediat optime sunt salvate pentru examinare dincolo de limita de adâncime la sfârșitul căutării și, în consecință, este au verificat că sunt într-adevăr optime. [5]
Notă
- ^ a b c d ( IT ) Horizon effect , pe okpedia.it , 15 noiembrie 2014. Accesat la 24 mai 2016 .
- ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Introducere în algoritmi , Jackson Libri, 2003, ISBN 88-256-1421-7 .
- ^ Stuart Russell, Peter Norvig, "Inteligența artificială o abordare modernă" Ediția a doua Depusă la 14 mai 2016 în Internet Archive ., Prentice Hall, 2003, New Jersey, pp. 616,617
- ^ a b c ( IT ) Andreas Vogt, Limitele computerului , la Șah! , 1998. Adus la 24 mai 2016 (arhivat din original la 10 aprilie 2016) .
- ^ Stuart Russell, Peter Norvig, "Inteligența artificială o abordare modernă" Ediția a doua Depusă la 14 mai 2016 în Internet Archive ., Prentice Hall, 2003, New Jersey, pp.174,175
