分散コンピューティング制御効率化のための平方分割手法による動的グラフにおける最小全域木クエリ処理

全文

(1)情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2016-AL-158 No.9 2016/6/25. ෼ࢄίϯϐϡʔςΟϯά੍‫཰ޮޚ‬ԽͷͨΊͷ ฏํ෼ׂख๏ʹΑΔ ಈతάϥϑʹ͓͚Δ࠷খશҬ໦ΫΤϦॲཧ ࢁ࡚ Ұ໌ ,a). ֓ཁɿϞόΠϧ‫Ͱثػ‬ͷ෼ࢄίϯϐϡʔςΟϯά੍‫ޚ‬͸σʔλసૹʹແઢ௨৴Λར༻͢Δ͕ɼ‫ڥ؀‬ͷӨ‫ڹ‬ Λड͚ίετ΍Մ༻ੑ͕มԽ͢Δແઢ௨৴ʹ͓͍ͯ͸ɼ࠷దͳωοτϫʔΫ΋มԽ͢Δɽ࠷దͳωοτ ϫʔΫͱ͸άϥϑཧ࿦ʹ͓͚Δ࠷খશҬ໦ʹରԠ͢Δɽຊ‫ڀݚ‬͸࠷খશҬ໦ʹ‫͍ͯͮج‬ωοτϫʔΫΛ࠶ ߏங͢Δ͜ͱͰ௨৴ίετΛ࠷খԽͰ͖Δ͜ͱΛࣔ͠ɼͦͷͨΊͷޮ཰తͳख๏ΛఏҊ͢Δ͜ͱΛ໨తͱ ͢Δɽάϥϑ G = (V, E) ͷ࠷খશҬ໦Λ‫ٻ‬ΊΔ Prim ΍ Kruskal ͷΞϧΰϦζϜ͕͋Δ͕ɼͲͪΒ΋ O(|V|2 ) ͕͔͔࣌ؒΔɽఏҊख๏Ͱ͸ɼάϥϑมԽ࣌ͷ࠷খશҬ໦ͷมԽ͸‫ॴہ‬తͰ͋Δ͜ͱΛར༻͢Δɽ௖఺ू √ ߹ V Λ |V| ‫ݸ‬ఔ౓ͷΫϥελʹ෼ׂ͠ɼͦΕʹ‫͍ͯͮج‬ลू߹Λ෼ׂ͢Δ͜ͱͰลͷ୳ࡧΛޮ཰ԽͰ͖ ΔɽάϥϑͷมԽʹରͯ͠͸਺‫ݸ‬ͷΫϥελͷ෼ׂɾ౷߹ʹΑΓɼߴ଎୳ࡧ͕Մೳͳลू߹෼ׂΛҡ࣋͢ √ Δɽཧ࿦ղੳʹΑΓఏҊख๏͕ O(|V| |V|) ࣌ؒͰಈ࡞͢Δ͜ͱΛࣔ͠ɼ‫ʹݧ࣮ػࢉܭ‬ΑΓ‫ط‬ଘख๏ͱൺֱ ͯ͠े෼ߴ଎ʹಈ࡞͢Δ͜ͱΛࣔͨ͠ɽ͜ΕʹΑΓɼϞόΠϧ‫Ͱثػ‬ͷ෼ࢄίϯϐϡʔςΟϯά੍‫͓ʹޚ‬ ͚Δ௨৴ίετ࠷খԽͷͨΊͷख๏ͷఏҊ͕Ͱ͖ͨɽ Ωʔϫʔυɿಈతάϥϑɼ࠷খશҬ໦. MST Query on Dynamic Graph with Square-Root-Decomposition for Optimization for Controlling Distributed Computing Yamazaki Kazuaki ,a). Abstract: Distributed computing on mobile entities uses wireless communication for data transportation. Costs and availability of wireless communication changes aﬀected by surroundings, thus optimal network (corresponds a MST) also change. Dynamic network can be modeled in dynamic graphs. This paper proposes a method for calculating Minimum Spanning Tree (MST) on dynamic graphs eﬃciently. The method is based on square-root-decomposition on tree nodes and dividing edge set into several sets according vertex dividing. Then, number of edges that candidate for MST is decreased and we can search edge in shorter time. Keywords: Dynamic Graphs, Minimum Spanning Trees. 1. ·͕͖͑ 1.1 എ‫ܠ‬ ۙ೥ɼεϚʔτϑΥϯͳͲΛ͸͡Ίͱ͢ΔϞόΠϧ‫ثػ‬ ͷԋࢉੑೳ͕޲্͍ͯ͠Δɽ·ͨɼϞόΠϧ‫ثػ‬͸ɼແઢ ௨৴Λ༻͍ͯ૬‫ʹޓ‬௨৴͢Δ͜ͱ͕Ͱ͖Δɽ͜͏ͨ͠ঢ়‫گ‬ a). [email protected]. ⓒ 2016 Information Processing Society of Japan. ʹΑΓɼϞόΠϧ‫ثػ‬Λར༻ͨ͠෼ࢄίϯϐϡʔςΟϯά ͕‫࣮ݱ‬తͳ΋ͷͱͳͬͨɽ ϞόΠϧ‫ثػ‬ΛऔΓ‫ڥ؀͘ר‬͸ਓ΍෺ମͷҠಈʹΑͬͯ มԽ͢ΔɽͦΕʹରԠͯ͠ɼ‫ؒثػ‬ͷ௚઀௨৴ͷίετ΍ Մ༻ੑ΋पғͷ‫ڥ؀‬ͷมԽʹରԠͯ͠มԽ͢Δɽ ͋ΔϞόΠϧ‫͕܈ثػ‬ར༻Մೳͳແઢ௨৴͸ɼ‫ثػ‬Λ௖ ఺ͱ͠ɼ‫ؒثػ‬ͷ௨৴Λลͱͨ͠άϥϑͱͯ͠ද‫͖Ͱݱ‬Δɽ. 1.

(2) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2016-AL-158 No.9 2016/6/25. . ͔͠͠ɼઌʹड़΂ͨΑ͏ʹແઢ௨৴ͷίετ΍Մ༻ੑ͸प ล‫ڥ؀‬ͷมԽͷӨ‫ڹ‬Λड͚มԽ͢ΔͨΊɼͦΕΛද‫ͨ͠ݱ‬ άϥϑ΋มԽ͢ΔɽैͬͯɼάϥϑͷมԽΛѻ͏ख๏͕ඞ.

