Диспетчерлік автоматтандырылған жүйелерде қолданылатын алгоритмдердің сипаттамасы


Жұмыс түрі:  Материал
Тегін:  Антиплагиат
Көлемі: 56 бет
Таңдаулыға:   

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ АУЫЛШАРУАШЫЛЫҒЫ МИНИСТРЛІГІ

С. СЕЙФУЛЛИН АТЫНДАҒЫ ҚАЗАҚ АГРОТЕХНИКАЛЫҚ ЗЕРТТЕУ

УНИВЕРСИТЕТІ

ОМАРОВ ЖӘҢГІР ҒАЛЫМЖАНҰЛЫ

ДИСПЕТЧЕРЛІК АВТОМАТТАНДЫРЫЛҒАН ЖҮЙЕЛЕРДЕ АҚПАРАТТЫҚ АЛМАСУДЫ ОҢТАЙЛАНДЫРУ МОДЕЛІН ӘЗІРЛЕУ

7М06101 - Ақпараттық жүйелер және IT сала бойынша шешімдер

Техника ғылымдарының магистрі дәрежесін тағайындау диссертациясы

Астана 2024

ҚАЗАҚСТАН РЕСПУБЛИКАСЫ АУЫЛШАРУАШЫЛЫҒЫ МИНИСТРЛІГІ

С. СЕЙФУЛЛИН АТЫНДАҒЫ ҚАЗАҚ АГРОТЕХНИКАЛЫҚ ЗЕРТТЕУ

УНИВЕРСИТЕТІ

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

«Ақпараттық жүйелер»

кафедрасының меңгерушісі

Шаушенова А. Г.

«___» 2024 ж.

ОМАРОВ ЖӘҢГІР ҒАЛЫМЖАНҰЛЫ

ДИСПЕТЧЕРЛІК АВТОМАТТАНДЫРЫЛҒАН ЖҮЙЕЛЕРДЕ АҚПАРАТТЫҚ АЛМАСУДЫ ОҢТАЙЛАНДЫРУ МОДЕЛІН ӘЗІРЛЕУ

7М06101 - Ақпараттық жүйелер және IT сала бойынша шешімдер

Техника ғылымдарының магистрі дәрежесін тағайындау диссертациясы

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

PhD, аға оқытушысы

Копеев Ж. Б.

Астана 2024

МАЗМҰНЫ

НОРМАТИВТІ СІЛТЕМЕЛЕР
НОРМАТИВТІ СІЛТЕМЕЛЕР: АНЫҚТАМАЛАР
:
НОРМАТИВТІ СІЛТЕМЕЛЕР: ТЕРМИНДЕР МЕН ҚЫСҚАРТУЛАР
:
НОРМАТИВТІ СІЛТЕМЕЛЕР:
:
НОРМАТИВТІ СІЛТЕМЕЛЕР: КІРІСПЕ . . .
: 7
НОРМАТИВТІ СІЛТЕМЕЛЕР: 1 Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыру моделін әзірлеудің алғышарттары . . .
: 9
НОРМАТИВТІ СІЛТЕМЕЛЕР: 1. 1 Диспетчерлік автоматтандырылған жүйелерде қолданылатын алгоритмдердің сипаттамасы . . .
: 9
НОРМАТИВТІ СІЛТЕМЕЛЕР: 1. 2 Диспетчерлік автоматтандырылған жүйелердің оңтайландыру моделін жобалау . . .
: 14
НОРМАТИВТІ СІЛТЕМЕЛЕР:
:
НОРМАТИВТІ СІЛТЕМЕЛЕР: 2 Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыру моделін жүзеге асыру . . .
: 19
НОРМАТИВТІ СІЛТЕМЕЛЕР: 2. 1 Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыру модельдің құрылымы . . .
: 19
НОРМАТИВТІ СІЛТЕМЕЛЕР: 2. 2 Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыру модельді іске асыру және тестілеу . . .
: 30
НОРМАТИВТІ СІЛТЕМЕЛЕР: ҚОРЫТЫНДЫ . . .
: 48
НОРМАТИВТІ СІЛТЕМЕЛЕР: ҚОЛДАНЫЛҒАН ӘДЕБИЕТТЕР ТІЗІМІ . . .
: 49
НОРМАТИВТІ СІЛТЕМЕЛЕР: РЕФЕРАТ . . .
: 51
НОРМАТИВТІ СІЛТЕМЕЛЕР: ҚОСЫМША . . .
: 55
НОРМАТИВТІ СІЛТЕМЕЛЕР

