1. 1Жиын ұғымы. Шекті және шексіз жиындар. Жиындарды анықтау тәсілдері.Ішкі жиындар. Берілген жиынның барлық жиынтығы. К- элемент жиындарының саны туралы n- элемент жиынтығы
жүктеу/скачать 336,61 Kb.
|
| Форд-Беллман Алгоритмі.
Беллман-Форд алгоритмі салмақты графиктегі ең қысқа жолды табуға арналған алгоритм болып табылады. кезінде О ( | В | ⋅ | Е | ) {\displaystyle O(|V|\cdot |E|)} алгоритмі бір график төбесінен барлық басқаларына дейінгі ең қысқа жолдарды табады. Дейкстра алгоритмінен айырмашылығы, Беллман-Форд алгоритмі теріс салмағы бар жиектерге мүмкіндік береді. Ричард Беллман және Лестер Форд тәуелсіз түрде ұсынған. Сириус ұнатады. Бағытталған немесе бағытталмаған график берілген Г Салмақталған жиектері бар G. Жолдың ұзындығы - бұл жолға кіретін жиектер салмағының қосындысы. Таңдалған шыңнан ең қысқа жолдарды табу қажет с s барлық график шыңдарына. Ең қысқа жолдар болмауы мүмкін екенін ескеріңіз. Сонымен, теріс жиынтық салмағы бар циклді қамтитын графикте осы циклдің бір шыңынан екіншісіне ерікті түрде қысқа жол бар (циклдің әрбір айналымы жолдың ұзындығын азайтады). Шетінің салмағының қосындысы теріс болатын цикл теріс цикл деп аталады. Берілген есепті сызба бойынша шешейік, онда теріс циклдар анық емес. Бір шыңнан барлық басқа шыңдарға ең қысқа жолдарды табу үшін біз динамикалық бағдарламалау әдісін қолданамыз. Матрицаны құрастырайық А мен j A_{{ij}}, оның элементтері келесіні көрсетеді: а мен j a_{{ij}} - ең қысқа жолдың ұзындығы с s in мен Мен ең көп қамтиды j j жиектері. 0 жиегі бар жол тек шыңға дейін бар с с. Осылайша, А мен 0 {\displaystyle A_{i0}} болғанда 0 болады мен = с {\displaystyle i=s}, және + ∞ +\infty басқаша. Енді барлық жолдарды қарастырыңыз с s in мен Мен дәл қамтиды j j жиектері. Әрбір осындай жол бір жол j − бір j-1 соңғы жиегі қосылған жиек. Ұзындық жолдары туралы болса j − бір j-1 барлық деректер есептелген, содан кейін анықтаңыз j матрицаның j-ші бағаны қиын емес. Беллман-Форд алгоритмі графикте бар-жоғын анықтауды жеңілдетеді Г G - шыңнан жетуге болатын теріс цикл с с. Циклдің сыртқы итерациясын жасау жеткілікті емес | В | − бір |V|-1, дәл | В | |V| бір рет. Егер соңғы итерацияны орындау кезінде кез келген шыңға ең қысқа жолдың ұзындығы қатаң түрде азайса, онда графикте теріс цикл болады, оған дейін жетуге болады. с с. Осыған сүйене отырып, біз келесі оңтайландыруды ұсына аламыз: графиктегі өзгерістерді қадағалаңыз және олар аяқтала салысымен циклден шығыңыз (бұдан әрі итерациялар мағынасыз болады). n төбелері мен m шеттері бар бағытталған өлшенген G графы берілсін және кейбір v төбесі көрсетілсін. v төбесінен барлық басқа төбелерге дейінгі ең қысқа жолдардың ұзындықтарын табу қажет. Дейкстра алгоритмінен айырмашылығы, бұл алгоритм теріс салмақты жиектері бар графиктерге де қолданылады. Алайда, егер графикте теріс цикл болса, онда, әрине, кейбір шыңдарға апаратын ең қысқа жол болмауы мүмкін (ең қысқа жолдың салмағы минус шексіздікке тең болуы керек болғандықтан); дегенмен, бұл алгоритмді теріс салмақ циклінің болуын көрсету үшін өзгертуге немесе тіпті циклдің өзін шығаруға болады. Алгоритм екі американдық ғалымның атымен аталады: Ричард Беллман және Лестер Форд. Форд шын мәнінде бұл алгоритмді 1956 жылы басқа математикалық есепті зерттеу кезінде ойлап тапты, оның ішкі мәселесі графиктегі ең қысқа жолды табу болды, ал Форд бұл мәселені шешетін алгоритмнің сұлбасын берді. Беллман 1958 жылы ең қысқа жолды табу мәселесімен арнайы айналысатын мақаласын жариялады және сол мақалада ол алгоритмді бүгінгі күні біз білетіндей анық айтты. жүктеу/скачать 336,61 Kb. Достарыңызбен бөлісу:
|