Граф тиімділік есептерін шешу әдістерінің алгоритмдері мен программалары

Пән: Информатика, Программалау, Мәліметтер қоры
Жұмыс түрі: Дипломдық жұмыс
Тегін: Антиплагиат
Көлемі: 45 бет
Таңдаулыға:

Қазақстан Республикасы Білім және Ғылым Министрлігі

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

Жаратылыстану факультеті

Информатика кафедрасы

Тақырыбы: Граф тиімділік есептерін шешу әдістерінің алгоритмдері мен программалары

Диплом жұмысы Орындаған: Муса. А. О.

Кафедра мәжілісінде талқыланып, 010540 «информатика»

қорғауға жіберілді мамандығының 4-курс студенті

Хаттама № «» 2006 ж Ғылыми жетекшісі : аға оқытушы

Кафедра меңгерушісі Ж. И. Ахатова

Г. И. Салғараева

Алматы 2006

Мазмұны

Кіріспе

I - ТАРАУ Граф теориясының негізгі түсініктері

1. 1. Графтағы алгоритмдер

1. 2. Графты көрсетудегі мәліметтер құрылымы

1. 3. Графикалық торлар

II - ТАРАУ Borland Delphi ортасында сыртқы функциялар құру және оны

MS Excel ортасында қолдану

2. 1. Delphi ортасында DLL құруға арналған жаңа проектінің терезесі

2. 2. MS Excel көмегімен бағытталған графика минималды жол

туралы есепті шешу

2. 3. Дискретті және комбинаторлық тиімділеу есебі

2. 4. Дейкстер белгілеу алгоритмі көмегімен графта минимальды жол

туралы есепті шешу

Қортынды

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

Қосымша

КІРІСПЕ

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

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

Ғылыми заңдарға байланыс жасалған гипотезалардың бірнеше түрі болады. Олар эприкалық, теориялық, құрылмдық, статикалық, динамикалық, санды және сапалы болып бөлінеді.

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

Саңды заңдар, математикалық формуламен теңдіктер тілінде тұжұрымдалады. Формальды математика аппаратты қолданған саңды заңдар болжаманаң жоғары дәлдігіне жетуге мүмкіңдік береді.

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

Жоғары деңгейлі тілдер адамның көру-есту (аудио-видио) сезімімен қабылдануына ыңғайлы.

Жоғары деңгейлі тілдер үлкен ұйымдар арқылы (мысалға, ANSI (Америка ұлттық стандарттар институты) ) стандартқа келтрілген. Мұндай стандарттау, тілдерді бір - бірне тасымалдауды жеңілдетеді. Жоғары деңгейлі тілдер қатарына FORTRAN, COBOL, PASCAL және т. б. жатады.

Қазіргі күнде компьютер әлемінде бағдарламалау тілдерінің саң алуан түрлері бар. Нақтылы амалды жасайтын бағдарламаны түрлі тілде жазуға болады: Visual Basic-VBA, Delphi 7, C++.

Visual Basic -VBA бағдарламалау тілін және орта ретінде пайдалануға (Visual Basic-VBA) Microsoft жүйесіне еңген Word, Excel, Power Point немсе Access қосымшалар арқылы қолданылады.

PASCAL бағдарламалау тілі сәтт болғаны соңдай, оның пайда болуынан бастап қысқа мерзім ішінде түрлі фирмалар сан алуан компилятор жасап үлгерді. Солардың ішінде ең тиімдісі болып Borland американдық фирмасы жасаған мәтн редакторы мен жоғары нәтижелі компилятор қосылған Turbo PASCAL жүйесі есептелінеді. Мұнда қолданылатын бағдарламалау тілі де осы есімге ие болды.

Есептегіш техника мен бағдарламалау техналогиясының дамуы жаңа бағдарлама өнімдерінің пайда болуына әкеледі. Осы Borland фирмасы жасаған Delphi деп аталатын өнім Windows ұстанымында жұмыс істеуге бағытталған бағдарламалар жасау ортасы.

Бағдарламаны Delphi ортасында ұсыну үшін негізгі айқын Turbo PASCAL тілімен саласы Borland фирмасы жасаған Object Pacal тілін пайдаланады. “Object” деген сөз бұл тілі объектте бағытталған бағдарламалау концепцияын қолдайтынына ерекше назар аударады.

Негізгі диплом жұмысымда қарастырғаным MS Excel - де қолданылатын ең минимальді жолды табатын фугкцияны Borland Delphi - де жасауы.

Мысал ретнде қарастырғаным Borland Delphi 7 ортасында жасалып MS Excel ортасында сәйкес қолданылатын бағытталған графтағы минимальды жолды табатын функцияны қарастырдым, сонымен қатар Visual Basic-VBA ортасында да қарастырылған мысал келтірілген.

1. 1. Граф теориясының негізгі түсініктері