(3) . ཁͱͳΔɽ. 1.2 ຊ‫ڀݚ‬ͷ໨త. ਤ1. 2 छྨͷΫΤϦ. ຊ‫ͱ͜͏ߦͰڀݚ‬͸ҎԼͷ఺Ͱ͋Δɽ. ( 1 ) पล‫ڥ؀‬ͷແઢ௨৴΁ͷӨ‫ͱڹ‬෼ࢄίϯϐϡʔςΟϯ ά੍‫͍ͯͭʹޚ‬ड़΂ɼ௨৴ίετ࠷খԽͷҙٛΛࣔ͢. ͳωοτϫʔΫΛར༻͢Δ͕࣌ؒ୹ॖ͠ɼ௨৴ʹඞཁͳి ྗ΍͕࣌ؒ‫ݮ‬গ͢Δɽ. ( 2 ) ໰୊ΛάϥϑʹఆࣜԽ͠ɼมߋΫΤϦΛಋೖ͢Δ. 3. ໰୊ͷఆࣜԽ. ( 3 ) άϥϑมߋΫΤϦΛޮ཰తʹॲཧ͢Δख๏ΛఏҊ͢Δ. 3.1 άϥϑɾMST. ( 4 ) ఏҊख๏ͷཧ࿦ղੳΛߦ͏ ( 5 ) ‫ط‬ଘख๏ͱఏҊख๏Λ࣮૷͠ɼ‫ؒ࣌ࢉܭ‬Λൺֱ͢Δ. 2. ෼ࢄίϯϐϡʔςΟϯά੍‫཰ޮޚ‬Խ 2.1 ϞόΠϧ‫্ثػ‬ͷ෼ࢄίϯϐϡʔςΟϯά੍‫ޚ‬ ϞόΠϧ‫্ثػ‬ͷ෼ࢄίϯϐϡʔςΟϯάͰ͸ɼϞόΠ ϧ‫͕܈ثػ‬ωοτϫʔΫΛߏ੒͢Δɽ ి೾௨৴ʹ͓͍ͯɼΞϯςφͷੑೳ΍‫ͱྗిͱ཭ڑ‬ͷ 2 λ ؔ܎Λද͕ࣜ͢ PPrt = 4πD Gt Gr ʢFriis ͷ఻ୡެࣜʣͰ͋ Δ [1]ɽ͜͜ͰɼPr ͸ड৴ిྗΛද͠ɼPt ͸ૹ৴ిྗΛද ͢ɽGt , Gr , λ ͸Ξϯςφͷੑೳ΍ి೾ͷ೾௕Λද͢ม਺Ͱ. άϥϑͱ͸ɼ௖఺ू߹ V ͱลू߹ू߹ E ⊆ V 2 ͷ૊. G = (V, E, w) Ͱ͋ΔɽॏΈ෇͖άϥϑͱ͸ɼάϥϑʹɼॏ Έؔ਺ w : E → Z+ ΛՃ͑ͨ (V, E, w) Ͱ͋Δɽຊ࿦จͰѻ ͏άϥϑ͸ແ޲άϥϑͷΈͰ͋ΔͨΊɼҎ߱ແ޲άϥϑͷ ͜ͱΛ୯ʹάϥϑͱॻ͖ɼ(u, v) = (v, u) Ͱ͋Δͱ͢Δɽ· ͨɼಉҰͷ௖఺Λ݁Ϳล (v, v) ∈ E ͸ଘࡏͤͣɼ·ͨɼάϥ ϑ͸ৗʹ࿈݁Ͱ͋ΔͱԾఆ͢Δɽ ࿈݁ͳάϥϑͰ͋ͬͯด࿏Λ‫͍ͳ·ؚ‬άϥϑ (V, E) Λ໦ ͱΑͿɽάϥϑ͕໦ͷͱ͖ɼ|E| = |V| − 1 Ͱ͋Δɽ໦ (V, T ) ͕‫ؚ‬ΉลͷॏΈͷ૯࿨ e∈T w(e) Λ໦ͷॏΈͱ‫Ϳݺ‬ɽ͋Δ άϥϑ G = (V, E) ʹର͠ɼ໦ (V, T ) Λ G ͷશҬ໦ͱ‫Ϳݺ‬ɽG. ͋Δ͕ɼར༻͢Δ୺຤΍प೾਺Λ‫ݻ‬ఆ͢Δͱఆ਺ͱ‫ݟ‬၏ͤ. ͷશҬ໦ͷ಺ɼॏΈ͕࠷খͷ΋ͷΛ G ͷ࠷খશҬ໦ ( MST. Δɽࣜ ?? ͔Βɼແઢ௨৴ʹΑΔϞόΠϧ‫ؒثػ‬ͷ௚઀௨. : Minimum Spanning Tree ) ͱ‫Ϳݺ‬ɽҎ߱͸ MST ͱॻ͘ɽ. ৴͸ɼ୺຤ͷҠಈͷӨ‫ڹ‬Λड͚ͯՄ༻ੑ΍ඞཁిྗ͕มԽ ͢Δͱ‫͑ݴ‬Δɽ·ͨɼো֐෺ͷӨ‫ڹ‬Λड͚ͯ௨৴Մೳ‫཭ڑ‬ ΍఻ૹ଎౓͕มԽ͢Δ [2]ɽ. 3.2 άϥϑมߋΫΤϦ΁ͷ‫ؼ‬ண Ϟ ό Π ϧ ‫ ث ػ‬ͷ ू ߹ Λ V ͱ ͠ ɼू ߹ E = {(u, v) |. 2 ‫ ثػ‬u, v ∈ V ؒͰ௨৴Մೳ } ΛͱΔɽؔ਺ w : E → Z+. 2.2 ੍‫ޚ‬ͷޮ཰ԽͷͨΊͷωοτϫʔΫߏ଄. Λ w((u, v)) := u, v ؒͷ௨৴ʹ͔͔Δίετ Ͱ͋Δؔ਺ͱ. 2.2.1 ωοτϫʔΫ্ͷ઀ଓঢ়ଶΛ͋ΒΘ͢໦. ͢Ε͹ɼάϥϑ G = (V, E, w) ͸͋Δ࣌఺Ͱར༻Մೳͳ௨৴. ෼ࢄίϯϐϡʔςΟϯά੍‫͍͓ͯʹޚ‬͸ɼ໦ͱ͍͏τϙ ϩδͷωοτϫʔΫΛߏ੒͢Δ͜ͱͰɼޮ཰తͳ੍‫ޚ‬Λ࣮ ‫͖Ͱݱ‬Δ [3]ɽ໦͸ɼϞόΠϧ‫܈ثػ‬Λ૬‫઀ʹޓ‬ଓ͢Δߏ ଄ͱͯ͠͸ߏ଄͕࠷΋୯७ͳ΋ͷͰ͋Δͱ‫͑ݴ‬Δɽτϙϩ δ͕໦ͱͳ͍ͬͯΔͱ͖ɼωοτϫʔΫதͷ೚ҙͷ‫͔ثػ‬ Βผͷ೚ҙͷ‫΁ثػ‬ͷ఻ૹ‫ܦ‬࿏͸ͨͩҰͭʹఆ·Δɽ. 2.2.2 ωοτϫʔΫߏ଄ͷมԽ΁ͷରԠ໰୊ 2.1 અͰड़΂ͨΑ͏ʹɼແઢ௨৴͸पғͷ‫ʹڥ؀‬Αͬͯ ௨৴ʹඞཁͳిྗ΍௨৴Մೳͳ‫͕཭ڑ‬มԽ͢Δɽ ‫ؒثػ‬ͷ௨৴ʹ͸ফඅిྗ΍଎౓ͰίετΛఆٛͰ͖Δ ͷͰɼ௚઀௨৴ͷू߹Ͱ͋ΔωοτϫʔΫશମͷίετ͸ ௨৴ͷίετͷ࿨ͱͯ͠ఆٛͰ͖Δɽ௨৴ͷίετ΍Մ༻ ੑ͕ಈతʹมԽ͢ΔதͰɼ֤࣌఺ʹ͓͍ͯ࠷খίετͰ࣮ ‫͖Ͱݱ‬ΔωοτϫʔΫΛߏ੒͢Δ͜ͱ͕ɼίετΛ࠷খԽ. Λද͢ɽ࠷దͳωοτϫʔΫ͸ɼG ͷ MST ʹରԠ͢Δɽ ωοτϫʔΫͷมԽΛѻ͏ͨΊʹɼάϥϑʹର͢ΔҎԼ ͷೋͭͷมߋૢ࡞Λఆٛ͢Δɽ. ( 1 ) add(u, v, x) E ʹ (u, v) ΛՃ͑ w((u, v)) ← x ͱ͢Δ ( 2 ) remove(u, v) E ͔Β (u, v) Λ࡟আ͢Δ 2 छྨͷΫΤϦΛਤ 1 ʹࣔ͢ɽਤʹ͓͍ͯɼଠ͍ઢͰඳ ͔Ε͍ͯΔล͕ΫΤϦʹΑΓมԽ͢ΔลͰ͋Δɽ2 ͭͷૢ ࡞ add ͱ remove ͸‫ٯʹ͍ޓ‬ͷૢ࡞ͱͳ͍ͬͯΔɽ ͋Δ࣌ؒൣғʹ͓͚Δ௨৴ͷঢ়ଶมԽ͸ɼ্‫ه‬ΫΤϦͷ ྻͱͯ͠ද‫͖Ͱݱ‬ΔɽมԽ͢ΔάϥϑΛಈతάϥϑͱ‫Ϳݺ‬ɽ. 4. άϥϑมߋͷख๏ 4.1 ‫ط‬ଘख๏. ͢Δ͜ͱʹ‫͕ܨ‬Δɽ࠷খίετͰ࣮‫͖Ͱݱ‬ΔωοτϫʔΫ. ಈతͰͳ͍άϥϑͷ MST Λ‫ٻ‬ΊΔख๏ͱͯ͠ɼPrim ͷ. ʹରԠ͢Δ໦Λ࠷খશҬ໦ͱ‫͏ݴ‬ɽ୹࣌ؒͰมԽ‫ޙ‬ͷ࠷খ. ΞϧΰϦζϜ [4], [5] ͱ Kruskal ͷΞϧΰϦζϜ [4], [6] ͕. શҬ໦Λ‫ٻ‬ΊωοτϫʔΫΛ࠶ߏ੒͢Δ͜ͱͰɼඇޮ཰త. ͋ΔɽPrim ͷΞϧΰϦζϜΛ༻͍ͯಈతάϥϑ্ͷ MST. ⓒ 2016 Information Processing Society of Japan. 2.

(4) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2016-AL-158 No.9 2016/6/25. ΫΤϦΛॲཧ͢Δ৔߹ɼมߋΫΤϦΛ Q ճॲཧ͢ΔͨΊʹ ͸ O(Q|E| log |V|) ͕͔͔࣌ؒΔɽKruskal ͷΞϧΰϦζϜΛ ༻͍ͯಈతάϥϑ্Ͱͷ MST ΫΤϦΛॲཧ͢Δ৔߹ɼม ߋΫΤϦΛ Q ճॲཧ͢ΔͨΊʹ͸ O(Q|E| log |E|) ͕͔࣌ؒ ͔Δɽ. . Kruskal ͷΞϧΰϦζϜΛར༻ͨ͠ΑΓޮ཰తͳΞϧΰ. .