«Ақпараттандыру туралы» 2015 жылғы 24 қарашадағы №418-V ҚРЗ.

ҚР СТ 34. 014-2002. Ақпараттық технология. Автоматтандырылған жүйелерге арналған стандарттар кешені. Автоматтандырылған жүйелер. Терминдер мен анықтамалар.

ҚР СТ 34. 005-2002. Ақпараттық технология. Негізгі терминдер мен анықтамалар.

ҚР СТ 34. 019-2005. (ISO / IEC 12207: 1995, MOD) Ақпараттық технология. Бағдарламалық құралдардың өмірлік циклінің процестері.

ҚР СТ ISO/IEC TR 24776-2012 (ISO / IEC TR 24776:2009, IDT) . Ақпараттық технологиялар. Жүйелер мен бағдарламалық қамтамасыз етуді әзірлеу. Инженерлік құралдың мүмкіндіктеріне қойылатын талаптар бойынша нұсқаулық.

Қазақстан Республикасының Қаулысы. 2017 жылғы 12 желтоқсандағы «Цифрлық Қазақстан, №827» Мемлекеттік бағдарламасы.

«Қазақстан Республикасы көлік жүйесінің инфрақұрылымын дамытудың және ықпалдастырудың 2020 жылға дейінгі мемлекеттік бағдарламасы және «Мемлекеттік бағдарламалар тізбесін бекіту туралы» Қазақстан Республикасы Президентінің 2010 жылғы 19 наурыздағы № 957 Жарлығына толықтыру енгізу туралы" Қазақстан Республикасының Президенті Жарлығының жобасы туралы Қазақстан Республикасы Үкіметінің 2013 жылғы 29 қарашадағы № 1263 қаулысы.

Қазақстан Республикасы Президентінің Жарлығы. «Ақпараттық Қазақстан-2020» мемлекеттік бағдарламасы: бекітілген. 2013 жылғы 8 қаңтар, №464.

АНЫҚТАМАЛАР

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

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

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

ТЕРМИНДЕР МЕН ҚЫСҚАРТУЛАР

АЖ - ақпараттық жүйе;

ИТӘ - иерархияларды талдау әдісі;

КИ - келісімділік индексі;

ТТ - техникалық тапсырма;

ДҚБЖ - деректер қорын басқару жүйесі;

МОЫПМ - Маршрутты оңтайландыру ықтималдығының пайыздық мәні.

КІРІСПЕ

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

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

Тақырыптың зерттелу және ғылыми әзірлену дәрежесі. Жұмысты орындау барысында диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыру мәселесімен айналысқан келесі авторлардың еңбектері қарастырылды, олар Li X., Zhang Y., Zhou D. [1], Wang J., Tian Y., Zhang Y., Wu W., Shen Z. [2], M. Frank, M. Ostermeier, A. Holzapfel, A. Hübner, H. Kuhn [3], Koutsandria G., Markakis E., Papavassiliou S. [4], Крутолапов А. С. [5] және т. б.

Зерттеу нысаны: Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасу қызметі.

Зерттеу пәні: Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды жетілдіру.

Жұмыстың мақсаты: Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыру моделін әзірлеу және жүзеге асыру болып табылады.

Жұмыстың міндеттері :

  • Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды жүзеге асырудың алгоритмдерін зерттеу;
  • Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасудың алгоритмдерін талдау және салыстыру;
  • Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды жүзеге асырудың моделін әзірлеу;
  • Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды жүзеге асырудың моделін жүзеге асыру және тестілеу.

Ғылыми жаңалығы:

  • диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасудың моделін әзірленді;
  • диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыру программасы құрылды.

Қорғауға ұсынылатын қағидалар:

  • диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасудың моделі;
  • диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыруды іске асыру үшін құрылған программасының іске асырылуы.

Теориялық маңыздылығы: жұмыс барысында жүргізілген теориялық зерттеулер мен талдаулардың қорытындылары болашақ жұмыстың негізін құра алады.