Формальдық көзкарас бойынша граф G=(V, E) жиындарының реттелген жұбы, олардың біріншісі төбеле мен түйіндерден тұрады, ал екіншісі - олардың қабырғаларынан. Қабырға екі төбені қосады. Біз графтармен жұмыс істеген кезде, графтың бір төбесінен екінші төбесіне қабырғалардан тұратын жолды қалай жүргізу керектігі жиі қызықтырады. Сондықтан біз қабырға бойымен қозғалысты айтқан кезде, біз АВ қабырғасымен қосылған А төбесінен басқа В төбесіне өті деп түсінеміз. Осы жағдайда біз төбесі В төбесі көрші бір бірімен түйіседі деп айтамыз.

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

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

1 суретінде бағдарланған (а) және бағдарланбаған (б) графтар олардың формалдық сипаттамасымен бірге көрсетілген.

Терминология

Толық граф - бұл әр төбе басқа төбелермен түгел қосылған граф. N төбесі бар толық графтағы қабырғалар саны (тұзақсыз)

(N ² -N) /2 тең. Толық бағдарланған графта бір төбеден екінші кез келген төбеге өту рұқсат етіледі. Графта қабырғалар бойынша өту екі бағытта да рұқсат етілгендіктен, ал орграфта тек бір бағытта болғандықтан, толық орграфта қабырға саны екі есе көп немесе олар саны (N ² -N) тең.

Графтың (V _s , E _s ) ішкі графы әлде (V, E) орграфы V _s ⊆V ішкі жиыннан және оларды қосатын қабырғалардың кейбір ішкі жиынан E _s ⊆E тұрады.

Графтағы әлде орграфтағы жол дегеніміз кезекпен өтетін қабырғалар қатары.

Басқаша айтқанда А төбесі В төбесіне дейінгі жол А-дан басталып В төбесіне жеткенге дейінгі қабырғалар тізбегімен өтеді. Формалдық көзқарас бойынша U _i төбесінен U _j төбесіне дейінгі жол бұл графтың U _i U _j +1, U _i+1 U _j+2 …U _j-1 U _j қабырғалар тізбегі. Сонымен қатар, осы жолда кез келген төбе бір реттен артық кездеспеуін талап етемыз. Кез келген жолдың ұзындығы - олардағы қабырғалар саны AB, BC, CD, DE жолының ұзындығы 4-ке тең.

Көтеріңкі графта әлде орграфта әр қабырғаға қабырға салмағы деп аталатын сан бекітілген. Графты бейнелеу барысында қабырға жанына қабырға салмағын жазамыз. Формалды сипаттау кезінде салмақ реттелген әлде реттелмеген төбелер жұбына қосымша элемент болады. Бағдарланған графтармен жұмыс істеген кезде қабырға салмағын онымен өту бағасы деп санаймыз. Көтеріңкі графта жол құны бүкіл жолдағы қабырғалар салмағының қосындысына тең. Көтеріңкі графтағы ең төте жол - қабырғалар салмағы ең төмен жол, тіпті жолдағы қабырғалар сан азайса да. Мысалы, егер P ₁ жолы жалпы салмағы 24 болатын бес қабырғадан тұрса, ал P ₂ жолы - жалпы салмағы 36 болатын үш қабырғадан болса, онда P ₁ жолы қысқалау деп саналады.

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

1. 2. Графтағы алгоритмдер

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

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

Кейде кейбір ақпаратты көп адамдар топтарына әлде үлкен желідегі барлық компьютерлерге таратуға тура келеді. Біз ақпараттың топтық әр мүшщесіне жеткенін қалаймыз, бірақ сонымен қатар тек бір рет қана. Осы мақсатта кейбір топтарда “телефондық шежіре” ұйымдастырылады: бұл жағдайда тың жаңалық алған топ мүшесі, оны қатысушылардың аз мөлшеріне хабарлайды. Егер шежіреде топтың әр мүшесі бір рет ғана кездессе, онда шежіре биіктігі үлкен емес және ақпарат барлығына тез жетеді. Ал жалпы көріністі графларда жағдай күрделірек, себебі орталау графтарда шежіреге қарағанда байланыс әлдеқайда көбірек. Осы қиындықты шешу мақсатында біз графтарды аралаудың екі әдісін үйренеміз: тереңдікке және деңгейлер бойынша.

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

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

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

1. 3. Графты көрсетудегі мәліметтер құрылымы

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

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

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

Матрица мен түйісу тізімін пайдалану келесі бөлімдерде жан-жақты жазылған.

Түйісу матрицалары.

G= (V, E) Графының [V] =N төбе саны бар AdyMat түйісу матрицасы NxN көлемді екі өлшемді массив түрінде жазылады. Осы массивтің әр [i, j] ұяшығында 0 мәні жазылады, бұл тек егер U _i төбесінен U _j төбесіне қабырға жүргенде сонда ұяшықта 1 мәні жазылған жағдайлардан басқа сәттерде ғана. Дәлірек айтқанда:

барлық i мен j 1 ден N ге дейін

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

Түйісу тізімі

