Մասնակից:ArtashesKarapetyan/Սևագրություն
Լավագույն առաջին փնտրում (Լավագույն առաջին փնտրում)-ը դա մի ալգորիթմ է, որը փնտրում է "explores" գրաֆիկը ի ընդլայնման առավել խոստումնալից հանգույց և ընտրված է որոշակի կանոնով is a search algorithm wahich explores a .
Judea Pearl -ը Լավագույն առաջին փնտրումում ներկայացնում է հանգույցի խոստում n -ը հերոստիկ գնահատման գործողության կողմից որը, հիմնականում կաղված է n -ից , նկարագրության նպատակից, ինֆորմացիայի հավաքից մինչ այդ պահը և ամենակաորևորը դա լրացուցիչ իմացությունն է՝ կապված ընդհանուր տիրուըտւմ եղած խնդիրների հետ: "[1] [2]
Որոշ հեղինակներ, որոնք օգտագործվում են "best-first search" -ը անդրադառնալով հատկապես հեուրիստիկ փնտրմանը՝ իմանալու թե ինչքանով է մոտ ուղու վերջը և և լուծումը Հեուռիստիկ, այնպես որ այդ գնահատված ուղիները, որոնք մոտ են լուծմանը՝ ներկայացվեն առաջինը: Այս հատուկ պնտրման տեսակը անվանվում է greedy best-first search.[2]
Արդյունավետ ընտրությունը ներկայիս լավագույն թեկնածու է, որպես կանոն, իրականացվում է երկարաձգումով՝ օգտագործելով առաջնային հերթ:
The A* որոնման ալգորիթմը դա լավագույն-առաջին փնտրման մեկ օրինակ է. Լավագույն-առաջին ալգորիթմները հաճախ օգտագործվում են ften used for path finding in համակցական փնտրման մեջ:
Algorithm [3][խմբագրել | խմբագրել կոդը]
Բաց = [նաղնական վճակ]
բացվելիս դատարկ չէ մինչև նպատակի հայտնաբերումը:
Կատարել
1. Հեռացնել լավագույն հանգույցը ԲԱՑ-ից՝ անվանելով նրան n:
2. Ետե n-ը նպատակի իրավիճակ է , ուղու ուղեվորումը n ին (արձանագրված ծնողներին)և հետադարձ չանապարհին:
3. Ստեղծել n-ի հետնորդներ:
4. Գնահատել յուրաքանչյուր հետնորդի, ավելավնել ԲԱՑ- ում և արձանագրել նրա ծնողներին:
Կատարված է:
Նշենք որ այս ալգորիթմի տարբերակը ամբօղջական չէ: Միշտ չէ որ նա գտնում է հանգույցների միջև եղած հնարավոր ճանապարհը, նույնիսկ երբ դա մեկն է: Օրինակ նա կախվում է եթե ցիկլի ժամանակ ընկնում է փակուղի. Այսինքն հանգույցը միակ հետնորդը հանդիսանում է հենց նրա ծնողը: Նա կգնա հետ իր ծնողի մոտ՝ նորից ավելացնելով փակուղային հետնորդOPEN ցանկում և այսպես շարունակ:
Հաջորդ տարբերակը ընդլայնում է անգորիթմը՝ օգտագործելով լրացուցիչ Փակ ցանկը, պարունակելով բոլոր գնահատված հանգույցները և նորից չի դիտարկի այն: Քանի որ դա հնարավորություն է տալիս ղուսափել յուրաքանչյուր հանգույցի կրկնակի անգամ գնահատմանը՝ նա չի ընկնի անվերջ ցիկլի մեջ:
ԲԱՑ = [նաղնական վիճակ]
Փակ = []
ԲԱՑ ժամանակ դատարկ չէ
Կատարել
1. Հեռացնել լավագույն հանգույցը Բաց-ից, անվանել n, ավելացնել ՓԱԿ-ում:
2. Եթե n-ը նպատակի իրավիճակ է , ուղու ուղեվորումը n-ին (արձանագրված ծնողներին) և վերադարձնել ծնողներին:
3. Ստեղծել n-ի հետնորդներ:
4. Յուրաքանչյուր հետնորդին կատարել.
ա. եթե նա ՓԱԿ-ում չէ, գնահատել նրան, ավելացնել ԲԱՑ-ում և արձանագրել ծնողներին:
բ. Աըլ դեպքում,փոփողել արձանագրված ծնողներին, եթե այդ նոր ուղին ավելի լավն է քան նաղորդը:
Կատարված է:
Նաև նշենք, որ այդ կեղծ կոդի երկու տարբերակները պարզապես կդադարեն երբ ոչ մի ուղիչգտնվի:Այս դեպքում փաստացի կատարումը, իհարկե պահանջում է հատուկ մշակում :
See also[խմբագրել | խմբագրել կոդը]
References[խմբագրել | խմբագրել կոդը]
- ↑ Pearl, J. Heuristics: Intelligent Search Strategies for Computer Problem Solving. Addison-Wesley, 1984. p. 48.
- ↑ 2,0 2,1 Կաղապար:Russell Norvig 2003. pp. 94 and 95 (note 3).
- ↑ http://www.macs.hw.ac.uk/~alison/ai3notes/subsubsection2_6_2_3_2.html Best First Search