十五个经典算法研究与总结


⧠ҍ˄㔝˅ǃsift ㇇⌅Ⲵ㕆䈁оᇎ ᖱᨀਆо३䝽ѻ SIFT ㇇⌅ ˄SIFT ㇇⌅㌫ࡇӄㇷ᮷ㄐ˅⢩ۿҍǃമ ǃ޽䈸੟ਁᔿᩌ㍒㇇⌅ޛ гǃ䚇Ր㇇⌅ 䘿᷀ GA ᵜ䍘 й㔝˅ǃKMP ㇇⌅ѻᙫ㔃ㇷ˄ᗵ៲ KMP˅˄ޝ ⌅㔝˅ǃӾ KMP ㇇⌅а↕а↕䈸ࡠ BM ㇇˄ޝ ˅ǃᮉ֐ࡍ↕Ҷ䀓 KMP ㇇⌅ǃupdated ˄KMP ㇇⌅㌫ࡇйㇷ᮷ㄐޝ ӄ˄㔝˅ǃ㓒唁ṁ㇇⌅Ⲵᇎ⧠оࢆ᷀ ㇷ᮷ㄐѻަѝєㇷ˅ޝӄǃᮉ֐䘿ᖫҶ䀓㓒唁ṁ ˄㓒唁ᮠ㌫ࡇ ഋǃBFS ઼ DFS Ոݸᩌ㍒㇇⌅ йǃࣘᘱ㿴ࡂ㇇⌅ Ҽ˄й㔝˅ǃDijkstra ㇇⌅+Heap ึⲴᆼᮤ c ᇎ⧠Ⓚ⸱ Ҽ˄޽㔝˅ǃDijkstra ㇇⌅+fibonacci ึⲴ䙀↕ c ᇎ⧠ Ҽ˄㔝˅ǃᖫᓅ⨶䀓 Dijkstra ㇇⌅ ҼǃDijkstra ㇇⌅ࡍ᧒ а˄㔝˅ǃA*ˈDijkstraˈBFS ㇇⌅ᙗ㜭∄䖳৺ A*㇇⌅Ⲵᓄ⭘ аǃA*ᩌ㍒㇇⌅ ॱӄњ㓿ި㇇⌅⹄ウ䳶䭖+ⴞᖅ ᮷ㄐ˖ 䇑 31 ㇷޡˈᢩ䇴ᤷ↓DŽ䉒䉒DŽԕлᱟᐢ㓿߉ҶⲴ 15 њ㓿ި㇇⌅䳶䭖ˈ㇇ᱟањⴞᖅ+㍒ᕅ OKˈԫօӪᴹԫօ䰞仈ˈ⅒䗾䲿ᰦ൘ blog к⮉䀰䇴䇪ˈᡆᶕؑ˖zhoulei0907@yahoo.cn Ҷ 5 ㇷ᮷ㄐ˗㘼㓒唁ṁ㌫ࡇˈࡉᴤᱟᴰਾ߉Ҷ 6 ㇷ᮷ㄐˈᡀѪҶഭ޵ᴰѪ㓿ިⲴ㓒唁ṁᮉ〻DŽ Ҷ㔝䳶ˈྲㅜҼњ㇇⌅˖Dijkstra ㇇⌅ˈׯ߉Ҷ 4 ㇷ᮷ㄐ˗sift ㇇⌅वᤜަ㕆䈁৺ᇎ⧠ˈ߉ 䇑 31 ㇷ᮷ㄐˈवᤜ㇇⌅⨶䇪Ⲵ⹄ウо䱀䘠ˈ৺ަ㕆〻Ⲵާփᇎ⧠DŽᖸཊњ㇇⌅䜭ਾ㔝߉ޡ ˈ⌅ਦਈᦒ.Hash.ᘛ䙏ᧂᒿ.SPFA.ᘛ䙂䘹ᤙ SELECT ㅹ 15 њ㓿ިส⹰㇇・ڵ.ᖱᨀਆ SIFT⢩ ۿᵜ㓿ި㇇⌅⹄ウ㌫ࡇˈ⏥ⴆ A*.Dijkstra.DP.BFS/DFS.㓒唁ṁ.KMP.䚇Ր.੟ਁᔿᩌ㍒.മ ㇇⌅᮷ㄐDŽޣ㌫ࡇ઼⴨ 㔝ˈ䲔Ҷ㔗㔝ᗞ䖟䶒䈅ˍˌˌ仈㌫ࡇˈ઼〻ᒿઈ㕆〻㢪ᵟ㌫ࡇѻཆˈׯ൘߉䘉㓿ި㇇⌅⹄ウ ਨⲴ䶒䈅仈ˈ㘼ਾⲴഋњᴸ㠣Ӻˈࡉᯝᯝ㔝ޜਟԕ䘉Ѹ䈤ˈᔰঊཤؙњᴸаⴤ൘ᮤ⨶ᗞ䖟ㅹ ᵜӪⲴ৏ࡋ֌૱㓿ި㇇⌅⹄ウ㌫ࡇˈ㠚Ӿˍˌᒤˍˎᴸᵛ㠣ˍˍᒤˍˎᴸˈ߉Ҷ䘁аᒤDŽ ࡽ䀰˖ ᮷ẓࡦ֌㘵˖㣡᰾ᴸ᳇ &ᴹ劬㖁http://www.youyur.com/˟ˡ˫੤䎵 ᵳᇊウDŽץˈ༠᰾˖⡸ᵳᡰᴹ ࠪ༴˖http://blog.csdn.net/v_JULY_v ᗞঊ˖http://weibo.com/julyweibo ᰦ䰤˖2010 ᒤ 12 ᴸᵛ-2011 ᒤ 12 ᴸDŽ ֌㘵˖July  ॱॱӄњ㓿ި㇇⌅⹄ウоᙫ㔃 1 ----------- ---------------------------------------------------------------------------------------------------------------------- ᴹ䈟ѻ༴ˈн੍ᤷ↓DŽ ⅒䗾ˈ਴սˈоᡁа਼ᆖҐ᧒䇘ˈӔ⍱⹄ウDŽ 3ǃᵜ㓿ި㇇⌅⹄ウ㌫ࡇˈ㋮⳺≲㋮ˈнᯝՈॆˈ≨ѵᴤᯠˈ≨ѵई䈟DŽ July ৺ࠪ༴DŽ 2ǃᵜ㓿ި㇇⌅⹄ウ㌫ࡇˈ㌫ᡁ৲㘳䍴ᯉˈаㇷаㇷ৏ࡋᡰ֌ˈ䖜䖭ᗵ享⌘᰾֌㘵ᵜӪ 1ǃᵜ㓿ި㇇⌅⹄ウ㌫ࡇˈ↔㌫ࡇ᮷ㄐ߉Ⲵнཏྭѻ༴ˈ䘈ᵋ㿱䈵DŽ ঊѫ䈤᰾˖ ----------- ---------------------------------------------------------------------------------------------------------------------- ֌㘵˖JulyǃҼ䴦ааᒤаᴸ аǃA*ᩌ㍒㇇⌅   ᵳᗵウDŽѕ⾱⭘Ҿԫօ୶ъ⭘䙄ˈ䘍㘵ᇊウ⌅ᖻ䍓ԫDŽץˈ ⡸ᵳᡰᴹ 䉒䉒བྷᇦDŽᆼDŽˈ⌘ޣ 䶎ᑨᝏ䉒ˈ਴սሩᡁⲴ᭟ᤱо ⭘ᡁⲴᰦ䰤DŽ 䏓Ⲵь㾯а㡜нՊঐޤ䏓DŽ2ǃ⋑ᴹޤⲴᰦ䰤ᶕᆖ㇇⌅ˈ൘↔ˈᡁᝯഎ༽਴սؙਕ䈍˖1ǃ 㠚ӾᵜӪ߉䘉њ㇇⌅㌫ࡇԕᶕˈᙫᴹнቁⲴᴻ৻䰞ᡁྲօᆖ㇇⌅ˈ䰞ᡁᘾѸՊᴹ䛓Ѹཊ ⌘⌘䀓 䟼ਦਈᦒڵॱӄǃཊ亩ᔿ҈⌅оᘛ䙏 ࠶᷀оᇎ⧠ޕ␡ॱഋǃᘛ䙏䘹ᤙ SELECT ㇇⌅Ⲵ ॱйǃ䙊䗷⎉བྷкᵪ༽䈅䈅仈ᆖ SPFA ㇇⌅ ॱҼ˄޽㔝˅˖ᘛ䙏ᧂᒿ㇇⌅ѻᡰᴹ⡸ᵜⲴ c/c++ᇎ⧠ ࠶᷀ޕ␡ॱҼ˄㔝˅ǃᘛ䙏ᧂᒿ㇇⌅Ⲵ ॱҼǃᘛ䙏ᧂᒿ㇇⌅ ˄ᘛ䙏ᧂᒿ㇇⌅ 3 ㇷ᮷ㄐ˅ 䭞䇽 Hash н䟽༽㕆⸱ᇎ䐥ޣᧂ㍒ᕅقॱа˄㔝˅ǃ ॱаǃӾཤࡠቮᖫᓅ䀓᷀ Hash 㺘㇇⌅ 䟼ਦਈᦒ㇇⌅ǃлڵॱǃӾཤࡠቮᖫᓅ⨶䀓 䟼ਦਈᦒ㇇⌅ǃкڵॱǃӾཤࡠቮᖫᓅ⨶䀓 ҍ˄й㔝˅˖SIFT ㇇⌅Ⲵᓄ⭘--ⴞḷ䇶࡛ѻ Bag-of-words ⁑ර ҍ˄޽㔝˅ǃᮉ֐а↕а↕⭘ c 䈝䀰ᇎ⧠ sift ㇇⌅ǃл ҍ˄޽㔝˅ǃᮉ֐а↕а↕⭘ c 䈝䀰ᇎ⧠ sift ㇇⌅ǃк 2 ф h(n)䐍⿫ h*(n)Ⲵ੸ᓖн㜭䗷བྷˈ੖ࡉ h(n)ቡ⋑ᴹ䗷ᕪⲴ४࠶㜭࣋ˈ㇇⌅᭸⦷ᒦнՊ 㓿൘⨶䇪к䇱᰾ᱟ┑䏣ᶑԦ 4 ⲴˈӾ㘼Ѫ䘉њ㇇⌅Ⲵ᧘ᒯ䎧ࡠҶߣᇊᙗⲴ֌⭘DŽ ㆆ⮕ h(n)нӵᖸྭ⨶䀓ˈ㘼фᐢޣᮠ⸱䰞仈ˈᴹӋ⴨ޛн䗷ˈሩҾമⲴᴰՈ䐟ᖴᩌ㍒઼ Ⲵ䳮㜭ਟ䍥ҶDŽ 㾱㋮ᗳ䇮䇑Ⲵˈ⭡Ҿ h*(n)ᱮ❦ᱟᰐ⌅⸕䚃Ⲵˈᡰԕˈањ┑䏣ᶑԦ 4 Ⲵ੟ਁㆆ⮕ h(n)ቡᶕ ሩҾањᩌ㍒䰞仈ˈᱮ❦ˈᶑԦ 1,2,3 䜭ᱟᖸᇩ᱃┑䏣Ⲵˈ㘼ᶑԦ 4˖ h(n)<=h*(n)ᱟ䴰 аᇊ㜭᢮ࡠᴰՈ䀓DŽ ᖃ↔ഋњᶑԦ䜭┑䏣ᰦˈањާᴹ f(n)=g(n)+h(n)ㆆ⮕Ⲵ੟ਁᔿ㇇⌅㜭ᡀѪ A*㇇⌅ˈᒦ DŽ˅4ǃh(n)=ⴞḷ亦⛩ V5 Ⲵᴰ⸝䐟ᖴDŽ V3ˈV4 ਴⛩䗮ࡠⴞⲴ⛩ V5DŽл䶒Ⲵ䰞仈ˈণᱟ≲↔䎧࿻亦⛩ V0->䙄ᖴԫ᜿亦⛩ V1ǃV2ǃ ݸѮањሿሿⲴֻᆀ˖ণ≲ V0->V5 Ⲵ䐟ᖴˈV0->V5 Ⲵ䗷〻ѝˈਟԕ㓿⭡ V1ˈV2ˈ A*ᩌᩌራ㇇⌅Ⲵᇎ⧠ ᖸ儈DŽሩањྭⲴ h(n)Ⲵ䇴ԧᱟ˖h(n)൘ h*(n)Ⲵл⭼ѻлˈᒦфቭ䟿᧕䘁 h*(n)DŽ 4 (function reconstruct_path(came_from,current_node return failure f_score[y] := g_score[y] + h_score[y] h_score[y] := heuristic_estimate_of_distance(y, goal) //x-->y-->goal g_score[y] := tentative_g_score came_from[y] := x if tentative_is_better = true tentative_is_better := false else tentative_is_better := true else if tentative_g_score < g_score[y] tentative_is_better := true add y to openset if y not in openset tentative_g_score := g_score[x] + dist_between(x,y) continue if y in closedset for each y in neighbor_nodes(x) CLSOE 㺘 ޕ add x to closedset //x᭮ remove x from openset return reconstruct_path(came_from,goal) // if x = goal //ྲ᷌ x ᱟањ䀓 x := the node in openset having the lowest f_score[] value //x Ѫ OPEN 㺘ѝᴰሿⲴ while openset is not empty //㤕 OPEN 㺘нѪオ f_score[start] := h_score[start] h_score[start] := heuristic_estimate_of_distance(start, goal) //h(n) g_score[start] := 0 //g(n) openset := set containing the initial node //ሶ㾱㻛ՠ㇇Ⲵ㢲⛩䳶ਸ closedset := the empty set //ᐢ㓿㻛ՠ㇇Ⲵ㢲⛩䳶ਸ //OPEN-->CLOSEˈ䎧⛩-->ԫ᜿亦⛩ g(n)-->ⴞḷ亦⛩ h(n) f(n)ˈሶ OPEN 㺘᤹ f(x)ᧂᒿˈᴰሿⲴ᭮൘㺘ཤˈ䟽༽㇇⌅ˈഎࡠ 1DŽ CLOSE 㺘ˈ਼ᰦ䇑㇇⇿ањਾ㔗㔃⛩Ⲵՠԧ٬ ޕOPEN 㺘ˈᒦᢺ S ᭮ ޕ㺘ѝˈቡሶᆳԜ᭮ 㚄Ⲵ㔃⛩˄ᆀ㔃⛩˅ˈྲ᷌н൘ CLOSEޣ3ǃሶ n Ⲵᡰᴹਾ㔗㔃⛩ኅᔰˈቡᱟӾ n ਟԕⴤ᧕ 2ǃn ᱟⴞḷ䀓ੇ˛ᱟˈ᢮ࡠањ䀓˄㔗㔝ራ᢮ˈᡆ㓸→㇇⌅˅DŽ 1ǃྲ᷌ OPEN 㺘нѪオˈӾ㺘ཤਆањ㔃⛩ nˈྲ᷌Ѫオ㇇⌅ཡ䍕DŽ OPEN 㺘ˈCLOSE 㺘㖞オˈ㇇⌅ᔰ࿻ᰦ˖ ޕ俆ݸሶ䎧࿻㔃⛩ S ᭮ A*㇇㇇⌅⍱〻˖ 䙊䗷к䶒Ⲵ A*ᩌ㍒ṁⲴާփ䗷〻ѝሶ h(n)䇮Ѫ 0 ᡆሶ g(n)䇮Ѫ 0 㘼ᗇࡠDŽ 5 ----------- ---------------------------------------------------------------------------------------------------------------------- ࠪ༴˖http://blog.csdn.net/v_JULY_v -----------֌㘵:July Ҽ䴦ааᒤйᴸॱᰕDŽ ---------------------------------------------------------------------------------------------------------------------- аа˄㔝˅ǃA*ˈDijkstraˈBFS ㇇⌅ᙗ㜭∄䖳৺ A*㇇⌅Ⲵᓄ⭘ ৺ A*㇇⌅Ⲵᓄ⭘DŽ䉒䉒བྷᇦDŽ˅ᵜ᮷ᆼDŽ ਴ս䈫㘵৲㘳↔ A*ᩌራ㇇⌅Ⲵਾ㔝аㇷ᮷ㄐ˖а˄㔝˅ǃA*ˈDijkstraˈBFS ㇇⌅ᙗ㜭∄䖳 ѝ䰤䎠ˈҏᱟᡰᴹ䐟ᖴ䜭䎠а⅑ˈ⇿ањ⛩ḷ⌘ᴰ⸝٬DŽ˄i am sorryDŽ᮷ㄐˈ߉Ⲵᐞˈᚣ䈧 A*㇇⌅ᇎ䱵ᱟњェѮ㇇⌅ˈҏо䈮ᵜкᮉⲴᴰ⸝䐟ᖴ㇇⌅㊫լDŽ䈮ᵜкᮉⲴᱟєཤᖰ ᙫ㔃˖ ࡉԫ᜿ਆаᶑণਟDŽ 㘼৽ੁ᢮䐏ᆳ⴨䘎Ⲵ↕ᮠ⴨㔗ቁањ٬Ⲵ⛩䘎䎧ᶕቡᖒᡀҶᴰ⸝䐟ᖴˈᖃཊњ⛩⴨਼ˈ ᱟᴰ⸝䐟ᖴˈ ᦹ৏ᴰሿ↕ᮠˈаⴤࡠᡰᴹⲴ䐟ᖴ⛩䜭н㜭㔗㔝䜭ҶѪ→ˈᴰ㓸䛓њ⛩㻛ḷ⌘Ⲵᴰሿ↕ᮠᰒ ࡔᯝᴰሿ↕僔ᱟ੖ሿҾ䇠ᖅⲴ޵ᇩˈྲ᷌ᱟˈࡉᴤᯠˈىᖃԫօㅜҼ⅑䎠ࡠањ⛩Ⲵᰦ ↕ᮠ˅ Ӿ A ⛩ᔰ࿻ˈ䙽শᡰᴹⲴਟ䎠䐟ᖴˈ䇠ᖅࡠањ㔃ᶴѝˈ䇠ᖅ޵ᇩѪ˄ս㖞⛩ˈᴰሿ ᯩ⌅˖ ⴞḷ˖Ӿᖃࡽս㖞 A ࡠⴞḷս㖞 B ᢮ࡠаᶑᴰ⸝Ⲵ㹼䎠䐟ᖴDŽ ㆰ䘠 A*ᴰ⸝䐟ᖴ㇇⌅Ⲵᯩ⌅˖ ਾ㔝˖JulyǃҼ䴦ааᒤйᴸаᰕᴤᯠDŽ ----------- ---------------------------------------------------------------------------------------------------------------------- JulyǃҼ䴦ааᒤҼᴸॱᰕᴤᯠDŽ ᵜ᮷ᆼDŽ ᓖѪ O(n*n)ˈ䘉⴨ᖃҾ Dijkstra ㇇⌅DŽ 䘋㹼ᧂᒿˈ㘼ᱟ⇿⅑Ӿ OPEN 㺘ѝ≲ањᴰሿⲴˈ䛓ਚ䴰㾱 O(n)Ⲵ༽ᵲᓖˈᡰԕᙫⲴ༽ᵲ ྲ᷌⇿⅑нᱟሩ OPEN 㺘䘋㹼ᧂᒿˈഐѪᙫᱟнᯝൠᴹᯠⲴ㔃⛩␫࣐䘋ᶕˈᡰԕн⭘ ሿᱟ O(n)䟿㓗Ⲵˈ㤕⭘ᘛᧂቡᱟ O(nlogn)ˈ҈ԕཆᗚ⧟ᙫⲴ༽ᵲᓖᱟ O(n^2 * logn)ˈ а⅑ᧂᒿˈOPEN 㺘བྷڊ⇿⅑ኅᔰањ㔃⛩Ⲵਾ㔝㔃⛩ᰦˈ䴰 O(n)⅑ˈ਼ᰦ޽ሩ OPEN 㺘 n њ㔃⛩˅ˈ ޡ˄ਆҶ n ⅑ޡˈ㘳㲁ࡠ㇇⌅ᙗ㜭ˈཆᗚ⧟ѝ⇿⅑Ӿ OPEN 㺘ਆањݳ㍐ ᗇӾ V0 ࡠަᆳᡰᴹ㔃⛩Ⲵᴰ⸝䐟ᖴDŽ f(n)ˈᖃ OPEN 㺘Ѫオᰦ CLOSE 㺘ѝሶ≲ о㔃⛩߉൘а䎧Ⲵᮠ٬㺘⽪䛓њ㔃⛩Ⲵԧ٬ return the empty path else return (p + current_node) p = reconstruct_path(came_from,came_from[current_node]) if came_from[current_node] is set 6 ˖аǃ䎧࿻⛩㔯ඇˈоⴞḷ⛩㓒ඇ൘਼аᶑ≤ᒣ㓯к okˈԫ᜿᩶᭮㔯ඇо㓒ඇⲴй⿽⣦ᘱ˖ A*ǃDijkstraǃBFS ㇇⌅ᙗ㜭∄䖳╄⽪˖ ⴆⲴ㤳തˈ਴㠚Ⲵᐕ֌⍱〻ˈᒦӾѝਟԕフ㿱ᆳԜⲴ᭸⦷儈վDŽ ᴰਾˈ䘀㹼〻ᒿˈ∄䖳֯⭘к䘠ӄ⿽㇇⌅ˈᗇࡠ਴㠚н਼Ⲵ䐟ᖴˈ਴㠚᢮ራ䗷〻ѝᡰ㾶 ⺽⢙ˈ л䶒ˈૡԜ䲿᜿᩶᭮䎧࿻⛩㔯ඇˈⴞḷ⛩㓒ඇⲴս㖞ˈ❦ਾˈ൘ᆳԜѝ䰤䲿ׯ⭫аӋ䳌 ⺽⢙ˈⲭ㢢Ⲵᯩඇԓ㺘ਟԕ䙊㹼Ⲵ䐟ᖴDŽ ૡԜԕлമѪֻˈമк㔯㢢ᯩඇԓ㺘䎧࿻⛩ˈ㓒㢢ᯩඇԓ㺘ⴞḷ⛩ˈ㍛㢢Ⲵᯩඇԓ㺘䳌 5. Bi-Directional Breadth-First-Search(ৼੁᒯᓖՈݸᩌ㍒) 4. Dijkstra 3. A* (࡙⭘࠷∄䴚ཛ䐍⿫) 2. A* (䟷⭘⅗∿䐍⿫) 1. A* (֯⭘ᴬ૸亯䐍⿫) ᡁԜ∄䖳ˈԕлӄ⿽㇇⌅˖ Ⲵঠ䊑DŽ ᵜ᮷ˈণԕ╄⽪മⲴᖒᔿˈ∄䖳ᆳԜ਴㠚Ⲵራ䐟䗷〻ˈ䇙਴սሩᆳԜᴹањ␵Რ㘼ⴤ㿲 䊑DŽ ᜣᗵˈ䘈ᱟᴹ䜘࠶䈫㘵ሩ↔㊫ᴰ⸝䐟ᖴ㇇⌅ˈᒦ䶎ᐢҶ❦Ҿ㜨ˈᡆ㘵ˈᰐањᙫփབྷᾲⲴঠ ҶDŽަѝˈDijkstra ㇇⌅ˈਾ৸߉Ҷаㇷ᮷ㄐ㔗㔝䱀䘠˖Ҽ˄㔝˅ǃ⨶䀓 Dijkstra ㇇⌅DŽնˈ ᴰ⸝䐟ᖴⲴ਴䐟㇇⌅ A*㇇⌅ǃDijkstra ㇇⌅ǃBFS ㇇⌅ˈ䜭ᐢ൘ᵜ BLOG ޵ᴹᡰ䱀䘠 ᕅᕅ䀰˖ 7 (1. A*(֯֯⭘ᴬ૸亯䐍⿫ ਴㠚Ⲵᩌራ䐟ᖴѪ˖ 8 9 2. A*(䟷䟷⭘⅗∿䐍⿫) 3. A*(࡙⭘࠷∄䴚ཛ䐍⿫) 10 4. Dijkstra ㇇㇇⌅. //ᖸ᰾ᱮˈDijkstra ᩌራ᭸⦷᰾ᱮᐞҾк䘠 A* ㇇⌅DŽ˄ⴻᆳᴰਾ ᢮ࡠⴞḷ⛩㓒ඇᡰ䎠䗷Ⲵ䐟ᖴˈ઼㾶ⴆⲴ㤳തˈণ㜭䖫᱃ⴻࠪᶕˈл䶒Ⲵ∄䖳ˈҏᱟส Ҿ਼ањ䚃⨶DŽⴻ䐟ᖴˈⴻ㾶ⴆⲴ㤳തˈ䇴ԧањ㇇⌅Ⲵ᭸⦷˅DŽ (Bi-Directional Breadth-First-Search(ৼৼੁᒯᓖՈݸᩌ㍒ .5 11 (2. A*(䟷⭘⅗∿䐍⿫ 1. A*(֯⭘ᴬ૸亯䐍⿫) ਴㠚Ⲵᩌራ䐟ᖴѪ˖ ҼҼǃ䎧࿻⛩㔯ඇˈⴞḷ⛩㓒ඇ൘аᯌ㓯к˖ 12 13 3. A*(࡙࡙⭘࠷∄䴚ཛ䐍⿫) 4. Dijkstra ㇇⌅DŽ //ок䘠 A* ㇇⌅∄䖳ˈ㾶ⴆ㤳തབྷˈᩌራ᭸⦷䖳վ (Bi-Directional Breadth-First-Search(ৼৼੁᒯᓖՈݸᩌ㍒ .5 14 15 ййǃ䎧࿻⛩㔯ඇˈⴞḷ⛩㓒ඇ㻛ཊ䟽䳌⺽⢙䱫ᥑ˖ ਴㠚Ⲵᩌራ䐟ᖴѪ˄਼ṧˈ䘈ᱟӾ㔯ඇࡠ㓒ඇ˅˖ (2. A*(䟷⭘⅗∿䐍⿫ A* (֯֯⭘ᴬ૸亯䐍⿫) .1 16 17 3. A*(࡙࡙⭘࠷∄䴚ཛ䐍⿫) 4. Dijkstra Dijkstra ㇇⌅аṧᖸབྷˈ᭸⦷վлDŽ Bi-Directional Breadth-First-Search(ৼৼੁᒯᓖՈݸᩌ㍒) //㾶ⴆ㤳ത਼к䘠 .5 18 ˈ䟽㾱Ⲵ䜘࠶ѻаDŽ⭘䙂ᖂҏᴹњྭ༴ቡᱟˈ൘㌫㔏Ḹѝਚ䴰㾱ᆈ㔃⛩ᴰབྷ␡ᓖ䛓ѸབྷⲴオ䰤 DFS ⭘ࡠҶḸˈᡰԕᴹањᖸྭⲴᇎ⧠ᯩ⌅ˈ䛓ቡᱟ䙂ᖂˈ㌫㔏Ḹᱟ䇑㇇ᵪ〻ᒿѝᶱ OPEN 㺘ཤਆ㔃⛩ˈҏӾ㺘ཤ␫࣐㔃⛩ˈҏቡᱟ䈤 OPEN 㺘ᱟањḸʽ ⛩ˈҏቡᱟ䈤 OPEN 㺘ᱟањ䱏ࡇˈᱟⲴˈBFS 俆ݸ䇙֐ᜣࡠþ䱏ࡇÿ˗㘼 DFSˈᆳᱟӾ Ԅ㓶㿲ሏ OPEN 㺘ѝᖵ䇯䰞Ⲵ㔃⛩Ⲵ㓴㓷ᖒᔿˈBFS ᱟӾ㺘ཤਆ㔃⛩ˈӾ㺘ቮ␫࣐㔃 ᱟ੖ᴹⴻࠪ˖к䘠Ⲵ BFS ઼ DFS ᴹӰѸн਼˛ CLOSE 㺘ˈ䟽༽㇇⌅ࡠ 1DŽ ޕOPEN 㺘ᔰ࿻ˈ㘼ᢺ S ᭮ ޕ㺘ѝˈቡሶᆳԜ᭮ 㚄Ⲵ㔃⛩˄ᆀ㔃⛩˅ˈྲ᷌н൘ CLOSEޣ3ǃሶ S Ⲵᡰᴹਾ㔗㔃⛩ኅᔰˈቡᱟӾ S ਟԕⴤ᧕ 2ǃS ᱟⴞḷ䀓ੇ˛ᱟˈ᢮ࡠањ䀓˄㔗㔝ራ᢮ˈᡆ㓸→㇇⌅˅˗нᱟࡠ 3 1ǃྲ᷌ OPEN 㺘нѪオˈӾ㺘ѝᔰ࿻ਆањ㔃⛩ Sˈྲ᷌Ѫオ㇇⌅ཡ䍕 OPEN 㺘ˈCLOSE 㺘㖞オˈ㇇⌅ᔰ࿻ᰦ˖ ޕ俆ݸሶ䎧࿻㔃⛩᭮ DFS˄Depth-First-Search ␡ᓖՈݸᩌ㍒˅ CLOSE 㺘ˈ䟽༽㇇⌅ࡠ 1DŽ ޕOPEN 㺘ᵛቮˈ㘼ᢺ S ᭮ ޕ㺘ѝˈቡሶᆳԜ᭮ 㚄Ⲵ㔃⛩˄ᆀ㔃⛩˅ˈྲ᷌н൘ CLOSEޣ3ǃሶ S Ⲵᡰᴹਾ㔗㔃⛩ኅᔰˈቡᱟӾ S ਟԕⴤ᧕ 2ǃS ᱟⴞḷ䀓ੇ˛ᱟˈ᢮ࡠањ䀓˄㔗㔝ራ᢮ˈᡆ㓸→㇇⌅˅˗нᱟࡠ 3 1ǃྲ᷌ OPEN 㺘нѪオˈӾ㺘ѝᔰ࿻ਆањ㔃⛩ Sˈྲ᷌Ѫオ㇇⌅ཡ䍕 OPEN 㺘ˈCLOSE 㺘㖞オˈ㇇⌅ᔰ࿻ᰦ˖ ޕ俆ݸሶ䎧࿻㔃⛩᭮ BFS˄Breadth-First-Search ᇭᓖՈݸᩌ㍒˅ 㴞࣋ᩌ㍒˄BFSˈDFS˅ 䳶ˈਖањਛ CLOSE 㺘ˈ㺘⽪䛓Ӌᐢ㓿䇯䰞Ⲵ㔃⛩䳶DŽ ᡁԜ⭘єᕐ㺘ᶕ䘋㹼ᩌ㍒ˈањਛ OPEN 㺘ˈ㺘⽪䛓Ӌᐢ㓿ኅᔰն䘈⋑ᴹ䇯䰞Ⲵ㔃⛩ ㍒ⲴⴞⲴᴹєњᯩ䶒ˈᡆ㘵≲ਟ㹼䀓ˈᡆ㘵Ӿਟ㹼䀓䳶ѝ≲ᴰՈ䀓DŽ њ䰞仈ˈнаᇊᴹ᰾⺞Ⲵᆈۘᖒᔿˈնᆳ䟼䶒Ⲵањ㔃⛩䜭ᴹਟ㜭ᱟањ䀓˄ਟ㹼䀓˅ˈᩌ н㇑ԕл䇪䘠ଚа⿽ᩌ㍒ˈ䜭㔏а⭘䘉ṧⲴᖒᔿ㺘⽪˖ᩌ㍒Ⲵሩ䊑ᱟањമˈᆳ䶒ੁа ৲㘳Ҷ㇇⌅傯ㄉкⲴ䜘࠶޵ᇩ˖ BFSǃDFS о A*ᩌራ㇇⌅Ⲵ∄䖳 䙊䗷к䶒Ⲵ A*ᩌ㍒ṁⲴާփ䗷〻ѝሶ h(n)䇮Ѫ 0 ᡆሶ g(n)䇮Ѫ 0 㘼ᗇࡠDŽ ⛩ࡠԫ᜿亦⛩ n Ⲵᴰ⸝䐟ᖴˈࡉ䖜ॆѪঅⓀᴰ⸝䐟ᖴ䰞仈ˈণ Dijkstra ㇇⌅DŽ䘉а⛩ˈਟԕ DFSˈᖃ h(n)=0 ᰦˈ䈕㇇⌅㊫լҾ BFSDŽф਼ᰦˈྲ᷌ h(n)Ѫ 0ˈਚ䴰≲ࠪ g(n)ˈণ≲ࠪ䎧 A*㇇⌅оᒯᓖǃ␡ᓖՈݸ઼ Dijkstra ㇇⌅Ⲵ㚄㌫ቡ൘Ҿ˖ᖃ g(n)=0 ᰦˈ䈕㇇⌅㊫լҾ Ѫ→DŽ ⴤࡠՈݸ䱏ࡇѪオ(ᰐ䀓)ᡆ᢮ࡠ㓸→⛩ˈ٬ ሩަਟ㜭ᆀ㔃⛩䇑㇇ gǃh ઼ fˈ˅٬ 俆ݳ㍐˄f 䘉ṧˈ൘ᮤփⲴᩌ㍒䗷〻ѝˈਚ㾱᤹➗㊫լᒯᓖՈݸⲴ㇇⌅ṶᷦˈӾՈݸ䱏ࡇѝᕩࠪ䱏 ࡇDŽ ٬ॷᒿⲴ䱏ࡇ(ণՈݸ䱏ࡇ)䘋㹼ᧂ 㘼ᡰᴹĀᐢ᧒⸕Ⲵնᵚᩌ㍒䗷⛩āਟԕ䙊䗷ањ᤹ f ٬ᴰሿⲴ㔃⛩䘋㹼ኅᔰDŽ ᩌ㍒䗷⛩ѝ(ਟ㜭ᱟн਼ቲˈӖਟн൘਼аᶑ᭟䐟к)ˈ䘹ਆ f A*㇇⌅ᴰѪṨᗳⲴ䗷〻ˈቡ൘⇿⅑䘹ᤙлањᖃࡽᩌ㍒⛩ᰦˈᱟӾᡰᴹᐢ᧒⸕Ⲵնᵚ ⭡кˈᡁԜҏਟԕⴻࠪˈA*ᩌራ㇇⌅Ⲵ⺞ᱟа⿽∄䖳儈᭸Ⲵራ䐟㇇⌅DŽ Dijkstraǃৼੁ BFS ࡠᓅଚњ㇇⌅ᴤՈˈ䘈ᗇⴻާփᛵߥDŽ к䘠╄⽪ˈᡁԜਟԕⴻࠪˈ൘ᴰ⸝䐟ᖴᩌራ᭸⦷кˈа㡜ᴹ A*>Dijkstraǃৼੁ BFSˈަѝ ྲкˈᱟнᱟሩ A*ǃDijkstraǃৼੁ BFS ㇇⌅਴㠚Ⲵᙗ㜭ᴹҶњᙫփབྷᾲⲴঠ䊑ࡇ?⭡ A*ᩌᩌራ㇇⌅Ⲵ儈᭸ѻ༴ 19 ᡰ൘㔃⛩ࡠ䎧࿻㔃⛩Ⲵ䐍⿫˄␡ᓖ˅㺘⽪ˈ㘼੟ਁ٬Ѫ 0ˈ䛓ቡᱟ BFS ᡆ㘵 DFSˈᆳԜє Ӿ A*Ⲵ䀂ᓖⴻࡽ䶒Ⲵᩌ㍒ᯩ⌅ˈྲ᷌䐟ᖴԧ٬Ѫ 0 ቡᱟᴹᒿᩌ㍒ˈྲ᷌䐟ᖴԧ٬ቡ⭘ ਸ൘а䎧㇇ՠᮤњ㔃⛩Ⲵԧ٬DŽˈ㡜ᙗ੟ਁԧ٬ ਖањ䜘࠶ᱟаˈㆰঅⲴᶕ䈤 A*ቡᱟሶՠ٬࠭ᮠ࠶ᡀєњ䜘࠶ˈањ䜘࠶ᱟ䐟ᖴԧ٬ а↕ቡ⴨ᖃҾੁਾཊኅᔰаቲ㔃⛩ˈ␡ᓖཊ㇇аቲˈྲ᷌㾱≲ᴰቁ↕ᮠˈ䛓ቡ䴰㾱⭘ A*DŽ ᮠ⸱䰞仈ˈྲ᷌н㘳㲁␡ᓖˈቡᱟ䈤н㾱≲ᴰቁ↕ᮠˈ〫ࣘޛˈ䛓ቡᱟ A*ˈѮњ䰞仈ֻᆀ ྲ᷌ՠ٬࠭ᮠ㘳㲁Ҷ␡ᓖˈᡆ㘵ᱟᑖᵳ䐍⿫˄Ӿ䎧࿻㔃⛩ࡠⴞḷ㔃⛩Ⲵ䐍⿫࣐ᵳ઼˅ˈ ㍒˄Ordered-Search˅ˈᆳ⵰䟽ⴻྭ㜭੖᢮ࠪ䀓ˈ㘼нⴻ䀓⿫䎧࿻㔃⛩Ⲵ䐍⿫˄␡ᓖ˅DŽ 㘼н㘳㲁␡ᓖˈ∄䖳ᴹ਽Ⲵቡᱟᴹᒿᩌˈྲ᷌ՠ٬࠭ᮠਚ㘳㲁㔃⛩ⲴḀ⿽ᙗ㜭кⲴԧ٬ Ⲵቡᱟ㾱֯〻ᒿᴹ੟ਁᙗˈᴤᘛⲴᩌࠪⴞḷ䀓DŽ ᧂᒿਟ㜭ᱟሩ OPEN 㺘ᮤփ䘋㹼ᧂᒿˈҏਟԕᱟሩਾ㔝ኅᔰⲴᆀ㔃⛩ᧂᒿˈᧂᒿⲴⴞ অᧂᒿ⌅ቡᖸ OK ҶDŽⴻާփᛵߥҶDŽ ᧂᒿˈᘾѸᧂ˛⭘ଚањ˛ᘛᧂ੗ˈqsortʽнаᇊˈ㾱ⴻ㾱ᧂཊቁ㔃⛩ˈྲ᷌ᖸቁˈㆰ ਆߣҾՠ٬࠭ᮠDŽޘ᭸⦷ᴹᡰᑞࣙ઒ˈ䘉ᆼ 䘉ṧⲴᐕ֌ՊнՊሩᮤփᩌ㍒ڊ䘉䟼⴨ᖃҾᱟ䴰㾱þᧂᒿÿˈᧂᒿᱟ㾱ᴹԓԧⲴˈ㘼㣡ᰦ䰤 ⲴᆙᆀԜⲴ᡻ˈଚњᖸ㜿ˈᴹ㓶㧼ˈଚњ⋑ᴹˈᖸᒢ߰ˈ❦ਾሩ䛓Ӌᒢ߰Ⲵᆙᆀ䘋㹼྆࣡DŽ аਠᱮᗞ䮌ˈаৼþភ⵬ÿˈᆳ㜭࠶䗘ࠪⴻк৫аṧۿԕ〠Ѫՠ٬DŽᢃњ∄ᯩˈՠ٬࠭ᮠቡ ٬࠭ᮠˈՠ٬࠭ᮠቡᱟ䇴ԧ࠭ᮠˈᆳ⭘ᶕ䇴ԧᆀ㔃⛩ⲴྭൿˈഐѪ߶⺞䇴ԧᱟнਟ㜭Ⲵˈᡰ ѪҶ᭩ழк䶒Ⲵ㇇⌅ˈᡁԜ䴰㾱ሩኅᔰਾ㔝㔃⛩ᰦሩᆀ㔃⛩ᴹᡰҶ䀓ˈ䘉䟼䴰㾱ањՠ ੟ਁᔿᩌ㍒ ᘛⲴ᢮ࡠⴞḷ㔃⛩ˈӾ㘼ᮤփкᨀ儈ᩌ㍒ᙗ㜭DŽ ྲ↔ˈਾ㔝㔃⛩ᱟᴹྭᴹൿⲴDŽྭˈቡᱟ䈤ᆳ⿫ⴞḷ㔃⛩þ䘁ÿˈྲ᷌Ոݸ༴⨶ᆳˈቡՊᴤ ⛩ᰦˈᱟሩᆳԜ⋑ᴹԫօþ䇔䇶ÿⲴˈᆳ䇔ѪᆳⲴᆙᆀԜ䜭ᱟаṧⲴþՈ⿰ÿˈնһᇎᒦ䶎 ᡁԜ䈤 DFS ઼ BFS 䜭ᱟ㴞࣋ᩌ㍒ˈഐѪᆳԜ൘ᩌ㍒ࡠањ㔃⛩ᰦˈ൘ኅᔰᆳⲴਾ㔝㔃 㺘ˈᴹਟ㜭䘈⋑ᆼᡀᩌ㍒ OPEN 㺘ቡ᳤┑Ҷˈ䘉ᱟ䳮Ҿ᧗ࡦⲴᛵߥDŽ ൘䊑ỻㅹỻ㊫〻ᒿѝˈቡᱟ⭘䘉ṧⲴ DFS Ⲵสᵜ⁑ᔿᩌ㍒ỻተተ䶒ṁⲴˈഐѪྲ᷌⭘ OPEN 㺘ˈ⣦ᘱቡᱟ cˈ൘Ḹ䟼ᆈҶࡽ䶒ᩌ㍒ᰦⲴѝ䰤ਈ䟿 cˈ൘ਾ䶒Ⲵ䙂ᖂ㔃ᶏਾˈc 㔗㔝ਾ〫DŽ ྲ᷌ᤷᇊᴰབྷᩌ㍒␡ᓖѪ nˈ䛓㌫㔏Ḹᴰཊ֯⭘ n њঅսˈᆳ⴨ᖃҾᴹ⣦ᘱᤷ⽪Ⲵ OPEN } } dfs(c)˗䙂ᖂ if(cн൘ CLOSE 㺘ѝ) for(c=s.ㅜањᆀ㔃⛩ ˗c нѪオ ˗c=c.лањᆀ㔃⛩() ) CLOSE 㺘˗ ޕ s᭮ { sᱟⴞḷ㔃⛩ੇ˛ᱟ˖⴨ᓄ༴⨶˗੖ࡉ˖ s䎵䗷ᴰབྷ␡ᓖҶੇ˛ᱟ˖⴨ᓄ༴⨶ˈ䘄എ˗ { ࠭ᮠ dfs(㔃⛩ s) ࡙࡙⭘㌫㔏Ḹᇎ⧠Ⲵ DFS ᘱˈ൘䙂ᖂ䈳⭘㔃ᶏਾ㔗㔝ኅᔰDŽ 䜘ኅᔰˈ⭘аӋ⧟ຳਈ䟿䇠ᖅᖃࡽⲴ⣦ޘҏቡᱟ൘ኅᔰањ㔃⛩Ⲵਾ㔝㔃⛩ᰦਟԕн⭘а⅑ 20 A*ᩌራ㇇⌅Ⲵᓄ⭘ 㓿൘⨶䇪к䇱᰾ᱟ┑䏣ᶑԦ 4 ⲴˈӾ㘼Ѫ䘉њ㇇⌅Ⲵ᧘ᒯ䎧ࡠҶߣᇊᙗⲴ֌⭘DŽ ㆆ⮕ h(n)нӵᖸྭ⨶䀓ˈ㘼фᐢޣᮠ⸱䰞仈ˈᴹӋ⴨ޛн䗷ˈሩҾമⲴᴰՈ䐟ᖴᩌ㍒઼ Ⲵ䳮㜭ਟ䍥ҶDŽ 㾱㋮ᗳ䇮䇑Ⲵˈ⭡Ҿ h*(n)ᱮ❦ᱟᰐ⌅⸕䚃Ⲵˈᡰԕˈањ┑䏣ᶑԦ 4 Ⲵ੟ਁㆆ⮕ h(n)ቡᶕ ሩҾањᩌ㍒䰞仈ˈᱮ❦ˈᶑԦ 1,2,3 䜭ᱟᖸᇩ᱃┑䏣Ⲵˈ㘼ᶑԦ 4˖ h(n)<=h*(n)ᱟ䴰 аᇊ㜭᢮ࡠᴰՈ䀓DŽ ᖃ↔ഋњᶑԦ䜭┑䏣ᰦˈањާᴹ f(n)=g(n)+h(n)ㆆ⮕Ⲵ੟ਁᔿ㇇⌅㜭ᡀѪ A*㇇⌅ˈᒦ DŽ˅4ǃh(n)=O˄E+V*lgV˅ << O˄E*lgV˅ˈሩ੗DŽ:D ᰦˈE+V*lgV ᱟањ䖳བྷⲴ᭩䘋DŽ 㘼 Prim ㇇⌅㤕䟷⭘ᯀ⌒䛓ཱྀึᇎ⧠Ⲵ䈍ˈ㇇⌅ᰦ䰤༽ᵲᓖѪ O˄E+V*lgV˅ˈᖃ |V|<<|E| ᴰሿ⭏ᡀṁ㇇⌅ KruskalǃPrim ㇇⌅Ⲵᰦ䰤༽ᵲᓖѪ O˄E*lgV˅DŽ а㡜䈤ᶕˈᡁԜ⸕䚃ˈBFSˈDFS ㇇⌅Ⲵᰦ䰤༽ᵲᓖѪ O˄V+E˅ˈ ∄䖳л BFSǃDFSǃKruskalǃPrimǃDijkstra ㇇⌅ᰦ䰤༽ᵲᓖ੗˖ к䶒ˈᰒ❦ᨀࡠҶ A*㇇⌅оᒯᓖǃ␡ᓖՈݸᩌ㍒㇇⌅Ⲵ㚄㌫ˈ䛓Ѹˈл䶒ˈҏ亪ׯ޽ BFSǃǃDFSǃKruskalǃPrimǃDijkstra ㇇⌅ᰦ䰤༽ᵲᓖ ራ㇇⌅ᙍᜣDŽ ᡰԕ BFS ਟԕ≲㾱≲䐟ᖴᴰ⸝Ⲵ䰞仈ˈਚᱟ⋑ᴹԫօ੟ਁᙗDŽ л᮷〽ਾˈՊާփ䈸 A*ᩌ 㘼 DFS ᱟӾ OPEN 㺘ѝ䘹ањ␡ᓖᴰབྷⲴ䘋㹼ኅᔰDŽᖃ❦ਚᴹ BFS ᡽㇇ᱟ⢩↺Ⲵ A*ˈ ࡊྭᱟњ৽ⲴˈBFS ᱟӾ OPEN 㺘ѝ䘹ањ␡ᓖᴰሿⲴ䘋㹼ኅᔰˈ 21 (++ for(j = 0;j < i;j for(i = 1; i< 9;i++) int a = 0,b = 0,i,j; { int Canslove(Node * suc, Node * goal) //ࡔᯝᱟ੖ਟ䀓 } return minx; free(temp); minp->next = minp->next->next; temp = minp->next; minx = min->npoint; } temp = temp->next; } minp = temp; min = temp->next; { if((temp->next ->npoint->f) < (min->npoint->f)) { while(temp->next != NULL) Node * minx; Lstack temp = (*Open)->next,min = (*Open)->next,minp = (*Open); { Node * Minf(Lstack * Open) ٬ᴰሿⲴ㢲⛩ˈ䘄എ䈕㢲⛩ൠ൰ //䘹ਆ OPEN 㺘к f }Stack,* Lstack; struct Stack * next; Node * npoint; { typedef struct Stack //OPEN CLOSED 㺘㔃ᶴփ }Node,*Lnode; struct Node * parent; double f,g; int data[9]; { typedef struct Node //㢲⛩㔃ᶴփ 䟺ᖸ䈖ቭˈቡн޽஠ఖҶˈᴹԫօ䰞仈ˈ䈧н੍ᤷ↓˖ ᮠ⸱䰞仈ˈл䶒ˈቡᱟަѫփԓ⸱ˈ⭡Ҿ㔉Ⲵ⌘ޛ⧠okˈૡԜቡᶕᓄ⭘ A*ᩌራ㇇⌅ᇎ 22 //////////////////////////////٬䜘࠶-ᔰ࿻ ///////////////䇑㇇ f } (*list)->next = temp; temp->next = (*list)->next; temp->npoint = suc; temp =(Stack *) malloc(sizeof(Stack)); Stack * temp; { void Putinto(Node * suc,Lstack * list) OPEN ᡆ CLOSED 㺘ѝ ޕ//ᢺ㢲⛩᭮ } return NULL; } temp = temp->next; if(Equal(suc,temp->npoint))return temp -> npoint; { while(temp != NULL) if(temp == NULL)return NULL; Lstack temp = (*list) -> next ; { Node * Belong(Node * suc,Lstack * list) //ࡔᯝ㢲⛩ᱟ੖኎Ҿ OPEN 㺘 ᡆ CLOSED 㺘ˈᱟࡉ䘄എ㢲⛩ൠ൰ˈ੖ࡉ䘄എオൠ൰ } return 1; if(suc->data[i] != goal->data[i])return 0; for(int i = 0; i < 9; i ++ ) { int Equal(Node * suc,Node * goal) //ࡔᯝ㢲⛩ᱟ੖⴨ㅹ ˈ1 ⴨ㅹˈ0 н⴨ㅹ } return 0; else return 1; if(a%2 == b%2) } b++; if((goal->data[i] > goal->data[j]) && goal->data[j] != 0) a++; if((suc->data[i] > suc->data[j]) && suc->data[j] != 0) } 23 } else } } flag = 1; temp->f = (*suc)->f; temp->g = (*suc)->g; temp->parent = (*suc)->parent; { if(((*suc)->g) < (temp->g)) else temp = Belong(*suc,Closed); if(Belong(*suc,Open) != NULL) temp = Belong(*suc,Open); { if((Belong(*suc,Open) != NULL) || (Belong(*suc,Closed) != NULL)) int flag = 0; Node * temp = NULL; {//ࡔᯝᆀ㢲⛩ᱟ੖኎Ҿ OPEN ᡆ CLOSED 㺘 ᒦ֌ࠪ⴨ᓄⲴ༴⨶ int BelongProgram(Lnode * suc ,Lstack * Open ,Lstack * Closed ,Node goal ,float speed) ///////////////////////ᢙኅਾ㔗㢲⛩䜘࠶Ⲵ࠭ᮠ-ᔰ࿻///////////////// ٬䜘࠶-㔃ᶏ////////////////////////////// ///////////////䇑㇇ f } return double(fabs(h1/3 - h2/3) + fabs(h1%3 - h2%3)); } if(goal.data[k] == i)h2 = k; if(suc.data[k] == i)h1 = k; { for(k = 0; k < 9; k++) int k,h1,h2; {//䇑㇇ᯩṬⲴ䭉ս䐍⿫ double Distance(Node suc, Node goal, int i) } എᴰՈ䀓˅ нՊ䘄 ٬໎࣐ᰦᩌ㍒䗷〻ԕ᢮ࡠⴞḷѪՈݸഐ↔ਟ㜭 return h*speed + suc.g; //f = h + g˄speed h = h + Distance(suc, goal, i); for(int i = 1; i <= 8; i++) double h = 0; double Distance(Node,Node,int); ٬ {//䇑㇇ f double Fvalue(Node suc, Node goal, float speed) 24 ⌅{//䙂ᖂᱮ⽪Ӿࡍ࿻⣦ᘱࡠ䗮ⴞḷ⣦ᘱⲴ〫ࣘᯩ int Shownum(Node * result) } } 㢲⛩ ᖃࡽ㢲⛩Ⲵਾ㔗 Spread(&minf, Open, Closed, **goal, speed); //ᖃࡽ㢲⛩нᱟⴞḷ㢲⛩ᰦᢙኅ if(Equal(minf, *goal))return minf; //ྲ᷌ᖃࡽ㢲⛩ᱟⴞḷ㢲⛩ˈࡉᡀ࣏䘰ࠪ CLOSED 㺘ѝ ޕ Putinto(minf, Closed); //ሶ㢲⛩᭮ ٬ᴰሿⲴ㢲⛩ Node * minf = Minf(Open); //Ӿ OPEN 㺘ѝਆࠪ f if((*Open)->next == NULL)return NULL; //ࡔᯝ OPEN 㺘ᱟ੖ѪオˈѪオࡉཡ䍕䘰ࠪ { while(1) {//ᙫᢗ㹼࠭ᮠ Node * Process(Lnode * org, Lnode * goal, Lstack * Open, Lstack * Closed, float speed) ///////////////////////ᢙኅਾ㔗㢲⛩䜘࠶Ⲵ࠭ᮠ-㔃ᶏ////////////////////////////////// } } } free(child); Ҿ OPEN ᡆ CLOSED 㺘 ᒦ֌ࠪ⴨ᓄⲴ༴⨶ if(BelongProgram(&child, Open, Closed, goal, speed)) // ࡔᯝᆀ㢲⛩ᱟ੖኎ Spreadchild(child, i); //ੁ䈕ᯩੁ〫ࣘオṬ⭏ᡀᆀ㢲⛩ child->parent = (*suc); //ᆀ㢲⛩⡦ᤷ䪸ᤷੁ⡦㢲⛩ ٬ child->g = (*suc)->g +1; //㇇ᆀ㢲⛩Ⲵ g child = (Node *) malloc(sizeof(Node)); //ᢙኅᆀ㢲⛩ { if(Canspread(**suc, i+1)) //ࡔᯝḀњᯩੁкⲴᆀ㢲⛩ਟ੖ᢙኅ { for(i = 0; i < 4; i++) Node * child; int i; {//ᢙኅਾ㔗㢲⛩ᙫ࠭ᮠ void Spread(Lnode * suc, Lstack * Open, Lstack * Closed, Node goal, float speed) } return flag; } (*suc)->f = Fvalue(**suc, goal, speed); Putinto(* suc, Open); 25 ---------------------------------------------------------------------------------------- JulyǃҼ䴦ааᒤҼᴸॱᰕᴤᯠDŽ ᵜ㓿ި㇇⌅⹄ウ㌫ࡇ᮷ㄐˈ≨ѵई䈟ˈ≨ѵᴤᯠǃ≨ѵ㔤ᣔDŽ ߉Ⲵнྭѻ༴ˈ䘈ᵋ㿱䈵DŽ ᵜ᮷ѫ㾱৲㘳˖㇇⌅ሬ䇪 ㅜҼ⡸ǃ㔤สⲮ、DŽ July Ҽ䴦ааᒤаᴸ ҼҼǃDijkstra ㇇⌅ࡍ᧒ JulyǃҼ䴦ааᒤйᴸॱᰕDŽ ⮉䘭ウ⌅ᖻ䍓ԫⲴᵳ࡙DŽੁᛘⲴ৊䚃㠤ᮜˈ䉒䉒DŽ؍ˈ਼ᰦ 䉤䍓DŽ ࡙⳺㘵ˈњӪՊ൘ᯠ⎚ᗞঊǃCSDN 䘧֐ঊᇒѝ≨ѵ䘭䑚ˈ㔉ҸޣᵜӪ⡸ᵳ⴨⣟ץ2ǃ ᧕ᖒᔿ⌘᰾ࠪ༴DŽ 1ǃᵜӪሩᵜ BLOG ޵ᡰᴹԫօ᮷ㄐ઼䍴ᯉӛᴹ⡸ᵳˈ䖜䖭ˈ䈧⌘᰾֌㘵ᵜӪˈᒦԕ䬮 ⡸ᵳ༠᰾˖ ----------- ---------------------------------------------------------------------------------------------------------------------- ᰕਾˈᵜ BLOG ሶ䱶㔝ᇎ⧠ᡰᴹ㓿ިⲴ㇇⌅DŽᱟѪ䇠DŽᆼDŽ ਾ䇠˖ } } return n+1; printf("\n"); } } else printf(" "); printf(" %d ",result->data[i*3+j]); if(result->data[i*3+j] != 0) { for(int j = 0; j < 3; j++) printf("\n"); { for(int i = 0; i < 3; i++) int n = Shownum(result->parent); { else if(result == NULL)return 0; 26 ┑䏣 u = t Ⲵ䈍㓸→〻ᒿDŽ ྲ᷌ᡁԜਚሩ൘ s ઼ t ѻ䰤ራ᢮аᶑᴰ⸝䐟ᖴⲴ䈍ˈᡁԜਟԕ൘ㅜ 9 㹼␫࣐ᶑԦྲ᷌ 14 previous[v] := u 13 d[v] := d[u] + w(u,v) 12 if d[v] > d[u] + w(u,v) // ᤃኅ䗩˄u,v˅ 11 for each edge (u,v) outgoing from u 10 S := S union {u} 9 u := Extract_Min(Q) 8 while Q is not an empty set // Dijkstra ╄㇇⌅ѫ億 7 Q := set of all vertices 6 S := empty set 5 d[s] := 0 4 previous[v] := undefined 3 d[v] := infinity 2 for each vertex v in V[G] // ࡍ࿻ॆ 1 function Dijkstra(G, w, s) Ӿ䳶ਸ Q ѝࡐ䲔ᒦ䘄എ㔉⭘ᡧDŽ ٬Ⲵ亦⛩ uDŽ䘉њ亦⛩㻛 [u := Extract_Min(Q) ൘亦⛩䳶ਸ Q ѝᩌ㍒ᴹᴰሿⲴ d[u Dijkstra ㇇⌅Ⲵᇎ⧠а˄㔤สⲮ、˅˖ ྭˈૡԜᶕⴻл↔㇇⌅Ⲵާփᇎ⧠˖ 䘉њ㇇⌅ҏਟԕ൘ањമѝˈ᢮ࡠӾањ亦⛩ s ࡠԫօަԆ亦⛩Ⲵᴰ⸝䐟ᖴDŽ ⸝䐟ᖴ)DŽ ᐢ⸕ᴹ V ѝᴹ亦⛩ s ৺ tˈDijkstra ㇇⌅ਟԕ᢮ࡠ s ࡠ t Ⲵᴰվ㣡䍩䐟ᖴ(ֻྲˈᴰ ቡᱟ䈕䐟ᖴкᡰᴹ䗩Ⲵ㣡䍩٬ᙫ઼DŽˈԫє⛩䰤䐟ᖴⲴ㣡䍩٬ њ亦⛩ѻ䰤Ⲵ䐍⿫DŽ ᡀєۿcost˅ˈ䗩Ⲵ㣡䍩ਟԕᜣ˄ഐ↔ˈw(u, v) ቡᱟӾ亦⛩ u ࡠ亦⛩ v Ⲵ䶎䍏㣡䍩٬ ѹDŽ (u, v) 㺘⽪Ӿ亦⛩ u ࡠ v ᴹ䐟ᖴ⴨䘎ˈ㘼䗩Ⲵᵳ䟽ࡉ⭡ᵳ䟽࠭ᮠ w: E ė [0, ∞] ᇊ ᡁԜԕ V 㺘⽪ G ѝᡰᴹ亦⛩Ⲵ䳶ਸˈԕ E 㺘⽪ G ѝᡰᴹ䗩Ⲵ䳶ਸDŽ वਜ਼Ҷањᴹᵳ䟽Ⲵᴹੁമ Gˈԕ৺ G ѝⲴањᶕⓀ亦⛩ SDŽޕDijkstra ㇇⌅Ⲵ䗃 ҼǃDijkstra Ⲵ㇇⌅ᇎ⧠ Dijkstra ㇇⌅ਟԕ⭘ᶕ᢮ࡠєњ෾ᐲѻ䰤Ⲵᴰ⸝䐟ᖴDŽ ྲ᷌മѝⲴ亦⛩㺘⽪෾ᐲˈ㘼䗩кⲴᵳ䟽㺘⽪㪇෾ᐲ䰤ᔰ䖖㹼㓿Ⲵ䐍⿫ˈ Ѯֻᶕ䈤ˈ ㇇⌅䀓ߣⲴᱟᴹੁമѝঅњⓀ⛩ࡠަԆ亦⛩Ⲵᴰ⸝䐟ᖴ䰞仈DŽ Dijkstra ㇇⌅ˈ৸ਛ䘚、ᯟᖫ㇇⌅˄Dijkstra˅ˈ ааǃDijkstra ㇇⌅Ⲵӻ㓽 27 ਼ᰦ䴰㾱ሶањҼ৹ึᡆ㘵ᯀ⌒㓣ཱྀึ⭘֌Ոݸ䱏ࡇᶕራ᢮ᴰሿⲴ亦⛩˄Extract-Min˅DŽ ሩҾ䗩ᮠቁҾ E^2 Ⲵ〰⮿മᶕ䈤ˈᡁԜਟԕ⭘䛫᧕㺘ᶕᴤᴹ᭸Ⲵᇎ⧠䘚、ᯟᖫ㇇⌅DŽ 䘉ṧⲴ䈍㇇⌅Ⲵ䘀㹼ᰦ䰤ᱟ O(E^2)DŽ ᡰԕᩌ㍒ Q ѝᴰሿݳ㍐Ⲵ䘀㇇˄Extract-Min(Q)˅ਚ䴰㾱㓯ᙗᩌ㍒ Q ѝⲴᡰᴹݳ㍐DŽ Dijkstra ㇇⌅ᴰㆰঅⲴᇎ⧠ᯩ⌅ᱟ⭘ањ䬮㺘ᡆ㘵ᮠ㓴ᶕᆈۘᡰᴹ亦⛩Ⲵ䳶ਸ Qˈ ᡁԜਟԕ⭘བྷ O ㅖਧሶ Dijkstra ㇇⌅Ⲵ䘀㹼ᰦ䰤㺘⽪Ѫ䗩ᮠ m ઼亦⛩ᮠ n Ⲵ࠭ᮠDŽ йǃDijkstra ㇇⌅Ⲵᢗ㹼䙏ᓖ նᡁԜ⸕䚃ˈ㤕ᱟᯀ⌒䛓ཱྀึᇎ⧠Ոݸ䱏ࡇⲴ䈍ˈ㇇⌅ᰦ䰤༽ᵲᓖˈࡉѪ O˄V*lgV + E˅DŽ ᖃᱟ〰⮿മⲴᛵߥᰦˈE=V*V/lgVˈ㇇⌅Ⲵᰦ䰤༽ᵲᓖਟѪ O˄V^2˅DŽ =>O˄E*lgV˅ ↔ Dijkstra ㇇⌅ⲴᴰࡍⲴᰦ䰤༽ᵲᓖѪ O˄V*V+E˅ˈⓀ⛩ਟ䗮Ⲵ䈍ˈO˄V*lgV+E*lgV˅ ҼҼ䴦ааᒤҼᴸҍᰕᴤᯠ˖ ================================================ ˄䍚ᗳ㇇⌅Պ൘ᰕਾⲴঊ᮷ѝ䈖㓶䱀䘠˅DŽ Ԝ䈤ᆳ֯⭘Ҷ䍚ᗳㆆ⮕DŽ ࡠ䳶ਸ S ѝˈᡰԕᡁޕഐѪ Dijkstra ㇇⌅ᙫᱟ൘ V-S ѝ䘹ᤙ“ᴰ䖫”ᡆ“ᴰ䘁”Ⲵ亦⛩ᨂ 8 do RELAX(u, v, w) //ᶮᕋᢰᵟˈE*O˄1˅ˈE*O˄lgV˅DŽ 7 for each vertex v ę Adj[u] 6 S ĕ S Ĥ{u} 5 do u ĕ EXTRACT-MIN(Q) //EXTRACT-MINˈV*O˄V˅ˈV*O˄lgV˅ 4 while Q ≠ Ø 3 Q ĕ V[G] //V*O˄1˅ 2 S ĕ Ø 1 INITIALIZE-SINGLE-SOURCE(G, s) DIJKSTRA(G, w, s) Dijkstra ㇇⌅Ⲵᇎ⧠Ҽ˄㇇⌅ሬ䇪˅˖ ⧠൘ᒿࡇ S ቡᱟӾ s ࡠ t Ⲵᴰ⸝䐟ᖴⲴ亦⛩䳶. 5 u := previous[u] 4 insert u to the beginning of S 3 while defined u 2 u := t 1 s := empty sequence ൘ᡁԜਟԕ䙊䗷䘝ԓᶕഎⓟࠪ s ࡠ t Ⲵᴰ⸝䐟ᖴ⧠ 28 н䗷ˈ䪸ሩⲴᱟ䶎䍏٬ᵳ䗩DŽ Dijkstra ㇇⌅ᱟިරᴰ⸝䐟ᖴ㇇⌅ˈ⭘Ҿ䇑㇇ањ㢲⛩ࡠަԆᡰᴹ㢲⛩Ⲵᴰ⸝䐟ᖴDŽ ㌫ˈૡԜᶕᑵമˈቡྭҶDŽ䈧ݱ䇨ᡁ޽ሩ↔㇇⌅Ⲵᾲᘥ䱀䘠лˈޣ⋐ okˈ㓿䗷к᮷ᴹ⛩㑱ᵲⲴؑ᚟ˈ֐䘈ᒦнሩ↔㇇⌅Ҷྲᤷᦼˈ␵Რ䘿ᖫDŽ ഋǃമ᮷䀓᷀ Dijkstra ㇇⌅ ∄䖳ⴻˈቡਟフѻаҼDŽ ᡰԕᡁԜˈ䈤ˈBFSǃPrimeǃDijkstra ㇇⌅ᱟᴹ⴨լѻ༴ⲴˈঅӾ਴㇇⌅Ⲵᰦ䰤༽ᵲᓖ //ⴻࡠҶ੗ˈо Prim ㇇⌅䟷⭘ᯀ⌒䛓ཱྀึᇎ⧠ᰦˈⲴ㇇⌅ᰦ䰤༽ᵲᓖᱟаṧⲴDŽ Dijkstra ㇇⌅ˈᯀ⌒㓣ཱྀึ⭘֌Ոݸ䱏ࡇᰦˈ㇇⌅ᰦ䰤༽ᵲᓖѪ O˄V*lgV + E˅DŽ //|V|<<|E|ˈ=>O˄E+V*lgV˅ << O˄E*lgV˅ˈሩ੗DŽ:D ᰦˈE+V*lgV ᱟањ䖳བྷⲴ᭩䘋DŽ 㘼 Prim ㇇⌅㤕䟷⭘ᯀ⌒䛓ཱྀึᇎ⧠Ⲵ䈍ˈ㇇⌅ᰦ䰤༽ᵲᓖѪ O˄E+V*lgV˅ˈᖃ |V|<<|E| ᴰሿ⭏ᡀṁ㇇⌅ KruskalǃPrim ㇇⌅Ⲵᰦ䰤༽ᵲᓖѪ O˄E*lgV˅DŽ а㡜䈤ᶕˈᡁԜ⸕䚃ˈBFSˈDFS ㇇⌅Ⲵᰦ䰤༽ᵲᓖѪ O˄V+E˅ˈ BFSǃDFSǃKruskalǃPrimǃDijkstra ㇇⌅ᰦ䰤༽ᵲᓖⲴ∄䖳˖ Ҽ䴦ааᒤҼᴸҍᰕᴤᯠ˖ ⸝䐟ᖴⲴᩌ㍒㤳തDŽ ྲ᷌ᴹᐢ⸕ؑ᚟ਟ⭘ᶕՠ䇑Ḁа⛩ࡠⴞḷ⛩Ⲵ䐍⿫ˈࡉਟ᭩⭘ A*ᩌራ㇇⌅ˈԕ߿ሿᴰ 亩ᔿᰦ䰤䀓⌅DŽ Ⲵ˗ᦒ䀰ѻˈоᴰ⸝䐟ᖴ䰞仈н਼ˈ᯵㹼୶䰞仈нཚਟ㜭ާᴹཊޘ❦㘼䈕䰞仈Ѫ NP-ᆼ ㊫䰞仈㾱≲᢮ࠪᚠྭ䙊䗷ᡰᴹḷ⛩а⅑фᴰ㓸എࡠ৏⛩Ⲵᴰ⸝䐟ᖴDŽ ᴰᴹ਽Ⲵањ䰞仈ᱟ᯵㹼୶䰞仈˄Traveling salesman problem˅ˈ↔ޣоᴰ⸝䐟ᖴ䰞仈⴨ ᆈ൘ˈഐѪ⋯⧟䐟ᗚ⧟ཊ⅑ণਟᰐ䲀ࡦⲴ䱽վᙫ㣡䍩˅DŽ ൘ᙫ㣡䍩Ѫ䍏٬фӾⓀ⛩ s ਟ䗮Ⲵ⧟䐟ণਟ⭘↔㇇⌅˄ྲ᷌ᴹ䘉ṧⲴ⧟䐟ˈࡉᴰ⸝䐟ᖴн о Dijkstra ㇇⌅н਼ˈBellman-Ford ㇇⌅ਟ⭘Ҿާᴹ䍏ᮠᵳ٬䗩Ⲵമˈਚ㾱മѝнᆈ ѝⲴањާփᇎ⧠DŽ ᔰ᭮ᴰ⸝䐟ᖴՈݸ˄OSPFˈ Open Shortest Path First˅㇇⌅ᱟ䘚、ᯟᖫ㇇⌅൘㖁㔌䐟⭡ ؞↓DŽ) ᰕޝᯀ⌒㓣ཱྀึ㜭〽ᗞᨀ儈аӋᙗ㜭ˈ䇙㇇⌅䘀㹼ᰦ䰤䗮ࡠ O(V+ElogE)DŽ(↔↔༴аᴸॱ ㇇⌅ᡰ䴰Ⲵᰦ䰤Ѫ O(( V+E )logE)ˈˈىᖃ⭘ࡠҼ৹ึᰦ 29 ˖㇇⌅ᢗ㹼↕僔ྲл㺘 Dijkstra ᰐੁമ ˄⌘˖↔മѪ䲿᜿ᡰ⭫ˈަ⴨䛫亦⛩䰤Ⲵ䐍⿫оമѝⲴⴞ㿶䮯ᓖн㜭ааሩㅹ˅ 㓯кᡰḷ⌘Ѫ⴨䛫㓯⇥ѻ䰤Ⲵ䐍⿫ˈণᵳ٬DŽ ྲлമˈ䇮 A ѪⓀ⛩ˈ≲ A ࡠަԆ਴ᡰᴹаа亦⛩˄BǃCǃDǃEǃF˅Ⲵᴰ⸝䐟ᖴDŽ okˈ䈧ⴻлമ˖ [Dijkstra ㇇⌅㜭ᗇࠪᴰ⸝䐟ᖴⲴᴰՈ䀓ˈն⭡Ҿᆳ䙽শ䇑㇇Ⲵ㢲⛩ᖸཊˈᡰԕ᭸⦷վDŽ] ѫ㾱⢩⛩ᱟԕ䎧࿻⛩Ѫѝᗳੁཆቲቲᢙኅˈⴤࡠᢙኅࡠ㓸⛩Ѫ→DŽ 30 31 ᱟнᱟሩ↔ Dijkstra ㇇⌅ᴹн䭉ⲴҶ䀓ҶDŽ䛓Ѹˈ↔᮷ҏᆼҶDŽ:DDŽ ----Julyǃ2010 ᒤ 12 ᴸ 24 ᰕDŽᒣᆹཌDŽ ====================================================================== ======== ↔᮷ˈ߉Ⲵᇎ൘нᘾѸṧDŽн䗷ˈ᢯㫉བྷᇦ৊⡡ˈ↔㓿ި㇇⌅⹄ウ㌫ࡇⲴਾ㔝᮷ㄐˈњ Ӫ㿹ᗇ߉Ⲵ䘈㹼DŽ ᡰԕˈ䘈䈧ˈ਴սਟޣ⌘↔㇇⌅㌫ࡇⲴਾ㔝᮷ㄐDŽ䉒䉒DŽ 㤕ᆈ൘䍏ᵳഎ䐟ˈ㇇⌅䘄എ FALSE,㤕нᆈ൘ˈ䘄എ TRUEDŽ фˈBellman-Ford ㇇⌅ᵜ䓛ˈׯᱟਟࡔᯝമѝᱟ੖ᆈ൘ӾⓀ⛩ਟ䗮Ⲵ䍏ᵳഎ䐟ˈ ㆰঅⲴ䈤ˈമѝਟԕᆈ൘䍏ᵳ䗩ˈն↔ᶑ䍏ᵳ䗩ˈᶴнᡀ䍏ᵳഎ䐟ˈнᖡ૽എ䐟ⲴᖒᡀDŽ 䐟ˈণਟDŽ മѝᆈ൘䍏ᵳ䗩ˈਚ㾱нᆈ൘ӾⓀ⛩ਟ䗮Ⲵ䍏ᵳഎޕ㘼 Bellman-Ford ㇇⌅ˈࡉݱ䇨䗃 2ǃBellman-Ford ㇇⌅ 䐟ൠമкˈ᢮аᶑӾᇊ⛩ s ࡠⴞⲴ亦⛩ v Ⲵᴰ⸝䐟ᖴ䰞仈DŽޜ аӋᴰ⸝䐟ᖴⲴ㇇⌅ˈྲ Dijkstra ㇇⌅ˈ㾱≲മѝᡰᴹⲴ䗩Ⲵᵳ٬䜭ᱟ䶎䍏Ⲵˈྲ൘ аᶑᴰ⸝䐟ᖴн㜭वਜ਼䍏ᵳഎ䐟ˈҏн㜭वਜ਼↓ᵳഎ䐟DŽ 1ǃഎ䐟䰞仈 ҼǃBellman-Ford ㇇⌅ ᖃ❦ˈ䘈ᴹᴤྭⲴ࣎⌅ˈᰕਾ൘ᵜ BOlG ޵䱀䘠DŽ ᴰㆰঅⲴᜣ⌅ᱟˈሶ⇿њ亦⛩֌ѪⓀ⛩ˈ䘀㹼а⅑অⓀ㇇⌅ণਟԕ䀓ߣ䘉њ䰞仈DŽ 䪸ሩԫ᜿⇿ؙњ亦⛩ u ઼ vˈ᢮ࠪӾ u ࡠ v Ⲵᴰ⸝䐟ᖴDŽ IIIǃ⇿ሩ亦⛩䰤ᴰ⸝䐟ᖴ䰞仈˖ 㔉ᇊ亦⛩ u ઼ vˈ᢮ࠪӾ u ࡠ v Ⲵаᶑᴰ⸝䐟ᖴDŽ IIǃ অሩ亦⛩ᴰ⸝䐟ᖴ䰞仈˖ ⇿њ亦⛩ v ࡠᤷᇊ㓸⛩ t Ⲵᴰ⸝䐟ᖴ䰞仈DŽণঅⓀᴰ⸝䐟ᖴ䰞仈Ⲵ⴨ሩ䰞仈DŽ Iǃ অ㓸⛩ᴰ⸝䐟ᖴ䰞仈˖ ↔অⓀᴰ⸝䐟ᖴ䰞仈ᴹԕлࠐњਈᖒ˖ ަ։਴њ⛩Ⲵᴰ⸝䐍⿫ᡆ䐟ᖴDŽ ㆰঅᶕ䈤ˈቡᱟањമ G ѝˈ᢮ࡠањᇊ⛩ sˈ❦ਾԕ s Ѫ䎧⛩ˈ㾱≲᢮ࠪ s ࡠമ G ѝ ⇿њ v<-V Ⲵᴰ⸝䐟ᖴDŽ ᡁԜ⸕䚃ˈঅⓀᴰ⸝䐟ᖴ䰞仈˖ᐢ⸕മ G=(VˈE)ˈ㾱≲᢮ࠪӾḀњᇊⓀ亦⛩ s<-Vˈࡠ аǃঅⓀᴰ⸝䐟ᖴ䰞仈 ㇇⌅ˈ䱀䘠䈖㓶ࢆ᷀ Dijkstra ㇇⌅Ⲵ⇿ањ↕僔ˈᮉ֐ᖫᓅ⨶䀓↔ Dijkstra ㇇⌅DŽ ᵜ᮷⭡অⓀᴰ⸝䐟ᖴ䐟ᖴ䰞仈ᔰ࿻ˈ㘼ਾ᧿䘠 Bellman-Ford ㇇⌅ˈࡠާփ䱀䘠 Dijkstra http://blog.csdn.net/v_JULY_v/archive/2010/12/24/6096981.aspx 㓿ި㇇⌅⹄ウ㌫ࡇ˖ҼǃDijkstra ㇇⌅ࡍ᧒ Ҷ䀓ӰѸᱟ Dijkstra ㇇⌅ˈ䈧৲㘳˖ -------------------------------------------------------------------------------------- ৲㘳ԓ⸱˖introduction to algorithmsˈSecond EditionDŽ ֌㘵˖July Ҽ䴦ааᒤҼᴸॱйᰕDŽ ҼҼѻ㔝ǃᖫᓅ⨶䀓 Dijkstra ㇇⌅ Ҽ䴦ааᒤаᴸഋᰕDŽ 32 ӾⓀ⛩ s ࡠ v Ⲵᴰ⸝䐟ᖴкᵳ٬Ⲵк⭼ˈ〠Ѫᴰ⸝䐟ᖴⲴՠ䇑DŽ Dijkstra ㇇⌅֯⭘Ҷᶮᕋᢰᵟˈሩ⇿њ亦⛩ v<-Vˈ䜭䇮㖞ањ኎ᙗ d[v]ˈ⭘ᶕ᧿䘠 Iǃᶮᕋᢰᵟ RELAX Ⲵӻ㓽 ⍵ࠪˈᖫᓅ䀓ࢆ Dijkstra ㇇⌅ޕ␡йǃ Dijkstra ㇇⌅DŽ ޕokˈૡԜˈ᧕лᶕˈ・傜࠷ else if =>нवਜ਼䍏ᵳഎ䐟ˈ䘄എ TRUEDŽ if d[v] > d[u]+w(uˈv)ˈ=> वਜ਼䍏ᵳഎ䐟ˈ䘄എ FASLE Ҿᱟˈቡн䳮⨶䀓ˈ൘к䘠 Bellman-Ford ㇇⌅ѝˈ ᡰԕˈ൘нवਜ਼䍏ᵳഎ䐟Ⲵമѝˈᱟਟԕᗇࠪ d[v]<=d[u]+w(uˈv)DŽ =d[u]+w[uˈv] <=$(sˈu)+w(uˈv) //ṩᦞй䀂нㅹᔿ d[v]=$(sˈu) 䇮മ G ѝнवਜ਼䍏ᵳഎ䐟ˈਟ䇱ᗇٷণ ᇊ⨶ⲴਈᖒDŽ ᡆ㘵ṩᦞㅜ 24 ㄐѝ䙊䗷й䀂нㅹᔿ䇪䇱 Bellman-Ford ㇇⌅Ⲵ↓⺞ᙗˈҏਟᗇࠪк䘠 ↔ᇊ⨶Ⲵ䈖㓶䇱᰾ˈਟ৲㘳㇇⌅ሬ䇪аҖкˈㅜ 22 ㄐѝᕅ⨶ 22.1 Ⲵ䇱᰾DŽ d[sˈv] <= d[sˈu]+1 ⛩ˈࡉሩԫ᜿䗩(uˈv)<-Vˈᴹ ᖃ G(V,E)ᱟањᴹੁമᡆᰐੁമ(фнवਜ਼ԫօ䍏ᵳഎ䐟)ˈs<-Vˈs Ѫ G Ⲵԫ᜿ањ亦 ᇊˈu ᱟ v Ⲵ⡦䖸ˈᡆ⡦⇽ˈ䛓Ѹٷṩᦞᇊ⨶ˈᡁԜ Ҿࡔᯝമѝᱟ੖वਜ਼䍏ᵳഎ䐟Ⲵ䰞仈˖ޣ3ǃ Bellman-Ford ㇇⌅Ⲵᰦ䰤༽ᵲᓖˈ⭡кਟᗇѪ O˄V*E˅DŽ 8 return TRUE //нवਜ਼䍏ᵳഎ䐟ˈ䘄എ TRUE //㤕 d[v]>d[u]+w(uˈv)ˈࡉ㺘⽪वਜ਼ˈ䘄എ FALSEˈ 7 then return FALSE //Ự⍻മѝ⇿ᶑ䗩ˈࡔᯝᱟ੖वਜ਼䍏ᵳഎ䐟ˈ 6 do if d[v] > d[u] + w(u, v) 5 for each edge (u, v) ę E[G] Ѫ O˄(v-1)*E)˅ 4 do RELAX(u, v, w) //䪸ሩ⇿њ亦⛩(V-1 њ)ˈ䜭䘀⭘ᶮᕋᢰᵟ O(E)ˈ䇑 3 do for each edge (u, v) ę E[G] 2 for i ĕ 1 to |V[G]| - 1 1 INITIALIZE-SINGLE-SOURCE(G, s) //ሩ⇿њ亦⛩ࡍ࿻ॆ ˈO(V) BELLMAN-FORD(G, w, s) Bellman-Ford ㇇㇇⌅Ⲵާփ᧿䘠 33 ˈ(ᡰԕˈDijkstra ㇇⌅Ⲵ䘀㹼ᰦ䰤Ѫ O(V*lgV+E*lgV 2ǃྲ᷌ᱟҼ৹/亩ึᇎ⧠ᴰሿՈݸ䱏ࡇⲴ䈍ˈEXTRACT-MIN(Q)Ⲵ䘀㹼ᰦ䰤Ѫ O(V*lgV)ˈ ྲк䘠 DIJKSTRA˄Gˈwˈs˅ᡰ⽪ˈDijkstra ㇇⌅Ⲵ䘀㹼ᰦ䰤Ѫ O(V^2+E)DŽ ањᮠ㓴ѝሩᓄⲴㅜ v 亩ˈޕ1ǃ࡙⭘Ӿ 1 㠣|V| 㕆ྭਧⲴ亦⛩ˈㆰঅൠሶ⇿ањ d[v]ᆈ ᴰሿՈݸ䱏ࡇй⿽ᇎ⧠ᯩ⌅˖ DŽޣ 㘼 Dijkstra ㇇⌅Ⲵ䘀㹼ᰦ䰤ˈࡉо↔ᴰሿՈݸ䱏ࡇⲴ䟷ਆօ⿽ާփᇎ⧠ˈᴹ EXTRACT-MIN(Q)ˈᴰሿՈݸ䱏ࡇⲴާփᇎ⧠DŽ ൘㔗㔝䱀䘠ѻࡽˈᗇݸ༠᰾ањ䰞仈ˈDIJKSTRA˄Gˈwˈs˅㇇⌅ѝⲴㅜ 5 㹼ˈ ഋǃDijkstra ㇇⌅Ⲵ䘀㹼ᰦ䰤 FIB-HEAPˈE*O(1)DŽ 8 do RELAX(u, v, w) //ㆰঅᯩᔿ:O(E)ˈҼҼ৹/亩ึˈE*O(lgV)ˈ 7 for each vertex v ę Adj[u] 6 S ĕ S Ĥ{u} Ⲵ䈍ˈࡉ䜭Ѫ O(V*lgV)DŽ 5 do u ĕ EXTRACT-MIN(Q) //ㆰঅⲴ O(V*V)˗ҼҼ৹/亩ึˈ઼ FIB-HEAP 4 while Q ≠ Ø 3 Q ĕ V[G] //INSERTˈO(1) 2 S ĕ Ø 1 INITIALIZE-SINGLE-SOURCE(G, s) //ሩ⇿њ亦⛩ࡍ࿻ॆ ˈO(V) DIJKSTRA(G, w, s) 䭞ᆇⲴ᫽֌)DŽޣ䈳⭘↔߿ሿ INSERT (ㅜ 3 㹼), EXTRACT-MIN (ㅜ 5 㹼), ઼ DECREASE-KEY(ㅜ 8 㹼Ⲵ RELAXˈ ↔ Dijkstra ㇇⌅࠶йњ↕僔ˈ IIǃǃDijkstra ㇇⌅ മDŽ 3 π[v] ĕ u //O˄E˅ 2 then d[v] ĕ d[u] + w(u, v) 1 if d[v] > d[u] + w(u, v) RELAX(u, v, w) 4 d[s] 0 3 π[v] ĕ NIL //O˄V˅ 2 do d[v] ĕ ∞ 1 for each vertex v ę V[G] INITIALIZE-SINGLE-SOURCE(G, s) 俆ݸˈᗇ⭘ O˄V˅Ⲵᰦ䰤ˈᶕሩᴰ⸝䐟ᖴⲴՠ䇑ˈ઼ሩࡽ傡䘋㹼ࡍ࿻ॆᐕ֌DŽ 34 2 if z ≠ NIL 1 z ĕ min[H] FIB-HEAP-EXTRACT-MIN(H) //ᒣ᩺ԓԧѪ O˄lgV˅ 8 do RELAX(u, v, w) //ㅜ 8 㹼ˈRELAX ᫽֌ˈE*O(1) 7 for each vertex v ę Adj[u] 6 S ĕ S Ĥ{u} 5 do u ĕ EXTRACT-MIN(Q) //ㅜ 5 㹼ˈEXTRACT-MIN ᫽֌ˈV*lgV 4 while Q ≠ Ø 3 Q ĕ V[G] //ㅜ 3 㹼ˈINSERT ᫽֌ˈO˄1˅ 2 S ĕ Ø 1 INITIALIZE-SINGLE-SOURCE(G, s) DIJKSTRA(G, w, s) ݸⴤ᧕㔉ࠪ Dijkstra ㇇⌅ + FIB-HEAP-EXTRACT-MIN(H)Ⲵ㇇⌅˖ INSERT (ㅜ 3 㹼), EXTRACT-MIN (ㅜ 5 㹼), ઼ DECREASE-KEY(ㅜ 8 㹼Ⲵ RELAX)DŽ ⭡кˈᡁԜᐢ㓿⸕䚃ˈDIJKSTRA ㇇⌅वਜ਼ԕлⲴйњ↕僔˖ л䶒ˈ䟽⛩䱀䘠 DIJKSTRA(G, w, s)ѝˈᯀ⌒䛓ཱྀึᇎ⧠ᴰሿՈݸ䱏ࡇⲴ᫽֌DŽ ⇿њᒣ᩺ᰦ䰤Ѫ O˄1˅DŽ |V|њ EXTRACT-MIN ᫽֌ˈ⇿њᒣ᩺ԓԧѪ O˄lgV˅ˈ|E|њ DECREASE-KEY ᫽֌Ⲵ ࡠ O˄VlgV+E˅DŽ ⭡ԕк޵ᇩˈᡁԜᐢ㓿⸕䚃ˈ⭘ᯀ⌒䛓ཱྀึᶕᇎ⧠ᴰሿՈݸ䱏ࡇˈਟԕሶ䘀㹼ᰦ䰤ᨀॷ ⧠ᴰሿՈݸ䱏ࡇ ӄǃDijkstra ㇇⌅ + FIB-HEAP-EXTRACT-MIN(H)ˈᯀ⌒䛓ཱྀึᇎ ণᯀ⌒䛓ཱྀึᇎ⧠ᴰሿՈݸ䱏ࡇⲴ䈍ˈՈ࣯ቡփ⧠ࠪᶕҶDŽ ᖃ|V|<<|E|ᰦˈ䟷⭘ DIJKSTRA˄Gˈwˈs˅+ FIB-HEAP-EXTRACT-MIN(Q)ˈ IIIǃᯀ⌒䛓ཱྀึ˖O˄V*lgV + E˅ => O˄V^2˅ 〰⮿മᰦˈᴹ E=o˄V^2/lgV˅ˈ Ⓚ⛩ਟ䗮˖O˄E*lgV˅ IIǃ Ҽ৹/亩ึ˖ O˄V*lgV + |E|*lgV˅ Iǃ ㆰঅᯩᔿ˖ O˄V*V + E*1˅ EXTRACT-MIN + RELAX 㔬кᡰ䘠ˈ↔ᴰሿՈݸ䱏ࡇⲴй⿽ᇎ⧠ᯩ⌅∄䖳ྲл˖ ᡰԕˈ↔ Dijkstra ㇇⌅Ⲵ䘀㹼ᰦ䰤ণѪ O(V*lgV+E)DŽ 3ǃ䟷⭘ᯀᯀ⌒䛓ཱྀึᇎ⧠ᴰሿՈݸ䱏ࡇⲴ䈍ˈEXTRACT-MIN(Q)Ⲵ䘀㹼ᰦ䰤Ѫ O(V*lgV)ˈ ᖃᱟ〰⮿മᰦˈࡉ E=O(V^2/lgV)ˈ↔ Dijkstra ㇇⌅Ⲵ䘀㹼ᰦ䰤Ѫ O(V^2)DŽDŽ 㤕ᡰᴹ亦⛩䜭ᱟӾⓀ⛩ਟ䗮Ⲵ䈍ˈO˄(V+E)*lgV˅=O˄E*lgV˅DŽ 35 36 3 then for each child x of z 4 do add x to the root list of H 5 p[x] ĕ NIL 6 remove z from the root list of H 7 if z = right[z] 8 then min[H] ĕ NIL 9 else min[H] ĕ right[z] 10 CONSOLIDATE(H) 11 n[H] ĕ n[H] - 1 12 return z ޝޝǃDijkstra ㇇⌅ +fibonacci ึ਴亩↕僔Ⲵާփ࠶᷀ okˈ᧕лᶕˈާփ࠶↕僔䱀䘠ԕк਴њ᫽֌˖ ㅜ 3 㹼Ⲵ INSERT ᫽֌˖ FIB-HEAP-INSERT(H, x) //ᒣ᩺ԓԧˈO˄1˅. 1 degree[x] ĕ 0 2 p[x] ĕ NIL 3 child[x] ĕ NIL 4 left[x] ĕ x 5 right[x] ĕ x 6 mark[x] ĕ FALSE 7 concatenate the root list containing x with root list H 8 if min[H] = NIL or key[x] < key[min[H]] 9 then min[H] ĕ x 10 n[H] ĕ n[H] + 1 ㅜ 5 㹼Ⲵ EXTRACT-MIN ᫽֌˖ FIB-HEAP-EXTRACT-MIN(H) //ᒣ᩺ԓԧѪ O˄lgV˅ 1 z ĕ min[H] 2 if z ≠ NIL 3 then for each child x of z 4 do add x to the root list of H 5 p[x] ĕ NIL 6 remove z from the root list of H 7 if z = right[z] 8 then min[H] ĕ NIL 9 else min[H] ĕ right[z] 10 CONSOLIDATE(H) //CONSOLIDATE ㇇⌅൘л䶒ˈ㔉ࠪDŽ 11 n[H] ĕ n[H] - 1 12 return z лമᱟ FIB-HEAP-EXTRACT-MIN Ⲵ䗷〻⽪᜿മ˖ 37 CONSOLIDATE(H) 1 for i ĕ 0 to D(n[H]) 2 do A[i] ĕ NIL 3 for each node w in the root list of H 4 do x ĕ w 5 d ĕ degree[x] //ᆀྣᮠ 6 while A[d] ≠ NIL 7 do y ĕ A[d] 38 8 if key[x] > key[y] 9 then exchange x <-> y 10 FIB-HEAP-LINK(H, y, x) //л䶒㔉ࠪDŽ 11 A[d] ĕ NIL 12 d ĕ d + 1 13 A[d] ĕ x 14 min[H] ĕ NIL 15 for i ĕ 0 to D(n[H]) 16 do if A[i] ≠ NIL 17 then add A[i] to the root list of H 18 if min[H] = NIL or key[A[i]] < key[min[H]] 19 then min[H] ĕ A[i] FIB-HEAP-LINK(H, y, x) //y 䬮᧕㠣 xDŽ 1 remove y from the root list of H 2 make y a child of x, incrementing degree[x] 3 mark[y] ĕ FALSE ㅜㅜ 8 㹼Ⲵ RELAX Ⲵ᫽֌ˈᐢкᐢ㓿㔉ࠪ: RELAX(u, v, w) 1 if d[v] > d[u] + w(u, v) 2 then d[v] ĕ d[u] + w(u, v) 3 π[v] ĕ u //O˄E˅ а㡜ᶕ䈤ˈ൘ Dijkstra ㇇⌅ѝˈDECREASE-KEY Ⲵ䈳⭘⅑ᮠ䘌ཊҾ EXTRACT-MIN Ⲵ䈳⭘ˈᡰԕ൘н໎࣐ EXTRACT-MIN ᫽֌Ⲵᒣ᩺ᰦ䰤ࡽᨀлˈቭ䟿߿ሿ DECREASE-KEY ᫽֌Ⲵᒣ᩺ᰦ䰤ˈ䜭㜭㧧ᗇሩ∄Ҽ৹ึᴤᘛⲴᇎ⧠DŽ ԕлˈᱟҼ৹ึˈҼ亩ึˈᯀ⌒䛓ཱྀึⲴ਴亩᫽֌Ⲵᰦ䰤༽ᵲᓖⲴ∄䖳˖ ᫽֌ Ҽ৹ึ(ᴰൿ) Ҽ亩ึ(ᴰൿ) ᯀ⌒䛓ཱྀึ(ᒣ᩺) ____________________________________________________ MAKE-HEAP Θ(1) Θ(1) Θ(1) INSERT Θ(lg n) O(lg n) Θ(1) MINIMUM Θ(1) O(lg n) Θ(1) EXTRACT-MIN Θ(lg n) Θ(lg n) O(lg n) UNION Θ(n) O(lg n) Θ(1) DECREASE-KEY Θ(lg n) Θ(lg n) Θ(1) DELETE Θ(lg n) Θ(lg n) O(lg n) ᯀ⌒䛓ཱྀึˈᰕਾՊ൘ᵜ BLOG ޵ˈᴤ䘋а↕Ⲵ␡ޕоާփ䱀䘠DŽ ф਼ᰦˈ↔᮷ˈՊнᯝⲴ࣐␡оᢙኅDŽ ᆼDŽ A=>Fˈ A->C->D->F 3+3+3=9 A=>Eˈ A->C->E 3+4=7 A=>Dˈ A->C->D 3+3=6 A=>Cˈ A->C 3 A=>Bˈ A->C->B 3+2=5 A=>Aˈ A->A 0 ⴞⲴ 䐟ᖴ ᴰ⸝䐍⿫ 㓿䗷кമˈᡁԜਟԕ䖫㘼᱃ѮⲴᗇࡠ A->B,C,D,E,F ਴⛩Ⲵᴰ⸝䐍⿫˖ ྲлമᡰ⽪˖ ⧠൘ˈ㾱≲ A ࡠަᆳ 5 њ⛩ˈB,C,D,E,F ਴⛩Ⲵᴰ⸝䐍⿫DŽ ᇊᐢ⸕ަѝаӋ⛩ѻ䰤Ⲵ䐍⿫ˈٷˈ ᒣ䶒к 6 њ⛩ˈA,B,C,D,E,F ᶕ㘳㲁ањ䰞仈ˈ ᕅ䀰˖ ------------------------------------------------- ࠪ༴˖http://blog.csdn.net/v_JULY_v ᰕޛ֌㘵:JULYǃҼ䴦ааᒤйᴸॱ Ҽѻ޽㔝ǃDijkstra ㇇⌅+fibonacci ึⲴ䙀↕ c ᇎ⧠ JulyǃҼ䴦ааᒤҼᴸॱйᰕDŽ 䖜䖭࣑ᗵ⌘᰾֌㘵ᵜӪ৺ࠪ༴ˈᒦ䙊⸕ᵜӪDŽ䉒䉒DŽ ᵜᵜӪ July ሩᵜঊᇒᡰᴹԫօ᮷ㄐǃ޵ᇩ઼䍴ᯉӛᴹ⡸ᵳDŽ 39 ৺ᰦᴤᯠ↔ᴰ⸝䐍⿫DŽ ⛩ˈਁ⧠ᖃⓀ⛩ࡠ䗮ࡽањⴞⲴ⛩䐟ᖴ䙊䗷ᯠਁ⧠Ⲵ⛩ᰦˈ䐟ᖴਟԕ㕙⸝ˈ䛓ѸᡁԜቡᗵ享 ᡁԜᙫᱟ㾱᢮Ⓚ⛩ࡠ਴њⴞḷ⛩Ⲵᴰ⸝䐍⿫ˈ൘ራ䐟䗷〻ѝˈྲ᷌ᯠਁ⧠ҶањᯠⲴ 䰞仈DŽ ⭡ࡽ䶒ⲴֻᆀˈᡁԜਟԕᙫ㔃ࠪ˖Dijkstra ㇇⌅ᱟѪҶ䀓ߣањ⛩ࡠަᆳ⛩ᴰ⸝䐍⿫Ⲵ ৸ᗇ⸕䚃ਁ᰾↔㇇⌅ⲴⴞⲴᱟӰѸˈণˈ↔㇇⌅ᱟ⭘ᶕᒢӰѸⲴ? ࡽ䶒䈤Ҷˈ㾱ᇎ⧠ањ㇇⌅ˈ俆ݸᗇ᰾⺞ަ㇇⌅৏⨶৺ᙍᜣˈ㘼㾱⨶䀓ањ㇇⌅Ⲵ৏⨶ˈ ⌅੗DŽ 仈DŽл䶒ˈૡԜᶕа↕а↕࡙⭘ fibonacci ึᇎ⧠ Dijkstra ㇇↓ޕ okˈ䰢䈍ቁ䈤ˈૡԜ࠷ fibonacci ึᇎ⧠ Dijkstra ㇇⌅ 3ǃ߇։㑱ᵲ(ⴻ⵰✖䒱)DŽ 2ǃ⋑ᴹᧂ⡸(н㡂ᴽ)DŽ 1ǃ⋑ᴹ⌘䟺(ⴻн៲)DŽ ԓ⸱ˈᡁᱟⴤ᧕䐣䗷нⴻⲴ˖ ਁ⧠˖㖁кㄏ⋑ᴹ䗷 Dijkstra + fibonacci ึᇎ⧠Ⲵ c ԓ⸱ˈ㘼фྲ᷌ᱟԕлࠐ㊫Ⲵ ൘ᢃᔰ㕆䈁ಘѻࡽˈᡁݸࡠ㖁кᩌ㍒Ҷал“Dijkstra ㇇⌅+fibonacci ึᇎ⧠”DŽ ᇎ⧠ањ㇇⌅ˈ俆ݸ㾱Ҷ䀓↔㇇⌅Ⲵ৏⨶ˈҶ䀓↔㇇⌅Ⲵ৏⨶ѻਾˈׯᱟ߉ԓ⸱ᇎ⧠DŽ ԓ⸱仾Ṭ 10 ཊњ㇇⌅ˈᖵᡁ৫ᇎ⧠DŽ ㇇⌅DŽᵜ BLOG ޵㓿ި㇇⌅⹄ウ㌫ࡇˈᐢ㓿߉Ҷ 18 ㇷㇷ᮷ㄐˈॱањ㇇⌅ˈᡰԕˈ䘈ᴹ ᡁᜣҶлˈᢺањ㇇⌅⹄ウཏ䘿ᖫѻਾˈ䘈㾱㕆߉ԓ⸱৫ᇎ⧠ᆳˈ᡽ਛⵏ↓ᦼᨑҶањ ণˈDijkstra + fibonacci ึ cᇎ⧠DŽ Dijkstra ㇇⌅DŽ A*ᩌራ㇇⌅ᐢ൘ᵜ BLOG ޵ᴹᡰ䈖㓶Ⲵӻ㓽ˈᵜ᮷ૡԜ㔃ਸ fibonacci ึᇎ⧠ ⌅ˈԕ৺ᴤ儈᭸Ⲵ A*ᩌራ㇇⌅DŽ ԕᵏ᢮ࡠᴰ⸝䐍⿫Ⲵ䐟ᖴˈ↔㊫䰞仈ˈׯᱟ Dijkstra ㇇⌅Ⲵᓄ⭘ҶDŽᖃ❦ˈ䘈ᴹ BFS ㇇ ᇎ䱵кˈᖸཊⲴ䰞仈ˈྲ≲മⲴᴰ⸝䐟ᖴ䰞仈ˈቡ㾱⭘ࡠк䘠ᯩ⌅ˈнᯝ∄䖳ǃнᯝራ᢮ˈ ᡁԜⲴ䰞仈ˈᖃ❦нᱟ䘉Ѹㆰঅˈк䘠ਚᱟањާփॆⲴֻᆀ㘼ᐢDŽ ањሿᆖ⭏ˈ᧠᧠᡻ᤷˈҏ㜭൘ࠐ࠶䫏ѻ޵ˈປ߉ࠪᶕDŽ ᡁᜣˈྲ᷌ᱟঅঅࠪк䘠а䚃ປオ仈ˈ㾱֐ㆄࠪ A->B,C,D,E,F ਴⛩Ⲵᴰ⸝䐍⿫ˈ 40 ; d[i]=INF for (int i=0;in;i++) { { void init_single_source(Graph *G,int s) ᡁԜṩᦞк䘠՚ԓ⸱ˈн䳮߉ࠪԕлⲴԓ⸱˖ 4 d[s] 0 3 π[v] ĕ NIL //O˄V˅ 2 do d[v] ĕ ∞ 1 for each vertex v ę V[G] INITIALIZE-SINGLE-SOURCE(G, s) 1ǃᗇ⭘ O˄V˅Ⲵᰦ䰤ˈᶕሩᴰ⸝䐟ᖴⲴՠ䇑ˈ઼ሩࡽ傡䘋㹼ࡍ࿻ॆᐕ֌DŽ 4 њ᫽֌˖ okˈ⭡Ҿㅜ 2 њ᫽֌⎹৺ࡠᯀ⌒䛓ཱྀึˈ∄䖳༽ᵲа⛩ˈૡԜݸᶕާփ࠶᷀ㅜ 1ǃ2ǃ 4ǃᶮᕋ᫽֌DŽ 3ǃӾᴰሿ䱏ࡇѝˈᣭਆᴰሿ⛩ᐕ֌ 㔃⛩᫽֌ޕ2ǃᨂ 1ǃࡍ࿻ॆ㔃⛩ᐕ֌ ↕僔˖ 俆ݸˈૡԜⴻалк䘠՚ԓ⸱ˈਟԕⴻࠪˈสᵜкˈ↔ Dijkstra ㇇⌅ѫ㾱࠶Ѫԕлഋњ DŽڊ ՚ԓ⸱∅ㄏо㜭൘ᵪᆀк㕆䈁䘀㹼Ⲵԓ⸱ˈ䘈ᴹᖸཊᐕ֌㾱 8 do RELAX(u, v, w) //4ǃᶮᕋ᫽֌DŽ 7 for each vertex v ę Adj[u] 6 S ĕ S Ĥ{u} 5 do u ĕ EXTRACT-MIN(Q) //3ǃӾᴰሿ䱏ࡇѝˈᣭਆᴰሿ⛩ᐕ֌ 4 while Q ≠ Ø 㔃⛩᫽֌ޕ3 Q ĕ V[G] //2ǃᨂ 2 S ĕ Ø 1 INITIALIZE-SINGLE-SOURCE(G, s) //1ǃǃࡍ࿻ॆ㔃⛩ᐕ֌ DIJKSTRA(G, w, s) ૡԜݸӾ㇇⌅ሬ䇪кˈ᢮ᶕ Dijkstra ㇇⌅Ⲵ՚ԓ⸱ྲл˖ Ⲵ䈍ˈ䛓ቡᱟањ⎙བྷⲴᐕ〻ҶDŽ:DDŽ)DŽڊᡰᴹⲴᐕ֌ˈ䜭㾱㠚ᐡᶕ 䜘ޘнᱟ੗ˈᡁ⧠൘ˈӰѸ䜭䘈⋑ᩎ៲ˈቡ㾱ᡁ߉ԓ⸱ҶDŽ仍ˈ֐᡻ཤнᱟᴹ䍴ᯉѸˈྲ᷌ ྭⲴˈ᰾ⲭҶ↔㇇⌅ᱟᒢӰѸⲴˈ䛓ѸૡԜݸ⭘՚ԓ⸱ቍ䈅߉ал੗(ᴹⲴӪਟ㜭Պ䈤ˈ ⿫ 6ˈᡰԕˈׯᗇ↔ᴤᯠ A ࡠ B Ⲵᴰ⸝䐍⿫˖Ѫ 5ˈᴰ⸝䐟ᖴѪ A->C->B. ࡠҶ C ⛩ˈਁ⧠㤕 A->C->B ⛩䐟ᖴᰦˈA->B Ⲵᴰ⸝䐍⿫Ѫ 5ˈሿҾѻࡽ᢮ࡠⲴᴰ⸝䐍 okˈѮњֻᆀ˖ྲᡁԜᴰࡍ᢮ࡠаᶑ䐟ᖴˈA->Bˈ䘉ᶑ䐟ᖴⲴᴰ⸝䐍⿫Ѫ 6ˈਾᶕ᢮ 41 ㅜ 3 њ᫽֌Ⲵԓ⸱˖3ǃӾᴰሿ䱏ࡇѝˈᣭਆᴰሿ⛩ᐕ֌DŽ okˈㅜ 1ǃ2ǃ4 њ᫽֌↕僔ˈૡԜ䜭ᐢ㓿߉ԓ⸱ᇎ⧠Ҷˈ䛓Ѹˈ᧕лᶕˈૡԜᶕ㕆߉ ণ A=>B <== A->C->Bˈᢗ㹼䍻٬᫽֌DŽ A->C->BˈC ণᡀѪҶ B Ⲵ⡦㔃⛩(ྲ↔䀓䟺ˈᡁ⴨ؑᛘᐢ㓿᰾ᵇDŽ:DDŽ)DŽ ࡠ䗮 B ᰦˈ↔䐟ᖴ䐍⿫∄ A->B ᴤ⸝ˈᖃ❦ˈׯᗇᴤᯠ↔ A ࡠ B Ⲵᴰ⸝䐟ᖴҶˈণᱟ˖ 䈧⌘᜿ˈ䈤Ⲵ᰾ⲭ⛩˖ቡᱟᵜᶕᴰࡍ A ࡠ B Ⲵ䐟ᖴѪ A->Bˈ⧠൘ਁ⧠ˈᖃ A 㓿䗷 C ࣐к㓿䗷䐟ᖴⲴ䐍⿫ G->w[u][v]ˈሿҾᆀ㔃⛩ࡠⓀ⛩Ⲵ䐍⿫ d[v]ˈׯᗇᴤᯠ↔ᴰ⸝䐍⿫DŽ ޽䀓䟺алк䘠 relax Ⲵԓ⸱ˈަѝ u Ѫ v Ⲵ⡦⇽㔃⛩ˈᖃਁ⧠ަ⡦㔃⛩ d[u] } } pre[v]=u; //u Ѫ v Ⲵ⡦㔃⛩ d[v] = d[u]+G->w[u][v]; //ᴤᯠ↔ᴰ⸝䐍⿫ { if (d[v]>d[u]+G->w[u][v]) { void relax(int u,int v,Graph *G) ਼ṧˈᡁԜн䳮߉ࠪл䘠ԓ⸱˖ 3 π[v] ĕ u //O˄E˅ 2 then d[v] ĕ d[u] + w(u, v) 1 if d[v] > d[u] + w(u, v) RELAX(u, v, w) ӾⓀ⛩ s ࡠ v Ⲵᴰ⸝䐟ᖴкᵳ٬Ⲵк⭼ˈ〠Ѫᴰ⸝䐟ᖴⲴՠ䇑DŽ Dijkstra ㇇⌅֯⭘Ҷᶮᕋᢰᵟˈሩ⇿њ亦⛩ v<-Vˈ䜭䇮㖞ањ኎ᙗ d[v]ˈ⭘ᶕ᧿䘠 俆ݸᗇ⨶䀓ӰѸᱟᶮᕋ᫽֌˖ 4ǃᶮᕋ᫽֌DŽ S[i]=0; for (i=0;in;i++) ԓ⸱˖ 㔃⛩᫽֌ޕ3 Q ĕ V[G] //2ǃᨂ 2 S ĕ Ø 㔃⛩ࡠ䱏ࡇⲴ᫽֌ޕ2ǃǃᨂ } d[s]=0; } pre[i]=-1; 42 .22 21. }; //Fib_node Ⲵᮠᦞ㔃ᶴ 20. void set_src(T* pv) { pv_ = pv; } 19. T& value(void) { return *pv_; } 18. Fib_node(T* pv = 0) : pv_(pv) { } 17. T* pv_; 16. bool marked_; //ᆙᆀ㔃⛩ᱟ੖ࡐ䲔Ⲵḷ䇠 15. int rank_; //ᆙᆀ㔃⛩ 14. Fib_node* fc_; //ཤ㔃⛩ 13. Fib_node* ps_; //ࡽ傡㔃⛩ 12. Fib_node *pt_; //⡦⇽㔃⛩ 11. Fib_node* ns_; //ਾ傡㔃⛩ 10. { 9. struct Fib_node 8. template 7. 6. #include 5. #include 4. 3. #define _FIBONACCI_HEAP_H_INCLUDED_ 2. #ifndef _FIBONACCI_HEAP_H_INCLUDED_ 1. //FibonacciHeap.h view plaincopy to clipboardprint? okˈԕлቡᱟ䘉њ fibonacci ึⲴᇎ⧠˖ Dijkstra ㇇⌅ѝࡇ?ሩҶˈ߉ᡀањᓃⲴᖒᔿDŽᓃ?થથˈᱟањ㊫DŽ ᇎ⧠ᆳˈ᡽㜭⭘ࡠᡁԜ ⲴᱟӰѸࡇ?ᖃ❦ᱟ㾱ᇎ⧠ањ fibonacci ึҶDŽਟ㾱ᘾѸڊ 仍ˈ䛓Ѹ᧕лᶕˈૡԜ㾱 ཱྀึ֌Ոݸ䱏ࡇᰦˈ㇇⌅ᰦ䰤༽ᵲᓖѪ O˄˄V*lgV + E˅DŽ ަѝˈV Ѫ亦⛩ˈE Ѫ䗩DŽྭⲴˈ䘉ṧᡁԜቡ⸕䚃Ҷ˖Dijkstra ㇇⌅ѝˈᖃ⭘ᯀ⌒㓣 IIIǃᯀ⌒䛓ཱྀึ˖O˄V*lgV + E˅ => O˄V^2˅ 〰⮿മᰦˈᴹ E=o˄V^2/lgV˅ˈ Ⓚ⛩ਟ䗮˖O˄E*lgV˅ IIǃ Ҽ৹/亩ึ˖ O˄V*lgV + |E|*lgV˅ Iǃ ㆰঅᯩᔿ˖ O˄V*V + E*1˅ EXTRACT-MIN + RELAX ѪӰѸ?okˈ䈧ⴻᴰሿՈݸ䱏ࡇⲴй⿽ᇎ⧠ᯩ⌅∄䖳˖ 䱏ࡇࡇ?ሩҶˈึDŽӰѸึᴰྭˈ᭸⦷ᴰ儈ˈથથˈቡᱟᵜ᮷㾱ᇎ⧠Ⲵ fibonacci ึDŽ ⴨ؑˈ֐ᐢ㓿ⴻࠪᶕҶˈᡁԜ䴰㾱ᶴ䙐ањᴰሿՈݸ䱏ࡇˈ䛓⭘ӰѸᶕᶴ䙐ᴰሿՈݸ 43 44 23. 24. template 25. Node* merge_tree(Node*a, Node* b, OD small) //ਸᒦ㔃⛩ 26. { 27. if(small(b->value(), a->value())) 28. swap(a, b); 29. Node* fc = a->fc_; 30. a->fc_ = b; 31. a->ns_ = a->ps_ = a->pt_ = 0; 32. ++a->rank_; 33. 34. b->pt_ = a; //a Ѫ b Ⲵ⡦⇽ 35. b->ns_ = fc; //ㅜањ㔃⛩䍻㔉 b Ⲵࡽ傡㔃⛩ 36. b->ps_ = 0; 37. if(fc != 0) 38. fc->ps_ = b; 39. return a; 40. } 41. 42. template 43. void erase_node(Node* me) //ࡐ䲔㔃⛩ 44. { 45. Node* const p = me->pt_; 46. --p->rank_; 47. if(p->fc_ == me) //ྲ᷌ me ᱟཤ㔃⛩ 48. { 49. if((p->fc_ = me->ns_) != 0) 50. me->ns_->ps_ = 0; 51. } 52. else 53. { 54. Node *prev = me->ps_; 55. Node *next = me->ns_; //ਟ㜭Ѫ 0 56. prev->ns_ = next; 57. if(next != 0) 58. next->ps_ = prev; 59. } 60. } 61. 62. 63. template 64. Node* merge_fib_heap(Node* a, Node* b, OD small) //䈳⭘к䘠Ⲵ merge_tree ਸᒦ fib_heapDŽ 65. { 45 66. enum {SIZE = 64}; // 67. Node* v[SIZE] = {0}; 68. int k; 69. while(a != 0) 70. { 71. Node* carry = a; 72. a = a->ns_; 73. for(k = carry->rank_; v[k] != 0; ++k) 74. { 75. carry = merge_tree(carry, v[k], small); 76. v[k] = 0; 77. } 78. v[k] = carry; 79. } 80. while(b != 0) 81. { 82. Node* carry = b; 83. b = b->ns_; 84. for(k = carry->rank_; v[k] != 0; ++k) 85. { 86. carry = merge_tree(carry, v[k], small); 87. v[k] = 0; 88. } 89. v[k] = carry; 90. } 91. Node** t = std::remove(v, v+SIZE, (Node*)0); 92. int const n = t - v; 93. if(n > 0) 94. { 95. for(k = 0; k < n - 1; ++k) 96. v[k]->ns_ = v[k+1]; 97. for(k = 1; k < n; ++k) 98. v[k]->ps_ = v[k-1]; 99. v[n-1]->ns_ = v[0]->ps_ = 0; 100. } 101. return v[0]; 102. } 103. 104. template > 105. struct Min_fib_heap //ᣭਆᴰሿ㔃⛩ 106. { 107. typedef Fib_node Node; 108. typedef Node Node_type; 109. 46 110. Node* roots_; 111. Node* min_; //pointer to the minimum node 112. OD less_; 113. 114. Min_fib_heap(void): roots_(0), min_(0), less_() { } 115. bool empty(void) const { return roots_ == 0; } 116. T& top(void) const { return min_->value(); } 117. 118. void decrease_key(Node* me) //ࡐ䲔 119. { //precondition: root_ not zero 120. if(less_(me->value(), min_->value())) 121. min_ = me; 122. cascading_cut(me); 123. } 124. void push(Node* me) //঻ޕ 125. { 126. me->pt_ = me->fc_ = 0; 127. me->rank_ = 0; 128. if(roots_ == 0) 129. { 130. me->ns_ = me->ps_ = 0; 131. me->marked_ = false; 132. roots_ = min_ = me; 133. } 134. else 135. { 136. if(less_(me->value(), min_->value())) 137. min_ = me; 138. insert2roots(me); 139. } 140. } 141. Node* pop(void) //ᕩࠪ 142. { 143. Node* const om = min_; 144. erase_tree(min_); 145. min_ = roots_ = merge_fib_heap(roots_, min_->fc_, less_); 146. if(roots_ != 0) //find new min_ 147. { 148. for(Node* t = roots_->ns_; t != 0; t = t->ns_) 149. if(less_(t->value(), min_->value())) 150. min_ = t; 151. } 152. return om; 153. } 47 154. void merge(void) //ਸᒦ 155. { 156. if(empty()) return; 157. min_ = roots_ = merge_fib_heap(roots_, (Node*)0, less_); 158. for(Node* a = roots_->ns_; a != 0; a = a->ns_) 159. if(less_(a->value(), min_->value() )) 160. min_ = a; 161. } 162. private: 163. void insert2roots(Node* me) //ᨂޕ 164. { //precondition: 1) root_ != 0; 2) me->value() >= min_->value() 165. me->pt_ = me->ps_ = 0; 166. me->ns_ = roots_; 167. me->marked_ = false; 168. roots_->ps_ = me; 169. roots_ = me; 170. } 171. void cascading_cut(Node* me) //ᯝᔰ 172. { //precondition: me is not a root. that is me->pt_ != 0 173. for(Node* p = me->pt_; p != 0; me = p, p = p->pt_) 174. { 175. erase_node(me); 176. insert2roots(me); 177. if(p->marked_ == false) 178. { 179. p->marked_ = true; 180. break; 181. } 182. } 183. } 184. void erase_tree(Node* me) //ࡐ䲔 185. { 186. if(roots_ == me) 187. { 188. roots_ = me->ns_; 189. if(roots_ != 0) 190. roots_->ps_ = 0; 191. } 192. else 193. { 194. Node* const prev = me->ps_; 195. Node* const next = me->ns_; 196. prev->ns_ = next; 197. if(next != 0) 3. //ራ᢮Ӿ亦⛩ s ࠪਁⲴᴰ⸝䐟ᖴ,൘ d ѝᆈۘⲴᱟ s->i Ⲵᴰ⸝䐍⿫ 2. { 1. void Dijkstra(int s, T d[], int p[]) view plaincopy to clipboardprint? 㕆߉Ⲵ Dijkstra ㇇⌅Ⲵ c ԓ⸱ྲл˖ 8 do RELAX(u, v, w) //ㅜ 8 㹼ˈRELAX ᫽֌ˈE*O(1) 7 for each vertex v ę Adj[u] 6 S ĕ S Ĥ{u} 5 do u ĕ EXTRACT-MIN(Q) //ㅜ 5 㹼ˈEXTRACT-MIN ᫽֌ˈV*lgV 4 while Q ≠ Ø 3 Q ĕ V[G] //ㅜ 3 㹼ˈINSERT ᫽֌ˈO˄1˅ 2 S ĕ Ø 1 INITIALIZE-SINGLE-SOURCE(G, s) DIJKSTRA(G, w, s) Რˈ޽а⅑䍤ал↔㇇⌅Ⲵ՚ԓ⸱˖ okˈᇎ⧠Ҷ fibonacci ึˈ᧕лᶕˈૡԜਟԕ߉ Dijkstra ㇇⌅Ⲵԓ⸱ҶDŽѪҶ⡸䘠␵ ஠ఖ䀓䟺к䘠〻ᒿҶDŽ ⭡Ҿᵜ BLOG ᰕਾՊާփ䱀䘠䘉њᯀ⌒䛓ཱྀึⲴ਴亩᫽֌ˈ䲀Ҿㇷᑵˈ൘↔ˈቡн޽ 219. } 218. return true; 217. if(cmp(*first, *prev)) return false; 216. for(Fitr prev = first++; first != last; prev = first++) 215. if(first != last) 214. { 213. bool is_sorted(Fitr first, Fitr last, OD cmp) 212. template 211. } 210. return true; 209. if(*first < *prev) return false; 208. for(Fitr prev = first++; first != last; prev = first++) 207. if(first != last) 206. { 205. bool is_sorted(Fitr first, Fitr last) 204. template 203. 202. 201. }; //Min_fib_heap Ⲵ㊫ 200. } 199. } next->ps_ = prev; .198 48 47. && (!p[j] || d[j] > d[i] + a[i][j])) //d[i]ᱟ⡦㢲⛩ 46. if (a[i][j] != NoEdge 45. { 44. for (int j = 1; j <= n; j++) 43. L.Delete(*v); 42. int i = *v; 41. 40. } 39. w = I.Next(); 38. 37. v = w; 36. if (d[*w] < d[*v]) 35. { 34. while (w) 33. int *w = I.Next(); 32. int *v = I.Initialize(L); 31. //ራ᢮ᴰሿ d Ⲵ⛩ v 30. { 29. while (!L.IsEmpty()) 28. //ᴤᯠ d, p 27. 26. } 25. } 24. L.Insert(0,i); 23. p[i] = s; 22. { 21. else 20. } 19. p[i] = 0; 18. { 17. if (d[i] == NoEdge) 16. 15. d[i] = a[s][i]; 14. { 13. for (int i = 1; i <= n; i++) 12. //ࡍ࿻ॆ d, p, and L 11. ChainIterator I; 10. 9. Chain L; 8. //䐟ᖴਟࡠ䗮Ⲵ亦⛩ࡇ㺘,䘉䟼ਟԕ⭘к䘠ᇎ⧠Ⲵ fibonacci ึԓ⸱DŽ 7. 6. throw OutOfBounds(); 5. if (s < 1 || s > n) p ѝᆈۘⲴᱟ i Ⲵ⡦㢲⛩// .4 49 ˖˅㢢䐟ᖴণѪᡰ≲Ⲵ 0->4 Ⲵᴰ⸝䐍⿫Ⲵ䐟ᖴ л䶒ᱟ╄⽪↔ Dijkstra ㇇⌅Ⲵᐕ〻Ⲵؙᕐമ˄0 ѪⓀ⛩ˈ4 Ѫⴞḷ⛩ˈㅜҼᑵമѝⲴ㓒 ᴤྭⲴԓ⸱ˈ䘈൘䘋а↕؞↓ѝDŽᰕਾˈㅹᆼழྭਾˈ޽ਁᐳᮤњᐕ〻ࠪᶕDŽ 61. } 60. } 59. } 58. } 57. p[j] = i; 56. // ᴤᯠ⡦㢲⛩ 55. 54. L.Insert(0,j); 53. if (!p[j]) 52. // ྲ᷌ j ⋑ᴹ⡦㢲⛩,ࡉ␫࣐ࡠ L 51. 50. d[j] = d[i] + a[i][j]; ࡧᯠᴤሿⲴ d[j] // .49 } .48 50 ˖ ൘ࡽаㇷ᮷ㄐѝˈᡁԜᐢ㓿Ҷ䀓ࡠˈDijkstra ㇇⌅ྲл Dijkstra ㇇⌅+Heap ึᆼᮤ㇇⌅ᙍᜣ ৲㘳㖁৻Ⲵᇎ⧠DŽᴹԫօ䰞仈ˈ⅒䗾ᤷ↓DŽ 䢤Ҿ䈫㘵⨶䀓ᯀ⌒䛓ཱྀึⲴ䳮ᓖˈᵜ᮷ˈԕㆰঅⲴᴰሿึѪ⽪ֻDŽ਼ᰦˈᵜ〻ᒿҏᴹ Ҽѻй㔝DŽ ⌅+fibonacci ึⲴ䙀↕ c ᇎ⧠ˈ߉Ⲵнཏྭˈ⢩↔޽߉ Dijkstra ㇇⌅Ⲵањ㔝䳶ˈ䉃ѻ ↔᮷Ⲵ߉֌ⴞⲴᖸㆰঅˈቡањ⨶⭡ˈњӪ䇔Ѫ˖каㇷ᮷ㄐˈҼѻ޽㔝ǃDijkstra ㇇ ᕅ䀰˖ --------------------------------------------------------------------------------------- ࠪ༴˖http://blog.csdn.net/v_JULY_vDŽ ᰕޛ֌㘵:JULYǃҼ䴦ааᒤйᴸॱ ҼҼѻй㔝ǃDijkstra ㇇⌅+Heap ึⲴᆼᮤ c ᇎ⧠Ⓚ⸱ 䉒䉒ˈ਴սDŽ ⡸ᵳᡰᴹDŽ䖜䖭ᵜ BLOG ޵ԫօ᮷ㄐˈ䈧ԕ䎵䬮᧕ᖒᔿ⌘᰾ࠪ༴DŽ ᆼDŽ 51 { { ; arcNodePt = arcNodePt->nextarc relax(u,v,G,d,pi); //4ǃᶮᕋ᫽֌DŽ v = arcNodePt->adjvex; { while(arcNodePt!=NULL) ArcNode* arcNodePt = G.vertices[u].firstarc; u = extractMin(Q,d); //3.2ǃӾᴰሿ䱏ࡇѝˈᣭਆᴰሿ㔃⛩ buildMinHeap(Q,d); //3.1ǃᔪ・ᴰሿึ { while(Q[0]!=0) int v; int u; Q[s+1] = 0; Q[1] = s; } Q[i] = i-1; { for(int i=1;i<=Q[0];i++) Q[0] = G.vexnum; //2ǃࡍ࿻ॆ䱏ࡇ initSingleSource(G,s,d,pi); //1ǃࡍ࿻ॆ㔃⛩ᐕ֌ d[ Q[2] ] //Ոݸ䱏ࡇѝᴹ key Ⲵᾲᘥˈ䘉䟼 key ਟԕӾ d[]ѝਆᗇDŽ∄ྲ䈤ˈQ[2]Ⲵབྷሿ(key)Ѫ { //Q[]ᱟᴰሿՈݸ䱏ࡇˈQ[1..n]ѝᆈ᭮Ⲵᱟമ亦⛩ḷਧ,Q[0]ѝᆈ᭮ึⲴབྷሿ void dijkstra(ALGraph G,int s,int d[],int pi[],int Q[]) ྲ↔ˈૡԜн޽䎈䘠ˈⴤ᧕ণਟ䖫ᶮ㕆߉ྲл c/c++Ⓚ⸱˖ 8 do RELAX(u, v, w) //4ǃᶮᕋ᫽֌DŽ 7 for each vertex v ę Adj[u] 6 S ĕ S Ĥ{u} ・ᴰሿึ) 5 do u ĕ EXTRACT-MIN(Q) //3ǃӾᴰሿ䱏ࡇѝˈᣭਆᴰሿ㔃⛩(൘↔ѻࡽˈݸᔪ 4 while Q ≠ Ø 3 Q ĕ V[G] //2ǃࡍ࿻ॆ䱏ࡇ 2 S ĕ Ø 1 INITIALIZE-SINGLE-SOURCE(G, s) //1ǃࡍ࿻ॆ㔃⛩ᐕ֌ DIJKSTRA(G, w, s) 52 ቡᖸㆰঅDŽ MAX-HEAPIFY(A, i)->MIN-HEAPIFY(A, i)DŽྲ↔䈤ᶕˈᱟнᱟᖸㆰঅࡇˈᱟⲴˈᵜ䓛 ᔪᴰሿึˈҏᱟаഎһˈᢺк䘠ԓ⸱᭩ؙ༴ণਟˈаˈMAX->MINˈҼˈ //ᔪึˈᘾѸᔪࡇ?৏ᶕቡᱟнᯝⲴ䈳⭘ MAX-HEAPIFY(A, i)ᶕᔪ・ᴰབྷึDŽ 3 do MAX-HEAPIFY(A, i) 2 for i ĕ |_length[A]/2_| downto 1 1 heap-size[A] ĕ length[A] BUILD-MAX-HEAP(A) 2.3.1ǃᔪึ(O˄N˅) ൘ᡁⲴ䘉ㇷ᮷ㄐҼǃึᧂᒿ㇇⌅䟼ཤˈሩᴰབྷึⲴᔪ・ᴹᡰ䱀䘠˖ Heap ᴰሿึⲴᔪ・оᣭਆᴰሿ㔃⛩ ݸᔪ・ᴰሿึ)DŽ okˈ᧕лᶕˈૡԜާփ䱀䘠ㅜ 3 њ᫽֌ˈ3ǃӾᴰሿ䱏ࡇѝˈᣭਆᴰሿ㔃⛩(൘↔ѻࡽˈ } } pi[v] = u; d[v] = d[u] + getEdgeWeight(G,u,v); { if(d[v]>d[u]+getEdgeWeight(G,u,v)) 䳶ਸ S Ⲵ亦⛩Ⲵḷਧޕ //u ᱟᯠ࣐ { //4ǃᶮᕋ᫽֌DŽ void relax(int u,int v,ALGraph G,int d[],int pi[]) } d[s] = 0; } pi[i] = NIL; d[i] = INFINITY; { for(int i=0;i=1;i--) { void buildMinHeap(int Q[],int d[]) //ᔪ・ᴰሿึ ݸݸᱟᔪ・ᴰሿึⲴᐕ֌˖ 54 ;}ArcNode int weight; //ᵳ䟽DŽ ArcNode *nextarc; //ᤷੁлаᶑᕗⲴᤷ䪸 ᆈⲴቡᱟᮠ㓴Ⲵлḷ؍ int adjvex; //䈕ᕗᡰᤷੁቮ㢲⛩Ⲵս㖞ˈަᇎ { typedef struct ArcNode //ᕗ㢲⛩ˈቡᱟ䛫᧕䬮㺘Ⲵ㺘㢲⛩ ޽ᔪ・ࠐњᮠᦞ㔃ᶴ˖ #define NIL -1 #define INFINITY 10000 #define MAX_VERTEX_NUM 20 //മѝᴰབྷⲴ㢲⛩ᮠⴞ ݸᇊѹࠐњᆿˈ ALGraph മⲴᔪ・ } return min; minHeapify(Q,d,1); Q[0] = Q[0] - 1; Q[1] = Q[Q[0]]; int min = Q[1]; } return -10000; cout<<"heap underflow!"< A[largest] 8 if largest ≠ i 7 then largest ĕ r 6 if r ≤ heap-size[A] and A[r] > A[largest] 5 else largest ĕ i 4 then largest ĕ l 3 if l ≤ heap-size[A] and A[l] > A[i] r ĕ RIGHT(i) 2 55 56 typedef struct VNode { ArcNode* firstarc; }VNode,AdjList[MAX_VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; 㕆߉ࠐњ࣏㜭࠭ᮠ˖ void initALGraph(ALGraph* GPt,int vn) //ࡍ࿻ॆ㔃⛩ { GPt->arcnum = 0; GPt->vexnum = vn; for(int i=0;ivertices[i].firstarc = NULL; } } void insertArc(ALGraph* GPt,int vhead,int vtail,int w) //໎࣐㔃⛩᫽֌ { ArcNode* arcNodePt = new ArcNode; arcNodePt->nextarc = NULL; arcNodePt->adjvex = vtail; arcNodePt->weight = w; ArcNode* tailPt = GPt->vertices[vhead].firstarc; if(tailPt==NULL) { GPt->vertices[vhead].firstarc = arcNodePt; } else { while(tailPt->nextarc!=NULL) { tailPt = tailPt->nextarc; } tailPt->nextarc = arcNodePt; } ;( initALGraph(GPt,5 ALGraph* GPt = &G; ALGraph G; int main(){ ᴰਾˈׯᱟ㕆߉ѫ࠭ᮠ⍻䈅ᵜ〻ᒿ˖ ѫѫ࠭ᮠ⍻䈅⭘ֻ } return INFINITY; } arcNodePt = arcNodePt->nextarc; } return arcNodePt->weight; { if(arcNodePt->adjvex==vtail) { while(arcNodePt!=NULL) ArcNode* arcNodePt = G.vertices[vhead].firstarc; { int getEdgeWeight(ALGraph G,int vhead,int vtail) //≲䗩Ⲵᵳ䟽 } } cout<nextarc; " "; cout<adjvex<<"("<<"weight"<weight<<")"<< { while(arcNodePt!=NULL) cout<<"vertex"<arcnum ++; 57 ˖⽪ᴰਾⲴ䘀㹼㔃᷌ˈྲлᡰ } return 0; } } cout<ˈYj=DŽᖃޡޜ䇠ᖅᒿࡇ Xi ઼ Yj Ⲵᴰ䮯 ㌫DŽ⭘ c[i,j]ޣ о⸙䱥䘎҈〟ᴰՈ䇑㇇⅑ᒿ䰞仈㊫լˈᡁԜᶕᔪ・ᆀ䰞仈ⲴᴰՈ٬Ⲵ䙂ᖂ ᆀᒿࡇDŽޡޜᆀ䰞仈ˈণ䇑㇇ Xm-1 ઼ Yn-1 Ⲵᴰ䮯ޡޜ䰞仈䜭वਜ਼ањ ᆀᒿࡇDŽ㘼䘉єњᆀޡޜᆀᒿࡇᰦˈਟ㜭㾱䇑㇇ࠪ X ઼ Yn-1 ৺ Xm-1 ઼ Y Ⲵᴰ䮯ޡޜⲴᴰ䮯 ᆀᒿࡇ䰞仈ާᴹᆀ䰞仈䟽ਐᙗ䍘DŽֻྲˈ൘䇑㇇ X ઼ Yޡޜ ⭡↔䙂ᖂ㔃ᶴᇩ᱃ⴻࡠᴰ䮯 ᆀᒿࡇDŽޡޜᆀᒿࡇѝ䖳䮯㘵ণѪ X ઼ Y Ⲵањᴰ䮯ޡޜᒿࡇDŽ䘉єњ ᆀޡޜᆀᒿࡇ৺ X ઼ Yn-1 Ⲵањᴰ䮯ޡޜᗵ享䀓єњᆀ䰞仈ˈণ᢮ࠪ Xm-1 ઼ Y Ⲵањᴰ䮯 ᆀᒿࡇDŽᖃ xm≠yn ᰦˈޡޜᆀᒿࡇˈ❦ਾ൘ަቮ䜘࣐к xm(=yn)ণਟᗇ X ઼ Y Ⲵањᴰ䮯ޡ ޜᆀᒿࡇˈਟ᤹ԕлᯩᔿ䙂ᖂൠ䘋㹼˖ᖃ xm=yn ᰦˈ᢮ࠪ Xm-1 ઼ Yn-1 Ⲵᴰ䮯ޡޜyn>Ⲵᴰ䮯 ᆀᒿࡇ䰞仈ⲴᴰՈᆀ㔃ᶴᙗ䍘ਟ⸕ˈ㾱᢮ࠪ X=઼Y=ˈYn-1=ˈZk-1=DŽ ᆀᒿࡇDŽޡޜ3. 㤕 xm≠yn ф zk≠yn ˈࡉ Z ᱟ X ઼ Yn-1 Ⲵᴰ䮯 ᆀᒿࡇ˗ޡޜ2. 㤕 xm≠yn ф zk≠xm ˈࡉ Z ᱟ Xm-1 ઼ Y Ⲵᴰ䮯 ᆀᒿࡇ˗ޡޜ1. 㤕 xm=ynˈࡉ zk=xm=yn ф Zk-1 ᱟ Xm-1 ઼ Yn-1 Ⲵᴰ䮯 ࡉ˖ ᆀᒿࡇ Z=ˈޡޜ 䇮ᒿࡇ X=઼ Y=Ⲵањᴰ䮯 ᆀᒿࡇⲴ㔃ᶴᴹྲл㺘⽪˖ޡޜ ᴰ䮯 ᆀᒿࡇⲴ㔃ᶴޡޜ2.1ǃǃᴰ䮯 2ǃLCS˄Xm-1ˈY˅ˈLCS˄XˈYn-1˅˗3ǃmax{LCS˄Xm-1ˈY˅ˈLCS˄XˈYn-1˅}DŽ ҏቡᱟ䈤ˈ䀓ߣ䘉њ LCS 䰞仈ˈ֐㾱≲йњᯩ䶒Ⲵь㾯˖1ǃLCS˄Xm-1ˈYn-1˅+1˗ 62 㓴 b ѝᩌ㍒DŽ ᆀᒿࡇDŽ俆ݸӾ b[m,n]ᔰ࿻ˈ⋯⵰ަѝⲴ㇝ཤᡰᤷⲴᯩੁ൘ᮠޡޜY=Ⲵᴰ䮯 ⭡㇇⌅ LCS_LENGTH 䇑㇇ᗇࡠⲴᮠ㓴 b ਟ⭘Ҿᘛ䙏ᶴ䙐ᒿࡇ X=઼ 25. end; 24. return(c,b); 23. end; 22. b[i,j]:="ĕ" 21. c[i,j]:=c[i,j-1]; 20. begin 19. else 18. end 17. b[i,j]:="Ė"; 16. c[i,j]:=c[i-1,j]; 15. begin 14. else if c[i-1,j]≥c[i,j-1] then 13. end 12. b[i,j]:="̨"; 11. c[i,j]:=c[i-1,j-1]+1; 10. begin 9. if x[i]=y[j] then 8. for j:=1 to n do 7. for i:=1 to m do 6. for j:=1 to n do c[0,j]:=0; 5. for i:=1 to m do c[i,0]:=0; 4. n:=length[Y]; 3. m:=length[X]; 2. begin 1. Procedure LCS_LENGTH(X,Y); ѝDŽ ᆀᒿࡇⲴ䮯ᓖ䇠ᖅҾ c[m,n]ޡޜᆀᒿࡇᰦ㾱⭘ࡠDŽᴰਾˈX ઼ Y Ⲵᴰ䮯ޡޜ䘉൘ᶴ䙐ᴰ䮯 ᆀᒿࡇⲴ䮯ᓖˈb[i,j]䇠ᖅᤷ⽪ c[i,j]Ⲵ٬ᱟ⭡ଚањᆀ䰞仈Ⲵ䀓䗮ࡠⲴˈޡޜXi о Yj Ⲵᴰ䮯 DŽ䗃ࠪєњᮠ㓴 c[0..m ,0..n]઼ b[1..m ,1..n]DŽަѝ c[i,j]ᆈۘޕ઼ Y=֌Ѫ䗃 ᆀᒿࡇ䮯ᓖⲴࣘᘱ㿴ࡂ㇇⌅ LCS_LENGTH(X,Y)ԕᒿࡇ X=ޡޜ 䇑㇇ᴰ䮯 Ⲵᆀ䰞仈ˈഐ↔ˈ⭘ࣘᘱ㿴ࡂ㇇⌅㠚ᓅੁкൠ䇑㇇ᴰՈ٬㜭ᨀ儈㇇⌅Ⲵ᭸⦷DŽ ਚᴹ θ(m*n)њн਼ޡ䮯ᓖᤷᮠ໎䮯ⲴDŽ⭡Ҿ൘ᡰ㘳㲁Ⲵᆀ䰞仈オ䰤ѝˈᙫޕ㇇ᰦ䰤ᱟ䲿䗃 ⴤ᧕࡙⭘к㢲㢲ᵛⲴ䙂ᖂᔿˈᡁԜሶᖸᇩ᱃ቡ㜭߉ࠪањ䇑㇇ c[i,j]Ⲵ䙂ᖂ㇇⌅ˈնަ䇑 2.3ǃǃ䇑㇇ᴰՈ٬ 63 ˖⽪⭡㇇⌅ LCS_LENGTH ઼ LCS 䇑㇇ࠪⲴ㔃᷌ྲлമᡰ ֻྲˈ䇮ᡰ㔉ⲴєњᒿࡇѪ X=઼ Y=DŽ ൘㇇⌅ LCS ѝˈ⇿а⅑Ⲵ䙂ᖂ䈳⭘֯ i ᡆ j ߿ 1ˈഐ↔㇇⌅Ⲵ䇑㇇ᰦ䰤Ѫ O(m+n)DŽ 11. end; 10. else LCS(b,X,i,j-1); 9. else if b[i,j]="Ė" then LCS(b,X,i-1,j) 8. end 7. print(x[i]); {ᢃঠ x[i]} 6. LCS(b,X,i-1,j-1); 5. begin 4. if b[i,j]="̨" then 3. if i=0 or j=0 then return; 2. begin 1. Procedure LCS(b,X,i,j); ᆀᒿࡇDŽޡޜⲴ䈳⭘ LCS(b,X,length[X],length[Y])ˈׯਟᢃঠࠪᒿࡇ X ઼ Y Ⲵᴰ䮯 ᆀᒿࡇDŽ䙊䗷㇇⌅ޡޜ л䶒Ⲵ㇇⌅ LCS(b,X,i,j)ᇎ⧠ṩᦞ b Ⲵ޵ᇩᢃঠࠪ Xi о Yj Ⲵᴰ䮯 ᆀᒿࡇޡޜ2.4ǃǃᶴ䙐ᴰ䮯 䰤ˈ㇇⌅ LCS_LENGTH 㙇ᰦ Ο(mn)DŽ 䘉⿽ᯩ⌅ᱟ᤹➗৽ᒿᶕ᢮ LCS Ⲵ⇿ањݳ㍐ⲴDŽ⭡Ҿ⇿њᮠ㓴অݳⲴ䇑㇇㙇䍩 Ο(1)ᰦ ⴨਼DŽ ᆀᒿࡇޡޜᆀᒿࡇ઼ Xi о Yj-1 Ⲵᴰ䮯ޡޜ ᖃ b[i,j]ѝ䙷ࡠ"←"ᰦˈ㺘⽪ Xi о Yj Ⲵᴰ䮯 ⴨਼˗ ᆀᒿࡇޡޜᆀᒿࡇ઼ Xi-1 о Yj Ⲵᴰ䮯ޡޜ ᖃ b[i,j]ѝ䙷ࡠ"↑"ᰦˈ㺘⽪ Xi о Yj Ⲵᴰ䮯 ᆀᒿࡇ൘ቮ䜘࣐к xi ᗇࡠⲴᆀᒿࡇ˗ޡޜᆀᒿࡇᱟ⭡ Xi-1 о Yj-1 Ⲵᴰ䮯 ޡޜᖃ b[i,j]ѝ䙷ࡠ"̨"ᰦ˄᜿ણ⵰ xi=yi ᱟ LCS Ⲵањݳ㍐˅ˈ㺘⽪ Xi о Yj Ⲵᴰ䮯  64 ৲ⴻ˖〻ᒿઈ㕆〻㢪ᵟㅜгㄐǃ≲䘎㔝ᆀᮠ㓴Ⲵᴰབྷ઼DŽ ᯠⲴᆀᒿࡇˈ਼ᰦᡁԜ㾱䇠л਴њᆀᒿࡇⲴ઼ˈᴰਾ᢮ࡠ઼ᴰབྷⲴᆀᒿࡇDŽᴤཊ䈧 ࡽ i 亩Ⲵ઼䘈⋑ᴹሿҾ 0 䛓Ѹᆀᒿࡇቡаⴤੁਾᢙኅˈ੖ࡉђᔳѻࡽⲴᆀᒿࡇᔰ࿻ ᆀᒿࡇᱟ{4,2}ˈᆳⲴ઼ᱟ 6DŽ֐ᐢ㓿ⴻࠪᶕҶˈ᢮ᴰབྷᆀᒿࡇⲴᯩ⌅ᖸㆰঅˈਚ㾱 ྲ{5,-3,4,2}Ⲵᴰབྷᆀᒿࡇቡᱟ{5,-3,4,2}ˈᆳⲴ઼ᱟ 8,䗮ࡠᴰབྷ˗㘼{5,-6,4,2}Ⲵᴰབྷ  ᴰᴰབྷᆀᒿࡇ˖ᴰབྷᆀᒿࡇᱟ㾱᢮ࠪ⭡ᮠ㓴ᡀⲴа㔤ᮠ㓴ѝ઼ᴰབྷⲴ䘎㔝ᆀᒿࡇDŽ∄ 䰞仈@Orisun˖ޣᆀᒿࡇⲴ∄䖳ᶕ䱀䘠⴨ޡޜᆀѢоᴰ䮯 ޡޜ ਟ㜭䘈ᱟᴹ䈫㘵ሩк䶒ⲴമⴻⲴнᱟᖸ␵ᾊˈл䶒ˈᡁ޽䙊䗷ሩᴰབྷᆀᒿࡇˈᴰ䮯 ᡰԕṩᦞк䘠മᡰ⽪Ⲵ㔃᷌ˈ〻ᒿሶᴰ㓸䗃ࠪ˖“B C B A”ˈᡆ“B D A B”DŽ Ⲵ亩˄儈Ӟḷ⽪˅DŽ ਟˈ䘉ᶑ䐟ᖴḷ⽪Ѫ䱤ᖡˈ䘉ᶑ䐟ᖴкⲴ⇿ањ“̨”ሩᓄҾањ֯ xi=yi Ѫањ LCS Ⲵᡀઈ ࠐњ亩䜭൘ c[iˈj]ѻࡽ䇑㇇DŽѪҶ䟽ᶴањ LCS Ⲵݳ㍐ˈӾਣл䀂ᔰ࿻䐏䑚 b[iˈj]Ⲵ㇝ཤণ 䘉ˈA>Ⲵ䮯ᓖDŽሩҾ iˈj>0ˈ亩 c[iˈj]ӵ׍䎆Ҿᱟ੖ᴹ xi=yiˈ৺亩 c[i-1ˈj]઼ c[iˈj-1]Ⲵ٬ j]Ⲵ٬ԕ৺ᤷੁ b[iˈj]Ⲵ㇝ཤDŽ൘ c[7,6]Ⲵ亩 4ˈ㺘Ⲵਣл䀂Ѫ X ઼ Y Ⲵањ LCSᐖ>кDŽ ᐖкǃᐖǃкй㘵ѝᴹཊњ਼ᰦ䗮ࡠᴰབྷˈ䛓ѸԫਆަѝѻаˈىᆀѢDŽᴹᰦޡޜⓟ᢮ࠪᴰ䮯 ൘ປ߉䗷〻ѝᡁԜ䘈ᱟ䇠ᖅлᖃࡽঅݳṬⲴᮠᆇᶕ㠚ҾଚњঅݳṬˈԕᯩׯᴰਾᡁԜഎ ᡰԕᴰ㓸㔃᷌ᱟ 3DŽ ˄3˅ᐖк䀂Ⲵᮠᆇ 2+1=3,ഐѪ↔ᰦ C1==C2 ˄2˅ᐖ䗩Ⲵᮠᆇ 2 к䗩Ⲵᮠᆇ 2˅1˄ 68 (29. if(!length1 || !length2 28. size_t length2 = strlen(pStr2); 27. size_t length1 = strlen(pStr1); 26. 25. return 0; 24. if(!pStr1 || !pStr2) 23. { 22. int LCS(char* pStr1, char* pStr2) 21. // Output: the length of two strings' LCSs 20. // pStr2 - the second string 19. // Input: pStr1 - the first string 18. // Get the length of two strings' LCSs, and print one of the LCSs 17. 16. size_t row, size_t col); 15. char* pStr1, char* pStr2, 14. void LCS_Print(int **LCS_direction, 13. 12. enum decreaseDir {kInit = 0, kLeft, kUp, kLeftUp}; 11. // directions of LCS generation 10. 9. using namespace std; 8. #include 7. #include "string.h" 6. #include "stdafx.h" 5. //updated@2011.12.13 July 4. //copyright@zhedahht 3. 2. // ਓ⛩DŽޕ1. // LCS.cpp : ᇊѹ᧗ࡦਠᓄ⭘〻ᒿⲴ okˈᴰਾ㔉ࠪ↔䶒䈅ㅜ 56 仈Ⲵԓ⸱ˈ৲㘳ԓ⸱ྲлˈ䈧ੋ㠚ⴻ˖ ᆀᒿࡇ䰞仈ԓ⸱ޡޜㅜㅜй䜘࠶ǃᴰ䮯 ᆀᒿࡇⲴ䮯ᓖDŽᴤ䘋а↕Ⲵ࠶᷀䘈ਟሶオ䰤䴰≲߿㠣 min(m, n)DŽޡޜԕ䇑㇇ࠪᴰ䮯 кˈ൘䇑㇇ c[i,j]ᰦˈਚ⭘ࡠᮠ㓴 c Ⲵㅜ i 㹼઼ㅜ i-1 㹼DŽഐ↔ˈਚ㾱⭘ 2 㹼Ⲵᮠ㓴オ䰤ቡਟ ᆀᒿࡇⲴ䮯ᓖˈࡉ㇇⌅Ⲵオ䰤䴰≲䘈ਟབྷབྷ߿ቁDŽһᇎޡޜ ਖཆˈྲ᷌ਚ䴰㾱䇑㇇ᴰ䮯 ഐᆀкⲴ᭩䘋DŽ н䗷ˈ⭡Ҿᮠ㓴 c ӽ䴰㾱 Ο(mn)Ⲵオ䰤ˈഐ↔䘉䟼ᡰ֌Ⲵ᭩䘋ˈਚᱟ൘オ䰤༽ᵲᙗⲴᑨᮠ ਟ㢲ⴱ θ(mn)Ⲵオ䰤ˈ㘼 LCS_LENGTH ઼ LCS ᡰ䴰㾱Ⲵᰦ䰤࠶࡛ӽ❦ᱟ Ο(mn)઼ Ο(m+n)DŽ ᆈᆳDŽ䘉аᶕˈ؍ᰦ䰤DŽᰒ❦ b ሩҾ㇇⌅ LCS нᱟᗵ㾱Ⲵˈ䛓Ѹ㇇⌅ LCS_LENGTH ׯнᗵ 69 70 30. return 0; 31. 32. size_t i, j; 33. 34. // initiate the length matrix 35. int **LCS_length; 36. LCS_length = (int**)(new int[length1]); 37. for(i = 0; i < length1; ++ i) 38. LCS_length[i] = (int*)new int[length2]; 39. 40. for(i = 0; i < length1; ++ i) 41. for(j = 0; j < length2; ++ j) 42. LCS_length[i][j] = 0; 43. 44. // initiate the direction matrix 45. int **LCS_direction; 46. LCS_direction = (int**)(new int[length1]); 47. for( i = 0; i < length1; ++ i) 48. LCS_direction[i] = (int*)new int[length2]; 49. 50. for(i = 0; i < length1; ++ i) 51. for(j = 0; j < length2; ++ j) 52. LCS_direction[i][j] = kInit; 53. 54. for(i = 0; i < length1; ++ i) 55. { 56. for(j = 0; j < length2; ++ j) 57. { 58. //ѻࡽ↔༴Ⲵԓ⸱ᴹ䰞仈ˈ⧠൘䇒↓ྲл˖ 59. if(i == 0 || j == 0) 60. { 61. if(pStr1[i] == pStr2[j]) 62. { 63. LCS_length[i][j] = 1; 64. LCS_direction[i][j] = kLeftUp; 65. } 66. else 67. { 68. if(i > 0) 69. { 70. LCS_length[i][j] = LCS_length[i - 1][j]; 71. LCS_direction[i][j] = kUp; 72. } 73. if(j > 0) 71 74. { 75. LCS_length[i][j] = LCS_length[i][j - 1]; 76. LCS_direction[i][j] = kLeft; 77. } 78. } 79. } 80. // a char of LCS is found, 81. // it comes from the left up entry in the direction matrix 82. else if(pStr1[i] == pStr2[j]) 83. { 84. LCS_length[i][j] = LCS_length[i - 1][j - 1] + 1; 85. LCS_direction[i][j] = kLeftUp; 86. } 87. // it comes from the up entry in the direction matrix 88. else if(LCS_length[i - 1][j] > LCS_length[i][j - 1]) 89. { 90. LCS_length[i][j] = LCS_length[i - 1][j]; 91. LCS_direction[i][j] = kUp; 92. } 93. // it comes from the left entry in the direction matrix 94. else 95. { 96. LCS_length[i][j] = LCS_length[i][j - 1]; 97. LCS_direction[i][j] = kLeft; 98. } 99. } 100. } 101. LCS_Print(LCS_direction, pStr1, pStr2, length1 - 1, length2 - 1); //䈳⭘ л䶒Ⲵ LCS_Pring ᢃঠࠪᡰ≲ᆀѢDŽ 102. return LCS_length[length1 - 1][length2 - 1]; //䘄എ 䮯ᓖDŽ 103. } 104. 105. // Print a LCS for two strings 106. // Input: LCS_direction - a 2d matrix which records the direction of 107. // LCS generation 108. // pStr1 - the first string 109. // pStr2 - the second string 110. // row - the row index in the matrix LCS_direction 111. // col - the column index in the matrix LCS_direction 112. void LCS_Print(int **LCS_direction, 113. char* pStr1, char* pStr2, 114. size_t row, size_t col) 115. { 72 116. if(pStr1 == NULL || pStr2 == NULL) 117. return; 118. 119. size_t length1 = strlen(pStr1); 120. size_t length2 = strlen(pStr2); 121. 122. if(length1 == 0 || length2 == 0 || !(row < length1 && col < length2)) 123. return; 124. 125. // kLeftUp implies a char in the LCS is found 126. if(LCS_direction[row][col] == kLeftUp) 127. { 128. if(row > 0 && col > 0) 129. LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col - 1); 130. 131. // print the char 132. printf("%c", pStr1[row]); 133. } 134. else if(LCS_direction[row][col] == kLeft) 135. { 136. // move to the left entry in the direction matrix 137. if(col > 0) 138. LCS_Print(LCS_direction, pStr1, pStr2, row, col - 1); 139. } 140. else if(LCS_direction[row][col] == kUp) 141. { 142. // move to the up entry in the direction matrix 143. if(row > 0) 144. LCS_Print(LCS_direction, pStr1, pStr2, row - 1, col); 145. } 146. } 147. 148. int _tmain(int argc, _TCHAR* argv[]) 149. { 150. char* pStr1="abcde"; 151. char* pStr2="acde"; 152. LCS(pStr1,pStr2); 153. printf("\n"); 154. system("pause"); 155. return 0; 156. } 73 〻ᒿ䘀㹼㔃᷌ྲлᡰ⽪˖ ᢙኅ˖ྲ᷌仈ⴞ᭩ᡀ≲єњᆇㅖѢⲴᴰ䮯ޜޡᆀᆇㅖѢˈᓄ䈕ᘾѸ≲˛ᆀᆇㅖѢⲴᇊѹ ઼ᆀѢⲴᇊѹ㊫լˈն㾱≲ᱟ䘎㔝࠶ᐳ൘ަԆᆇㅖѢѝDŽ ∄ྲ䗃ޕєњᆇㅖѢ BDCABA ઼ ABCBDAB Ⲵᴰ䮯ޜޡᆇㅖѢᴹ BD ઼ ABˈᆳԜⲴ䮯ᓖ 䜭ᱟ 2DŽ ㅜㅜഋ䜘࠶ǃLCS 䰞仈Ⲵᰦ䰤༽ᵲᓖ ㇇⌅ሬ䇪кᤷࠪˈ 1. ᴰ䮯ޜޡᆀᒿࡇ䰞仈Ⲵања㡜Ⲵ㇇⌅ǃᰦ䰤༽ᵲᓖѪ O˄mn˅DŽ❦ਾˈMasek ઼ Paterson 㔉ࠪҶањ O(mn/lgn)ᰦ䰤޵ᢗ㹼Ⲵ㇇⌅ˈަѝ n<=mˈ㘼ф↔ᒿࡇᱟӾ { { ᔿDŽޜ opt[i][j] = Math.max(opt[i + 1][j], opt[i][j + 1]); //৲㘳к᮷ᡁ㔉Ⲵ else ᔿDŽޜ opt[i][j] = opt[i + 1][j + 1] + 1; //৲㘳к᮷ᡁ㔉Ⲵ if (x.charAt(i) == y.charAt(j)) for (int j = substringLength2 - 1; j >= 0; j--){ for (int i = substringLength1 - 1; i >= 0; i--){ // ࣘᘱ㿴ࡂ䇑㇇ᡰᴹᆀ䰞仈 int[][] opt = new int[substringLength1 + 1][substringLength2 + 1]; // ᶴ䙐Ҽ㔤ᮠ㓴䇠ᖅᆀ䰞仈 x[i]઼ y[i]Ⲵ LCS Ⲵ䮯ᓖ Long startTime = System.nanoTime(); String y = GetRandomStrings(substringLength2); String x = GetRandomStrings(substringLength1); // 䲿ᵪ⭏ᡀᆇㅖѢ int substringLength2 = 20; //ާփབྷሿਟ㠚㹼䇮㖞 int substringLength1 = 20; //䇮㖞ᆇㅖѢ䮯ᓖ public static void main(String[] args){ public class LCS{ import java.util.Random; ᆀᒿࡇ䰞仈Ⲵ java ㇇⌅Ⓚ⸱ˈᡁ㠚㹼⍻䈅Ҷлˈ↓⺞˖ޡޜҾ↔ᴰ䮯ޣ㺕㺕ݵ˖а㖁৻ᨀ׋Ⲵ ㅜ 56 仈Ⲵᴤཊˈਟ৲㘳ᡁণሶᮤ⨶кՐⲴㆄṸ V04 ⡸ㅜ 41-60 仈ⲴㆄṸDŽ Ҿ↔䶒䈅ޣҾ↔ࣘᘱ㿴ࡂ㇇⌅ᴤཊਟ৲㘳 ㇇⌅ሬ䇪аҖㅜ 15 ㄐ ࣘᘱ㿴ࡂ䰞仈ˈ㠣Ҿޣ ֯⭘ O˄n˅Ⲵᰦ䰤઼ O˄n˅Ⲵオ䰤ˈᴰਾˈKnuth ᢺᰦ䰤䱽ࡠҶ O˄nlgn˅DŽ ᰦ䰤Ⲵ㇇⌅DŽHu ઼ Tucker 䇮䇑Ҷањ㇇⌅ˈᆳ൘ᡰᴹⲴᾲ⦷ pi 䜭ᱟ 0 Ⲵᛵߥлˈ ൘ᡰᴹⲴᾲ⦷ pi 䜭ᱟ 0 Ⲵᛵߥлᶴ䙐ᴰՈҼ৹ḕ᢮ṁˈ䘉ㇷ䇪᮷㔉ࠪањ O˄n^3˅ Ҿਟਈ䮯ᓖҼݳ㕆⸱Ⲵᰙᵏ䇪᮷ѝᴹ䘉ṧⲴᓄ⭘˖ޣ2. аㇷ⭡ Gilbert ઼ Moore ᫠߉Ⲵ 䈤᰾䘉њ䰞仈ਟ൘ O(˄n+m˅lg˄n+m˅)޵䀓ߣDŽ ᒿࡇѝ⋑ᴹࠪ⧠䎵䗷а⅑Ⲵ⢩↺ᛵߥѝˈSzymanskޕањᴹ䲀䳶ਸѝ㘼ᶕDŽ൘䗃 74 75 ------------------------------------------------------------------------------------- ⨶䀓к⇥ˈ৲㘳к᮷ᡁ㔉Ⲵޜᔿ˖ ṩᦞк䘠㔃䇪ˈਟᗇࡠԕлޜᔿˈ ྲ᷌ᡁԜ䇠ᆇㅖѢ Xi ઼ Yj Ⲵ LCS Ⲵ䮯ᓖѪ c[i,j]ˈᡁԜਟԕ䙂ᖂൠ≲ c[i,j]˖ ------------------------------------------------------------------------------------- System.out.println("substring1:"+x); System.out.println("substring2:"+y); System.out.print("LCS:"); int i = 0, j = 0; while (i < substringLength1 && j < substringLength2){ if (x.charAt(i) == y.charAt(j)){ System.out.print(x.charAt(i)); i++; j++; } else if (opt[i + 1][j] >= opt[i][j + 1]) i++; else j++; } Long endTime = System.nanoTime(); System.out.println(" Totle time is " + (endTime - startTime) + " ns"); } //ਆᗇᇊ䮯䲿ᵪᆇㅖѢ public static String GetRandomStrings(int length){ StringBuffer buffer = new StringBuffer("abcdefghijklmnopqrstuvwxyz"); StringBuffer sb = new StringBuffer(); Random r = new Random(); { 1 for each vertex u ę V [G] - {s BFS(G, s) //u Ѫ v Ⲵݸ䖸ᡆ⡦⇽DŽ ⲴᙍᜣDŽ ൘ Prime ᴰሿ⭏ᡀṁ㇇⌅ˈ઼ Dijkstra অⓀᴰ⸝䐟ᖴ㇇⌅ѝˈ䜭䟷⭘Ҷо BFS ㇇⌅㊫լ ᒯᓖՈݸᩌ㍒˄BFS˅ ㇇⌅ሬ䇪ㅜҼ⡸ˈѝ䈁ᵜˈㅜ 324 亥DŽ Ҿ ↔ BFS ᒯᓖՈݸᩌ㍒㇇⌅Ⲵᾲ䘠DŽޣ俆ݸˈⴻл㇇⌅ሬ䇪аҖ ૡԜ⭡ BFS ᔰ࿻˖ ֐ሩമⲴᒯᓖՈݸᩌ㍒઼␡ᓖՈݸᩌ㍒ᇊՊᴹњ䙊䙊䘿䘿ˈᖫᖫᓅᓅⲴ䇔䇶DŽ 䈫ᆼ↔᮷ˈᡁᜣˈ Ҿ↔㊫ BFS ઼ DFS ㇇⌅Ⲵ᮷ㄐˈᖸཊDŽնˈ䜭䈤нࠪњᡰԕ❦ᶕDŽޣˈ㘫䙽㖁к okˈᔰ࿻DŽ ---------------------------------------------------------------------------------------------------------------------- ᵜӪ༠᰾˖њӪ৏ࡋˈ䖜䖭䈧⌘᰾ࠪ༴DŽ ᵜӪ৲㘳˖㇇⌅ሬ䇪 ֌㘵˖July Ҽ䴦ааᒤаᴸаᰕ ഋǃBFS ઼ DFS Ոݸᩌ㍒㇇⌅ ᆀᒿࡇ˄LCS˅䰞仈DŽᆼDŽޡޜ OKˈᴤཊˈ䈧৲㘳˖〻ᒿઈ㕆〻㢪ᵟㅜॱаㄐǃᴰ䮯 LCS:qheq Totle time is 818058 ns substring2:tdzbujtlqhecaqgwfzbc substring1:akqrshrengxqiyxuloqk eclipse 䘀䘀㹼㔃᷌Ѫ˖ } } return sb.toString(); } sb.append(buffer.charAt(r.nextInt(range))); for (int i = 0; i < length; i++){ int range = buffer.length(); 76 18 color[u] ĕ BLACK //u 㖞Ѫ唁㢢 䱏ࡇѝޕ17 ENQUEUE(Q, v) //ᨂ 16 π[v] ĕ u //u 䇠Ѫ䈕亦⛩Ⲵ⡦⇽ 15 d[v] ĕ d[u] + 1 //䐍⿫㻛㖞Ѫ d[u]+1 14 then color[v] ĕ GRAY //㖞Ѫ⚠㢢 13 do if color[v] = WHITE 12 for each v ę Adj[u] //for ᗚ⧟㘳ሏ u Ⲵ䛫᧕㺘ѝⲴ⇿њ亦⛩ v //ㅜ 11 㹼ˈ⺞ᇊ䱏ࡇཤ䜘 Q ཤ䜘Ⲵ⚠㢢亦⛩ uˈᒦሶަӾ Q ѝ৫ᦹDŽ 11 do u ĕ DEQUEUE(Q) //ࠪ䱏 10 while Q ≠ Ø //ㅜ 8ǃ9 㹼ˈࡍ࿻ॆ䱏ࡇ Qˈ֯ަӵਜ਼Ⓚ亦⛩ sDŽ 䱏ޕ// ( 9 ENQUEUE(Q, s 8 Q ĕ Ø 7 π[s] ĕ NIL //ሶⓀ亦⛩Ⲵ⡦亦⛩㖞Ѫ NILDŽ 6 d[s] ĕ 0 //ሶ d[s]ࡍ࿻ॆѪ 0DŽ //ㅜ 5 㹼ˈሶⓀ亦⛩ s 㖞Ѫ⚠㢢ˈ䘉ᱟഐѪ൘䗷〻ᔰ࿻ᰦˈⓀ亦⛩ᐢ㻛ਁ⧠DŽ 5 color[s] ĕ GRAY //㖞⇿њ亦⛩Ⲵ⡦⇽Ѫ NILDŽ //䲔ҶⓀ亦⛩ s ѻཆˈㅜ 1-4 㹼㖞⇿њ亦⛩Ѫⲭ㢢ˈ㖞⇿њ亦⛩ u Ⲵ d[u]Ѫᰐェབྷˈ 4 π[u] ĕ NIL 3 d[u] ĕ ∞ do color[u] ĕ WHITE 2 77 1 color[u] ĕ GRAY //u ᔰ࿻ᰦ㻛ਁ⧠ˈ㖞Ѫⲭ㢢 DFS-VISIT(u) //⇿њ亦⛩ u 䜭ሩᓄҾањਁ⧠ᰦ࡫ d[u]઼ањᆼᡀᰦ࡫ f[u]DŽ //ㅜ 5-7 㹼ˈ׍⅑Ự㍒ V ѝⲴ亦⛩ˈਁ⧠ⲭ㢢亦⛩ᰦˈ䈳⭘ DFS-VISIT 䇯䰞䈕亦⛩DŽ ἥᯠⲴṁ 7 then DFS-VISIT(u) //䈳⭘ DFS-VISIT 䇯䰞 uˈu ᡀѪ␡ᓖՈݸ἞᷇ѝа 6 do if color[u] = WHITE 5 for each vertex u ę V [G] 4 time ĕ 0 //༽սᰦ䰤䇑ᮠಘ //ㅜ 1-3 㹼ˈᢺᡰᴹ亦⛩㖞Ѫⲭ㢢ˈᡰᴹ π ฏ㻛ࡍ࿻ॆѪ NILDŽ 3 π[u] ĕ NIL 2 do color[u] ĕ WHITE 1 for each vertex u ę V [G] DFS(G) //u Ѫ v Ⲵݸ䖸ᡆ⡦⇽DŽ ␡ᓖՈݸ᧒㍒㇇⌅ DFS okˈн޽䎈䘠DŽ᧕лᶕˈާփ䇢䀓␡ᓖՈݸᩌ㍒㇇⌅DŽ --------------------------------------------------------------------------------------- http://sjjg.js.zwu.edu.cn/SFXX/sf1/gdyxbl.html ᒯᓖՈݸ䙽শ╄⽪ൠ൰˖ ⭡лമ৺䬮᧕Ⲵ╄⽪䗷〻ˈ␵Რ൘ⴞˈҏቡн⭘ཊ䈤Ҷ˖ 78 ˖л䶒Ⲵ䬮᧕ˈ㔉ࠪҶ␡ᓖՈݸᩌ㍒Ⲵ╄⽪㌫㔏 ഐ↔ˈᙫⲴᢗ㹼ᰦ䰤Ѫ O(V+E)DŽ ㅜ 4-7 㹼ˈᢗ㹼ᰦ䰤Ѫ O˄E˅DŽ 䗷〻DŽ ሩҾ⇿њ亦⛩ v(-Vˈ䗷〻 DFS-VISIT ӵ㻛䈳⭘׍⅑ˈഐѪਚᴹሩⲭ㢢亦⛩᡽Պ䈳⭘↔ ㅜ 1-3 㹼ˈ5-7 㹼ᗚ⧟ঐ⭘ᰦ䰤Ѫ O˄V˅ˈ↔нवᤜ䈳⭘ DFS-VISIT Ⲵᰦ䰤DŽ //ᆼ time ĕ time +1 //䇯䰞ᆼᡀᰦ䰤䇠ᖅ൘ f[u]ѝDŽ ڿ [9 f [u 8 color[u] <-BLACK //u 㖞Ѫ唁㢢ˈ㺘⽪ u ৺ަ䛫᧕⛩䜭ᐢ䇯䰞ᆼᡀ 7 DFS-VISIT(v) //䙂ᖂ␡ᓖˈ䇯䰞䛫㔃⛩ v 6 then π[v] ĕ u //㖞 u Ѫ vⲴݸ䖸 5 do if color[v] = WHITE //ྲ᷌ v Ѫⲭ㢢ˈࡉ䙂ᖂ䇯䰞 vDŽ 4 for each v ę Adj[u] //Ựḕᒦ䇯䰞 u Ⲵ⇿ањ䛫᧕⛩ v 3 d[u] <-time //䇠ᖅ u 㻛ਁ⧠Ⲵᰦ䰤 time ĕ time +1 //time 䙂໎ 2 79 ;(" assertF(inGraph!=NULL,"in dfsR,inGraph is null\n PVexType v1; { void dfsR(PGraphMatrix inGraph,PVexType inV) } printf("\n===end of dft recursive version===\n"); dfsR(inGraph,v); if(v->marked==0) for(v=firstVertex(inGraph);v!=NULL;v=nextVertex(inGraph,v)) printf("\n===start of dft recursive version===\n"); assertF(inGraph!=NULL,"in dftR, pass in inGraph is null\n"); PVexType v; { void dftR(PGraphMatrix inGraph) 1ǃǃDFS 䙂ᖂᇎ⧠˖ ᴰਾˈૡԜ޽ᶕⴻ␡ᓖՈݸᩌ㍒Ⲵ䙂ᖂᇎ⧠о䶎䙂ᖂᇎ⧠ ================================================ http://sjjg.js.zwu.edu.cn/SFXX/sf1/sdyxbl.html മⲴ␡ᓖՈݸ䙽শ╄⽪㌫㔏˖ 80 //䇯䰞ᖃࡽ㔃⛩ //аӋਈ䟿༠᰾,ࡍ࿻ॆࣘ֌ PSeqStack testStack; //ᆈ᭮ᖃࡽቲѝⲴ m-1 њᵚ䇯䰞㔃⛩ᶴᡀ䱏ࡇⲴึḸ. PSingleRearSeqQueue tmpQ; //ᇊѹѤᰦ䱏ࡇˈ⭘ԕ᧕ਇḸ亦䱏ࡇ৺঻Ḹᰦ֯⭘ { void dfsUR(PGraphMatrix inGraph,PVexType inV) //dfsUR:࣏㜭ӾањṁⲴḀњ㔃⛩ inV ਁˈԕ␡ᓖՈݸⲴ৏ࡉ䇯䰞ᡰᴹоᆳ⴨䛫Ⲵ㔃⛩ ሶ㇇⌅䙊䗷㋮ㆰ䗷Ⲵ C Ⓚ〻ᒿⲴᯩᔿ᧿䘠ྲл: ᩌ㍒˅DŽ→ ڌⴤ㠣䙷ࡠᴹᵚ䇯䰞㔃⛩(䇯䰞ᒦ㖞ᖃࡽ⛩Ѫ䈕⛩)ᡆⴤࡠḸѪオ˄ࡉᖃࡽⲴ␡ᓖՈݸᩌ㍒ṁ 㤕ᐢ䇯䰞ˈࡉ㔗㔝ࠪ䱏(ᖃᖃࡽ䱏ࡇ㔃⛩ᐢオᰦˈࡉ㔗㔝ࠪḸˈᕩࠪлањḸ亦Ⲵ䱏ࡇ)ˈ ࡉӾḸ亦Ⲵ䱏ࡇ㔃⛩ѝᕩࠪ䱏ࡇݳ㍐ˈሶ䱏ࡇѝⲴ㔃⛩ݳ㍐׍⅑ࠪ䱏, 䘉ṧˈᖃᖃࡽⲴ㔃⛩Ⲵ䛫᧕⛩൷ᐢ䇯䰞ᡆᰐ䛫᧕⛩䴰㾱എ䇯ᰦˈ ањึḸѝDŽޕᒦሶ䘉њ䱏ࡇ঻ ањ䱏ࡇѝDŽޕࡉᴰᐖⲴањ䴰㾱䇯䰞ˈ㘼ሶ࢙։Ⲵ m-1 њ㔃⛩᤹ӾᐖࡠਣⲴ亪ᒿ᧘ 㔃⛩, ൘䘉䟼ˈ㤕㾱ᇎ⧠⴨ᓄⲴ࣏㜭ˈ㘳㲁ሶ⇿ањᖃࡽ㔃⛩Ⲵлቲ㔃⛩ѝˈྲ᷌ᴹ m њᵚ䇯䰞 նᱟˈሩҾṁ㘼䀰ˈᱟᨀ׋ rightSibling 䘉ṧⲴ᫽֌Ⲵˈഐ㘼䇯ਣ⴨ᖃྭᇎ⧠DŽ 2ǃ㘼മⲴഎ䇯кቲᵚ䇯㔃⛩઼ṁⲴࡽᒿ䙽শѝⲴ“䇯ਣ”ҏᱟа㠤Ⲵ. ਚ㾱ሩᐢ䇯䰞䗷Ⲵ㔃⛩֌ањࡔᇊণਟDŽ а㠤,ޘ 1ǃമⲴ␡ᓖ᧒㍒䘉ṧањ䗷〻઼ṁⲴ“᧒ᐖ”ᆼ ൘മⲴ␡ᓖՈݸᩌ㍒ѝˈ਼ṧਟ࠶ᡀ“␡ᓖ᧒㍒”઼“എ䇯кቲᵚ䇯㔃⛩”єඇ: ਟ⸕ˈަѝᰐ䶎ᱟ࠶ᡀ“᧒ᐖ”઼“䇯ਣ”єབྷඇ䇯ਣ䴰ُࣙḸѝᕩࠪⲴ㔃⛩䘋㹼. 㚄㌫ṁⲴࡽᒿ䙽শⲴ䶎䙂ᖂᇎ⧠˖ 䶎䙂ᖂ⡸ᵜ---ُࣙ㔃⛩㊫රѪ䱏ࡇⲴḸᇎ⧠ 2ǃǃDFS 䶎䙂ᖂᇎ⧠ } dfsR(inGraph,v1); if(v1->marked==0) //v1 ᖃѪ v Ⲵ䛫᧕⛩DŽ nV,v1)) for(v1=firstAdjacent(inGraph,inV);v1!=NULL;v1=nextAdjacent(inGraph,i visit(inV); inV->marked=1; assertF(inV!=NULL,"in dfsR,inV is null\n"); 81 { { ;( enQueue(tmpQ,v1 { else if(flag2==2)//ᖃࡽ㔃⛩Ⲵ䛫᧕⛩ᴹ 2 њᵚ㻛䇯䰞 } flag2=2; ㅜањ㔃⛩ޕ //ᯠᔪањ䱏ࡇˈ⭣䈧オ䰤ˈᒦ࣐ { else if(flag2==1) //ᖃࡽ㔃⛩Ⲵ䛫᧕⛩ᴹ 1 њᵚ䇯䰞 } time)adjacent node //save the current node's first unvisited(has been visited at this lChildV=v1; //䇠ᖅᴰᐖݯᆀ flag2=1; // v1->marked=1; //䇯䰞ᆼᡀ visit(v1); //俆ݸˈ䇯䰞ᴰᐖ㔃⛩ { if(flag2==0) //ᖃࡽ㔃⛩Ⲵ䛫᧕⛩ᴹ 0 њᵚ䇯䰞 { if(v1->marked==0) //.. { while(v1!=NULL) //䇯䰞ᖃࡽ㔃⛩Ⲵᡰᴹ䛫᧕⛩ v1=firstAdjacent(inGraph,inV); //䛫᧕⛩ v1 visited. //2:current node has more than one adjacent node which have not been //1:current node has only one adjacent node which has not been visited. //flag2:0:current node has no adjacent which has not been visited. Ⲵ⭘ 2 ԓ㺘 //flag2 ᱟањ䟽㾱Ⲵḷᘇਈ䟿ˈ⭘ԕǃ䈤᰾ᖃࡽ㔃⛩Ⲵᡰᴹᵚ䇯䰞㔃⛩Ⲵњᮠ,єњԕк flag2=0; { do visit(inV); ٬Ѫ 1 ᰦሶнᗵ޽䇯䰞DŽ inV->marked=1; //ᖃ marked 82 ˖к䘠〻ᒿⲴࠐ⛩䈤᰾ ----------------------------- } }while(!isNullSeqStack(testStack));//the algorithm ends when the stack is null } } } flag=1; inV=v1; v1->marked=1; visit(v1); { if(v1->marked==0) deQueueInSt(testStack); //ሶḸ亦㔃⛩Ⲵ䱏ࡇѝⲴ䱏俆ݳ㍐ᕩࠪ v1=frontQueueInSt(testStack); //䘄എḸ亦㔃⛩Ⲵ䱏ࡇѝⲴ䱏俆ݳ㍐ { while(!isNullSeqStack(testStack)&&!flag) flag=0; ᡆⴤࡠḸѪオDŽ //ࡉ㔗㔝ࠪḸˈᕩࠪлањḸ亦Ⲵ䱏ࡇ)ˈⴤ㠣䙷ࡠᴹᵚ䇯䰞㔃⛩(䇯䰞ᒦ㖞ᖃࡽ⛩Ѫ䈕⛩) //ሶ䱏ࡇѝⲴ㔃⛩ݳ㍐׍⅑ࠪ䱏,㤕ᐢ䇯䰞ˈࡉ㔗㔝ࠪ䱏(ᖃᖃࡽ䱏ࡇ㔃⛩ᐢオᰦˈ ࡇݳ㍐ˈ //ᖃᖃࡽⲴ㔃⛩Ⲵ䛫᧕⛩൷ᐢ䇯䰞ᡆᰐ䛫᧕⛩䴰㾱എ䇯ᰦˈࡉӾḸ亦Ⲵ䱏ࡇ㔃⛩ѝᕩࠪ䱏 { //has no adjacent nodes or all adjacent nodes has been visited else if(flag2==0) } inV=lChildV; //ਚᴹањᴰᐖݯᆀˈࡉ㖞ᖃࡽ⛩Ѫᴰᐖݯᆀ { else if(flag2==1)//only has one adjacent which has been visited. } inV=lChildV; seqPush(testStack,tmpQ); //ሶᆈᴹᖃࡽ㔃⛩Ⲵ m-1 њᵚ䇯䰞䛫᧕⛩Ⲵ䱏ࡇ঻Ḹ { if(flag2==2)//push adjacent nodes which are not visited. } v1=nextAdjacent(inGraph,inV,v1); 83 (( if(isEmptyQueue(seqTop(inStack))||isNullSeqStack(inStack { QElemType frontQueueInSt(PSeqStack inStack) 2.2) frontQueueInSt ᫽֌⭘ԕ䘄എḸ亦㔃⛩Ⲵ䱏ࡇѝⲴ䱏俆ݳ㍐. } inStack->slot--; if(isEmptyQueue(seqTop(inStack))) deQueue(seqTop(inStack)); } return; printf("in deQueueInSt,under flow!\n"); { if(isEmptyQueue(seqTop(inStack))||isNullSeqStack(inStack)) { void deQueueInSt(PSeqStack inStack) 2.1) deQueueInSt ᫽֌⭘ҾሶḸ亦㔃⛩Ⲵ䱏ࡇѝⲴ䱏俆ݳ㍐ᕩࠪ. ѪҶᨀ׋ᴤྭⲴሱ㻵ᙗˈሩ䘉њึḸᇎ⧠є⿽⢩↺Ⲵ᫽֌ }; int slot; StackElemType dataArea[SEQ_STACK_LEN]; { struct SeqStack typedef struct SeqStack* PSeqStack; struct SeqStack; #define StackElemType PSingleRearSeqQueue #define SEQ_STACK_LEN 1000 2)ึḸⲴᇎ⧠ѝˈ⇿њึḸѝⲴ㔃⛩ݳ㍐൷Ѫањᤷੁ䱏ࡇⲴᤷ䪸,ᇊѹྲл: ަ։สᵜ᫽֌н޽䎈䘠. }; QElemType dataPool[MAXNUM]; int quelen; int rear; { struct SingleRearSeqQueue typedef struct SingleRearSeqQueue* PSingleRearSeqQueue; typedef PVexType QElemType; struct SingleRearSeqQueue; ᇊѹањԕ䱏ࡇቮ䜘лḷ࣐䱏ࡇ䮯ᓖⲴ⧟ᖒ䱏ࡇྲл: 1)䱏ࡇⲴᇎ⧠ѝˈ⇿њ䱏ࡇ㔃⛩൷ѪമѝⲴ㔃⛩ᤷ䪸㊫ර. ᡰԕˈ䘉䟼ᓄ֯⭘Ⲵᮠᦞ㔃ᶴⲴᶴᡀᯩᔿᓄ䈕䟷⭘л䶒䘉⿽ᖒᔿ: 84 аǃ㓒唁ṁⲴӻ㓽 ------------------------------------------------ 6ǃ㓒唁ṁⲴ c++ᆼᮤᇎ⧠Ⓚ⸱ 〻╄⽪ޘࡐ䲔㔃⛩Ⲵ઼ޕ5ǃ㓒唁ṁᨂ 4ǃа↕аമаԓ⸱ˈR-B Tree 3ǃ㓒唁ṁⲴ c Ⓚ⸱ᇎ⧠оࢆ᷀ 2ǃ㓒唁ṁ㇇⌅Ⲵᇎ⧠оࢆ᷀ 1ǃᮉ֐䘿ᖫҶ䀓㓒唁ṁ ㇷ᮷ㄐҾӺᰕᐢ㓿ᆼᡀ˖ޝˈ㓒唁ṁ㌫ࡇ ------------------------------------------------ ⴤ᧕л䖭˖http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf Structures, Wadern, Germany, February, 2008. ᧘ 㦀 䰵 䈫 ˖ Left-Leaning Red-Black Trees, Dagstuhl Workshop on Data ᵜӪ༠᰾˖њӪ৏ࡋˈ䖜䖭䈧⌘᰾ࠪ༴DŽ ᵜ᮷৲㘳˖Googleǃ㇇⌅ሬ䇪ǃSTL Ⓚ⸱ࢆ᷀ǃ䇑㇇ᵪ〻ᒿ䇮䇑㢪ᵟDŽ ֌㘵˖Julyǃsaturnman 2010 ᒤ 12 ᴸ 29 ᰕ ӊӊȽᮏ֖䙅ᖱҼ䀙㓘唇ṇ JulyǃҼ䴦ааᒤаᴸаᰕDŽHappy 2011 new yearʽ okˈᵜ᮷ᆼDŽ =================== } return getHeadData(seqTop(inStack)); } return '\r'; printf("in frontQueueInSt,under flow!\n"); } 85 ҼǃṁⲴ᯻䖜⸕䇶 ↔മᘭ⮕Ҷਦᆀ઼ṩ䜘Ⲵ⡦㔃⛩DŽ лമᡰ⽪ˈণᱟа仇㓒唁ṁ˖ 5˅ሩ⇿њ㔃⛩ˈӾ䈕㔃⛩ࡠަᆀᆉ㔃⛩Ⲵᡰᴹ䐟ᖴкवਜ਼⴨਼ᮠⴞⲴ唁㔃⛩DŽ 4˅ྲ᷌ањ㔃⛩ᱟ㓒Ⲵˈ䛓ѸᆳⲴؙњݯᆀ䜭ᱟ唁ⲴDŽ 3˅⇿њਦ㔃⛩ˈণオ㔃⛩˄NIL˅ᱟ唁ⲴDŽ 2˅ṩ㔃⛩ᱟ唁ⲴDŽ 1˅⇿њ㔃⛩㾱Ѹᱟ㓒Ⲵˈ㾱Ѹᱟ唁ⲴDŽ 䜘ᙗ䍘ⲴṁˈᡁԜ᡽〠ѻѪ㓒唁ṁ˖ޘа㡜Ⲵˈ㓒唁ṁˈ┑䏣ԕлᙗ䍘ˈণਚᴹ┑䏣ԕл Ⲵᤷ䪸ฏ⋑ᴹˈࡉ䇮Ѫ NILDŽ okˈᡁԜ⸕䚃ˈ㓒唁ṁк⇿њ㔃⛩޵ਜ਼ӄњฏˈcolorˈkeyˈleftˈrightˈpDŽྲ᷌⴨ᓄ 䇱൘ᴰൿᛵߥлˈสᵜⲴࣘᘱࠐօ᫽֌Ⲵᰦ䰤൷Ѫ O˄lgn˅DŽ؍㘼㓒㓒唁ṁˈ㜭 2.ն㤕ᱟаἥާᴹ n њ㔃⛩Ⲵ㓯ᙗ䬮ˈࡉ↔Ӌ᫽֌ᴰൿᛵߥ䘀㹼ᰦ䰤Ѫ O˄n˅DŽ 12.4 㢲DŽ //㠣Ҿ n њ㔃⛩ⲴҼ৹ṁ儈ᓖѪ lgn Ⲵ䇱᰾ˈਟ৲㘳㇇⌅ሬ䇪 ㅜ 12 ㄐ Ҽ৹ḕ᢮ṁ ㅜ ֌Ⲵᢗ㹼ᰦ䰤Ѫ O˄lgn˅DŽ ഐѪˈаἥ⭡ n њ㔃⛩ˈ䲿ᵪᶴ䙐ⲴҼ৹ḕ᢮ṁⲴ儈ᓖѪ lgnˈᡰԕ亪⨶ᡀㄐˈа㡜᫽ ǃࡐ䲔ㅹ᫽֌ˈⲴᰦ䰤༽ᵲᓖѪ O˄lgn˅DŽޕ1.൘аἥҼ৹ḕ᢮ṁкˈᢗ㹼ḕ᢮ǃᨂ л䶒ˈ൘ާփӻ㓽㓒唁ṁѻࡽˈૡԜݸᶕҶ䀓л Ҽ৹ḕ᢮ṁⲴа㡜ᙗ䍘˖ Ⲵа㡜ᙗ䍘DŽ ࡽ䶒䈤Ҷˈ㓒唁ṁˈᱟа⿽Ҽ৹ḕ᢮ṁˈᰒ❦ᱟҼ৹ḕ᢮ṁˈ䛓Ѹᆳᗵ┑䏣Ҽ৹ḕ᢮ṁ ᖴՊ∄ަԆ䐟ᖴ䮯ؙࠪؽˈഐ㘼ᱟ᧕䘁ᒣ㺑ⲴDŽ ᴹаᶑ䐟⋐؍⺞䙊䗷ሩԫօаᶑӾṩࡠਦᆀⲴ䐟ᖴк਴њ㔃⛩⵰㢢ᯩᔿⲴ䲀ࡦˈ㓒唁ṁ Red ᡆ BlackDŽ 㓒唁ṁˈа⿽Ҽ৹ḕ᢮ṁˈն൘⇿њ㔃⛩к໎࣐ањᆈۘս㺘⽪㔃⛩Ⲵ仌㢢ˈਟԕᱟ ݸᶕⴻл㇇⌅ሬ䇪ሩ R-B Tree Ⲵӻ㓽˖ 86 6 then root[T] ĕ y 5 if p[x] = nil[T] Link x's parent to y. ڿ [4 p[y] ĕ p[x 3 p[left[y]] ĕ x Turn y's left subtree into x's right subtree. ڿ [2 right[x] ĕ left[y Set y. ڿ [1 y ĕ right[x LEFT-ROTATE(T, x) ᶕⴻ㇇⌅ሬ䇪ሩ↔᫽֌Ⲵ㇇⌅ᇎ⧠˄ԕ x ԓᴯк䘠Ⲵ pivot˅˖ b ࡉᡀѪ pivot ⲴਣᆙᆀDŽ ᐖ᯻ԕ pivot ࡠ y ѻ䰤Ⲵ䬮Ѫ“᭟䖤”䘋㹼ˈᆳ֯ y ᡀѪ䈕ᆙᆀṁᯠⲴṩˈ㘼 y Ⲵᐖᆙᆀ ԕѪṁ޵ԫ᜿ਣᆙᆀ㘼нᱟ NIL[T]Ⲵ㔃⛩DŽ 䇮ᆳⲴਣᆙᆀ y нᱟ NIL[T]ˈpivot ਟٷᐖ᯻᫽֌ᰦˈᡁԜڊˈᖃ൘Ḁњ㔃⛩ pivot к ྲкമᡰ⽪˖ 1.ᐖ᯻ ᖒ䊑Ⲵ䀓䟺઼ӻ㓽˖ڊṁⲴ᯻䖜ˈ࠶Ѫᐖ᯻઼ਣ᯻ˈԕлُࣙമᶕ ᤱᆳ⢩ᴹⲴᙗ䍘˄ྲк᮷ᡰ䘠Ⲵˈӄ⛩ᙗ䍘˅DŽ؍ǃࡐ䲔㔃⛩ㅹ᫽֌ᰦˈ㓒唁ṁ׍❦㜭ޕᨂ 䪸㔃ᶴˈԕ䗮ࡠሩ㓒唁ṁ䘋㹼 ᤱ㓒唁ṁⲴᙗ䍘ˈᡁԜਟԕ䙊䗷ሩṁ䘋㹼᯻䖜ˈণ؞᭩ṁ⿽ḀӋ㔃⛩Ⲵ仌㢢৺ᤷ؍ѪҶ ᙗ䍘DŽ Ҷ؞᭩ˈ䛓Ѹਟ㜭Պ䘍㛼㓒唁ṁⲴڊࡐ䲔ㅹ᫽֌ᰦˈሩṁ઼ޕᖃᡁԜ൘ሩ㓒唁ṁ䘋㹼ᨂ 87 ањᯠ㔃⛩Ⲵ᫽֌ਟԕ൘ O˄lgn˅ᰦ䰤޵ᆼᡀDŽޕੁаἥਜ਼ᴹ n њ㔃⛩Ⲵ㓒唁ṁᨂ ᫽֌DŽޕ йǃIǃokˈ᧕лᶕˈૡԜᶕާփҶ䀓㓒唁ṁⲴᨂ ǃࡐ䲔᫽֌Ⲵާփᇎ⧠ޕййǃ㓒唁ṁᨂ ԕҶDŽ Ⲵ޵ᇩˈഐ↔䘉䟼ቡн޽ӻ㓽Ҷˈ㘼фᐖਣ᯻ҏᱟ⴨ӂሩ〠Ⲵˈਚ㾱⨶䀓ަѝа⿽᯻䖜ቡਟ 㠣ҾᴹӋҖྲ STL Ⓚ⸱ࢆ᷀ᴹሩৼ᯻Ⲵ᧿䘠ˈަᇎৼ᯻ਚᱟঅ᯻Ⲵє⅑ᓄ⭘ˈᒦᰐᯠ ࡐ䲔ਾਟ࡙⭘᯻䖜઼仌㢢䟽⎲ᶕᚒ༽ṁⲴ㓒唁ᙗ䍘DŽ઼ޕ൘㓒唁ṁⲴᮠᦞᨂ ᤱˈ؍ᤱнਈⲴਚᴹ৏ṁⲴᩌ㍒ᙗ䍘ˈ㘼৏ṁⲴ㓒唁ᙗ䍘ࡉн㜭؍ሩҾṁⲴ᯻䖜ˈ㜭 䈖㓶ӻ㓽DŽڊਣ᯻оᐖ᯻ᐞнཊˈ޽↔н 2.ਣ᯻ 11 p[x] ĕ y Put x on y's left. ڿ 10 left[y] ĕ x 9 else right[p[x]] ĕ y 8 then left[p[x]] ĕ y else if x = left[p[x]] 7 88 Case 3 ڿ 12 color[p[z]] ĕ BLACK Case 2 ڿ (11 LEFT-ROTATE(T, z Case 2 ڿ [10 then z ĕ p[z 9 else if z = right[p[z]] Case 1 ڿ [[ 8 z ĕ p[p[z Case 1 ڿ 7 color[p[p[z]]] ĕ RED Case 1 ڿ 6 color[y] ĕ BLACK Case 1 ڿ 5 then color[p[z]] ĕ BLACK 4 if color[y] = RED 3 then y ĕ right[p[p[z]]] 2 do if p[z] = left[p[p[z]]] 1 while color[p[z]] = RED RB-INSERT-FIXUP(T, z)ˈྲлᡰ⽪˖ ᤱ㓒唁ṁⲴᙗ䍘DŽ؍ᡰԕˈ൘ㅜ 17 㹼ˈ䈳⭘ RB-INSERT-FIXUP˄T,z˅ᶕ ㅜ 16 㹼ˈሶ z ⵰Ѫ㓒㢢ˈ⭡Ҿሶ z ⵰Ѫ㓒㢢ਟ㜭Պ䘍㛼Ḁаᶑ㓒唁ṁⲴᙗ䍘ˈ ᤱ↓⺞Ⲵṁ㔃ᶴ؍// [15 right[z] ĕ nil[T 14 left[z] ĕ nil[T] ᶕሩ㔃⛩䘋㹼䟽ᯠ⵰㢢ˈᒦ᯻䖜DŽ RB-INSERT-FIXUP ᤱˈк䘠ԓ⸱䈳⭘Ҷањ䖵ࣙ〻ᒿ؍❦᫽֌ਾ׍ޕ䇱㓒唁ᙗ䍘൘ᨂ؍Ѫ 㓒唁ṁ T ѻ޵DŽޕRB-INSERT(T, z)ˈሶ z ᨂ ૡԜᶕާփ࠶᷀лˈ↔⇥ԓ⸱˖ 17 RB-INSERT-FIXUP(T, z) 16 color[z] ĕ RED 15 right[z] ĕ nil[T] 14 left[z] ĕ nil[T] 13 else right[y] ĕ z 12 then left[y] ĕ z 11 else if key[z] < key[y] 10 then root[T] ĕ z 9 if y = nil[T] 8 p[z] ĕ y 7 else x ĕ right[x] 6 then x ĕ left[x] 5 if key[z] < key[x] 4 do y ĕ x 3 while x ≠ nil[T] 2 x ĕ root[T] 1 y ĕ nil[T] RB-INSERT(T, z) ㇇⌅ሬ䇪˖ 89 ൘↔ˈᡁԜਚ㘳㲁⡦㔃⛩Ѫ⾆⡦ᐖᆀⲴᛵߥDŽ ቡਟԕҶDŽ о↔਼ᰦˈ৸࠶Ѫ⡦㔃⛩ᱟ⾆⡦㔃⛩Ⲵᐖᆀ䘈ᱟਣᆀˈሩҾሩ〠ᙗˈᡁԜਚ㾱䀓ᔰањᯩੁ ࡽቡᐢнᱟ㓒唁ṁDŽޕ↔ᰦ⡦㔃⛩Ⲵ⡦㔃⛩аᇊᆈ൘ˈ੖ࡉᨂ ᛵߥ 3˖ᖃࡽ㔃⛩Ⲵ⡦㔃⛩ᱟ㓒㢢ф⾆⡦㔃⛩Ⲵਖањᆀ㔃⛩˄਄਄㔃⛩˅ᱟ㓒㢢DŽ DŽڊ ሩㆆ˖ӰѸҏн ↔нՊ䘍৽ᙗ䍘 2 ઼ᙗ䍘 4ˈ㓒唁ṁ⋑ᴹ㻛⹤ൿDŽ Ⲵ㔃⛩Ⲵ⡦㔃⛩ᱟ唁㢢DŽޕᛵߥ 2˖ᨂ ሩㆆ˖ⴤ᧕ᢺ↔㔃⛩⎲Ѫ唁㢢DŽ ৏ṁᱟオṁˈ↔ᛵߥਚՊ䘍৽ᙗ䍘 2DŽ Ⲵᱟṩ㔃⛩DŽޕᛵߥ 1˖ᨂ //⌘˖ԕлᛵߥ 3ǃ4ǃ5 ок䘠㇇⌅ሬ䇪кⲴԓ⸱ RB-INSERT-FIXUP(T, z)ˈ⴨ሩᓄ˖ Ⲵॆᖂࡠл䶒Ⲵࠐ⿽ᛵߥˈ ަҼǃェѮᡰᴹⲴਟ㜭ᙗˈѻਾᢺ㜭ᖂҾ਼а㊫ᯩ⌅༴⨶ⲴᖂѪ਼а㊫ˈн㜭ⴤ᧕༴⨶ ⴤ᧕؞᭩ṩ㔃⛩ᶕᚒ༽㓒唁ṁⲴᙗ䍘DŽⴤ᧕䙊䗷؞᭩ṩ㔃⛩ᶕᚒ༽㓒唁ṁᓄ┑䏣Ⲵᙗ䍘DŽ ަаǃᢺࠪ⧠䘍㛼㓒唁ṁᙗ䍘Ⲵ㔃⛩ੁк〫ˈྲ᷌㜭〫ࡠṩ㔃⛩ˈ䛓Ѹᖸᇩ᱃ቡ㜭䙊䗷 ᡁԜⲴഎ༽ㆆ⮕ᖸㆰঅˈ ањ㓒㢢㔃⛩ਚՊ⹤ൿᙗ䍘 2 ᡆᙗ䍘 4DŽޕഐ↔ˈᙫ㘼䀰ѻˈᨂ ᙗ䍘 4DŽ 㔃⛩Ⲵ⡦㔃⛩ᱟ㓒㢢ˈࡉՊ⹤ൿޕⲴ㔃⛩ᱟṩ㔃⛩ˈᙗ䍘 2 Պ㻛⹤ൿˈྲ᷌ᨂޕྲ᷌ᨂ ഐ↔ݳ㍐Ⲵᩌ㍒ᙗ䍘нՊ᭩ਈDŽˈޕ⭡ҾˈᡁԜᱟ᤹➗Ҽ৹ṁⲴᯩᔿ䘋㹼ᨂ ањ㔃⛩ਾˈਟ㜭Պ֯৏ṁⲴଚӋᙗ䍘᭩ਈࡇ?ޕ䛓ѸˈᡁԜᨂ ѝቭ䟿䚯ݽሩṁⲴ䈳ᮤDŽ 䗷〻ޕ㓒㢢Ⲵ㔃⛩ˈഐѪ䘉ṧਟԕ൘ᨂޕ᫽֌ᰦˈᡁԜа㡜ᙫᱟᨂޕ൘ሩ㓒唁ṁ䘋㹼ᨂ 5˅ሩ⇿њ㔃⛩ˈӾ䈕㔃⛩ࡠަᆀᆉ㔃⛩Ⲵᡰᴹ䐟ᖴкवਜ਼⴨਼ᮠⴞⲴ唁㔃⛩DŽ 4˅ྲ᷌ањ㔃⛩ᱟ㓒Ⲵˈ䛓ѸᆳⲴؙњݯᆀ䜭ᱟ唁ⲴDŽ 3˅⇿њਦ㔃⛩ˈণオ㔃⛩˄NIL˅ᱟ唁ⲴDŽ 2˅ṩ㔃⛩ᱟ唁ⲴDŽ 1˅˅⇿њ㔃⛩㾱Ѹᱟ㓒Ⲵˈ㾱Ѹᱟ唁ⲴDŽ 䇱䱀䘠␵Რˈᡁ޽߉л㓒唁ṁⲴ 5 њᙗ䍘˖؍ѪҶ okˈ৲㘳а㖁৻Ⲵ䀰䇪ˈ⭘㠚ᐡⲴ䈝䀰ˈ޽ᶕާփ䀓ࢆлк䘠ؙ⇥ԓ⸱DŽ 16 color[root[T]] ĕ BLACK with "right" and "left" exchanged) 15 else (same as then clause Case 3 ڿ ([[14 RIGHT-ROTATE(T, p[p[z Case 3 ڿ color[p[p[z]]] ĕ RED 13 90 91 ਼ᰦˈ䘈ਟԕ࠶Ѫᖃࡽ㔃⛩ᱟަ⡦㔃⛩Ⲵᐖᆀ䘈ᱟਣᆀˈնᱟ༴⨶ᯩᔿᱟаṧⲴDŽᡁԜ ሶ↔ᖂѪ਼а㊫DŽ ሩㆆ˖ሶᖃࡽ㢲⛩Ⲵ⡦㢲⛩઼਄਄㢲⛩⎲唁ˈ⾆⡦㔃⛩⎲㓒ˈᢺᖃࡽ㔃⛩ᤷੁ⾆⡦㢲⛩ˈ ӾᯠⲴᖃࡽ㢲⛩䟽ᯠᔰ࿻㇇⌅DŽ 䪸ሩᛵߥ 3ˈਈॆࡽ˄മ⡷ᶕⓀ˖saturnman˅[ᨂޕ 4 㢲⛩]˖ ਈॆਾ˖ ˖@㢲⛩ޕྲлമᡰ⽪ˈਈॆࡽ>ᨂ ѪᯠⲴᖃࡽ㢲⛩ˈԕᯠᖃࡽ㢲⛩Ѫ᭟⛩ᐖ᯻DŽڊሩㆆ˖ᖃࡽ㢲⛩Ⲵ⡦㢲⛩ ᆀ ᛵᛵߥ ˖ᖃࡽ㢲⛩Ⲵ⡦㢲⛩ᱟ㓒㢢਄਄㢲⛩ᱟ唁㢢ˈᖃࡽ㢲⛩ᱟަ⡦㢲⛩Ⲵਣ 92 93 ਈॆਾ˖ 94 ᛵߥ ˖ᖃࡽ㢲⛩Ⲵ⡦㢲⛩ᱟ㓒㢢਄਄㢲⛩ᱟ唁㢢ˈᖃࡽ㢲⛩ᱟަ⡦㢲⛩Ⲵᐖ ᆀ 䀓⌅˖⡦㢲⛩ਈѪ唁㢢ˈ⾆⡦㢲⛩ਈѪ㓒㢢ˈ൘⾆⡦㢲⛩Ѫ᭟⛩ਣ᯻ ྲлമᡰ⽪>ᨂޕ㢲⛩@ ਈॆਾ˖ 95 ================== йǃIIǃokˈ᧕лᶕˈૡԜᴰਾᶕҶ䀓ˈ㓒唁ṁⲴࡐࡐ䲔᫽֌˖ ㇇⌅ሬ䇪аҖˈ㔉Ⲵ㇇⌅ᇎ⧠˖ RB-DELETE(T, z) অ㓟ࡐ䲔㔃⛩Ⲵᙫ᫽֌ 1 if left[z] = nil[T] or right[z] = nil[T] 2 then y ĕ z 3 else y ĕ TREE-SUCCESSOR(z) 4 if left[y] ≠ nil[T] 5 then x ĕ left[y] 6 else x ĕ right[y] 7 p[x] ĕ p[y] 8 if p[y] = nil[T] 9 then root[T] ĕ x 10 else if y = left[p[y]] 11 then left[p[y]] ĕ x 12 else right[p[y]] ĕ x 13 if y 3≠ z 14 then key[z] ĕ key[y] 15 copy y's satellite data into z 16 if color[y] = BLACK 17 then RB-DELETE-FIXUP(T, x) 18 return y Ⲵᚒ༽ᐕ֌DŽڊᤱ㓒唁ṁ৏ᴹⲴ 5 ⛩ᙗ䍘ˈᡰ؍઼༽ѪҶᚒ ԕлᡰᴹⲴ᫽֌ˈᱟ䪸ሩ㓒唁ṁᐢ㓿ࡐ䲔㔃⛩ѻਾˈ ঊѫᨀ䟂˖ ----------------------------------------------------------------- 㓒唁ṁࡐ䲔Ⲵࠐ⿽ᛵߥ˖ saturnman˖ ˄⴨ؑˈ䟽䘠Ҷ 3 ⅑ˈ֐ᓄ䈕ᴹ␡࡫䇠ᗶҶDŽ:D˅ 5˅ሩ⇿њ㔃⛩ˈӾ䈕㔃⛩ࡠަᆀᆉ㔃⛩Ⲵᡰᴹ䐟ᖴкवਜ਼⴨਼ᮠⴞⲴ唁㔃⛩DŽ 4˅ྲ᷌ањ㔃⛩ᱟ㓒Ⲵˈ䛓ѸᆳⲴؙњݯᆀ䜭ᱟ唁ⲴDŽ 3˅⇿њਦ㔃⛩ˈণオ㔃⛩˄NIL˅ᱟ唁ⲴDŽ 2˅ṩ㔃⛩ᱟ唁ⲴDŽ 1˅˅⇿њ㔃⛩㾱Ѹᱟ㓒Ⲵˈ㾱Ѹᱟ唁ⲴDŽ 䇱ԕлⲴӻ㓽о䱀䘠␵Რˈᡁㅜй⅑䟽߉л㓒唁ṁⲴ 5 њᙗ䍘؍ѪҶ 23 color[x] ĕ BLACK 22 else (same as then clause with "right" and "left" exchanged) Case 4 ڿ [21 x ĕ root[T Case 4 ڿ ([20 LEFT-ROTATE(T, p[x Case 4 ڿ 19 color[right[w]] ĕ BLACK Case 4 ڿ 18 color[p[x]] ĕ BLACK Case 4 ڿ [[17 color[w] ĕ color[p[x Case 3 ڿ [[16 w ĕ right[p[x Case 3 ڿ (15 RIGHT-ROTATE(T, w Case 3 ڿ 14 color[w] ĕ RED Case 3 ڿ 13 then color[left[w]] ĕ BLACK 12 else if color[right[w]] = BLACK Case 2 ڿ [11 x p[x Case 2 ڿ 10 then color[w] ĕ RED 9 if color[left[w]] = BLACK and color[right[w]] = BLACK Case 1 ڿ [[ 8 w ĕ right[p[x Case 1 ڿ ([ 7 LEFT-ROTATE(T, p[x Case 1 ڿ 6 color[p[x]] ĕ RED Case 1 ڿ 5 then color[w] ĕ BLACK 4 if color[w] = RED 3 then w ĕ right[p[x]] 2 do if x = left[p[x]] 1 while x ≠ root[T] and color[x] = BLACK ᤱ㓒唁ᙗ䍘Ⲵᐕ֌؍RB-DELETE-FIXUP(T, x) ᚒ༽о 96 ˖ 3.ਈॆࡽ ⛩Ѫ唁㢢ⲴᛵߥDŽ а⅑ᐖ᯻DŽ↔ਈᦒਾ৏㓒唁ṁᙗ䍘 5 нਈˈ㘼ᢺ䰞仈䖜ॆѪݴᕏ㢲ڊ ❦ਾˈ䪸ሩ⡦㢲⛩ 㢲⛩ᱟަ⡦㢲⛩ᐖᆙᆀᰦⲴᛵߥ˅DŽ ㇇⌅˄ᡁԜਚ䇘䇪ᖃࡽޕ 䀓⌅˖ᢺ⡦㢲⛩ḃᡀ㓒㢢ˈᢺݴᕏ㔃⛩ḃᡀ唁㢢ˈѻਾ䟽ᯠ䘋 ᛵߥ 3˖ᖃࡽ㢲⛩ᱟ唁㢢ˈфݴᕏ㢲⛩Ѫ㓒㢢(↔ᰦ⡦㢲⛩઼ݴᕏ㢲⛩Ⲵᆀ㢲⛩࠶Ѫ唁)DŽ 㔃ᶏˈڊ 䀓⌅˖ӰѸ䜭н ᛵߥ 2˖ᖃࡽ㢲⛩ᱟ唁㢢фᱟṩ㢲⛩ 䜘ᚒ༽DŽޘ ↔ᰦ㓒唁ṁᙗ䍘 䀓⌅ˈⴤ᧕ᢺᖃࡽ㢲⛩ḃᡀ唁㢢ˈ㔃ᶏDŽ ᛵߥ 1˖ᖃࡽ㢲⛩ᱟ㓒㢢 ѝ case1ˈcase2ˈcase3ˈcase4 ⴨ሩᓄDŽ) ᤱ؍ (⌘˖ԕлⲴᛵߥ 3ǃ4ǃ5ǃ6ˈок䘠㇇⌅ሬ䇪ѻԓ⸱ RB-DELETE-FIXUP(T, x) ᚒ༽о ------------------------------------------------------------ Ҽ䴦ааᒤаᴸгᰕᴤᯠDŽ Ⲵ؞༽㓒唁ṁᙗ䍘Ⲵᐕ֌DŽڊ㘼л䶒ᡰᴹⲴ᮷ᆇˈࡉᱟ䪸ሩ㓒唁ṁࡐ䲔㔃⛩ਾˈᡰ 2ǃ䈳ᮤ䜘࠶ᤷ䪸Ⲵᤷੁˈণᐖ᯻ǃਣ᯻DŽ 1ǃ䜘࠶㔃⛩仌㢢ˈ䟽ᯠ⵰㢢 ؙᯩ