[V] =N саны бар G=(V, E) графының Adibist түйісу тізімі ұзындығы N бір өлшемді массив түрінде жазылады. Соның әр элементы тізімге сілтеме түрінде болады. Осындай тізім графтың әр төбесіне бекітілген және ол графтың осы төбесімен көрші әр төбесіне бір-бірден элемент ұстайды.

6. 3 суретінде 6. 1 суретіндегі граф пен орграфтың түйісу тізімін бейнелейді. Көтеріңкі графтың түйісу тізімінің элементі құрамында қабырға салмағын сақтайтын қосымша алаң бар.

Тереңдікке және деңгейлерді аралау алгоритмі

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

Осындай аралауды екі әртүрлі тәсілмен істеуге болады. Тереңдікті аралау кезінде таңдалған жолмен өту барша мүмкін тереңдікке дейін іске асырылады, ал деңгейлер бойынша аралауда біз барша мүмкіндік бар бағыттарда бірқалыпты қозғаламыз. Енді осы екі тәсілді жанжақты қарайық. Екі жағдайда да біз басталу нүктесі ретінде графтың бір төбесін таңдаймыз. Төменде «түйінге кіру» деп әрбір төбеде істеуге қажет әрекеттерді орындау деп түсінмезі. Мысалы, егер іздеу жүріп жатқанда, біз осы түйінге кірдік деген сөз, біз онда керекті ақпарат барлығын тексердік деген сөз. Аталған әдістер еш өзгеріссіз бағдарланған, сондай-ақ бағдарланбаған графтарда жұмыс істей береді. Біз оларды бағдарланбаған графтар арқылы көрсетеміз.

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

Тереңдікке аралау

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

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

Осы және басқа алгоритмдарды көрсеткенде, екі төбеден біреуінен таңдауда, біз әрқашан кішілеу белгісі бар төбені таңдаймыз. Алгоритмді іске асыру кезінде таңдау графтың қабырғаларын сақтау тәсілі таңдау түрін белгілейді. 6. 4 суретіндегі графты қарайық. Бір төбеден тереңдікке аралауды бастап, біз одан кейін 2, 3, 4, 5, 6 төбелерінде болып, тұыққа тірелеміз. Одан кейін 7 төбесіне қайтуға тура келеді, онда біз 8 төбені шолмағымыз анықталады. Бірақ осы төбеден өтіп, біз бірден тағы да тұыққа тірелеміз. 4 төбеге қайтқанда біз 9 төбенің шолынбау қалғанын көреміз, енді оған бару бізді тағы да тұйыққа әкеледі. Бүкіл көрші төбелер түгел шолығандықтан біз қайтадан бастапқы нүктеге қайтамыз; аралау осымен аяқталады

1. 4. Графикалық торлар

Графикалық торлар-бұл техника мен ұйымдастыру жүйелерді графика арқылы көрсету әдісі. Ғылыми жұмыстарды графикамен көркемдеу нақты мәнін көрнекілігімен көрсетеді, кей жағдайда қойылған міндеттің шешімін табуды тіпті жеңілдетеді. Әр түрлі көрнекілікті графикамен көрсетудің әмбебап құралы ретінде граф табылады. Мұнда граф деп, торап пен қырлардың жиынтығын түсінеді. (1-сурет) . Түрлі торап пен қабырғалардың сан алуан құрамалары, мүмкін болатын графтар мен олардың қолдану жолдарын көрсетеді. Қабырға бағыттары көрсетілмеген, ал тораптар төртбұрыш түріне келтірілген графтар техникалық жүйелердің құрылымын көрсетуге қолданылатын блоксхемаларды суреттейді. 1-суретте көрсетілген графты ағаш деп атайды. Мұндай ағаш-граф арқылы толық санды бағдарламалау міндетін қарастыратын бұтақтар мен шекаралар әдісін қөркемдейді. Егер ағаштағы баоылық тораптар бірнеше деңгейге бөлінсе, онда оны көп деңгейлі иерархия жүйесі деп білеміз. Егер граф қабырғасы бағытқа ие болса, яғни доға арқылы жүзеге асса, ондай графты тор деп атайды. Тор арқылы орын ауыстыру немесе уақыт бойында орындалатын жұмыстардың тиімді шешімін табудың түрлі міндеттері көрсетіледі. Тор доғалардың құрылым мен параметрлері сипатталады. Тор құрылымы, немесе оны топология деп атайды, байланысшы доғалардың юағытын және тораптарын өзара қалай байланысатынын көрсетеді. Әрбір торапты реттік санмен белгілейді. Бастапқы торапты бастау деп, ал соңғысын ағаш деп атайды.

1- сурет

Доғаны қосарланған индекспен белгілеиді. Жалпы i-j деп көрсетеді, онда i доға шығатын тораптың нөмеірі, j-доға кіретін торап нөмірі деп қабылданады. Әрбір доға өз сипатына ие болады. Мысалы, t _i - j доға бойымен қозғалу мерізімі, c _i -j- орын ауыстыру құны, d _i -j доғаның өткізу қабілеті, т. б.

2 - сурет

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