Қысқа жолды іздеу алгоритмдері

Қазақстан Республикасының Білім және ғылым министрлігі Л. Н. Гумилев атындағы Еуразия ұлттық университеті

Айса Бейбарыс Бауыржанұлы

Тақырыбы: Дейкстра алгоритмы және оны тасымалдау төлемақысын санау кезінде тарифтік арақашықтықты табуға пайдалану

ДИПЛОМДЫҚ ЖҰМЫС

5В070500 - «Математикалық және компьютерлік моделдеу» мамандығы

Қазақстан Республикасының Білім және ғылым министрлігі Л. Н. Гумилев атындағы Еуразия ұлттық университеті

«Қорғауға жіберілді»

«Математикалық және компьютерлік моделдеу» кафедрасының меңгерушісі

Адамов А. А

« » 2022 ж.

ДИПЛОМДЫҚ ЖҰМЫС

Тақырыбы: «Дейкстра алгоритмы және оны тасымалдау төлемақысын санау кезінде тарифтік арақашықтықты табуға пайдалану»

5В070500 «Математикалық және компьютерлік моделдеу» мамандығы бойынша

Орындаған Б. Б. Айса

Ғылыми жетекшісі

ф. -м. ғ. к., қауым. профессор М. Б. Габбасов

Л. Н. Гумилев атындағы Еуразия ұлттық университеті Механика - математика факультеті

«Математикалық және компьютерлік моделдеу» кафедрасы 5В070500 - «Математикалық және компьютерлік моделдеу» мамандығы

БЕКІТЕМІН

Кафедра меңгерушісі

А. А. Адамов

« » 20 ж.

Студент Айса Бейбарыс Бауыржанұлы _

(тегі, аты, әкесінің аты)

4-курс, МКМ-41 тобы, 5В070500 − «Математикалық және _

компьютерлік моделдеу» мамандығы, күндізгі_ (курс, тобы, мамандық, оқу формасы)

Диплом жұмысты орындауға арналған ТАПСЫРМА

1. Жұмыстың тақырыбы «Дейкстра алгоритмы және оны тасымалдау төлемақысын санау кезінде тарифтік арақашықтықты табуға пайдалану»

университет бойынша 2022ж. « 14 » қаңтар берілген №47-n бұйрығымен бекітілген.

2. Студент аяқтаған жұмысты тапсыру мерзімі « 28 » мамыр 2022 ж.
3. Жұмыстың бастапқы деректері:дипломдық жұмыс тақырыбы бойыншағылыми мақалалар, сондай-ақ заманауи басылымдар, зерттеліп, ғылымиәдебиет көздері пайдаланылды
4. Дипломдық жұмысты дайындауға қатысты сұрақтар тізімі:Екі стансаның арасындағы тарифтік арақашықтықты Дейкстра әдісімен табатын программа жазу
5. Графикалық материалдың тізбесі: 28сурет
6. Негізгі ұсынылған әдебиеттер тізімі

1. Березина Л. Графы и их применение. М. : Просвещение, 1979 г. 2. Зыков А. А. Основы теорий графов. М. : Наука, 1987г.

3. Евстигнеев В. А. Применение теорий графов в программиро-

вании / под редакцией Ершова А. П. -М: Наука, 1985 г.

4. Татт У. / перевод с английского Гаврилова Г. П. - М: Мир,

1988г.

5. Оре О. /перевод с английского Врублевская И. Н. - М: Наука,

1980г.

6. Емеличев В. А. Лекции по теории графов / В. А. Емеличев и др.

- М. : Наука, 1990.

7. Кристофидес Н. Теория графов. Алгоритмический подход /

Н. Кристофидес. - М. : Мир, 1978.

8. Ловас Л . Прикладные задачи теории графов / Л. Ловас,

М. Пламмер. - М. : Мир, 1998.

9. Новиков Ф. А. Дискретная математика для программистов / Ф.

А. Новиков. - СПб. : Питер, 2001.

7. Жұмыс бойынша тиісті бөлімдерде көрсетілген кеңестер

8. Дипломдық жұмысты орындау кестесі

Тапсырманы беру күні «14» қаңтар 2022ж.