Практикалық маңыздылығы: жұмыс автоматтандырылған жүйелерді диспетчерлеуде ақпарат алмасуды жүзеге асырудың моделін зерттеуді қарастырады, сонымен қатар ұзақ мерзімді даму арқылы толық логистикада ақпараттық жүйенің құралы ретінде қолданыла алады.

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

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

Бірінші тарауда автоматтандырылған жүйелерді беру кезінде ақпарат алмасу алгоритмдерінің шарттары анықталған. Автоматтандырылған жүйені беру кезінде ақпарат алмасу алгоритмдерін талдау, Vol. is б . Эвристикалық әдістердің сипаттамасы, толық артық әдіс, ашкөздік алгоритмі, кездейсоқ артық әдіс, тереңдікті шектеу әдісі, Sati әдісі талданады.

Екінші тарауда диспетчерлік автоматтандырылған жүйелерде ақпарат алмасу реформасын жүзеге асыру қарастырылады: диспетчерлік автоматтандырылған жүйелерде ақпарат алмасу моделін қалыптастыру; диспетчерлік автоматтандырылған жүйелерде ақпарат алмасу моделіне негізделген бағдарламалық жасақтама жасау.

1 Диспетчерлік автоматтандырылған жүйелерде ақпараттық алмасуды оңтайландыру моделін әзірлеудің алғышарттары

1. 1 Диспетчерлік автоматтандырылған жүйелерде қолданылатын алгоритмдердің сипаттамасы

Нақты жобаның міндеті - Қазақстан қалалары арасында және қала ішіндегі тауарлық материалдық құндылықтар тасымалдау қозғалысының математикалық моделін жасау.

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

Сондықтан бірнеше түрлі көліктерден тұратын жолдың қанша және қандай учаскелерінде ең аз қозғалыс уақыты тұрғысынан оңтайлы болатындай етіп тоқтауы керек екенін анықтау қажет.

Ұқсас мәселелерді шешу, көбінесе логистикалық тапсырманың көмегімен қолданылады.

Логистика мәселесі деп аталатын математикалық модель экономика саласында кеңінен қолданылады. Оқу және ғылым әдебиеттерінде тауар жеткізу мәселесін шешу көп жағдайда Гамильтон циклін іздеуді білдіреді. Бірақ бұл екі тапсырма жалпы алғанда, екі түрлі болып табылады. Гамильтон циклін іздеу тек тапсырма шарттарына елеулі шектеулер болған жағдайда ғана шешімі табылады. Басқаша жағдайда бұл қатеге әкеліп соқтыруы мүмкін. Сатушының міндетін Гамильтон циклін іздеуге азайту шарттары келтірілген және осы шарттар орындалмаған жағдайда шешім алгоритміне қосымша қадамдар енгізу қажеттілігі көрсетілген [6] .

Экономикалық және басқарушылық есептерді шешу үшін математикалық әдістерді қолданған кезеңінде маңызды кезең болып қолайлы математикалық модельді таңдау немесе құру болып табылады, бір жағынан - қойылған тапсырмаға сәйкес, екінші жағынан - қажетті қиындық деңгейіне ие. Кеңінен қолданылатын математикалық модельдердің бірі - оңтайландыру міндеті, онда мақсатты функция әр түрлі «Қалалар» арасында қозғалудың «Құны» болып табылады және шешу әдістері жақсы зерттеліп барлық экономикалық бағыттағы студенттердің оқу жоспарына енеді. Дегенмен, дайын шешім алгоритмдерін пайдаланудан сақ болу керек, себебі модель жасау кезінде ресімдеу қателерін байқау есептеу қателерін байқаудан қиын болып саналады. Төменде практикалық басқару міндеттерін шешу кезінде орындалуы керек шарттар егжей-тегжейлі қарастырылады [7-8] .

