Թարգմանչական աշխատանքներ

Դիպլոմային Գրաֆում կարճագույն ճանապարհի որոնման ալգորիթմների ուսումնասիրություն և վերլուծություն

Բովանդակություն
Ներածություն
1.1. Գրաֆներ
1․2․ Գրաֆների նրկայացումը
1․3․Գրաֆիկների տեսակները և նրանց տրման եղանակները
Հարակից մատրիցա
Հաճախականության մատրիցա
1․4․ Ճանապարհներ, ուղիներ, կապակցում
Քաշը և ճանապարհի երկարությունը
2.1 Խնդրի դրվածքը
2․2․Գրաֆում կարճագույն ճանապարհի որոնման ալգորիթմներ
2․2․1․Բելման-Ֆորդ ալգորիթմ
2․2․2․ Դիկստրայի ալգորիթմ
2․3 Գրաֆում կարճագույն ճանապարհի որոնման դիկստրայի ալգորիթմ ծրագրային իրագործում
Ծրագրի իրագործում
Ծրագրի գործարկում
Օգտագործված գրականություն

Հատված
Մեր ծրագրում մեկ հանգույցն ունի մի քանի կարևոր հատկություններ. Այն տարբերում է բոլոր մյուսներից, ունի եզրեր, որոնք այն կապում են մյուսների հետ, հատկություն, որը ցույց կտա՝ արդյոք այցելե՞լ ենք հանգույցը, թե ոչ, դրա կոորդինատները օգտագործվում է դրա գրաֆիկական ներկայացման մեջ և ընդհանուր արժեքը: Եզրը գրաֆիկի երկու հանգույցների կապն է: Գոյություն ունեն երկու տեսակի եզրեր`ուղղորդված և չուղղորդված: Ուղղորդված ծայրը կարելի է դիտարկել որպես միակողմանի փողոց: Դա ցույց է տալիս, որ չնայած A հանգույցից դեպի B հանգույց ուղի կա, հակառակ ուղղությամբ անցնելը (B- ից A) հնարավոր չէ: Դա անելու համար մեզ պետք է մեկ և մյուս եզրը, որը կապում է A և B և որի ուղղությունը ցույց է տալիս դեպի A: Անուղղակի եզրը, մյուս կողմից, չի սահմանափակում այդպիսի սահմանափակումներով և թույլ է տալիս մեզ գնալ երկու ուղղություններով: Եզրին կարևոր հատկություններն այն վերջնական հանգույցներն են, որոնք այն կապում է, անկախ նրանից, թե այդ եզրը այցելված է, թե ոչ, դրա քաշը և ուղղությունը, եթե այդպիսիք կան:Ընդհանրապես, գրաֆն ունի միայն մեկ տեսակի եզր: Կախված գրաֆի եզրերի տեսակից, այն որակվում է որպես ուղղորդված կամ չուղղորդված: Այս ծրագրում մենք կքննարկենք չուղղորդված գրաֆները: Այս երկու տարրերը ծրագրում ունեն իրենց համապատասխան իրականացումը. Node և Edge դասերը: Բացի այդ, կան տվյալների ևս երկու կառույցներ, որոնք մեզ օգնում են ալգորիթմի կատարման հարցում միևնույն ժամանակ պարզության և արագության տեսանկյունից. ReachableNode և ReachableNodeList դասերը: Օժանդակ այս երկու դասերը թույլ կտան մեզ արագ տեսակավորել չայցելված հանգույցներն ըստ իրենց ընդհանուր արժեքի և ընտրել լավագույնը և դա անել ամենաարդյունավետ ձևով: Գրաֆի երկու հանգույցների միջև ամենակարճ ուղին գտնելու համար Դիկստրայի ալգորիթմը սովորաբար բնութագրվում է որպես «ագահ» ալգորիթմ: Այսինքն, ճանապարհի յուրաքանչյուր քայլափոխի ալգորիթմը կընտրի այն հանգույցը, որն ունի ամենացածր ընդհանուր արժեքը և որը չի այցելվել: Վերցնենք մի պարզ օրինակ և փորձենք ձեռքով գործարկել ալգորիթմը ՝ տեսնելու, թե ինչ է հարկավոր անել յուրաքանչյուր քայլ առ քայլ: Պատկերացնենք, որ մենք ուզում ենք 1-ին հանգույցից անցնել 8-րդ հանգույց: Մենք սկսում ենք հաշվի առնելով բոլոր հարևանները (կամ ինչպես նշված է կոդի նմուշներում — հասանելի իրերի հանգույցները) դեպի մեկնարկային հանգույցը `2, 4 և 5 հանգույցները:

Գրականության ցանկ
1. Diestel R. Graph Theory — Springer, 2005 — 410 pages.
2. Graph Theory with Applications, 487 Pages • 2007 , by C. Vasudev
3. Алексеев, В. Е. Графы и алгоритмы. Структуры данных. Модели вычислений / В.Е. Алексеев, В.А. Таланов. — М.: Бином. Лаборатория знаний, Интернет-университет информационных технологий, 2009. — 320 c.
4. Алексеев В.Е., Таланов В.А. — Графы. Модели вычислений. Структуры данных, Глава 3.4 Нахождение кратчайших путей в графе — Нижний Новгород, 2005;
5. Олифер В.Г. Олифер Н.А. — Основы компьютерных сетей — Питер, 2009;
6. Харари Ф., Палмер Э. Перечисление графов — М.: Мир, 1977. — 324 с.
7. …