Ғылыми жетекші, ф. -м. ғ. к., қауым. профессор М. Б. Габбасов Тапсырманы қабылдады: студент __Б. Б. Айса

МАЗМҰНЫ

КІРІСПЕ 9

1. Теориялық бөлім 11Графтар теориясының негіздері 11Темір жол стансаларынан тұратын граф салу 22
2. Дейкстра алгормін игеру 30Қысқа жолды іздеу алгоритмдері 31

2. 2. Қысқа жолды іздеу процесі 32

3. Практикалық бөлім 373. 1 Екі стансаның арасындағы тарифтік арақашықтықты Дейкстра әдісімен табатын программа жазу 37ҚОРЫТЫНДЫ 43

ПАЙДАЛАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ 44

ҚОСЫМША 46

КІРІСПЕ

Жергілікті тарифтерді тeмip жолдың басшылары белгілейді. Жүктерді тасымалдағаны үшін төленетін ақы және түрлі жинақ, қойылымдары кіретін бұл тарифтер берілген темір жол шеңберінде қызмет етеді.

Темір жол бойымен жүк үлкен, жолаушылар немесе жүктік жылдамдықпен тасымалдануы мүмкін. Жылдамдық түpi жүктің тәулігіне қанша килoметр жүруі тиіс екенін анықтайды.

Тарифтік қашықтық осы тасымалдау ара қашықтығы болып табылады. Тасымалдау ақысы ең қысқа бағыттағы ара қашықтық бойынша алынуы мүмкін, жүктік немесе үлкен жылдамдықпен жүктерді тасымалдау кезінде тарифтік қашықтыққа немесе габариттік емес жүктерді немесе жүктерді жолаушылар жылдамдығымен тасымалдау кезінде нақты өткен кашықтық үшін алынуы мүмкін.

Жүктердің тасымалдауы жүргізілетін вагон типі түрліше келеді. Темір жол бойымен жүктер әртүрлі, арнайы немесе изотермиялық вагондарда, цистерналарда немесе платформаларда тасымалдануы мүмкін. Тасымалдау ақысы әр жағдайда әр түрліше болады. Тасымалданатын жүктердің саны - тасымалдауға маңызды әсер ететін фактор.

Дипломдық жұмыстың мақсатына орай бұл тарифтік қашықтықты есептеуге графтар көмекке келеді. Яғни, Дейкстра алгоритмін тақырыпқа сәйкес темір жол логистикасында қолданылу аясында графтар негізгі рөл атқарады.

Графтар теориясы - графтардың қасиетін оқытатын дискретті математиканың бір бөліміне жатады. Графтар теориясының практикалық мүмкіндіктері өте зор. Түрлі білім салаларында, мысалы психология, химия, электротехника, сонымен қатар көлік тасымалдауда, басқаруда, сауда-саттықта жəне білім беруді жоспарлауда туындайтын кейбір проблемалар графтар теориясының мəселесі ретінде қалыптасуы мүмкін. Осы жағдайларға байланысты графтар теориясы өз алдына қызықты деп қана саналмай, алынған нəтижелерін жинақтайтын, біліктендіретін, жалпылайтын жəне жан-жақты тарататын білімнің түрлі аймағындағы басты негіздерін көрсетеді. Мысалы, графтар теориясы геоақпараттық жүйелерде де қолданылады. Жаңадан жоспарланған немесе салынған үйді қайта жоспарлауда, құрылыстарда, нысандарда жəне т. б. ол төбелері ретінде қарастырылса, олардың жолдарының бірігуін, инженерлік желілер, электротасымалдау желілері жəне т. б. - оның қабырғасы ретінде қарастырылады. Сонымен қоса, ең қысқа айналу жолын немесе ең жақын азық-түлік дүкенін табу сияқты графтардан шығатын түрлі есептеулерді қолдану тиімді бағдарларды жоспарлауға мүмкіндік береді.

Бүгінгі таңда көптеген адамдар маршрутты құру үшін навигаторларды, электронды карталарды пайдаланады. Бұл уақытты қысқартуға, жолды алдын-ала жоспарлауға мүмкіндік береді. Қала масштабындағы навигациядан бастап ғимарат ішіндегі навигацияға дейін бәрі мобильді немесе веб - қосымшалар арқылы жүреді.

