«Дискретті математика»
жүктеу/скачать 445,27 Kb.
|
- Бұл бет үшін навигация:
- Алгоритмнің күрделілігі
| Дұрыстығын дәлелдеу
a төбесінен v шыңына дейінгі ең қысқа жолдың ұзындығы l(v) болсын. Кез келген z шыңына барған кезде d(z)=l(z)} теңдігі болатынын индукция арқылы дәлелдейік. Негіз. Алдымен а шыңы барады. Осы сәтте d(a)=l(a)=0 Қадам. Жоғарыға баруды таңдайық z≠a. Осы сәтте d(z)=l(z) екенін дәлелдейік. Біріншіден, кез келген v шыңы үшін d(v)≥l(v) әрқашан орындалатынын ескеріңіз (алгоритм барлық бар жолдардың ең қысқасынан қысқа жолды таба алмайды). Болсын P - а-дан z-ге дейінгі ең қысқа жол. Vertex z P нүктесінде және оған кірген жоқ. Демек, P нүктесіндегі ашылмаған шыңдар жиыны бос емес. y P нүктесіндегі бірінші кірмеген шыңы болсын, оның алдындағы x (демек барған). P жолы ең қысқа болғандықтан, оның а-дан х-тен у-ға дейінгі бөлігі де ең қысқа, сондықтан l(y)=l(x)+w(xy). Индукциялық гипотеза бойынша х шыңына бару сәтінде d(x)=l(x) орындалды, сондықтан у шыңы d(x)+w(xy)=l(x) мәнінен аспайтын белгіні алды. +w(xy)= l(y)}. Демек, d(y)=l(y). Егер z=y болса, онда индуктивті ауысу дәлелденеді. Әйтпесе, енді y емес, z шыңы таңдалғандықтан, белгі z кірмегендер арасында минималды, яғни d(z)≤d(y)=l(y)≤l(z). Мұны d(z)≥l(z)-мен біріктірсек, бізде болады d(z)=l(z), бұл дәлелдеуді қажет етті. Алгоритм барлық шыңдарға барған кезде аяқталатындықтан, осы кезде d=l барлық шыңдар үшін. Алгоритмнің күрделілігі Дийкстра алгоритмінің күрделілігі v шыңын табу әдісіне, сонымен қатар қаралмаған шыңдар жиынын сақтау әдісіне және белгілерді жаңарту әдісіне байланысты. G графындағы төбелер санын n арқылы, ал жиектер санын m арқылы белгілейік. Ең қарапайым жағдайда, ең аз d[v] төбесін іздеу үшін шыңдардың барлық жиынын іздегенде және d мәндерін сақтау үшін массив пайдаланылса, алгоритмнің орындалу уақыты: O(n^{2}). Негізгі цикл шамамен n рет орындалады, олардың әрқайсысында минимумды табуға шамамен n амал жұмсалады. Әрбір барған шыңның көршілері арқылы өтетін циклдар m жиектерінің санына пропорционалды бірқатар операцияларды талап етеді (өйткені әрбір жиек осы циклдарда дәл екі рет орын алады және операциялардың тұрақты санын қажет етеді). Осылайша, алгоритмнің жалпы орындалу уақыты O(n^{2}+m), бірақ m≤n(n-1) болғандықтан, ол O(n^{2}). Сирек Графтар үшін (яғни, олар үшін m n²-ден әлдеқайда аз) қосылмаған шыңдарды екілік үймеде сақтауға болады, ал d[i] мәндерін кілт ретінде пайдалануға болады, содан кейін жою уақыты d[i ] модификация уақыты log n-ге дейін ұлғаятынын ескерсек, Ū шыңы logn болады. Цикл шамамен n рет орындалатындықтан және белгіні өзгерту саны m-ден аспайтындықтан, мұндай іске асырудың орындалу уақыты (nog n+mlog n) болады. Орташа O(\og n) ішінде жойылатын және орташа O(1) мәнін азайтатын кірмеген шыңдарды сақтау үшін Фибоначчи үйіндісін қолдансақ, онда алгоритмнің орындалу уақыты O(nlog n) болады. +м).
import math def get_link_V(V, D):
def arg_min(T, S): amin = -1 m = math.inf for i, t in enumerate(T): if t < m and i not in S: m = t amin = i return amin D = (
(6, 0, 8, 0, 4, 0, 0, 0), (0, 8, 0, 3, 0, 0, 0, 9), (0, 0, 3, 0, 7, 8, 0, 0), (0, 4, 0, 7, 0, 0, 0, 0), (0, 0, 0, 8, 0, 3, 5, 0), (0, 0, 0, 0, 0, 5, 0, 0), (0, 0, 9, 0, 0, 0, 0, 0), ) N = len(D) T = [math.inf] * N V = 0 S = set([V]) T[V] = 0 while V != -1: for j in get_link_V(V, D): if j not in S: w = T[V] + D[V][j] if w < T[j]: T[j] = w V = arg_min(T, S) if V != -1: S.add(V) # А төбесінен барлық басқа төбелерге дейінгі ең қысқа қашықтықтарды басып шығару for i in range(N): print(f"Расстояние от узла A до узла {chr(65 + i)} составляет {T[i]}" жүктеу/скачать 445,27 Kb. Достарыңызбен бөлісу:
|