Классикалық есептің сипаттамасы. Диспетчер міндеті - біріктіру, оңтайландыру. Жүргізуші өзі үшін ең аз шығындармен N қалаларды айналып өтуі керек. Классикалық қойылымда қалалар арасындағы қашықтықты, көшу құнын немесе жұмсалған уақытты шығындар ретінде қарастыруға болады. Барлық қалалар арасында қозғалу үшін шығындар мәндерін біле отырып, сіз тарифтік пішін (төлем пішіні, шығындар пішіні) деп аталатын пішін құра аласыз c = (cij), i қаладан j қаласына ауысудың «Мәндерінен» тұрады. Азайтуды қажет ететін мақсатты функция келесідей:

Изображение выглядит как текст Автоматически созданное описание

(1)

Xij = 1 айнымалысы, егер жүргізушінің жалпы жолында i қаладан j қаласына дейінгі жол болса және Xij = 0 керіс жағдайда [9-10] .

Классикалық қойылымдағы мәселені шешу және оның кемшіліктеріне тоқталып кетейік. Тек шағын қашықтық үшін N шешімді шамадан тыс табуға болады, қалалар саны бірнеше ондағанға дейін ұлғайған кезде шешім өте көп еңбекті қажет етіп, кез-келген заманауи компьютерге қол жетімді емес, оның себебі - диспетчер міндеті толық тапсырмалар класына кіреді. NP. Математиктер жүргізуші мәселесін ең қысқа деп Гамильтон циклін табу арқылы шешуді ұсынды, яғни мұндай цикл, әр қалаға дәл бір рет барып бірнеше рет бару тиімсіз. Мұны оңай түсіндіруге болады, себебі қаладан қалаға дейінгі жол әрдайым басқа қаладан өтетін жолға қарағанда қысқа. Ең қысқа маршрутты іздеу қаладан қалаға дәл N қозғалысынан тұратын маршрутты іздеуге дейін азаяды. Мұндай мәселені дереу шешуге болады. Өткен ғасырдың екінші жартысында динамикалық программалау әдістері, сызықтық және алгоритмдік тұрғыдан ең тиімді әдістердің бірі болып табылатын филиалдар мен шекаралар әдісі пайда болды [11] . Бұл әдістердің барлығы оқу әдебиеттерінде сипатталған, тек шектеулі қолданысқа ие, себебі олар тек метрикалық есепті шығаруға жарамды. Егер қалалар арасындағы қашықтықты қарастыратын болсақ, онда С матрицасының элементтері үшін үшбұрыштың теңсіздігі әрдайым орындалатыны анық. Бірақ метрикалық шарт (үшбұрыштың теңсіздігін орындау), қашықтық емес, қаладан қалаға көшу құны CL1 ретінде қарастырылса, орындалмауы мүмкін, сонымен қатар олар әртүрлі көлік түрлерін таңдау мүмкіндігіне байланысты бұзылады. Егер аталған шарттар орындалмаса мәселені басқа жолмен шешу керек немесе оны метрикалық ету үшін тарифтік матрицаның кейбір түрлендірулерін жүргізу керек. Алайда, көбінесе оқулық авторлары Гамильтон циклін қолданудың шектеулілігі туралы ештеңе жазбайды, сонымен қатар оқу материалдарында Гамильтон циклін жауап ретінде табудың мысалдарын көруге болады және бұл жауап оңтайлы емес.

Толық шамадан тыс (немесе «Дөрекі күш» әдісі, ағылш. brute force) - математикалық есептерді шешу әдісі. Ол барлық нұсқаларды жан-жақты шешуді іздеу әдістерінің класына жатады. Толық таңдаудың қиындығы мәселенің барлық мүмкін шешімдерінің санына байланысты. Егер шешімдер кеңістігі өте үлкен болса, онда толық шамадан тыс бірнеше жыл немесе тіпті ғасырлар бойы нәтиже бермеуі мүмкін. NP санабындағы кез-келген тапсырманы толық шамадан тыс шешуге болады. Сонымен қатар, есептің әрбір нақты мүмкін шешімінен мақсатты функцияны есептеу барлық мүмкін шешімдердің санына байланысты көпмүшелік уақытта жүзеге асырылуы мүмкін болса да, толық шамадан тыс жұмыс экспоненциалды жұмыс уақытын қажет етуі мүмкін. Толық шамадан тыс екі программалық жасақтама мүмкін. Біріншісі - графиктің барлық шыңдарын рекурсивті айналып өту және әр шың үшін оған іргелес барлық ықтимал бояу нұсқалары жатады.

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

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