Web-қосымшаның қарапайым сайттан айырмашылығы пайдаланушының ресурстағы деректермен өзара әрекеттесуі болып табылады. Ол әр түрлі нысандарды толтыра алады, жеке кабинет арқылы тапсырмаларды орындай алады және т. б.

Бұл жұмыстың мақсаты Дейкстер әдісімен екі станция арасындағы тарифтік қашықтықты табу бойынша сервисті әзірлеу және іске қосу болып табылады. Осы міндетке сәйкес іске асырудың оңтайлы әдістерін таңдау қажет, олардың өлшемдері пайдалану ыңғайлылығы, деректерді өңдеу жылдамдығы, нәтижелердің көрінуі мен дәлдігі болып табылады. Ол үшін таңдау керек:

1) бағдарламалау тілі

2) web-сервер

3) ең қысқа жолды табу алгоритмі

4) қосымшаны әзірлеу құралдары

Бұл дипломдық жұмыстың негізгі мақсаты графтың бойындағы ең қысқа арақащықтықты табуға арналған Дейкстра алгоритмін игеріп және оны тасымалдау төлемақысын санау кезінде екі стансаның арасындағы тарифтік арақашықтықты табатын программада пайдалану көзделген.

Бірінші бөлімде дипломдық жобаның тақырыбы бойынша зерттеу жүргізуге қажетті барлық графтар туралы толық мәліметтер, тақырыпқа сәйкес қолданылуын келтіреміз.

Екінші бөлімде Дейкстра алгоритмінің маңызын ашамыз. Сондай-ақ есепте қолданылуын жіті назарға алып, алгоритм бойынша күрделі жұмыс жүргіземіз.

Үшінші бөлімде тәжірибе жүзінде нақты көрсете отырып негізгі бөлімнің маңызын осы python тілінде бағдарламалап түсіреміз.

Қорытындылай келе, дипломдық жобаның тақырыбы бойынша алынған зерттеу нәтижелері мен қолданылу аясы қорытындыланады.

Пайдаланылған әдебиеттер тізімінде 23 әдебиет бар.

1. Теориялық бөлім1. 1 Графтар теориясының негіздері

Графтар ғылым мен практиканың түрлі салаларындағы математикалық модельдердің маңызды элементтері болып саналады. Графтың көмегімен автоматика, электроника, физика, химия жəне т. б. сияқты білім аймақтарында жинақталған мəселелерді шешуді жеңілдетуге болады. Графтың көмегімен жол, газ құбырлары, жылу жəне электр желілерінің сұлбалары бейнеленеді. Сонымен қатар графтар математикалық жəне экономикалық есептерді шешуде үлкен көмек көрсетеді.

1. 1. Граф жəне оның түрлері

Бөлімімізді графтар теориясының негізгі ұғымдарынан бастайық. Осы ұғымдарға негізделген бірнеше нəтижелерді келтірейік.

Граф анықтамасын қарапайым сөзбен түсіндірсек ол нүктелер жиынынан (графтың төбелері) тұратын жəне осы нүктелер жиынын қосатын түзу немесе қисық кесінділерден (граф қабырғалары) тұратын сұлбаны айтамыз. Граф G=(V, E) екі жиыннан, яғни шекті жиындар элементтерінен тұрады. Бұл жерде G - граф, ал V - графтың төбелері, E - графтың қабырғалары деп аламыз.

Графтар, негізінен, геометриялық фигура түрінде бейнеленеді, сондықтан графтың төбелері нүкте арқылы, қабырғалары нүкте- лерді бір-бірімен қосатын сызықтар арқылы бейнеленеді (1. 1-сурет) .

Графтың шеткі төбелері бірдей болса, онда барлық қабырға- лары параллель болып табылады. Ал, егер қабырғасының басы мен соңы бір төбеде орналасса (1. 1 а-суретте), онда оны ілмек деп атаймыз. Жалпы айтқанда, ілмектің бағыты болмайды. Бірақ бағытталған графтарды аралас графтардан ажырату үшін бағытталған графтарда ілмектің бағыты көрсетіледі.