(5) . ϦζϜͱͯ͠ɼลॏΈʹؔͯ͠ঢॱιʔτࡁΈͷลϦετ Λอ࣋͠ɼมߋΫΤϦͷͨͼʹιʔτࡁΈϦετ΁ૠೖɾ ࡟আ͢Δ͜ͱʹΑͬͯ৽ͨͳιʔτࡁΈลϦετΛಘΔΞ. ਤ 2 ௖఺ͷΫϥελϦϯά. ϧΰϦζϜΛߏ੒Ͱ͖Δɽ͜ͷख๏Λ Enhanced Kruskal ͱ ‫͢ʹͱ͜Ϳݺ‬ΔɽEnhanced Kruskal Λ༻͍ͯมߋΫΤϦΛ. Q ճॲཧ͢Δʹ͸ O(Q|E|) ͕͔͔࣌ؒΔɽ ઴ۙతʹ΋ͬͱ΋ߴ଎ʹಈ࡞͢Δͷ͸ Enhanced Kruskal Ͱ͋Δɽ͜ͷ͜ͱ͔Βɼ‫ط‬ଘख๏Λ༻͍ͯάϥϑมߋΫΤ ϦΛ Q ॲཧ͢Δʹ͸ O(Q|E|) ͕࣌ؒඞཁͰ͋Δͱ‫͑ݴ‬Δɽ. 4.2 ఏҊख๏ άϥϑ G = (V, E) ͷมԽ͸ɼҎԼͷ 4 ௨Γʹ෼ྨͰ͖Δɽ. ( 1 ) ล͕௥Ճ͞Εɼมߋ‫ޙ‬ͷ MST ͕ͦͷลΛ‫ؚ‬Ήͱ͖ ( 2 ) ล͕௥Ճ͞Εɼมߋ‫ޙ‬ͷ MST ͕ͦͷลΛ‫͖ͱ͍ͳ·ؚ‬ ( 3 ) ล͕࡟আ͞Εɼมߋલͷ MST ͕ͦͷลΛ‫ؚ‬Ήͱ͖ ( 4 ) ล͕࡟আ͞Εɼมߋલͷ MST ͕ͦͷลΛ‫͖ͱ͍ͳ·ؚ‬ (2) ͱ (4) ͷ৔߹͸ MST ͸มԽ͠ͳ͍ɽ. ಺෦ล ֎෦ล ਤ 3 ಺෦ลͱ֎෦ลΛநग़ͨ͠ਤ. ଄ʹ‫͍ͯͮج‬௖఺ू߹Λ෼ׂ͠ɼͦΕΛลू߹෼ׂͷ‫ج‬४ ͱ͢Δɽண໨͍ͯ͠Δ (3) ͷέʔε͸ T ͔Β͋Δล (u, v) ΛऔΓআ͍ͨ৔߹Λ‫ؚ‬Ή͕ɼ͜ͷ৔߹͸ T = T \ {(u, v)} ͱ ͯ͠άϥϑ S = (V, T ) ͷߏ଄Λ‫ج‬४ͱ͢Δɽ෼ׂʹ͓͍. (1) ͷͱ͖ɼMST ʹลΛՃ͑Δͱด࿏͕Ͱ͖Δɽ͜ͷ৔. ͯ͸ɼ௖఺ू߹Λ n ‫ݸ‬ͷ෦෼ू߹ V0 , V1 , . . . , Vn−1 ⊆ V ʹ෼. ߹ɼͰ͖ͨด࿏͔ΒॏΈ͕࠷΋େ͖͍ลΛऔΓআ͘͜ͱͰɼ. ׂ͠ɼ∀i, j(0 ≤ i, j < n, i j), Vi ∩ V j = ∅ ͱͳΔΑ͏ʹ͢Δɽ. άϥϑมԽ‫ޙ‬ͷ MST ͱͳΔͷͰɼ͜ͷ৔߹͸ล 2 ຊ͚ͩ. ߋʹ֤ Vi ʹ͍ͭͯɼVi ʹΑΔ S ͷ༠ಋ෦෼άϥϑ͕࿈݁. MST ͕มԽ͢Δɽ. ͱͳΔΑ͏ʹ͢Δɽ͜ͷ෼ׂΛΫϥελϦϯάͱ‫ͼݺ‬ɼ෼. (3) ͷͱ͖ɼMST ͔ΒลΛऔΓআ͘ͱೋͭͷ࿈݁੒෼͔. ׂ‫ޙ‬ͷ֤௖఺ू߹ΛΫϥελͱ‫Ϳݺ‬ɽΫϥελϦϯάͷྫ. ΒͳΔάϥϑʹͳΔɽ͜ͷ৔߹ɼҟͳΔ࿈݁੒෼ʹଐ͢Δ. Λਤ 2 ʹࣔ͢ɽਤͷάϥϑʹ͓͍ͯɼଠࣔͨ͘͠ล͕άϥ. ௖఺ؒΛ݁Ϳลͷ಺ͰɼลॏΈ͕࠷খͷ΋ͷΛՃ͑Δ͜ͱ. ϑͷ MST ͕‫ؚ‬ΉลͰ͋ΔɽഁઢͰඳ͔Εͨ࿮ͰғΘΕͯ. ͰɼάϥϑมԽ‫ޙ‬ͷ MST ͱͳΔɽैͬͯɼ͜ͷ৔߹΋ล. ͍Δ௖఺‫͕ͦ܈‬ΕͧΕͷΫϥελͰ͋Δɽ. 2 ຊ͚ͩ MST ͕มԽ͢Δɽ Ҏ্ʹΑΓɼ(1), (2), (3), (4) ͷ͍ͣΕͷ৔߹Ͱ΋ɼMST ͷมԽ͸ߴʑ 2 ຊͷลͰ͋Δɽ. 4.1 અͰࣔͨ͠ΞϧΰϦζϜ͸͍ͣΕ΋άϥϑ͕มԽ͢ ΔͨͼʹશͯͷลΛௐ΂ MST Λ࠶‫͍ͯ͠ࢉܭ‬Δ͕ɼ্Ͱ ࣔͨ͜͠ͱΛ౿·͑Δͱແବͳ‫ࢉܭ‬Λ͍ͯ͠ΔɽఏҊख๏ Ͱ͸֤࣌఺ʹ͓͚Δ MST Λอ࣋͠ɼมߋΫΤϦʹΑΓม Խ͢ΔลΛޮ཰తʹ୳ࡧ͢Δ͜ͱͰޮ཰Խ͢Δɽ ީิͱͳΔลͷ਺͸ (3) ͷέʔε͕࠷΋ଟ͍ͨΊɼ(3) ͷ. ลू߹ͷ෼ׂͰ͸ɼ֤ลू߹͕࣍ͷ৚݅ͷ͍ͣΕ͔Λຬ ͨ͢Α͏ʹ͢Δɽ. ( 1 ) ͋Δ i ( 0 ≤ i < n ) ͕ଘࡏͯ͠ɼลू߹͕‫ؚ‬Ή֤ลʹͭ ͍ͯ୺఺͕ͲͪΒ΋ Vi ʹଐ͢Δ. ( 2 ) ͋Δ i, j ( 0 ≤ i, j < n, i j ) ͕ଘࡏͯ͠ɼลू߹͕‫ؚ‬Ή ֤ลͷ୺఺ͷҰํ͕ Vi ʹଐ͠ɼଞํ͕ V j ʹଐ͢Δ લऀͷ৚݅Λຬͨ͢ลΛɼΫϥελͷ಺෦Λ݁Ϳ͜ͱ͔Β ಺෦ลͱ‫Ϳݺ‬ɽ‫ऀޙ‬ͷ৚݅Λຬͨ͢ลΛɼҟͳΔΫϥελ. έʔεΛߴ଎Խ͢Δ͜ͱ͕ߴ଎ԽͷͨΊͷओ୊ͱͳΔɽ. ؒΛ݁ͼɼΫϥελͷ֎෦Λ௨Δ͜ͱ͔Β֎෦ลͱ‫Ϳݺ‬ɽ. 4.2.1 ลू߹ͷฏํ෼ׂ. ֤ΫϥελɼΫϥελͷରʹ͍ͭͯରԠ͢Δลू߹͕ଘࡏ. 4.2 અͷ (3) ͷέʔεʹ͓͍ͯล࡟আ‫ ʹޙ‬MST ʹՃ͑Δ. ͠ɼશͯͷล͸͍ͣΕ͔ͷลू߹ʹ֘౰͢ΔɽMST ͕‫ؚ‬Ή. ลͷ୳ࡧʹ O(|V|2 ) ͕࣌ؒඞཁͱͳΔɽ͜Ε͸ɼ୳ࡧର৅. ลʹ͍ͭͯ͸ɼT ʹՃ͑ͯ MST Λߏங͢Δࡍʹ࢖͏ลͱ. ͱͳΔลϦετͷ௕͕͞ O(|V|2 ) ͱͳΔͨΊͰ͋ΔɽఏҊ. ͳΓಘͳ͍ͷͰɼ෼ׂͨ͠ลू߹ʹ‫ؚ‬Ίͳ͍ɽਤ 2 ͔Β಺. ख๏Ͱ͸ɼลϦετΛ෼ׂͯ͠ෳ਺ͷลϦετΛอ࣋͢Δɽ. ෦ลͱ֎෦ลΛநग़ͨ͠ਤΛਤ 3 ʹࣔ͢ɽ. ลू߹Λ෼ׂ͢Δʹ͋ͨΓɼ·ͣ͸ MST S = (V, T ) ͷߏ ⓒ 2016 Information Processing Society of Japan. ෼ׂ֤ͨ͠ลू߹Λද͢ลϦετ͸ɼ4.1 ͷ Enhanced. 3.