Берілген G графигінде екі іргелес емес шыңдарды таңдап, екі жаңа график құрайық: G графигіне жиек қосу арқылы алынған және X және У шыңдарын біріктіру арқылы G-ден алынған. Х, У шыңдарының кем дегенде біреуі іргелес.

Егер G графигінің дұрыс бояуында X және У шыңдары әртүрлі түстерге ие болса, онда ол график үшін де дұрыс болады . Егер G графигінің бояуындағы X және У шыңдарының түстері бірдей болса, онда графикті түстердің бірдей санына бояуға болады: жаңа Z шыңы X және У шыңдары боялған түске боялады, ал қалған шыңдар G графигіндегі түстерді сақтайды және керісінше, графиктердің әрқайсысының бояуы G графигін түстердің бірдей санына бояйтыны анық. Сондықтан, бұл графиктің бояуын түстердің минималды санына рекурсивті түрде табуға мүмкіндік береді. Графиктің бастапқы графикпен бірдей шыңдары бар екенін ескеріңіз, бірақ оның шеттері көп. Сондықтан рекурсия, соңына келгенде, толық графиктерге әкелінеді, және олар үшін бояу мәселесі тривиальды түрде шешіледі.

Ашкөз алгоритм - хроматикалық санға жақын бағытталмаған графиктің бояуын табудың ең қарапайым әдісі болып келеді [12] . Ашкөз алгоритм G графигінің барлық Х шыңдарын мүмкіндігінше минималды түске дәйекті түрде бояудан тұрады, егер берілген шыңға іргелес бірде-бір шың осы түске боялмаған болса. Графикті минималды бояу мәселесі үшін аталған әдіс оңтайлы шешімді табуға кепілдік бермейді. Әдістің уақыттық күрделілігі - O (N) бағанындағы шыңдар санына (N) қатысты сызықтық болып табылады. Ең жылдам болғандықтан, бұл әдіс оңтайлы нәтижеден алыс нәтиже бере алады (онда графиктің бояуы минималды болады) . Ашкөзді алгоритм v_1 v_n шыңдарын реттейді және v_i шыңына v_i V_(i-1) көршілерін бояу үшін пайдаланылмаған ең кіші қол жетімді түсті дәйекті түрде тағайындайды немесе жаңасын қосады. Алынған бояу парағының сапасы таңдалған тәртіпке байланысты. Әрқашан ашкөз алгоритмді (_X^) (G) түстердің оңтайлы санына әкелетін тәртіп бар. Екінші жағынан, ашкөзді алгоритм қалағаныңызша нашар болуы мүмкін; мысалы, n шыңдары бар тәжді 2 түспен бояуға болады, бірақ N/2 түстің ашкөзді бояуына әкелетін шыңдардың реті бар.

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

Ашкөздік алгоритмі оңтайлы бояуды қамтамасыз етпейтіндіктен, ашкөздік алгоритмі арқылы алынған нәтижелерді оңтайлыға жақындату үшін Графиктерді Шың градустары бойынша дәйекті бояуды ұйымдастыру үшін әртүрлі стратегиялар қолданылады. Мысалы, ең қисық (және іргелес) шыңдарды табу стратегиясы алдымен боялған. Тағы бір стратегия - графиктің барлық шыңдарын олардың дәрежелерінің өспеуі және кейіннен бояуы бойынша алдын-ала сұрыптау. Мұндай алгоритмнің есептеу күрделілігі ашкөз іздеудің басқа әдістеріне қарағанда үлкен, себебі графиктің шыңдарын алдын-ала сұрыптау қажет. 2. 2-суретте шыңдарды ашкөзді алгоритммен бояудың реттілігі көрсетілген. 2. 3-суретте ашкөзді алгоритммен хроматикалық санды іздеу кезінде шыңдардың бояу тізбегі көрсетілген.

C:\Users\Astarel\Desktop\институт\1 семестр\УИРС\презентация\Жадный алгоритм\GreedyRandom.bmp

Сурет 1. Графиктің шыңдарын ашкөзді алгоритммен бояу реті

C:\Users\Astarel\Desktop\институт\1 семестр\УИРС\презентация\Сортировка по невозрастанию дуг\по кадрам слои\перебор_0017_3.bmp