Ілмек - бұл бастапқы жəне шеткі доғаның бір-бірмен сəйкес- тенуі.

Ілмексіз жəне параллель қабырғасыз графтар қарапайым граф деп аталады. Графтың төбелерінің жиыны n элементтен тұратын болса, онда G граф n-ретті граф болады.

Қабырғалары жоқ графтар бос граф деп аталады (1. 1 в-сурет) . Ал, егер графтың төбелері жоқ болса (онда əрине қабырғалары да жоқ), онда мұндай граф нөл-граф деп аталады.

Графикалық графтар диаграмма түрінде де берілуі мүмкін, онда төбелері нүктемен немесе дөңгелекпен, ал қабырғалары сəйкес қабырға төбелерінің шеттеріндегі нүктелер немесе дөң- гелектерді қосатын сызық кесінділермен бейнеленеді (1. 1 а, ə-сурет) .

Графтарды суретте немесе сұлбада бейнелегенде кесінділері түзу сызық немесе қисық сызық түрінде, ал кесінділердің ұзындықтары мен нүктелердің арақашықтықтары əртүрлі түрде берілуі мүмкін. Əрбір қабырға жұптасқан төбелер арқылы анықталады. Егер графтың қабырғалары реттеліп жұптасқан төбелер арқылы анықталса, онда G бағытталған граф (сызықтары доға түрінде болады) деп аталады. Кері жағдайда, оны G бағытталмаған граф (сызықтарының бəрі қабырғасы болып табылады) деп атаймыз.

Егер графтың əртүрлі екі төбесі бір-бірімен тек қана бір қабырға арқылы қосылған болса, онда ол толық граф деп аталады. Əртүрлі төбелерінің əрбір жұбы көршілес болатын қарапайым графты толық граф деп те атауымызға болады. n төбесі бар

толық граф n(n−1) қабырғадан тұрады жəне K деп белгіленеді 2n

(1. 2-сурет) . n - 1 дəрежелі граф тұрақты граф болып табылады.

Графтың толық болуы немесе болмауы оның жалпы сипаттама- сына байланысты болады.

Графтың төбелерінің əрбір жұбы бір бағытталған қабырғамен дəл қосылған болса, ондай графтарды толық бағытталған граф деп атаймыз. Егер толық бағытталған графтың əрбір қабырғасында көрсетілген бағыттарын алып тастасақ, онда ол бағытталмаған қабырғалары бар толық графқа айналады.

Графтың төбелері бір-бірінен олардың қанша қабырғаға жататындығына байланысты ажыратылады.

Егер графтың қабырғасының ұштарының орналасу реті еске- рілмейтін болса, онда оны бағытталмаған қабырға деп атайды.

Егер графтың қабырғасының ұштарының орналасу реті ескерілетін болса, онда оны бағытталған қабырға деп атайды. Бұл жағдайда g(xi, xj) қабырғасының басы xi төбесі, ал соңы xj төбесі деп аталады.

Бағытталған қабырға графтың доғасы деп те аталады.

Егер графта бағытталған жəне бағытталмаған да қабырғалар бар болса, онда оны аралас граф деп атайды.

G(X) графындағы əрбір қабырғаның бағытын қарама-қарсыға (керіге) өзгерту арқылы оған кері граф G-1(X) аламыз. Яғни, əрбір бағытталған графқа кері граф бар.

Бағытталмаған толық граф деп кез келген xi, xj О X (i≠j) үшін қабырғалары əртүрлі g(xi, xj) жұптары болатын U(X) графын атайды (1. 3-сурет) .

Кез келген екі төбесі бірнеше қабырғалармен немесе доғалармен қосылған графты мультиграф деп атайды.

1. 4-суретте бағытталмаған жəне бағытталған мультиграфтар берілген.

Қабырғалары G(X) графымен бірге толық U(X) графын беретін Gk(X) графын G(X) -тің толықтаушы граф деп атайды.

Графтағы барлық қабырғалары əр түрлі болатын жолдың бағытын тізбек деп атаймыз. Егер графтың барлық төбелері (сонымен қатар қабырғалары) əр түрлі болса, ондай тізбекті қарапайым тізбек деп атаймыз.