(6) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2016-AL-158 No.9 2016/6/25. . Kruskal ͱಉ༷ʹॏΈʹؔͯ͠ঢॱιʔτࡁΈͷঢ়ଶΛอ ͭɽ͜ͷ৔߹ɼ(3) ͷέʔεͰ MST ෼அ‫ ʹޙ‬MST ʹՃ͑. . . Δล͸͍ͣΕ͔ͷลϦετͷઌ಄ʹ͋Δɽैͬͯɼลू߹ Λ m ‫ʹݸ‬෼ׂͨ͠ͱ͢Ε͹ɼMST ʹՃ͑Δลͷ୳ࡧ͸֎ ෦ลू߹ʹରԠ͢ΔลϦετʹ͍ͭͯઌ಄ཁૉ͚ͩΛର৅. . . . . . . ʹ͢Ε͹Α͍ͷͰ O(m) ࣌ؒͰ࣮ߦՄೳͰ͋Δɽ ௖఺ू߹ͷ෼ׂͷํ๏ʹΑͬͯลͷू߹ͷ෼ׂ͕มΘΓɼ. . ลͷ୳ࡧʹඞཁͳ‫ྔࢉܭ‬΋มΘΔɽఏҊख๏Ͱ͸ɼΫϥε √ λ਺ n ͕ |V| ఔ౓ͱͳΔΑ͏ʹ෼ׂ͢Δɽߏ଄͕ዞҙత. . . . Ͱͳ͍άϥϑͰ͜ΕΛ࣮‫͢ݱ‬Δʹ͸ɼॴଐΫϥελ͕ܾఆ ͞Ε͍ͯͳ͍ద౰ͳ௖఺͔Β MST ্Ͱͷ෯༏ઌ୳ࡧΛߦ √ ͍ɼ๚໰ࡁΈ͔ͭΫϥελະܾఆͳ௖఺͕ |V| ‫ͬͳʹݸ‬ ͨ࣌఺ͰͦΕΒͷ௖఺ΛҰͭͷΫϥελͱ͢ΔॲཧΛɼະ ๚໰௖఺͕ແ͘ͳΔ·Ͱ‫܁‬Γฦͤ͹Α͍ [7]ɽ͜ΕʹΑΓɼ √ ֤Ϋϥελʹଐ͢Δ௖఺਺͕ฏ‫ۉ‬తʹ |V| ‫ͳͱݸ‬ΔɽΫ √ ϥελ਺͸௖఺਺ |V| ΛΫϥελͷฏ‫ۉ‬αΠζ |V| Ͱׂͬ √ √ ͨ஋ఔ౓Ͱ͋ΔͨΊɼ √|V||V| = |V| ΑΓɼΫϥελ਺͸ |V|. . (ii) Ϋϥελͷ౷߹ ਤ 4 Ϋϥελͷ෼ׂɾ౷߹. ͷลू߹. ( 1 ) ci ͷ಺෦ลू߹. ‫ݸ‬ఔ౓ͱͳΔɽΫϥελϦϯάͷ‫ʹࢉܭ‬ଓ͖ɼ‫ͨ͠ࢉܭ‬Ϋ. ( 2 ) c j ͷ಺෦ลू߹. ϥελϦϯάʹ‫͍ͯͮج‬ลू߹Λ෼ׂ͢ΔɽશͯͷลΛॏ. ( 3 ) ci , c j ؒͷ֎෦ลू߹. Έʹؔͯ͠ঢॱιʔτ͠ɼลϦετͷઌ಄͔ΒॱʹลΛৼ Γ෼͚Ε͹ɼลू߹ͷ෼ׂ͸ O(|E| log |E|) = O(|V|2 log |V|) ࣌ؒͰ‫ྃ͢׬‬Δɽ. 4.2.2 ΫΤϦͷฏํ෼ׂ 5 ষͰࣔ͢Α͏ʹɼఏҊख๏Ͱ͸άϥϑτϙϩδͷมԽ ʹ߹ΘͤͯΫϥελϦϯάΛߋ৽͢Δɽ͜ͷͱ͖ɼάϥϑ ͷશମΛௐ΂Δ͜ͱͳ͘ɼมԽͨ͠෦෼ͷपลͷΈΛ࠶Ϋ ϥελϦϯά͢Δ͜ͱͰ‫ؒ࣌ࢉܭ‬Λ୹ॖ͢ΔɽͦͷͨΊɼ ෳ਺ͷมߋΫΤϦͷॲཧΛ௨ͯ͠ɼΫϥελϦϯά͕ཧ૝ తͳঢ়ଶͰ͸ͳ͘ͳΔɽͦ͜ͰఏҊख๏Ͱ͸ɼΫΤϦྻΛ ͋Δఔ౓ͷ௕͞ͷप‫Ͱظ‬෼ׂ͠ɼप‫ظ‬ͷ։࢝࣌ʹάϥϑશ ମ΁ͷ෯༏ઌ୳ࡧΛߦͬͯΫϥελϦϯάΛ࠶‫͢ࢉܭ‬Δɽ प‫ظ‬͸ |V| ʢล਺ͷฏํࠜʣఔ౓ͱ͢Δɽ ͜ͷͱ͖ɼΫΤϦҰճ͋ͨΓͷ࣌ؒ‫ ͕ྔࢉܭ‬Ω(|V|) Ͱ͋. Λ౷߹͠ c i ͷ಺෦ลू߹ͱ͢ΔɽͦͷଞͷΫϥελ ck (. k {i, j} ) ʹ͍ͭͯɼೋͭͷลू߹ ( 1 ) c j , ck ؒͷ֎෦ลू߹ ( 2 ) ci , ck ؒͷ֎෦ลू߹ Λ౷߹͠ c i , ck ؒͷ֎෦ลू߹ͱ͢Δɽ͜ͷ݁Ռɼ౷߹ʹ ΑΓফ໓͢ΔΫϥελ c j ʹؔΘΔ಺෦ลɾ֎෦ล͸શͯ৽ ͨͳลू߹΁Ҡಈ͢Δɽ ลू߹ͷ౷߹ͷྫΛਤ 4 ʹࣔ͢ɽ(i) ʹ͓͚ΔΫϥελ. 1, 2 Λ౷߹͢Δͱɼ(ii) ʹ͓͚ΔΫϥελ 4 ʹͳΔɽ྆ਤʹ ͓͚ΔΫϥελ 3 ͸౷߹ʹ௚઀ؔΘΒͳ͍ΫϥελͰɼ্ ‫ه‬ͷ ck ʹ͋ͨΔɽਤ 4 ʹ͓͚Δล a, b, c, d, e ͷ෼ྨΛࣔ͢ ͱҎԼͷΑ͏ʹͳΔɽ. Ε͹ɼมߋΫΤϦ |V| ճ͝ͱͷ෯༏ઌ୳ࡧʹ͔͔Δ࣌ؒί. ( 1 ) a : Ϋϥελ 1 ͷ಺෦ล. ετ͸ఆ਺ഒͷࠩʹऩ·Δɽ6.1 અͰࣔ͢Α͏ʹ͜ͷ৚݅. ( 2 ) b : Ϋϥελ 2 ͷ಺෦ล. ͸ॆ଍͞Εɼ|V| ճ͝ͱͷ࠶ΫϥελϦϯάͷঈ٫࣌ؒ‫ࢉܭ‬. ( 3 ) c : Ϋϥελ 1, 2 ؒͷ֎෦ล. ྔ͸ O(1) ࣌ؒͱͳΔɽ. ( 4 ) d : Ϋϥελ 1, 3 ؒͷ֎෦ล. 5. άϥϑมߋख๏ͷৄࡉ. ( 5 ) e : Ϋϥελ 2, 3 ؒͷ֎෦ล. ఏҊख๏Ͱ͸ɼάϥϑͷมߋʹ߹ΘͤͯҰ෦ͷΫϥελ ͷΈΛมߋ͢Δɽ͜ΕʹΑΓɼάϥϑมߋΫΤϦͷͨͼʹ ΫϥελϦϯάͷ࠶‫ࢉܭ‬Λ͢Δ͜ͱͳ͘มߋ‫ޙ‬ͷลू߹ ෼ׂΛಘΔɽΫϥελϦϯάͷมԽʹ߹Θͤͯลू߹Λ౷ ߹ɾ෼ׂ͢Δ͜ͱͰɼมߋΫΤϦडཧ‫ʹޙ‬΋ 4.2 અͰࣔ͠ ͨล୳ࡧ͕ՄೳͰ͋Δɽ. . (i) Ϋϥελͷ෼ׂ. Ϋϥελ 1, 2 ͷ౷߹ͷ݁Ռɼ(ii) ʹ͓͍ͯ͸෼ྨ͕มԽ͠ɼ ҎԼͷΑ͏ʹͳΔɽ. ( 1 ) a, b, c : Ϋϥελ 4 ͷ಺෦ล ( 2 ) d, e : Ϋϥελ 3, 4 ؒͷ֎෦ล Ҏ্Ͱࣔͨ͠Α͏ʹɼΫϥελ౷߹ͷ࣮૷ʹ͸ลू߹Λ ౷߹͢Δૢ࡞͕ඞཁͱͳΔɽೋͭͷลू߹Λ౷߹͢ΔΞϧ. 5.1 ลू߹ͷ౷߹ ೋͭͷΫϥελ ci , c j Λ ci ʹ౷߹͠ c i ͱ͢Δͱ͖ɼࡾͭ ⓒ 2016 Information Processing Society of Japan. ΰϦζϜ͕͋Ε͹ɼ͜ͷΞϧΰϦζϜΛෳ਺ճద༻͢Δ͜ ͱͰࡾͭҎ্ͷลू߹Λ౷߹Ͱ͖Δɽೋͭͷลू߹Λ౷߹. 4.