Сурет 2. Ашкөзді алгоритмнің рекурсивті вариациясы арқылы хроматикалық санды іздеу кезінде шыңдарды бояудың реттілігінің мысалы

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

Әдістердің ең қарапайымында шыңдар алдымен олардың дәрежелерінің өспеу ретімен орналасады.

Бірінші шың 1 түске боялған; содан кейін шыңдар тізімі жоғарыдан төменге қарай қаралады (дәрежелердің өспеуі бойынша) және 1-ші түс осы түске боялған басқа шыңға іргелес емес кез-келген шыңды бояйды. Содан соң тізімдегі бірінші боялмаған шыңға ораламыз, оны 2-ші түске бояп шыңдар тізімін жоғарыдан төмен қарай қайта қараймыз, 2-ші түске боялмаған кез-келген боялмаған шыңды 2-ші түске боялған басқа шыңмен байланыстырамыз. Сол сияқты, барлық шыңдар боялғанша 3, 4 және т. б. түстермен әрекет етеміз. Пайдаланылған түстер саны графиктің хроматикалық санының шамамен мәні болады.

Кездейсоқ сұрыптау әдісі графикті бояудың (Z) нұсқаларының берілген санын ерікті түрде сұрыптау және олардың ішінен ең оңтайлы таңдау болып табылады. 2. 3-суретте кездейсоқ шамадан тыс жұмыс әдісінің мысалы келтірілген [9] . Алгоритмнің күрделілігі: O (Z) .

Сурет 3. Кездейсоқ шамадан тыс жұмыс әдісінің мысалы

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

1. Бастапқы күйге сәйкес келетін бастапқы шың ашылады.

2. Бастапқы шыңның ашылуы нәтижесінде алынған бірінші шың ашылады. Көрсеткіш қойылады.

3. Егер ол ашылса, келесі жаңадан пайда болған шың ашылады. Егер шың ашылмаса, онда үдеріс алдыңғы шыңға оралады.

4. Мақсат еткен шыңды алғаннан кейін ашу процесі аяқталып белгілерге сәйкес тамырға апаратын жол салынады. Доғаларға сәйкес келетін операторлар есептің шешімін құрайды.

5. Егер берілген ашылу тереңдігі үшін мақсат етілген шың табылмаса, онда барлық үдеріс қайтадан қайталанады, ал алдыңғы кезеңде алынған ең сол жақ жаңа шың ретінде қарастырылады.

1. 2 Диспетчерлік автоматтандырылған жүйелердің оңтайландыру моделін жобалау

Ақпараттық жүйенің өмірлік циклі, Әдетте, Ақпараттық жүйені пайдаланудың барлық компоненттерінің тұтастығы мен үздіксіздігін қамтамасыз ету үшін қажетті шаралар тізімі болып саналады [13-14] .

... жалғасы

Сіз бұл жұмысты біздің қосымшамыз арқылы толығымен тегін көре аласыз.
Ұқсас жұмыстар
Технологиялық процесстің автоматтандырылған басқару жүйесінің қызметі берілген басқарудың мақсаттардың орындалуына қол жеткізу
Сорғы станцияның сорғы агрегаттары
Техналогиялық процестер құрамын басқару
Геоақпарат жүйелері бойынша дәрістер
Телім жолы бой
Жылу энергиясының шығынын есептеу
Тұрғын үй - коммуналдық шаруашылықтағы жылу пунктін TIA Portal программалық қамтамасы негізінде сымды байланысы бар үлестірілген өндірістік желіні құрастыру және зерттеу мәселелері
Автобус маршрутының жалпы сипаттамасы
ТПБАЖ және диспетчерлік басқару
Робот манипуляторын жинақтау
Пәндер



Реферат Курстық жұмыс Диплом Материал Диссертация Практика Презентация Сабақ жоспары Мақал-мәтелдер 1‑10 бет 11‑20 бет 21‑30 бет 31‑60 бет 61+ бет Негізгі Бет саны Қосымша Іздеу Ештеңе табылмады :( Соңғы қаралған жұмыстар Қаралған жұмыстар табылмады Тапсырыс Антиплагиат Қаралған жұмыстар kz