Тұйықталған тізбекті цикл деп атаймыз. Бір төбеден басталып жəне сол төбемен аяқталатын бірден кем емес қарапайым жол ұзындығын бағытталған графтағы цикл дейміз.

Іздеу мәселесінің қазіргі жағдайын талдау қысқа жол.

Графикалық теория-бұл дискретті математиканың саласы, оның ерекшелігі объектілерді зерттеуге геометриялық көзқарас болып табылады. Ол әдетте топологияға жатады (өйткені көптеген жағдайларда графиктердің тек топологиялық қасиеттері қарастырылады), бірақ ол жиын теориясының, комбинаторлық математиканың, алгебраның, геометрияның, матрица теориясының, ойын теориясының, математикалық логиканың және басқа да көптеген математикалық пәндердің көптеген бөлімдерімен қиылысады. Графтар теориясының негізгі объектісі-граф және оны жалпылау.

Графикалық теорияның алғашқы міндеттері математикалық ойын-сауық есептері мен жұмбақтарды шешумен байланысты болды (Кенигсберг көпірлері туралы есеп, шахмат тақтасында патшайымдарды орналастыру туралы есеп, тасымалдау туралы есептер, әлем бойынша саяхат туралы есеп және басқалар) . Графтар теориясындағы алғашқы нәтижелердің бірі Л. Эйлердің Кенигсберг көпірлері мәселесін шешуде алған барлық жиектерін қайталамай айналып өту өлшемі болды.

Пазлдар мен ойын-сауық ойындарын шешуде дүниеге келген графикалық теория қазіргі уақытта көптеген мәселелерге қатысты мәселелерді шешудің қарапайым, қол жетімді және қуатты құралына айналды. Бағандар сөзбе-сөз қарапайым. 20 ғ. графиктерге байланысты міндеттер тек физика, химия, электротехника, биология, экономика, әлеуметтану және т. б. ғана емес, сонымен қатар математикада топология, алгебра, ықтималдық теориясы, сандар теориясы сияқты бөлімдерде пайда бола бастады. Ол Қарулы Күштерді айналып өтпеді.

Мемлекеттік шекараны қорғау, оқу-жаттығу шаралары мен әскери операцияларды жүргізу әскерлерді жиі қайта топтастыруды, шерулерді өткізуді талап етеді, ал оларды өткізуге уақыт пен ресурстар шектеулі болғандықтан, бай математикалық аппараты бар графтар теориясы қойылған міндеттерді шешу үшін өте пайдалы болды. Жауынгерлік техниканың немесе бөлімшелердің жаяу тәртіпте дұрыс құрастырылған қозғалыс бағыты тапсырманы тез ғана емес, сонымен қатар сапалы орындауға мүмкіндік береді. Тапсырманы орындау кезінде бұл сізге аз жанармай жұмсауға мүмкіндік береді, ауыр жүктемелерге, күш пен уақытты үнемдеуге байланысты марш кезінде істен шыққан жабдықтардың санын азайтуға көмектеседі, бұл сізге жеке құрамның көңіл-күйін көтеруге мүмкіндік береді. Бұл әсіресе соғыс жағдайында маңызды.

Графтар теориясы бойынша зерттеулер 40-жылдардың аяғы мен 50 - жылдардың басында, ең алдымен кибернетика мен компьютерлік технологияның дамуына байланысты едәуір кеңейді. Компьютерлік технологияның дамуына, күрделі кибернетикалық жүйелерді зерттеуге байланысты графтар теориясына деген қызығушылық артып, графиктер теориясының мәселелері айтарлықтай байытылды. Сонымен қатар, компьютерлерді қолдану бұрын шешілмеген есептеулердің үлкен көлемімен байланысты нақты мәселелерді шешуге мүмкіндік берді. Графикалық теорияның бірқатар экстремалды есептері үшін оларды шешу әдістері жасалды, мысалы, осындай әдістердің бірі желі арқылы максималды ағынды құру мәселелерін шешуге мүмкіндік береді. Бұрын зерттелген және зерттелген графиктердің жеке кластары үшін (ағаштар, жалпақ графиктер және т. б. ) осы сыныптардағы графиктер үшін кейбір мәселелерді шешу ерікті графиктерге қарағанда оңай екендігі көрсетілген (берілген қасиеттері бар графиктердің өмір сүру жағдайларын табу, графиктердің изоморфизмін құру және т. б. ) .