(7) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2016-AL-158 No.9 2016/6/25. Algorithm 1 MergeEdgeLists. Algorithm 3 SplitEdgeList. Require: es1, es2 are sorted edge list Ensure: es1, es2 will be empty list, result will be sorted 1: function MergeEdgeLists( es1, es2 ) 2: i = 0, j = 0 3: result = [] [] is a empty list 4: while True do 5: if i = |es1| then 6: result.append(es2) 7: break 8: else if j = |es2| then 9: result.append(es1) 10: break 11: end if 12: if w(es1[i]) ≤ w(es2[j]) then 13: result.appned(es1[i]) 14: i=i+1 15: else 16: result+.appned(es2[j]) 17: j= j+1 18: end if 19: end while 20: es1 = es2 = [] 21: return result 22: end function. Require: es is soted, f is a function that f : E → {True, False} Ensure: each element e ∈ result1 will satisfy f (e) = True and each element e ∈ result2 will not 1: function SplitEdgeList( es, f ) 2: result1 = [], result2 = [] 3: for all e ∈ es do 4: if f (e) then 5: result1.append(e) 6: else 7: result2.append(e) 8: end if 9: end for 10: return (result1, result2) 11: end function. Algorithm 2 MergeClusters 1: procedure MergeClusters ( i, j ) 2: inneri = MergeEdgeLists (innteri , innerj ) 3: inneri = MergeEdgeLists (inneri , outeri,j ) 4: for all k ∈ {c | c ∈ AllClusters \ {i, j}} do 5: outeri,k = MergeEdgeLists (outeri,k , outerj,k ) 6: end for 7: end procedure. Algorithm 4 SpliteCluster 1: procedure SplitCluster ( i, j ) = SplitEdgeList (inneri , (λe.True ⇔ 2: (inneri , innerj ) e is inner edge of cluster i )) = SplitEdgeList (inneri , (λe.True ⇔ 3: (innerj , outeri,j ) e is inner edge of cluster j )) 4: for all k ∈ {c | c ∈ AllClusters \ {i, j}} do 5: (outeri,k , outerj,k = SplitEdgeList (outeri,k , (λe.True ⇔ e is outer edge between clusters i, k )) 6: end for 7: end procedure. ૢ࡞ͳͷͰɼਤ 4 ͷ (ii) ͷঢ়ଶ͔Β (i) ͷঢ়ଶʹมԽ͢Δɽ ΫϥελΛ෼ׂ͢ΔͨΊʹ͸ลू߹Λ෼ׂ͢Δૢ࡞͕ඞ ཁͱͳΔɽҰͭͷลू߹Λɼลʹؔ͢Δ৚݅ʹ‫͍ͯͮج‬ೋ ͭͷลू߹ʹ෼ׂ͢ΔΞϧΰϦζϜ͕͋Ε͹ɼͦͷΞϧΰ. ͢ΔΞϧΰϦζϜͷٖࣅίʔυΛ Algorithm 1 ʹࣔ͢ɽؔ. ϦζϜΛ࿈ଓతʹద༻͢Δ͜ͱͰࡾͭҎ্ͷลू߹΁ͷ෼. ਺ MergeEdgeLists ͸ɼes1, es2 ಺ͷཁૉΛঢॱιʔτ͠. ׂ΋ՄೳͱͳΔɽลू߹ͱลʹؔ͢Δ৚݅Λද͢ߴ֊ؔ਺. ͨྻΛฦ͢ɽؔ਺ MergeEdgeLists Λ༻͍ͯೋͭͷΫϥ. Λೖྗͱ͠ɼ෼ׂ‫ޙ‬ͷลू߹ͷ૊Λฦ͢ΞϧΰϦζϜͷٖ. ελ i, j ͷ౷߹Λ࣮૷͢Δ͜ͱ͕Ͱ͖ΔɽΞϧΰϦζϜΛ. Algorithm 2 ʹࣔ͢ɽٖࣅίʔυதͷ inneri ͸Ϋϥελ i ʹ ରԠ͢Δ಺෦ลू߹Λද͢ɽouteri,j ͸Ϋϥελ i, j ؒͷ֎ ෦ลΛද͢ɽҎ߱ͷٖࣅίʔυ΋ಉ༷Ͱ͋Δɽ. ࣅίʔυΛ Algorithm 3 ʹࣔ͢ɽؔ਺ SplitEdgeList ʹΑ Γลू߹ͷ෼ׂ͕࣮‫͖Ͱݱ‬Δɽؔ਺ SplitEdgeList Λ༻͍ ͯΫϥελ i ΛೋͭͷΫϥελ i, j ʹ෼ׂ͢ΔॲཧΛ࣮૷͢ Δ͜ͱ͕Ͱ͖ΔɽΞϧΰϦζϜͷٖࣅίʔυΛ Algorithm. 4 ʹࣔ͢ɽ 5.2 ลू߹ͷ෼ׂ ลू߹ c Λ෼ׂ͠ೋͭͷลू߹ ci , c j ͱ͢Δͱ͖ɼc ͷ಺ ෦ลू߹Λ෼ׂ͠ࡾͭͷลू߹. 5.3 ลͷ࡟আ ࡟আΫΤϦ remove(u, v) Λॲཧ͢Δखॱʹ͍ͭͯड़΂Δɽ. remove(u, v) ͷॲཧ͸ɼMST ͕ล (u, v) Λ‫ؚ‬Ή͔൱͔ʹΑͬ. ( 1 ) ci ͷ಺෦ลू߹. ͯҟͳΔɽ(u, v) ͕ MST ʹ‫·ؚ‬Ε͍ͯͳ͍ͱ͖͸ɼ(u, v) ͕. ( 2 ) c j ͷ಺෦ลू߹. ଐ͢Δลू߹͔Β (u, v) ΛऔΓআ͘ͷΈͰ͋Δɽ. ( 3 ) ci , c j ؒͷ֎෦ลू߹. ͦ͏Ͱͳ͍৔߹͸ɼ·ͣ MST ͔Β (u, v) ΛऔΓআ͍ͯ. ͱ͢ΔɽͦͷଞͷΫϥελ ck ( ck c ) ʹ͍ͭͯɼc, ck ؒ. MST Λೋͭͷ࿈݁੒෼ʹ෼͚Δɽ͜ͷͱ͖ɼ(u, v) ͕಺෦. ͷ֎෦ลू߹Λ෼ׂ͠ɼ. ลͰ͋Ε͹ u, v ͕ଐ͢ΔΫϥελΛ෼ׂ͢Δɽͦͷ‫ޙ‬ɼ࿈. ( 1 ) ci , ck ؒͷ֎෦ลू߹ ( 2 ) c j , ck ؒͷ֎෦ลू߹ ͷೋͭͷลू߹ͱ͢ΔɽΫϥελ౷߹͸Ϋϥελ෼ׂͷ‫ٯ‬. ⓒ 2016 Information Processing Society of Japan. ݁੒෼ؒΛ݁Ϳลͷ಺࠷΋͍ܰ΋ͷΛ௥Ճ͢Δ͜ͱͰ࠶ ͼ࿈݁ʹ͢Δɽ෼ׂͨ͠࿈݁੒෼ؒΛ݁Ϳล͸ɼҟͳΔ࿈ ݁੒෼ʹଐ͢Δ௖఺͕ଐ͢ΔΫϥελؒͷ֎෦ลͰ͋Δɽ ैͬͯɼ௥Ճ͢Δล͸֎෦ลू߹Λ૸ࠪ͢Δ͜ͱͰൃ‫Ͱݟ‬. 5.

(8) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2016-AL-158 No.9 2016/6/25. Algorithm 5 RemoveEdge. Algorithm 6 AddEdge. 1: procedure RemoveEdge ( u, v ) 2: if Not MST.hasEdge(u, v) then 3: if cluster(u) = cluster(v) then 4: innercluster(u) .erase(u, v) 5: else 6: outercluster(u),cluster(v) .erase(u, v) 7: end if 8: return 9: end if 10: MST.remove edge((u, v)) 11: if cluster(u) = cluster(v) then 12: assign new cluster for vertices such that connected from v on MST and belongs to cluter( u) 13: SplitCluster(cluster(u), cluster(v)) 14: end if 15: c = cluster which has lightest head edge 16: MST.add edge(c[0]) 17: c.remove(c[0]) 18: MergeClusters (cluster(u), cluster(v)) 19: end procedure. 1: procedure AddEdge ( u, v, x ) 2: modify w to be w((u, v)) = x 3: e = (p, q) = most heavy edge in u-v path in MST 4: if w(e) ≤ x then 5: if cluster(u) = cluster(v) then 6: innercluster(u) .insert((u, v)) 7: else 8: outercluster(u),cluster(v) .insert((u, v)) 9: end if 10: return 11: end if 12: MST.remove edge(e) 13: if cluster(p) = cluster(q) then 14: assign new cluster for vertices such that connected from v on MST and belongs to cluter( u) 15: SplitCluster (cluster(p), cluster(q)) 16: end if 17: outerclusterp ,clusterq .insert(e) 18: MST.add edge((u, v)) 19: MergeClusters (cluster( u), cluster( v)) 20: end procedure. ͖ΔɽΞϧΰϦζϜΛ Algorithm 5 ʹࣔ͢ɽ ද [4] Λ༻͍ͨՄม௕഑ྻΛ༻͍Δͱ͢Δɽ. 5.4 ลͷ௥Ճ ௥ՃΫΤϦ add(u, v, x) Λॲཧ͢Δखॱʹ͍ͭͯड़΂Δɽ ॏΈ w ͷล (u, v) Λ MST ʹՃ͑ͨάϥϑΛߟ͑Δͱɼล. (u, v) ʹΑΓด࿏͕Ͱ͖Δɽ͜ͷด࿏͸ɼMST ্Ͱ 2 ௖఺ u, v ؒΛ݁Ϳύεͷ୺ʹɼ(u, v) ΛՃ͑ͨ΋ͷͰ͋Δɽ৽ͨ ͳ MST ΛಘΔͨΊʹด࿏͔Β࠷΋ॏ͍ลΛऔΓআ͘ඞཁ ͕͋Δ͕ɼऔΓআ͘ล͸࣍ͷ 2 ௨Γʹ৔߹෼͚Ͱ͖Δɽ. ( 1 ) (u, v) ΛऔΓআ͘ ( 2 ) ͦΕҎ֎ͷลΛऔΓআ͘ ͜Ε͸ɼ(u, v) ͷॏΈͱ u-v ύεதͰ࠷΋ॏ͍ลͷॏΈΛൺ ֱ͢Ε͹൑ผͰ͖Δɽ ௥ՃΫΤϦʹΑΓάϥϑʹ௥Ճͨ͠ลͰ͋Δ (u, v) Λด ࿏͔ΒऔΓআ͘৔߹͸ɼ(u, v) ΛରԠ͢ΔลϦετʹૠೖ ͢Δɽͦ͏Ͱͳ͍৔߹͸ɼu-v ύεதͰ࠷΋ॏ͍ลΛ MST. ·ͣ͸‫ج‬ຊతͳૢ࡞ʹ͍ͭͯղੳ͢Δɽ࣍ͷ஋ͷΦʔμ ͸શͯ O(|V|) Ͱ͋Δɽ. ( 1 ) ҰͭͷΫϥελͷ಺෦ลͷຊ਺ ( 2 ) ֎෦ลू߹ͷ‫਺ݸ‬ ( 3 ) Ұͭͷ֎෦ลू߹͕‫ؚ‬Ήลͷຊ਺ Proof. ͋ΔΫϥελͷ಺෦ลͷ૯਺͸ɼΫϥελ಺෦͔ Βೋͭͷ௖఺ΛબͿ૊߹ͤͷ૯਺Ͱ͋ΔͨΊɼೋ߲܎਺ √|V| √|V| ʹ౳͍͠ɽ = O(|V|) Ͱ͋ΔͷͰɼ͋ΔΫϥελ 2 2 ͷ಺෦ลͷ૯਺͸ O(|V|) ຊͰ͋Δɽ. . Proof. ֎෦ลू߹ͷ૯਺͸ɼҟͳΔΫϥελೋͭΛબͿ √ ૊߹ͤͷ૯਺Ͱ͋ΔɽΫϥελ਺͸ O( |V|) ‫͋Ͱݸ‬Δͷ Ͱɼ಺෦ลू߹αΠζʹؔ͢Δٞ࿦ͱಉ༷ʹ O(|V|) ‫ͳͱݸ‬ Δɽ. . ͔ΒऔΓআ͍ͯ MST Λೋͭͷ࿈݁੒෼ʹ෼அ͔ͯ͠Βɼ. Proof. ͋Δ֎෦ลू߹͕‫ؚ‬Ήลͷຊ਺͸ɼରԠ͢Δೋͭ. (u, v) Λ MST ʹՃ͑Δɽύε͔ΒऔΓআ͍ͨล͸ɼରԠ. ͷΫϥελͷͦΕͧΕ͔ΒҰͭͣͭ௖఺ΛऔΓग़͢૊߹ͤ. ͢ΔลϦετ΁ૠೖ͢ΔɽΞϧΰϦζϜͷٖࣅίʔυΛ. ͷ૯਺Ͱ͋ΔɽҰͭͷΫϥελ͔Β௖఺ΛऔΓग़͢બͼํ √ ͸ O( |V|) ௨ΓͰ͋ΔɽͦΕͧΕͷΫϥελ͔Β௖఺Λऔ. Algorithm 6 ʹࣔ͢ɽ. 6. ޮ཰Խʹؔ͢Δ࣮‫݁ݧ‬ՌͱධՁ 6.1 ‫ྔࢉܭ‬ղੳ݁Ռͱߟ࡯ ฏ‫ۉ‬తͳঢ়ଶʹ͍ͭͯߟ࡯͢ΔͨΊɼຊઅͰ͸ҎԼͷೋ ͭͷԾఆΛஔ্͍ͨͰఏҊख๏Λղੳ͢Δɽ. √ ( 1 ) Ϋϥελͷ૯਺͸ |V| ‫͋Ͱݸ‬Δ √ ( 2 ) ֤Ϋϥελ಺ͷ௖఺਺͸ |V| ‫͋Ͱݸ‬Δ √ ද‫͕ه‬൥ࡶʹͳΔͷΛආ͚ΔͨΊɼҎԼͷٞ࿦Ͱ͸ |V| √ Λ୯ʹ |V| ͱॻ͘ɽ·ͨɼ഑ྻΛ࢖༻͢Δࡍʹ͸ಈతͳ ⓒ 2016 Information Processing Society of Japan. Γग़͢ૢ࡞͸ಠཱͰ͋ΔͨΊɼೋͭͷΫϥελ͔ΒҰͭͣ ͭ௖఺ΛऔΓग़͢બͼํ͸ͦΕͧΕͷΫϥελ͔ΒͷऔΓ √ ग़͠ํͷ૯਺ͷੵͰ͋Δैͬͯ O( |V|2 ) = O(|V|) ௨ΓͰ͋ Δɽ. . MST ΁ͷҎԼͷૢ࡞͸ɼMST Λྡ઀ϦετͰද‫ͯ͠ݱ‬ ͍Δͱ͢Ε͹࣌ؒ‫ ྔࢉܭ‬O(|V|) ࣌ؒͰ͋Δɽ. ( 1 ) ลͷ௥Ճ ( 2 ) ลͷ࡟আ ( 3 ) ͋ΔลΛ‫ؚ‬Ή൱͔Λௐ΂Δ 6.

(9) 情報処理学会研究報告 IPSJ SIG Technical Report. Vol.2016-AL-158 No.9 2016/6/25. ( 4 ) 2 ௖఺ u, v ؒͷύεΛ‫ٻ‬ΊΔ ࣍ ʹ ɼ5 Ͱ ఆ ٛ ͠ ͨ ؔ ਺ɾख ଓ ͖ Λ ղ ੳ ͢ Δ ɽ. MergeEdgeLists (es1, es2) ͸ O(|es1|+|es2|) ࣌ؒͰಈ࡞͢Δɽ Proof.. MergeEdgeLists ͷ 12 ʙ 18 ߦ໨ͷ if จʹΑΓɼ. ྆഑ྻͷ֤ཁૉΛߴʑҰճͣͭ result ͷ຤ඌʹૠೖ͢Δɽ ঈ٫ O(1) ࣌ؒͷॲཧΛ |es1| + |es2| ճ࣮ߦ͢ΔͷͰɼঈ٫. O(|es1| + |aes2|) ࣌ؒͱͳΔɽ. ͋Δɽ֤Ϋϥελʹ͍ͭͯ SplitEdgeList Λ࣮ߦ͢ΔɽΫ √ ϥελ਺͸ O( |V|) Ͱ͋ΔͨΊɼঈ٫ O(|V|) ࣌ؒͷॲཧΛ √ O( |V|) ճ࣮ߦ͢Δɽ √ Ҏ্ΑΓɼ SplitCluster ͸ O(|V| |V|) ࣌ؒͰಈ࡞͢. . Δɽ. 6.1.1 ลͷ࡟আ ࡟আΫΤϦ remove(u, v) Λॲཧ͢Δؔ਺ RemoveEdge ͷ ࣮૷ʹඞཁͱͳΔૢ࡞͸ҎԼͷ΋ͷͰ͋Δɽ. ยํͷ഑ྻ͕ۭʹͳͬͨͱ͖ɼଞํͷ഑ྻΛ result ͷ຤ ඌʹ࿈݁͢Δɽ͜ͷॲཧ͸ɼͲͪΒͷϦετ͕࢒ͬͨͱ͠. ( 1 ) MST ͕͋ΔลΛ‫ؚ‬Ή͔൱͔Λௐ΂Δ. ͯ΋ঈ٫ O(max(|es1|, |aes2|)) ࣌ؒͰ࣮ߦͰ͖Δɽ. ( 2 ) u, v ʹ͍ͭͯɼଐ͢ΔΫϥελΛͦΕͧΕௐ΂Δ. Ҏ্ΑΓɼ MergeEdgeLists ͸ঈ٫ O(|es1| + |es2|) ࣌ؒ Ͱಈ࡞͢Δɽ. . ·ͨɼลϦετͷ௕͞͸ O(|V|) Ͱ͋ΔͨΊɼ MergeEdge-. ( 3 ) ลϦετ͔Β (u, v) Λ࡟আ͢Δ ( 4 ) MST ͔Β (u, v) Λ࡟আ͢Δ ( 5 ) MST ͔ΒลΛҰຊऔΓআ͍ͨάϥϑ্Ͱɼv ͱ࿈͔݁ ͭॴଐΫϥελ͕ u ͱ౳͍͠௖఺Λྻ‫͠ڍ‬ɼॴଐΫϥ. Lists ͸ঈ٫ O(|V|) ࣌ؒͰ͋Δɽ. √ MergeClusters (i, j) ͸ঈ٫ O(|V| |V|) ࣌ؒͰಈ࡞͢Δɽ. ελΛมߋ͢Δ. (6). SplitCluster. Proof. ୈ 2, 3 ߦͰ͸ɼ MergeEdgeLists ʹΑΓ innerj ͱ. ( 7 ) Ϧετͷઌ಄ʹ͋Δล͕࠷΋͍ܰ௖఺ू߹Λ‫ٻ‬ΊΔ. outeri,j Λ inneri ʹ౷߹͢Δɽ͜ΕΒͷॲཧ͸ɼঈ٫ O(|V|). ( 8 ) MST ʹลΛՃ͑Δ. ࣌ؒͰ࣮ߦͰ͖Δɽ ୈ 4 ʙ 6 ߦͷ for จʹ͓͍ͯɼk ͸ i, j Λআ͍ͨશͯͷΫ √ ϥελʹؔͯ͠ϧʔϓ͠ɼͦͷର৅ͷ‫਺ݸ‬͸ O( |V|) Ͱ͋ Δɽ֤Ϋϥελʹ͍ͭͯ MergeEdgeLists ʹΑΓ outeri,k √ ͱ outerj,k Λ౷߹͢ΔɽΫϥελ਺͸ O( |V|) Ͱ͋ΔͨΊɼ √ ঈ٫ O(|V|) ࣌ؒͷॲཧΛ O( |V|) ճ࣮ߦ͢Δɽ √ Ҏ্ΑΓɼ MergeClusters ͸ O(|V| |V|) ࣌ؒͰಈ࡞͢ Δɽ. . SplitEdgeList (es, f ) ͸ɼ৚݅ؔ਺ f ͕ఆ਺࣌ؒͰॲཧͰ. ( 9 ) ลϦετͷઌ಄ཁૉΛ࡟আ͢Δ ( 10 ). MergeClusters Λ࣮ߦ͢Δ MST ͔ΒลΛҰຊऔΓআ͍ͨάϥϑ্Ͱ৚݅Λຬͨ͢. ௖఺Λྻ‫͢ڍ‬Δૢ࡞͸ɼv ͔Β෯༏ઌ୳ࡧͳͲΛߦ͏͜ͱ Ͱ࣮‫͖Ͱݱ‬Δɽ ଞͷૢ࡞ʹ͍ͭͯ͸ɼ‫ྔࢉܭʹط‬Λࣔͨ͠ɽૢ࡞ͷ಺࠷ ΋͕͔͔࣌ؒΔ΋ͷ͸ SplitCluster ͷ࣮ߦͱ MergeClus√ ters ͷ࣮ߦͰ͋ΓɼͦΕͧΕঈ٫࣌ؒ‫ ྔࢉܭ‬O(|V| |V|) ࣌. ͖ΔͳΒ͹ɼঈ٫ O(|V|) ࣌ؒͰಈ࡞͢Δɽ. ؒͰ͋Δɽैͬͯɼ࡟আΫΤϦͷॲཧʹ͔͔Δঈ٫࣌ؒ‫ܭ‬ √ ࢉྔ͸ O(|V| |V|) ࣌ؒͰ͋Δɽ. Proof. ୈ 3 ʙ 9 ߦͷ for จʹΑΓɼe ͸ es ͷશͯͷཁૉ. 6.1.2 ลͷ௥Ճ. ʹؔͯ͠ϧʔϓ͢Δɽ֤ e ʹ͍ͭͯɼ f (e) ͷ஋ʹΑͬͯ. ௥ՃΫΤϦΛ add(u, v, x) Λॲཧ͢Δؔ਺ AddEdge ͷ࣮. result1, result2 ͷ͍ͣΕ͔ͷ຤ඌʹ࿈݁͢ΔॲཧΛ͢Δɽ഑. ૷ʹඞཁͱͳΔૢ࡞ͷ಺ɼ࡟আΫΤϦʹ‫ݱ‬Εͳ͔ͬͨ΋ͷ. ྻ຤ඌ΁ͷ୯Ұཁૉͷ௥Ճ͸ঈ٫ O(1) ࣌ؒͰ͋Γɼ࿈݁. ͸ҎԼͷૢ࡞Ͱ͋Δɽ. Λ |es| ճ࣮ߦ͢Δɽ. |es| = O(|V|) Ͱ͋ΔͨΊɼ SplitEdgeList ͸ O(|V|) ࣌ؒͰ ಈ࡞͢Δɽ. . √ SplitCluster (i, j) ͸ঈ٫࣌ؒ‫ ྔࢉܭ‬O(|V| |V|) ࣌ؒͰ ಈ࡞͢Δɽ. ( 1 ) w((u, v)) ͷ஋͕ x ͱͳΔΑ͏ʹ w Λมߋ͢Δ ( 2 ) MST ্ͷ u-v ύε্Ͱ࠷΋ॏ͍௖఺Λ୳͢ w Λมߋ͢Δॲཧ͸ɼ֤ u, v ʹର͢Δ w((u, v)) ͷ஋Λ 2 ࣍‫ݩ‬഑ྻͰอ͍࣋ͯ͠Ε͹ O(1) ࣌ؒͰ࣮ߦͰ͖ΔɽMST ্ͷ u-v ύεΛ‫ٻ‬ΊΔॲཧ͸ɼ্Ͱࣔͨ͠Α͏ʹ O(|V|) ࣌. Proof. ॴଐΫϥελʹؔ͢Δ৚݅ؔ਺͸ɼ௖఺൪߸ʹର. ؒͰ࣮ߦͰ͖Δɽu-v ύε͕‫ؚ‬Ήลͷຊ਺͸࠷େͰ |V| − 1. ͢ΔॴଐΫϥελͷ৘ใΛ഑ྻʹ‫ه‬Ա͓ͯ͘͜͠ͱͰఆ਺. Ͱ͋Γɼ͔ͦ͜Β࠷΋ॏ͍௖఺Λ୳͢ૢ࡞͸ઢ‫ʹࡧ୳ܗ‬Α. ࣌ؒͰಈ࡞͢ΔΑ͏࣮૷Ͱ͖Δɽैͬͯɼॲཧʹར༻͢Δ. Γ O(|V|) ࣌ؒͰ࣮ߦͰ͖Δɽैͬͯɼ্ʹ‫࡞ૢͨ͛ڍ‬͸͍. SplitEdgeList ͸ঈ٫ O(|V|) ࣌ؒͰಈ࡞͢Δɽ. ͣΕ΋ O(|V|) ࣌ؒͰ࣮ߦͰ͖Δɽ. ୈ 2, 3 ߦͰ͸ɼ SplitEdgeList ʹΑΓ inneri Λ 2 ճॲཧ. SplitCluster ͱ MergeClusters ͷ࣮ߦ͸௥ՃΫΤϦͷ. ͢Δɽ͜ΕΒͷॲཧ͸ɼঈ٫ O(|V|) ࣌ؒͰ࣮ߦͰ͖Δɽ. ॲཧʹ΋‫·ؚ‬Ε͓ͯΓɼ͜ΕΒͷ࣮ߦʹ࠷΋͕͔͔࣌ؒΔɽ. ୈ 4 ʙ 6 ߦͷ for จʹ͓͍ͯɼk ͸ i, j Λআ͍ͨશͯͷ √ Ϋϥελʹؔͯ͠ϧʔϓ͠ɼͦͷର৅ͷ‫਺ݸ‬͸ O( |V|) Ͱ. ैͬͯɼ௥ՃΫΤϦʹ͔͔Δঈ٫࣌ؒ‫ྔࢉܭ‬΋࡟আΫΤϦ √ ͱಉ༷ʹ O(|V| |V|) ࣌ؒͰ͋Δɽ. ⓒ 2016 Information Processing Society of Japan. 7.

(10) 情報処理学会研究報告 IPSJ SIG Technical Report ද1. Vol.2016-AL-158 No.9 2016/6/25. Խͨ͠. ‫ط‬ଘख๏‫ͼٴ‬ఏҊख๏ͷ࣮ߦ࣌ؒൺֱʢϥϯμϜέʔεʣ ख๏. ࣌ؒ‫ྔࢉܭ‬. ࣮ߦ࣌ؒʢ࣮ଌʣ [sec]. Prim ͷΞϧΰϦζϜ. O(|E| log |V|) = O(|V|2 log |V|). 32.71. ( 3 ) ࠷దͳωοτϫʔΫ͕άϥϑʹ͓͚Δ MST ʹରԠ͢. Kruskal ͷΞϧΰϦζϜ. O(|E| log |E|) = O(|V|2 log |V|). 787.31. Δ͜ͱΛ্ࣔͨ͠Ͱɼάϥϑมߋ࣌ͷ MST ͷมԽ͕. Enhanced Kruskal. O(|E|) = O(|V|2 ) √ O(|V| |V|) = O(|V|1.5 ). 60.41. ‫ॴہ‬తͰ͋Δ͜ͱʹண໨͠ɼάϥϑมߋΫΤϦΛߴ଎. ఏҊख๏. 6.57. 6.2 ఆྔతղੳ݁Ռͱߟ࡯. ʹॲཧ͢Δख๏Λ։ൃͨ͠. ( 4 ) ఏҊख๏ͷཧ࿦ղੳΛߦ͍ɼ‫ط‬ଘख๏Ͱ͋Δ Prim ͷ ΞϧΰϦζϜ΍ Kruskal ͷΞϧΰϦζϜΑΓ઴ۙతʹ. ఏҊख๏ͷධՁͷͨΊɼ‫ط‬ଘख๏ͱఏҊख๏Λ C++ Ͱ࣮. ߴ଎Ͱ͋Δ͜ͱΛࣔͨ͠. ૷͠ɼ࣮ߦ࣌ؒΛ‫ܭ‬ଌ͢Δ࣮‫ݧ‬Λߦͬͨɽ࣮‫಺ݧ‬༰͸ɼ1024 ௖఺ͷάϥϑʹର͠ϥϯμϜͳάϥϑมߋΛ 1024 ճߦ͏. ( 5 ) ఏҊख๏ͱ‫ط‬ଘख๏Λ࣮૷͠ɼ‫Ͱݧ࣮ػࢉܭ‬ͷ࣮ଌʹ ΑΓఏҊख๏͕‫ط‬ଘख๏ΑΓ 5 ʙ 120 ഒఔ౓ߴ଎Ͱ͋. ॲཧΛ 20 ճ‫܁‬Γฦ͠ɼ࣮ߦ࣌ؒΛ‫ܭ‬ଌ͢Δ΋ͷͰ͋Δɽ. Δ͜ͱΛࣔͨ͠. ࣮‫ݧ‬͸ Windows 7 ʹΠϯετʔϧͨ͠ VMWare ্Ͱಈ ࡞͢Δ Ubuntu 15.04 ্Ͱ࣮ࢪͨ͠ɽ֤ϓϩάϥϜ͸ϓϩά ϥϛϯά໰୊࡞੒ิॿπʔϧ Rime [8] Λ༻͍ͯࣗಈ࣮ߦ ͠ɼ࣮ߦ࣌ؒΛ‫ܭ‬ଌͨ͠ɽ ࣮‫݁ݧ‬ՌΛද 1 ʹࣔ͢ɽදதʹ͸ൺֱͷͨΊʹ‫ྔࢉܭ‬΋ ࣔͨ͠ɽ෼͔Γ΍͢͞ͷͨΊɼม‫ͨ͠ܗ‬΋ͷ΋ซ‫͍ͯ͠ه‬ Δɽ‫ط‬ଘख๏ͷ಺࠷΋ߴ଎ʹಈ࡞ͨ͠ͷ͸ Prim ͷΞϧΰ ϦζϜͰ͋Δ͕ɼఏҊख๏͸ Prim ͷΞϧΰϦζϜͷ໿ 5 ഒߴ଎ʹಈ࡞ͨ͠ɽ. Prim ͷΞϧΰϦζϜͱ Kruskal ͷΞϧΰϦζϜͷ‫ྔࢉܭ‬. ैͬͯɼϞόΠϧ‫ʹثػ‬ΑΔ෼ࢄίϯϐϡʔςΟϯά੍ ‫͍͓ͯʹޚ‬ɼ௨৴ʹΑΓൃੜ͢ΔίετΛ࠷খԽ͢Δख๏ Λࣔ͢͜ͱ͕Ͱ͖ͨͱ‫͑ݴ‬Δɽ͜ΕʹΑΓɼॲཧͷ࣌ؒ୹ ॖ΍লిྗԽ͕‫ظ‬଴Ͱ͖Δɽ. 7.2 ల๬ ຊ‫ڀݚ‬ͷల๬ͱͯ͠ҎԼͷ఺͕͋Δɽ. ( 1 ) άϥϑͷ‫ʹܗ‬ந৅Խͯ͠ѻͬͨ͜ͱͰɼಉ༷ͷ‫ࣜܗ‬Խ. ͕౳͍͠ʹ΋ؔΘΒ࣮ͣߦ࣌ؒʹେ͖ͳ͕ࠩ͋Δ͕ɼ͜. ͕Ͱ͖Δ໰୊΁ͷԠ༻͕‫ظ‬଴Ͱ͖Δ. Ε͸ Prim ͷΞϧΰϦζϜʹ͓͍ͯ༏ઌॱҐ෇͖Ωϡʔʹ. ( 2 ) ฏ‫͍ͯͭʹྔࢉܭۉ‬ͷΈ෼ੳͨͨ͠ΊɼΫϥελϦϯ. push ͞Εͳ͍ล͕ଟ͍ͨΊͰ͋ΔɽҰํɼKruskal ͷΞϧ. άͷมԽΛ෼ੳ͠࠷ѱέʔεͰͷղੳΛߦ͍͍ͨ. ΰϦζϜ͸શͯͷลʹ͍ͭͯૢ࡞͢Δɽ. ( 3 ) ‫Ͱ্ػࢉܭ‬ͷ࣮‫͕ݧ‬ϥϯμϜέʔεͷΈͰ͋ͬͨͨ. ఏҊख๏ͱಉ༷ʹιʔτࡁΈลϦετΛѻ͏ Enhanced √ √ O(|V|2 ) Kruskal ͱൺֱ͢Δͱ O(|V| |V|) ΑΓ 1024 = 32 1.5 ) = O(. Ίɼੑೳ͕ѱԽ͢ΔέʔεΛൃ‫͠ݟ‬௥ࢼ͢Δ͜ͱͰΑ Γৄࡉͳ෼ੳΛߦ͍͍ͨ. ഒͷߴ଎Խ͕‫ظ‬଴Ͱ͖Δ͕ɼ࣮ࡍ͸ 10 ഒఔ౓ͱͳ͍ͬͯ Δɽ͔͠͠ɼΞϧΰϦζϜ࣮૷͕ΑΓෳࡶͰ͋Δʹ΋ؔΘ. ࢀߟจ‫ݙ‬. Βͣఆ਺ഒͷ͕ࠩ 3 ഒఔ౓ʹऩ·͍ͬͯΔͱ΋‫͑ݴ‬ɼे෼. [1]. ʹޮ཰తͰ͋Δɽ ཧ࿦ղੳ‫Ͱ্ػࢉܭͼٴ‬ͷ࣮‫ݧ‬ͷ݁ՌɼఏҊख๏͸྆‫؍‬. [2]. ఺ʹ͓͍ͯ‫ط‬ଘख๏ΑΓ΋ޮ཰తͰ͋Δͱ‫͑ݴ‬Δɽ͜Εʹ ΑΓɼϞόΠϧ‫্ثػ‬ͷ෼ࢄίϯϐϡʔςΟϯάʹ͓͍ͯɼ ҎԼͷΑ͏ͳޮՌ͕‫ظ‬଴Ͱ͖Δɽ. [3]. ( 1 ) ௨৴Ͱͷిྗফඅ͕‫ݮ‬গ͢Δ͜ͱʹΑΔՔಇ࣌ؒͷ Ԇ௕. [4]. ( 2 ) ੍‫ޚ‬΍λεΫʹؔ͢Δσʔλసૹͷॴཁ࣌ؒ‫ݮ‬গʹΑ Δॲཧ࣌ؒ୹ॖ [5]. 7. Ή͢ͼ 7.1 ݁࿦. [6]. ຊ‫Ͱڀݚ‬͸ҎԼͷ͜ͱΛߦͬͨɽ [7]. ( 1 ) पล‫͕ڥ؀‬ແઢ௨৴ʹ༩͑ΔӨ‫ͱڹ‬෼ࢄίϯϐϡʔ ςΟϯά੍‫ޚ‬ͷͨΊͷ௨৴ʹ͍ͭͯड़΂ɼ௨৴ίετ ࠷খԽͷҙٛΛࣔͨ͠. [8]. Shaw, J. A.: Radiometry and the Friis transmission equation, American Journal of Physics, Vol. 81, No. 1, pp. 33–37 (2013). ruuroo: ແઢ LAN ʹର͢Δো֐෺ͷӨ‫ ڹ‬- ύιίϯτ ϥϒϧͱࣗ‫ݾ‬ղܾɼhttp://pctrouble.lessismore.cc/ network/wirelesslan_obstacle.html, (2016/01/19 Ӿ ཡ). Abbas, S., Mosbah, M. and Zemmari, A.: Distributed computation of a spanning tree in a dynamic graph by mobile agents, Engineering of Intelligent Systems, 2006 IEEE International Conference on, IEEE, pp. 1–6 (2006). Cormen, T. H.ɼLeiserson, C. E.ɼRivest, R. L.ɼStein, C.ɼઙ ໺఩෉ɼ‫ؠ‬໺࿨ੜɼകඌത࢘ɼࢁԼխ࢙ɼ࿨ా޾ҰɿΞϧ ΰϦζϜΠϯτϩμΫγϣϯ: ੈքඪ४ MIT ‫ڭ‬Պॻɼۙ୅ Պֶࣾɼୈ 3 ൛ edition (2012). Prim, R. C.: Shortest connection networks and some generalizations, Bell system technical journal, Vol. 36, No. 6, pp. 1389–1401 (1957). Kruskal, J. B.: On the shortest spanning subtree of a graph and the traveling salesman problem, Proceedings of the American Mathematical society, Vol. 7, No. 1, pp. 48–50 (1956). ळ༿୓࠸ɿ‫׬‬શ੍೼ɾπϦʔ্ͰͷΫΤϦॲཧٕ๏ - (iwi) ʨ ൓ল͠·͢ - TopCoder ෦ɼhttp://topcoder.g.hatena. ne.jp/iwiwi/20111205/1323099376 (2016/01/14 Ӿཡ). Takahashi, S.: Rime – Rime 1.0 documentation, ”http:// nya3jp.github.io/rime/, (2016/01/14 Ӿཡ).. ( 2 ) ϞόΠϧ‫ؒثػ‬ͷແઢ௨৴ΛάϥϑมߋΫΤϦʹఆࣜ ⓒ 2016 Information Processing Society of Japan. 8.

(11)