Соңғы үш онжылдықта графикалық теория математиканың қарқынды дамып келе жатқан бөлімдерінің біріне айналды. Бұл тез дамып келе жатқан қосымшалар аймағының сұраныстарына байланысты. Теориялық-графикалық терминдерде дискретті объектілерге байланысты көптеген мәселелер тұжырымдалады. Мұндай міндеттер интегралды схемалар мен басқару схемаларын жобалау кезінде, машиналарды, логикалық тізбектерді, бағдарламалық ағындарды зерттеу кезінде, экономика мен статистикада, химия мен биологияда, кесте теориясы мен дискретті оңтайландыруда туындайды. Осылайша, графикалық теория кибернетиканың математикалық аппаратының маңызды бөліктерінің біріне, Дискретті математика тіліне айналады.

Граф - абстрактілі математикалық объект, ол графиктің шыңдары мен жиектер жиынтығын, яғни шыңдардың жұптары арасындағы қосылыстарды білдіреді. Әр түрлі қосымшалар үшін графиктердің түрлері бағдармен, байланыстар санына шектеулермен және шыңдар мен жиектер туралы қосымша мәліметтермен ерекшеленуі мүмкін. Математика мен информатикаға практикалық қызығушылық тудыратын көптеген құрылымдар графиктермен ұсынылуы мүмкін.

G= (X, U) қарапайым немесе бағдарланбаған графигі реттелген жиындар жұбы деп аталады: элементтері G графигінің шыңдары деп аталатын соңғы бос емес Х және элементтері осы графиктің шеттері деп аталатын 𝑈 ⊆ 𝑋 жиынтығы[3] . X, 𝑦 𝜖 𝑋 шыңдары іргелес, егер 𝑥 𝑦 ∈ 𝑈 болса, ал егер 𝑥 𝑦 ∉ 𝑈 болса, іргелес емес. 𝑥 𝑦 Шеті X және Y шыңдарын, сондай-ақ олардың әрқайсысын кездейсоқ байланыстырады. Бағдарланбаған графиктің мысалы 2-суретте көрсетілген.

Сурет 2.

Жол графикте шыңдардың соңғы тізбегі деп аталады, онда әр шың (соңғысынан басқа) келесі шеттермен ретпен қосылады. Тізбек-бұл қайталанатын жиектері жоқ жол.

---

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.

• Іс жүргізу
• Автоматтандыру, Техника
• Алғашқы әскери дайындық
• Астрономия
• Ауыл шаруашылығы
• Банк ісі
• Бизнесті бағалау
• Биология
• Бухгалтерлік іс
• Валеология
• Ветеринария
• География
• Геология, Геофизика, Геодезия
• Дін
• Ет, сүт, шарап өнімдері
• Жалпы тарих
• Жер кадастрі, Жылжымайтын мүлік
• Журналистика
• Информатика
• Кеден ісі
• Маркетинг
• Математика, Геометрия
• Медицина
• Мемлекеттік басқару
• Менеджмент
• Мұнай, Газ
• Мұрағат ісі
• Мәдениеттану
• ОБЖ (Основы безопасности жизнедеятельности)
• Педагогика
• Полиграфия
• Психология
• Салық
• Саясаттану
• Сақтандыру
• Сертификаттау, стандарттау
• Социология, Демография
• Спорт
• Статистика
• Тілтану, Филология
• Тарихи тұлғалар
• Тау-кен ісі
• Транспорт
• Туризм
• Физика
• Философия
• Халықаралық қатынастар
• Химия
• Экология, Қоршаған ортаны қорғау
• Экономика
• Экономикалық география
• Электротехника
• Қазақстан тарихы
• Қаржы
• Құрылыс
• Құқық, Криминалистика
• Әдебиет
• Өнер, музыка
• Өнеркәсіп, Өндіріс