エッシャー風タイリング問題に対する効率的な網羅探索アルゴリズムの提案
8
0
0
全文
(2) Vol.2018-AL-166 No.1 2018/1/28. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report k2. h(2). h(3). k1. k1. Tiling edge. h(1)=1. Tiling polygon. h(4). k3. Tiling vertex. ਤ 3. λΠϧܗঢ়Λଟ֯Ͱܗද͢ݱΔ߹ͷ IH51 ͷςϯϓϨʔτɽ. Αͼ I ͍ͯͭʹܕड़Δ)ɽ ਤ 1 isohedral λΠϦϯάͷྫɽ. J ܕ: λΠϦϯάลҙܗঢ়ɽͨͩ͠ɼରԠ͢ΔλΠϦ ϯάลಉ͡ܗঢ়Ͱͳ͚ΕͳΒͳ͍ɽ. S ܕ: λΠϦϯάลลͷத৺ʹରͯ͠ରশɽ. F. S. U ܕ: λΠϦϯάลลͷਨೋઢʹରͯ͠ઢରশɽ I ܕ: λΠϦϯάลઢɽ. J. F. J (a) ਤ 2. F. S. F (b). ֤ IH λΠϓʹଐ͢ΔҙͷλΠϧܗঢ়ɼςϯϓϨʔ τͷλΠϦϯάͱλΠϦϯάลΛɼςϯϓϨʔτͰن ఆ͞ΕΔ੍ͷԼͰมͤ͞ܗΔ͜ͱͰಘΒΕΔɽ. (a) IH51 ͷςϯϓϨʔτɼ͓Αͼ (b) λΠϧؒͷྡؔɽ. 2.2 Koizumi ΒͷϞσϧԽͱ֦ு 2.1 Isohedral λΠϦϯά λΠϦϯά͕ 1 छྨͷλΠϧͰߏ͞ΕΔ߹ɼͦͷλ. Koizumi Β [7] ೖྗਤ ܗS ͱλΠϧܗঢ় T ΛͦΕͧΕ n ݸͷͰߏ͞ΕΔଟ֯Ͱܗදͨ͠ݱɽλΠϧܗঢ়Λ. ΠϦϯά monohedral ͱݺΕΔɽmonohedral ͳλΠϦ. ଟ֯Ͱܗද͢ݱΔ߹ɼIH51 ͷςϯϓϨʔτਤ 3 ͷΑ͏. ϯάͷதͰɼλΠϦϯά͕͍͔ͭ͘ͷྡ͢ΔλΠϧ܈. ʹද͖ͰݱΔɽςϯϓϨʔτʹ n ݸͷ͕ஔ͞ΕɼͲ. ͷ܁Γฦ͠ߏΛ࣋ͭ߹ɼͦͷλΠϦϯά isohedral ͱ. ͷλΠϦϯάʹ̍ͭͷΛׂͯʢਤதͷࠇؙʣ ɼ. ݺΕΔɽisohedral λΠϦϯά 93 छྨͷλΠϓʹྨ. ΓͷΛλΠϦϯάล্ʹׂΓͯΔʢਤதͷനؙʣɽ͢. Ͱ͖Δ͜ͱ͕ΒΕ͓ͯΓ [1]ɼͦΕͧΕʹ IH1, IH2, . . . ,. ͳΘͪɼςϯϓϨʔτ্ͷςϯϓϨʔτ͕ද͢ݱΔ੍. IH93 ͱ͍͏໊લ͕͚ΒΕ͍ͯΔɽ. ݅Λຬͨ͢ൣғͰͷΈಈ͘͜ͱ͕Ͱ͖ΔɽKoizumi Β. ਤ 1 ʹ IH51 ʹଐ͢ΔλΠϦϯάͷྫΛࣔ͢ɽ͋ΔλΠ. શͯͷλΠϦϯάลʹಉͷΛஔ͢ΔϞσϧΛఏҊ. ϧʹର͠ɼ2 ͭҎ্ͷλΠϧͱྡ͍ͯ͠Δڥք෦Λλ. ͍͕ͯͨ͠ɼࠓງΒ [3] ֤ลʹҟͳΔͷΛஔ͢Δ. ΠϦϯά (tiling vertex) ͱͿݺɽ࣍ʹɼλΠϦϯά. Ϟσϧʹ֦ுͨ͠ɽ֤ลʹஔ͢ΔͷΛ k1 , k2 , . . . ͷ. Ͱׂ͞ΕΔͦΕͧΕͷڥք෦ʢ1 ͭλΠϧͱͷΈྡ. Α͏ʹද͢هΔͷͱ͢Δʢਤࢀরʣɽ. ʣΛλΠϦϯάล (tiling edge) ͱͿݺɽ·ͨɼλΠϦϯ άΛઢͰͭͳ͍Ͱߏ͞ΕΔଟ֯ܗλΠϦϯάଟ. ςϯϓϨʔτ্ͷ n ݸͷʹ࣌ܭճΓʹ 1 ͔Β n ͷ൪߸ Λ͚ɼn ݸͷͷ࠲ඪΛ 2 × n ߦྻ. . ֯( ܗtiling polygon) ͱݺΕΔɽ ֤ IH λΠϓͷҰൠతͳܗঢ়ςϯϓϨʔτͰද͢͜ͱ. U=. ͕Ͱ͖Δɽਤ 2(a) ʹ IH51 ͷςϯϓϨʔτΛࣔ͢ɽ͜ͷς ϯϓϨʔτ IH51 ʹଐ͢ΔҙͷλΠϦϯάͷλΠϦϯ. x1. x2. .... xn. y1. y2. .... yn. (1) . Ͱද͢ɽ·ͨɼϕΫτϧ u = (x1 , . . . , xn , y1 , . . . , yn ) ͱ. άଟ֯ܗ 1 ͷ͔͍߹͏ಉ͡͞ͷ 2 ลͱͦΕҎ֎ͷ. ఆٛ͢ΔɽλΠϦϯάͷݸΛ nv ͱ͠ɼλΠϦϯά. ҙͷ 2 ลͰߏ͞ΕΔ࢛֯͋ͰܗΔ͜ͱΛ͍ࣔͯ͠Δɽ. ͷ൪߸Λ h(s) (s = 1, . . . , nv )ʢਤ 3 ࢀরʣͱ͢ΔɽIH51. ·ͨɼ4 ͭͷλΠϦϯάล J ܕ͘͠ S ͋ͰܕΔ͜ͱ. ΛྫʹऔΔͱɼςϯϓϨʔτΑΓλΠϧܗঢ় U ͷ࠲ඪ. Λ͍ࣔͯ͠ΔɽλΠϦϯάลͷʹܕ J ܕɼS ܕɼU ܕɼI ܕͷ 4 छྨ͕͋Γɼਤʹࣔͨ͠Α͏ͳ৭͖ͷϚʔΫͰܕ Λද͢ݱΔͷ͕ศརͰ͋ΔʢਤͰ J ͱܕS ܕͷΈࣔͯ͠ ͍ΔʣɽλΠϦϯάลͷܕλΠϧͷྡؔͱີʹؔ ͓ͯ͠Γɼྫ͑ IH51 Ͱਤ 2(b) ʹࣔͨ͠Α͏ͳྡ ؔΛ࣋ͭɽ͜͜Ͱɼ͢ྡʹ͍ޓΔλΠϦϯάลਤͰ ࣔͨ͠Α͏ʹɼಉҰͷ৭͖ͷϚʔΫ͕ॏͳΔΑ͏ʹஔ ͠ͳͯ͘ͳΒͳ͍͜ͱʹҙ͞Ε͍ͨɽ͜ͷྡؔΑ ΓɼJ ͱܕS ܕͷλΠϦϯάล࣍ͷੑ࣭Λ࣋ͭ (U ͓ܕ ⓒ 2018 Information Processing Society of Japan. ҎԼͷ੍݅Λຬͨ͢ඞཁ͕͋Δɽ. ⎧ ⎪ xh(1)+i − xh(1) ⎪ ⎪ ⎪ ⎪ ⎪ yh(1)+i − yh(1) ⎪ ⎪ ⎪ ⎨ x h(2)+i − xh(2) ⎪ yh(2)+i − yh(2) ⎪ ⎪ ⎪ ⎪ ⎪ xh(4)+i − xh(4) ⎪ ⎪ ⎪ ⎩ y h(4)+i − yh(4). =. xh(3)+i − xh(3) (i = 1, . . . , k1 + 1). =. −(yh(3)+i − yh(3) ) (same as above). =. −(xh(3)−i − xh(3) ) (i = 1, . . . , k22+1 ). =. −(yh(3)−i − yh(3) ) (same as above). =. −(xh(5)−i − xh(1) ) (i = 1, . . . , k32+1 ). =. −(yh(5)−i − yh(1) ) (same as above) (2). ͨͩ͠ɼh(5) = n + 1 ͱ͢Δɽ͜͜Ͱɼࣜ (2) 2 ຊͷ J. 2. ,.
(3) Vol.2018-AL-166 No.1 2018/1/28. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. ࢬ͕ x ࣠ʹରͯ͠ฒਐ͋Ͱ૾ڸΔʢยํͷ J ࢬଞํͷ J. ͱ؆ུԽͰ͖Δ͜ͱΛࣔͨ͠ɽ͜͜ͰɼV . . ࢬΛ x ࣠ͰંΓฦ͠ɼx ࣠ʹฏߦҠಈͯ͠ಘΒΕΔʣ͜ͱ ΛԾఆͯ͠ಋग़͞Ε͍ͯΔ͜ͱʹҙ͞Ε͍ͨɽ੍݅ Λ 1 ࣍ࣜͰද͢ݱΔͨΊʹ͜ͷԾఆ͕ඞཁͱͳΔɽ ࣜ (2) ੪࣍࿈ཱҰ࣍ํఔࣜͷܗΛ͍ͯ͠ΔͷͰɼA Λ. m × 2n ( ྻߦܕm ࣜ (2) ͷࣜͷ) ͱͯ͠ɼ Au = 0. wx wy −wy wx . wy wx −wx wy . wx wx +wy wy . (8). Ͱఆٛ͞ΕΔ 2n × 2n ରশߦྻͰ͋Δɽ ݁ہɼU ͷ࠷దܗঢ়ΛٻΊΔ੍ (4) ͷԼͰࣜ (7) ͷ࠷খΛٻΊΔʹؼண͞ΕɼB B ͕୯ҐߦྻͰ͋. (3). ͷΑ͏ʹද͖ͰݱΔɽ͜ͷํఔࣜͷҰൠղ. u = ξ1 b1 + ξ2 b2 + · · · + ξm bm = Bξ. V =. wx wx +wy wy . Δ͜ͱ͔Βɼ࣍ͷແ੍࠷దԽͱՁͱͳΔɽ. maximize: (4). Ͱ༩͑ΒΕΔɽ͜͜Ͱɼm Ker(A) ͷ࣍Ͱݩɼbi (i =. 1, . . . , m) Ker(A) ͷਖ਼نަجఈϕΫτϧɼξi (i = 1, . . . , m) ύϥϝʔλʔͰ͋Δɽ·ͨɼ2n × m ྻߦܕ B = (b1 , b2 , . . . , bm )ɼξ = (ξ1 , ξ2 , . . . , ξm ) ͱఆٛ͢Δ.. ξ B V Bξ . ξ ξ. (9). ͨͩ͠ɼߦྻ B IH λΠϓ͓Αͼ n ݸͷͷλΠϦϯ άลͷׂͯํʹґଘ͢Δɽ·ͨɼU ͱ W ͷϓϩΫϥ εςεڑʢϢʔΫϦουڑͷ߹ʣΛ͢ࢉܭΔࡍʹ ɼ྆ਤܗͷؒͷ n छྨͷҟͳΔରԠؔΛߟྀ͢Δඞ ཁ͕͋Δɽ͜ͷͨΊʹɼਤ ܗW ͷΠϯσοΫεͷ࢝. 93 छྨͷ IH λΠϓͷશͯςϯϓϨʔτʹରͯ͠ɼࣜ (4). Λγϑτ͠ͳ͕Β n छྨͷҟͳΔ൪߸͚ͮΛશͯߟ͑Ε. ͱಉ༷ͷ੍Ͱࣜܗ݅Λهड़͢Δ͜ͱ͕Ͱ͖Δɽͨͩ. ྑ͍ɽͦ͜ͰɼWj (j = 1, 2, . . . , n) Λ W ͷ j ྻ͕ 1 ྻ. ͠ɼߦྻ B IH λΠϓͱ k1 , k2 , . . . ͷʹґଘ͢Δɽm ͷ n ఔͱͳΔͨΊɼߦྻ B ΛಘΔͨΊͷྔࢉܭ దͳํ๏Λ༻͍ͯ O(n3 ) ͱͳΔɽ ೖྗਤ ܗS Λද͢ݱΔଟ֯ܗͷ n ݸͷʹ࣌ܭճΓ ʹ 1 ͔Β n ·Ͱͷ൪߸͕ৼΒΕ͍ͯΔͷͱ͢Δɽࣜ (1) ͱಉ༷ʹɼS Λද͢ݱΔଟ֯ܗͷ࠲ඪΛཁૉͱ͢Δ 2 × n ྻߦܕΛ W ͱ͢ΔɽKozumi Β U ͱ W ͷྨࣅΛଌ Δࢦඪͱͯ͠ϓϩΫϥεςε[ ڑ9] Λಋೖͨ͠ɽϓϩΫ. ʹରͯ͠ɼಉ༷ʹ wj ͱ Vj Λఆٛ͢Δͷͱ͢ΔʢV ͱ ͯ͠શͯͷ Vj Λࢼ͢ʣɽ. (9) ϨΠϦʔͱݺΕɼ࠷ద B V B ͷ࠷େ ݻ༗ɼ࠷దղ ξ ∗ ͦͷ࣌ͷݻ༗ϕΫτϧͱͳΔɽग़ Β [6] Imahori Β [4] B V B ͕ϥϯΫ 2 ͷରশߦྻͰ ͋Δ͜ͱΛར༻ͨ͠ղ๏ʢࣹӨ๏ʣ༻͍ͯɼO(n2 ) ࣌ؒͰ ݻ༗ɼݻ༗ϕΫτϧΛٻΊΔํ๏ΛߟҊ͍ͯ͠Δɽ ϢʔΫϦουڑΛ༻Ͱ͖Δ߹ɼU ͷ࠷దܗঢ়. ϥεςεڑͷ 2 ࣍ࣜͰఆٛ͞ΕΔɽ. 2 U W 2 , d (U, W ) = min sR(θ) − s,θ U W . ʹͳΔΑ͏ʹγϑτͯ͠ಘΒΕΔߦྻͱఆٛ͠ɼw ͱ V. 2. ࠷దԽ minimize: Bξ − w Λղ͘͜ͱͰٻΊΒΕ. (5). Δɽ͜ͷ࠷খೋͰ͋Γɼ࠷దղ ξ ∗ = B wɼ ࠷খ −ξ ∗ ξ ∗ + w w ͱͳΔɽ. ͜͜Ͱɼs εΧϥʔɼR(θ) ֯ θ ʹର͢Δճసߦྻɼ. · ϑϩϕχεϊϧϜΛද͢ɽఆٛΑΓϓϩΫϥες. 3. ޮతͳࢉܭ๏. εڑͷ 2 εέʔϧ/ճసෆมͰ͋Δɽ͢ͳΘͪɼλ. 3.1 ཏతͳ Koizumi ͷํ๏. Πϧܗঢ় U ͕ඪܗঢ় W ʹ࠷ۙ͘ͳΔΑ͏࠷దʹ֦େ. ू߹ I Λ IH λΠϓΛද͢ΠϯσοΫεू߹ʢi ∈ I. ʢॖখʣ ɾճసͨ͠ޙͷ྆ਤܗͷڑʢରԠ͢Δؒͷઢ. IHi ʹ ର Ԡ ʣͱ ͢ Δ ɽ· ͨ ɼKi Λ λ Π ϓ IHi ʹ ͓. ڑͷ 2 ʣΛࢉग़͢ΔɽIH51 ͷΑ͏ʹɼରͱͳΔ J ࢬ. ͍ ͯ ɼn ݸͷ ͷ λ Π Ϧ ϯ ά ล ͷ ׂ ͯ ํ Λ ද ͢. ʹฒਐ૾ڸΛԾఆ͠ͳ͚ΕͳΒͳ͍߹ɼճసෆมͷ. Π ϯ σ ο Ϋ ε ू ߹ ͱ ͢ Δ ɽྫ ͑ ɼIH51 ʹ ର ͠ ͯ . ੑ࣭͕ඞཁͰ͋Δ͜ͱʹҙ͞Ε͍ͨ*1 ɽͨͩ͠ɼฒਐڸ. K51 = {(k1 , k2 ) | 0 ≤ k1 , 0 ≤ k2 , 2k1 + k2 ≤ n − 4} ͱ. ૾ΛԾఆ͠ͳͯ͘ྑ͍ IH λΠϓͷ߹ɼڑఆٛΛ୯. ఆٛ͞ΕΔɽͨͩ͠ɼk3 = n − 4 − 2k1 − k2 Ͱ͋Δɽߦྻ. 2. ७ʹ U − W ͱ͢Εɼ࠷దԽޙͷ݁Ռಉ͡ͱͳΔɽ. B i ∈ I ͱ k ∈ Ki ʹґଘ͢ΔͨΊ Bik ͱදΘ͢ɽ·ͨɼ. ຊߘͰ͜ͷڑΛϢʔΫϦου͢ʹࣄͿݺͱڑΔɽ. J Λඪਤ ܗW ͷΠϯσοΫεͷ൪߸͚ͮΛද͢Πϯσο. Koizumi Β 2n ࣍ݩϖΫτϧ uɼw Λ u wx ux wx x U= , W= , u= , w= , (6) uy wy uy wy. Ϋεू߹ͱ͢Δʢj ∈ J ΠϯσοΫεͷ࢝ʣ ɽຊߘͰ. ͱఆٛ͢Δͱɼࣜ (5) ͕. 1− *1. (7). Ұ ํ ɼε Χ ϥ ʔ ෆ ม ੑ ඞ ཁ Ͱ ͳ ͘ ɼ࣮ ࡍ ڑΛ minθ R(θ)U − W 2 ͱఆٛͯ͠ಉ݁͡Ռ͕ಘΒΕΔɽ. ⓒ 2018 Information Processing Society of Japan. ݸͷͷλΠϦϯάลׂͯํΛશͯࢼ͢ํ๏Λཏత ͳ Koizumi ͷํ๏ͱ͢ʹͱ͜ͿݺΔɽ͢ͳΘͪɼཏత ͳ Koizumi ͷํ๏Ͱɼશͯͷ i ∈ I, k ∈ Ki , j ∈ J ͷ. . 1 u Vu W u u. Koizumi Βͷํ๏ʹ͓͍ͯɼશͯͷ IH λΠϓʹରͯ͠ɼn. ʹରͯ͠ɼ࣍ࣜΛ͢ࢉܭΔ͜ͱʹͳΔɽ. evalikj = min d2 (U, Wj ) = 1 − u=Bik ξ ξ∈Rm. λikj. 2,. W . (10). 3.
(4) Vol.2018-AL-166 No.1 2018/1/28. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report ∗ ͜͜Ͱɼλikj Bik Vj Bik ͷ࠷େݻ༗Ͱ͋Δɽ·ͨɼξikj. Λͦͷ࣌ͷݻ༗ϕΫτϧͱ͢ΔɽҰํɼϢʔΫϦουڑ ͕ར༻Ͱ͖Δ߹࣍ࣜΛ͕ํͨ͠ࢉܭίετ͕গͳ͍ɽ 2. evalikj = min. u=Bik ξ ξ∈Rm. U − Wj =. ∗ ∗ −ξikj ξikj. . + w w,. k1. k1. k1. k5. k4. ਤ 4. ཏతͳ Koizumi ͷํ๏Λ࣮ߦ͢ΔͨΊͷΞϧΰϦζ ࡧͷաఔͰͦΕ·Ͱʹ͍͔ͯͬͭݟΔ evalikj ͷ࠷খΛ อ͓࣋ͯ͠Γɼu∗ ͦͷ࣌ʹಘΒΕͨλΠϧܗঢ়ͷ࠲ඪ Λอ࣋͢Δɽ֤ i ∈ I, k ∈ Ki ͷʹର͢Δखଓ͖ (lines. k3. k4 k4. IH4. ϜΛ Algorithm 1 ʹࣔ͢ɽΞϧΰϦζϜதɼevalmin ୳. k1. s. s. (11) ∗ ͨͩ͠ɼξikj = Bik wj Ͱ͋Δɽ. k2. k2 k1. k1 s. k2. k3. k2. k3. k2. IH5. IH6. IH4, IH5, IH6 ͷςϯϓϨʔτ: ରͱͳΔ J ࢬʹϚʔΫ ∧ ͕ ͍͍ͯΔ߹ͦΕΒฏߦͰ͋Δɽͦ͏Ͱͳ͍߹ɼର ͱͳΔ J ࢬ x ࣠·ͨ y ࣠ʹରͯ͠ฒਐ૾ڸͷؔʹ͋Δɽ. “s” 1 ൪ͷλΠϦϯάɽ. λ Π Ϧ ϯ ά ͷ ࠲ ඪ Λ ϕ Ϋ τ ϧ uv. (xv1 , . . . , xvnv , y1v , . . . , ynv v ). =. Ͱ ද ͢ ͷ ͱ ͢ Δ ͱ ɼλ. 4–11) ͷྔࢉܭ O(n3 ) Ͱ͋Δɽ͜ΕɼBik ͷ( ࢉܭline. ΠϦϯάʹ՝͞ΕΔ੍݅ࣜ (2) ͱಉ༷ʹද͢ݱ. 4) ͕ྔࢉܭO(n3 ) Ͱ͋Δ͜ͱͱɼevalikj ͷͰࢉܭඞཁͳ. Δ͜ͱ͕Ͱ͖Δɽྫ͑ɼIH51 (ਤ 3 ࢀর) ͷ߹Ͱ͋Ε. Bik Vj Bik ͷ࠷େݻ༗ͷ ࢉܭʢϓϩΫϥεςεڑͷ. ɼ੍݅࣍ࣜͰද͞ΕΔɽ. ߹ʣ(line 6) ͷ ֤͕ྔࢉܭj ͝ͱʹ O(n2 ) Ͱ͋ΔͨΊͰ͋. ΔʢϢʔΫϦουڑΛ༻͍ͨ߹ಉ༷ʣ ɽ. Algorithm 1 : Exhaustive Search 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14:. xv2 − xv1. =. xv4 − xv3. y2v − y1v. =. −(y4v − y3v ). .. (12). uv ࣜ (4) ͱಉ༷ʹύϥϝτϥΠζ͢Δ͜ͱ͕Ͱ͖Δͷ. evalmin = ∞; for i ∈ I (isohedral types) do for k ∈ Ki (possible assignments of the points) do Compute Bik ; for j ∈ J (choices of the first point) do ∗ Compute evalikj (and ξikj ) (Eq.(10) or (11)); if evalikj < evalmin then evalmin := evalikj ; ∗ u∗ := Bik ξikj ; end if end for end for end for return u∗ ;. ͰɼBv Λ 2nv × md ྻߦܕʢmd IH λΠϓʹґଘʣ ɼξd Λ md ࣍ݩϕΫτϧͱͯ͠ɼ uv . uv = Bv ξd. (13). ͱύϥϝτϥΠζ͢Δ͜ͱ͕Ͱ͖Δɽ࣍ʹɼߦྻ Bv ͷୈ. i ྻΛ bvi ɼୈ l ߦΛ dl ͱද͢ݱΔ͜ͱʹͯ͠ɼ Bv Λ࣍ͷΑ͏ʹදΘ͢͜ͱʹ͢Δɽ. ⎛. IH λΠϓͷछྨ 93 छྨ͋Δ͕ɼ࣮ࡍʹ 29 छྨͷ. d1 . ⎞. ⎜ ⎟. v v ⎜ d2 ⎟ v ⎜ Bv = b1 b2 · · · bmd = ⎜ . ⎟ ⎟. ⎝ .. ⎠ d2nv . (14). IH λΠϓͷΈΛߟྀ͢Εྑ͍ [3]ɽ͜ΕɼΓͷ IH. ·ͣɼఏҊ๏Ͱ IH51ʢਤ 3 ࢀরʣͷλΠϧܗঢ় U Λύϥ. λΠϓ͕ 29 छྨͷ IH λΠϓͷಛघέʔεͱͯ͠আ֎Ͱ. ϝτϥΠζ͢Δ۩ମྫΛઆ໌͢ΔɽJ ࢬͱ S ࢬͷੑ࣭Λߟ. ͖ΔͨΊͰ͋Δɽ͞Βʹɼཏతͳ Koizumi ͷํ๏ʹ͓. ྀ͢Δͱɼn ͷλΠϦϯάลͷ͕ (k1 , k2 ) ∈ K51. ͍ͯɼ͋Δ IHi ͷλΠϦϯάลΛআͯ͠ผͷ IHj ͕ಘ. Ͱ͋Δ߹ɼλΠϧܗঢ় U ͷ࠲ඪ u ࣜ (15) ͷΑ͏ʹ. ΒΕΔ߹ɼIHj Λ IHi ͷಛघέʔεͱͯ͠আ֎͢Δ͜ͱ. ύϥϝτϥΠζ͢Δ͜ͱ͕Ͱ͖Δʢ1–3 ൪ͷλΠϦϯά. ʹ͢Δɽ݁Ռͱͯ͠ɼ10 छྨͷ IH λΠϓʢIH1–8, IH21,. ลͷ x ࠲ඪͷΈදࣔʣɽͨͩ͠ɼۭͷཁૉ 0 Λද͠ɼλ. IH28ʣΛ࠷దԽͷରͱ͢Δɽਤ 4 ʹ IH4–6 ͷςϯϓϨʔ. ΠϦϯάʹରԠ͢Δߦʹֻ͚ͯ͋͠Δɽ͜͜Ͱɼ. τΛࣔ͢ɽ10 छྨͷ IH λΠϓͷதͰ Ki ͷΦʔμʔ. λΠϦϯάͷ࠲ඪ (xh(s) , yh(s) ) (s = 1, 2, . . . , nv ) ࣜ. IH5 ͱ IH6 Ͱ O(n )ɼ͞Βʹ IH4 Ͱ O(n ) ʹͳΔͨΊɼ. (13), (14) ΑΓ (ds ξd , dnv +s ξd ) ͱύϥϝτϥΠζ͞Ε. ैདྷͷํࢉܭ๏ [7][6][4] Ͱཏతͳ Koizumi ͷํ๏Λ࣮ݱ. ͍ͯΔɽͦͷଞͷ͍ͭͯɼಉ͡λΠϦϯάล্ͷҰ. తͳ͢ߦ࣮Ͱؒ࣌ࢉܭΔ͜ͱࠔͱ͍͑Δɽ. ํͷλΠϦϯάʢ·ͨɼ྆ͷλΠϦϯάͷ. 3. 4. தʣ͔ΒͷࠩΛՃͯ͠࠲ඪΛύϥϝτϥΠζ͠. 3.2 ߦྻ B ͷޮࢉܭ. ͍ͯΔɽྫ͑ɼରͱͳΔ J ࢬ্ͷ h(1) + i ͱ h(3) + i 3. ैདྷͷํ๏Ͱߦྻ B (= Bik ) Λ͢ࢉܭΔͷʹ O(n ). (i = 1, 2, . . . , k1 ) ͷ x ࠲ඪύϥϝʔλʔ ξ1s , . . . , ξks1 ͱͦ. ͷ͕ྔࢉܭඞཁͰ͕͋ͬͨɼຊઅͰߦྻ B Λ O(n) ͷܭ. ΕΒΛͱ͢ΔϕΫτϧͰʢλΠϦϯά h(1) ͔Β. ࢉྔͰߏங͢Δํ๏Λઆ໌͢Δɽ. ͷ͕ࠩʣύϥϝτϥΠζ͞Ε͍ͯΔɽ·ͨɼ֤ϕΫτϧ. ⓒ 2018 Information Processing Society of Japan. 4.
(5) Vol.2018-AL-166 No.1 2018/1/28. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ ⎡ ⎤ d xh(1) 1 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ xh(1)+1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ d 1 ⎢ ⎥ ⎢ ⎥ ⎢1⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ .. .. ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ . . ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ xh(1)+k1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢1⎥ ⎢ ⎥ ⎢ ⎥ d1 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ d2 xh(2) ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ xh(2)+1 ⎥ ⎢ (d2 +d3 ) ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢2 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 1 ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ .. .. ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ . . ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ xh(2)+ k2 ⎥ ⎢ 12 (d2 +d3 ) ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ 1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ 2 1 ⎢ ⎢x ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ s k2 +1 (d +d ) ξ s s 2 3 k s ⎢ ⎥ ⎢ h(2)+ 2 ⎥ ⎢ 2 ⎥ ⎥ ⎢ ⎥ ξk ⎢ ⎥ ξk +1 ⎢ k1 + 2 ξ 1 ⎢ ⎥ 2 1 ⎢ ⎥ 1 ⎢ ⎢ x ⎥ ⎥ ⎢ ⎥ ⎢ ⎥+···, √ √ √ √ = ξ + +···+ + +···+ ⎢ h(3)− k2 ⎥ ⎢ 1 (d2 +d3 ) ⎥ d ⎥ ⎢ ⎥ 2⎢ ⎥ 2⎢ ⎥ 2 ⎢ 2 2 ⎢ ⎥ ⎢2 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢−1⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ . . ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ . . ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ . . ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ x ⎥ ⎢ 1 (d +d ) ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ 2 3 h(3)−1 −1 2 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ x d h(3) 3 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ xh(3)+1 ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ d3 ⎢ ⎥ ⎢ ⎥ ⎢1⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ . . ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ .. .. ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ x ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ d h(3)+k1 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢1⎥ ⎢ ⎥ ⎢ ⎥ 3 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ xh(4) d4 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦ .. .. . . (15). ⎡. ⎡. ਖ਼نԽͯ͋͠Δʢ √12 ͘͘Γग़ͯ͋͠Δʣɽಉ༷ʹɼS. Bd. ⎤ d 1 ⎢ ⎥ ⎢ ⎥ df1 ⎢ ⎥ ⎢ ⎥ . ⎢ ⎥ .. ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ f ⎢ ⎥ d1 ⎢ ⎥ ⎢ ⎥ d2 ⎢ ⎥ ⎢1 ⎥ ⎢ (d2 +d3 ) ⎥ ⎢2 ⎥ ⎢ ⎥ .. ⎢ ⎥ ⎢ ⎥ . ⎢ ⎥ ⎢1 ⎥ ⎢ 2 (d2 +d3 ) ⎥ ⎢ ⎥ ⎢ 1 (d2 +d3 ) ⎥ ⎢2 ⎥ ⎥ =⎢ ⎢ 1 (d2 +d3 ) ⎥ . ⎢2 ⎥ ⎢ ⎥ .. ⎢ ⎥ ⎢ ⎥ . ⎢ ⎥ ⎢ 1 (d +d ) ⎥ ⎢2 2 ⎥ 3 ⎢ ⎥ ⎢ ⎥ d 3 ⎢ ⎥ ⎢ ⎥ f ⎢ ⎥ d 3 ⎢ ⎥ ⎢ ⎥ . ⎢ ⎥ .. ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ f d3 ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ d4 ⎢ ⎥ ⎣ ⎦ .. . (16). ަ ͠ ͳ ͍ʢ Ұ ෦ ަ ͢ Δ ʣɽͦ ͜ Ͱ ɼྻ ϕ Ϋ τ ϧ ܈. ࢬ্ͷ h(2) + i ͱ h(3) − i (i =. 1, . . . , k22 ). ͷ x ࠲ඪ. bd1 , bd2 , . . . , bdmd ΛผͷྻϕΫτϧ ܈b 1 , b 2 , . . . , b md. ύϥϝʔλʔ ξks1 +1 , . . . , ξ s. ͱͦΕΒΛͱ͢Δϕ. ʹઢܗมͯ͠ɼb 1 , b 2 , . . . , b md , bs1 , bs2 , . . . , bsms ͕. ΫτϧͰʢ྆ͷλΠϦϯά h(2) ͱ h(3) ͷத͔Β. span(bd1 , bd2 , . . . , bdmd , bs1 , bs2 , . . . , bsms ) ͷਖ਼نަجఈͱ. ͷ͕ࠩʣύϥϝτϥΠζ͞Ε͍ͯΔɽͨͩ͠ɼk2 ͕ۮ. ͳΔΑ͏ʹ͍ͨ͠ɽ. k1 +. k2 2. . ͷ࣌ʢ͢ͳΘͪɼ k22 = k22+1 ʣɼxh(2)+ k2 +1 ͷߦऔ 2. Γআ͍ͯߟ͑Δͷͱ͢Δɽ. d. d. d. d. d. d. ·ͣɼbdi (i = 1, . . . , md ) Λ bsj (j = 1, . . . , ms ) ʹަ͞ ͤΔ͜ͱΛߟ͑Δɽ͜Εɼ୯ʹάϥϜγϡϛοτͷަ. ࣜ (15) ͷӈลʹ͓͍ͯɼξd ֻ͕͚ΒΕ͍ͯΔ 2n×md ߦܕ. Խ๏Λ༻͍Δ͜ͱͰ࣮͖ͰݱΔɽ͢ͳΘͪɼb i Λ bdi ʹά. ྻΛ Bd ͱ͢Δɽಉ༷ʹɼύϥϝʔλʔ ξi (i = 1, 2, . . . , ms ). ϥϜγϡϛοτͷަԽ๏Λద༻ͨ͠ޙͷϕΫτϧͱ͢Ε. ͕ͱͳ͍ͬͯΔ 2n ࣍ݩϕΫτϧΛɼͦΕͧΕ. bsi. d. ɼb i ࣍ࣜͰಘΒΕΔɽ d. (i = 1, 2, . . . , ms ) ͱ͢Δɽ͜͜ͰɼBd ͷྻϕΫτϧදݱɼ 2n × ms ྻߦܕBs ɼms ࣍ݩϕΫτϧ ξs Λ. d d. Bd = b1 b2 · · · bdmd. s s. Bs = b1 b2 · · · bsms ξs =. s (ξ1s ξ2s · · · ξm ) s. b i = bdi − bdi , bs1 bs1 − bdi , bs2 bs2 − · · · − bdi , bsms bsms . d. (17). . 2n × md ྻߦܕB ٛ͢Δɽ࣮ B. . d. . d. ΛB. . d. =. d b 1. d b 2. ···. d b md. (19) . ͱఆ. ͷߦʢྻͰͳ͍ʣ͋Δಛఆͷϕ. ΫτϧͷΈΛऔΔɽྫ͑ɼࣜ (15) ΛݟΔͱɼJ ࢬ্ͷ. ͱఆٛ͢Δͱɼࣜ (15) ͷߦྻදݱ࣍ͷΑ͏ʹͳΔɽ. u = Bd ξd + Bs ξs = (Bd Bs ). ξd. . ξs. ΛύϥϝτϥΠζ͍ͯ͠Δ Bd ͷ h(1) + i ߦͱ h(3) + i ߦͷ ߦϕΫτϧϖΞ (i = 1, . . . , k1 ) άϥϜγϡϛοτͷަ. .. (18). ͜͜·ͰͰઆ໌͖ͯͨ͠ߦྻ B ͷࢉܭ๏ͷར࣍ͷ 3 ʹ͋Δɽ. ( 1 ) Ұ Bv Λ͚͓ͯ͠ࢉܭɼBd ͱ Bs Ker(A) Λܭ ࢉʢ ͕ྔࢉܭO(n3 )ʣ͢Δ͜ͱͳ͘ಘΒΕΔ.. Խ๏Λద༻ͨ͠ʹޙɼi ͷʹΑΒͣಉ͡ߦϕΫτϧϖΞ . ʹͳΔɽ͜ͷߦϕΫτϧϖΞΛ df1 ɼdf3. . Α͏ʹ͞ࢉܭΕΔɿ. df1 df3. . =. d1. . d3 . . . ͱ͢Δͱɼ࣍ͷ. d1 1 1 − [1 1] 2 d3 1. ɽ͜ͷࣜͷୈ i ྻάϥϜγϡϛοτͷަԽ๏Ͱ b i. d. Λ͍ͯ͠ࢉܭΔʢඞཁͳ 2 ͷΈࢉܭʣ͜ͱʹҙ͞Εͨ. ( 2 ) Bs εύʔεߦྻͰ͋Δ.. ͍ɽҰํɼS ࢬ্ͷΛύϥϝτϥΠζ͍ͯ͠Δ Bd ͷୈ l. ( 3 ) Bs ͷྻϕΫτϧʹ͍ޓަ͢Δɽ. ߦ (h(2) < l < h(3)) ϕΫτϧάϥϜγϡϛοτͷަԽ. Ұ ํ ɼBd Λ ߏ ͢ Δ ྻ ϕ Ϋ τ ϧ ʹ ͍ ޓ ަ ͠ ͯ. ͷʹޙมԽ͠ͳ͍ɽ͜ΕɼS ࢬΛύϥϝτϥΠζ͍ͯ͠Δ. ͓ Β ͣ ɼ͜ Ε Β Bs Λ ߏ ͢ Δ ྻ ϕ Ϋ τ ϧ ͱ . bsj (j = k1 + 1, . . . , k1 + k22 ) ͕ ʹطbdi (i = 1, . . . , md ) ͱ. ⓒ 2018 Information Processing Society of Japan. 5.
(6) Vol.2018-AL-166 No.1 2018/1/28. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. ަ͍ͯ͠ΔͨΊͰ͋Δɽ݁Ռͱͯ͠ɼߦྻ B d ࣜ (16). J ࢬ্ͷΛύϥϝτϥΠζ͍ͯ͠Δ߹ɼࣜ (15) ʹ͓͍. W:. ͯɼxl (l = 1, . . . , n) ͕ xh(s)+i (resp. xh(s)−i ) ͱද͞ݱΕ. U:. ͍ͯΔͳΒ dfs. . . (resp. dbs ) ͱදࣔ͢Δͷͱ͢Δɽy. ࠲ඪʹ͍ͭͯಉ༷Ͱ͋Δ͕ɼdfnv +s. . . දࣔ͢Δɽ ަ Խ ๏ ʹ Α Γ b 1 , b 2 , . . . , b md Λ ਖ਼ ن ަ Խ ͠ ͯ d. d. d. b 1 , b 2, . . . , b md Λߏ͢Δɽ 2n × md ྻߦܕB d Λ d d d B d = b 1 b 2 · · · b md ͱఆٛ͢Δͱɼߦྻ B d. d. d. ਤ 5. W jp. j. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 12 13 14 15 16 17 18 19 20 21 22 1 2 3 4 5 6 7 8 9 10 11 J. S. k1. (resp. dbnv +s ) ͱ. ࠷ ޙͷ ε ς ο ϓ ͱ ͠ ͯ ɼά ϥ Ϝ γ ϡ ϛ ο τ ͷ . Wec. e. ͷΑ͏ʹߏங͢Δ͜ͱ͕Ͱ͖Δɽ͜͜ͰɼB d ͷୈ l ߦ͕. k4. S. Uc. J. k5. S. k1. S. k2. Up. k3. ඪਤ ܗW ͱ IH4 ʹଐ͢ΔλΠϧܗঢ় U ͷͷରԠؔ ʢj = 12 ͷ߹ʣɽ. քΛޮྑͯ͘͠ࢉܭར༻͢Δํ๏ΛఏҊ͢Δɽ͜ͷํ๏ Ki ͷΦʔμʔ͕ O(n3 ) Ҏ্ͱͳΔ IH4, IH5, IH6 ʹͷ. (B d Bs ) ͱͯ͠ಘΒΕɼλΠϧܗঢ় U ࠷ऴతʹ࣍ͷΑ. Έద༻͢Δɽࢴ໘ͷ߹্ IH4 ʹରͯ͠ͷΈఏҊ͢Δํ๏. ͏ʹύϥϝτϥΠζ͞ΕΔɽ. ͷઆ໌Λߦ͏͕ɼIH5, IH6 ʹରͯ͠جຊతͳߟ͑ํಉ. u=B. . d ξd. + Bs ξs = (B. . d. Bs ). ξd. . ͡Ͱ͋Δɽ. .. ξs. (20). IH4 ͷςϯϓϨʔτʢਤ 4ʣΑΓɼn ͷλΠϦϯά ลͷՄೳͳৼΓ͚ํ K4 = {(k1 , k2 , k3 , k4 ) | 0 ≤. ߦྻ B (= Bik ) ͷߏங๏ͱඞཁͳྔࢉܭΛҎԼʹ·ͱΊ Δɽͨͩ͠ɼྔࢉܭΛߟ͑Δ্Ͱ md nv (md ≤ 2nv ) Ͱ. k1 , k2 , k3 , k4 , 2k1 + k2 + k3 + k4 ≤ n − 6} ͱͳΔɽͨͩ͠ɼ k5 = n − 6 − (2k1 + k2 + k3 + k4 ) Ͱ͋Δɽ͜͜Ͱɼevalikj. ༻͢Δɽ֤ IH λΠϓ i ∈ I ʹରͯ͠ɼߦྻ Bv ͓Αͼϕ. Λ eval(k1 , k2 , k3 , k4 ; j) ͱද͢ݱΔ͜ͱʹ͢ΔɽIH4 ʹର. Ϋτϧ dbs , dfs. ͯ͠ϢʔΫϦου Ͱڑevalikj Λ͢ࢉܭΔ͜ͱ͕Ͱ͖. . . (s = 1, 2, . . . , 2nv ) Λ࠷ॳʹҰ͚ͩࢉܭ. ͓ͯ͘͠ɽ͜ΕΒͷྔࢉܭͦΕͧΕ O(nv 3 ) ͱ O(nv n) Ͱ͋ΓɼશମͷʹྔࢉܭൺͯແࢹͰ͖Δɽ֤ k ∈ Ki ʹ ର͠ɼߦྻ Bik Λ࣍ͷ 3 εςοϓͰߏ͢Δɽ . ( 1 ) ࣜ (16) ͷ Α ͏ ʹ ߦ ϕ Ϋ τ ϧ ds , dbs , dfs. . ΔͷͰɼIH4 ʹର͢Δࣜ (11) ࣍ࣜͰද͞ΕΔɽ 2. eval(k1 , k2 , k3 , k4 ; j) = min U − Wj . u=B4k ξ ξ∈Rm. (s =. (21). Λߏங͢Δɽ. ਤ 5 ʹඪਤ ܗW ͱ IH4 ʹଐ͢ΔλΠϧܗঢ় U ͷؒͷ. Bd 2n×md ͳྻߦܕͷͰɼྔࢉܭ O(nv n) Ͱ͋Δɽ. ͚͓ʹࢉܭڑΔؒͷରԠؔΛࣔ͢ʢWj ͷΠϯσο. 1, 2, . . . , 2nv ) Λஔ͢Δ͜ͱͰߦྻ. Bd. ( 2 ) ࣜ (16) ͷΑ͏ʹߦྻ Bs ߏங͢ΔɽBs ͷඇθϩ. Ϋεͷ͕࢝ j = 12 ͷ߹ʣɽͨͩ͠ɼਤͰ Wj Ͱͳ. ͷΦʔμʔ O(n) Ͱ͋ΔͷͰɼదͳεύʔεߦྻ. ͘ W ͷΠϯσοΫεΛද͍ࣔͯ͠Δ͜ͱʹҙ͞Ε͍ͨɽ. දݱΛ༻͍Δ͜ͱͰɼྔࢉܭ O(n) ͱͳΔɽ. ޙͷઆ໌Ͱదٓ͜ͷਤΛࢀর͞Ε͍ͨɽ. ( 3 ) Bd Λߏ͢ΔྻϕΫτϧΛਖ਼نަԽͯ͠ B d Λಘ Δɽ͜ͷεςοϓͷྔࢉܭ. O(n2v n). ͱͳΔɽ. IH4 ͷςϯϓϨʔτʹ͓͍ͯɼk1 , k2 , k3 ͷͷΈ͕༩͑ ΒΕ߹ɼࣜ (15) ͞Βʹࣜ (20) ͱಉ༷ͷํ๏ͰɼIH4 ͷ. nv ͕ఆʢߴʑ 6) Ͱ͋ΔͷͰɼ্هखଓ͖Ͱߦྻ Bik Λ. ςϯϓϨʔτͷ 1–4 ൪ͷλΠϦϯάลʹΑΓ੍Λ͏͚. ߏங͢Δྔࢉܭ O(n) Ͱ͋Δɽ. Δ෦తͳλΠϧܗঢ় U p ΛύϥϝτϥΠζ͢Δ͜ͱ͕Ͱ. ࢴ໘ͷ߹্ɼৄࡉׂѪ͢Δ͕ɼҙͷ i ∈ I, k ∈ Ki. ͖Δɽ͜͜ͰɼU p ΛύϥϝτϥΠζ͢ΔͨΊͷߦྻ B Λ. ʹରͯ͠ɼIH51 ʹରͯ͠આ໌͖ͯͨ͠ͷͱಉ༷ͷํ๏ʢܭ. p B4k ͱදΘ͢͜ͱʹ͢Δɽ·ͨɼU p ͱରԠ͢Δ W ͷ෦. ࢉྔʣͰߦྻ Bik Λߏங͢Δ͜ͱ͕Ͱ͖Δɽ. Λ Wjp ͱද͢͜ͱʹ͢Δɽ࣍ʹؔ. ߦྻ B ͷޮࢉܭͷ෭࣍తͳޮՌͱͯ͠ɼϢʔΫϦου ڑΛ༻͍ͨ߹ʹ evalikj ͷࢉܭΛ O(n) ࣌ؒͰ࣮ߦ͢Δ. 2. evalp (k1 ,k2 ,k3 ;j)= pminp U p −Wjp u =B4k ξ. (22). . ∗ ͜ͱ͕ՄೳʹͳΔʢैདྷ O(n2 )ʣ ɽ͜Εɼξikj = Bik wj. ξ∈Rm. ͷ͍͓ͯʹࢉܭɼBik ͷඇθϩཁૉͷΦʔμʔ͕ O(n) Ͱ͋. Λఆٛ͢Δɽͨͩ͠ɼup ࣜ (6) ͱಉ༷ʹ U p ͷ࠲ඪΛද͢. ΔͨΊͰ͋Δɽ·ͨɼࢴ໘ͷ߹্ৄࡉলུ͢Δ͕ɼຊݚ. ϕΫτϧͰ͋Δɽevalp (k1 , k2 , k3 ; j) ͷࣜ (11) ͱಉ༷. ͰڀϓϩΫϥεςεڑΛ༻͍ͨ߹Ͱ Bik Vj Bik ͷ. ʹ͢ࢉܭΔ͜ͱ͕Ͱ͖Δ͕ɼ͜ͷ eval(k1 , k2 , k3 , k4 ; j). ࠷େݻ༗Λ O(n) ࣌ؒͰ͢ࢉܭΔํ๏։ൃͯ͠༻͍Δɽ. ͷ U p − Wjp ෦ͷԼքΛ༩͑Δɽ͜Ε෦తͳλΠ. 2. ϧܗঢ় U p ʹ՝͞Ε͍ͯΔ੍͕݅ɼ͜ͷ෦ʹຊདྷ՝. 3.3 ׂ؇Λ༻͍ͨޮతͳཏ୳ࡧ ߦྻ Bik Λޮతʹ͖ͰࢉܭΔ͜ͱʹΑΓɼAlgorithm. ͞Ε͍ͯΔ੍݅ͷ؇݅ͱͳ͍ͬͯΔͨΊͰ͋Δ ʢU p ͷ྆ͷλΠϦϯά 5,6 ൪ͷλΠϦϯάลͷ. 1 ͷ࣮ߦ࣌ؒͷ΄ͱΜͲ evalikj ͷʹ ࢉܭඅ͞ΕΔɽ. ྆Ͱ͋ΔͷͰɼຊདྷͦͪΒ͔Β੍Λड͚Δ͕ɼ. ͦ͜Ͱɼevalikj ͷࢉܭճΛݮΒͨ͢Ίʹɼevalikj ͷԼ. ͜͜Ͱड͚͍ͯͳ͍ʣɽ. ⓒ 2018 Information Processing Society of Japan. 6.
(7) Vol.2018-AL-166 No.1 2018/1/28. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. ࣍ʹɼU p ͱ૬ิతͳ෦ U c ʹ͍ͭͯߟ͑Δɽ͜ͷ෦. Algorithm 2 ʹ Algorithm 1 ʹ evalikj ͷԼքΛར༻͠. IH4 ͷςϯϓϨʔτͷ 5ɼ6 ൪ͷλΠϦϯάลʹΑΓ. ͯࢉܭΛޮԽͨ͠ΞϧΰϦζϜʢIH4 ͷ෦ͷΈʣΛ. ੍Λ͏͚Δ෦తͳλΠϧܗঢ়Ͱ͋Δ͕ɼ྆ͷλΠϦ. ࣔ ͢ ɽॏ ཁ ϙ Π ϯ τ ֤ (k1 , k2 , k3 , k4 ) ∈ K4 ʹ ର ͠ ɼ. c. ϯάʹͱ͍͜ͳ·ؚҙ͕ඞཁͰ͋ΔɽU ͱରԠ. evalp (k1 , k2 , k3 ; j) + evalc (k4 , k5 ; e) < evalmin ͱͳΔ. ͢Δ W ͷ෦Λ Wec ͱද͢͜ͱʹ͢ΔʢW ͷ e + 1 ൪. ߹ͷΈ eval(k1 , k2 , k3 , k4 ; j) Λ͢ࢉܭΔ͜ͱͰ͋Δ (line 7,. ͷΛ࢝ͱ͢Δʣɽ͜͜Ͱ e U ͷ 5 ൪ͷλΠϦϯά. 9)ɽ·ͨɼ͍͔ͭ͘ͷ (k1 , k2 , k3 , k4 ) ∈ K4 ʹ͓͍ͯɼ. ͱରԠ͢Δ W ͷͷΠϯσοΫεͰ͋Δɽ෦ܗঢ়. eval(k1 , k2 , k3 , k4 ; j) ͷΛશͯͷ j = 1, 2, . . . , n ʹରͯ͠. p. U Λߏ͢Δ 5ɼ6 ൪ͷλΠϦϯάลʹׂΓͯΔͷ. ͢ࢉܭΔඞཁ͕ͳ͍ɽ͜ͷ߹ߦྻ B4k Λ͢ࢉܭΔඞཁ. k4 ɼk5 Ͱ༩͑ΒΕɼࣜ (20) ͱಉ༷ͷํ๏Ͱ U c Λύ. ͕ͳ͍ͷͰɼඞཁͱͳͬͨ࣌Ͱ͍ͯ͠ࢉܭΔ (line 8)ɽ. ϥϝτϥΠζ͢Δ͜ͱ͕Ͱ͖Δɽͨͩ͠ɼU c ʹ྆ͷ λΠϦϯά͕·ؚΕ͍ͯͳ͍͜ͱΛߟྀ͢Δඞཁ͕͋. 4. ࣮݁ݧՌ. Δ͕ɼ͜Ε B ͷߏங๏ͷεςοϓ 1–2 ͷʹޙಘΒΕΔߦ. 4.1 ࣮ݧઃఆ. ྻ Bd ͱ Bs ʹ͓͍ͯɼ྆ͷλΠϦϯάΛύϥϝτ. ఏҊͨ͠ΞϧΰϦζϜ C++ͱ Eigen library Λ༻͍ͯ. ϥΠζ͍ͯ͠Δ 4 ྻΛআ͢Δ͚ͩͰ࣮͖ͰݱΔʢεςο. Ubuntu 14.04 Linux PC (Intel Core [email protected] GHz). c B4k. Λߏ͢Δྻ. ্Ͱ࣮ͨ͠ɽ2 ͭͷޮԽ (1) ߦྻ B ͷޮతͳߏங. ϕΫτϧͷަੑอͨΕΔ͕ূ໌লུ͢Δɽ࣍ʹؔ. ๏ɼ(2) evalikj ͷԼքʹࢉܭΑΔෆཁͳ evalikj ͷࢉܭͷ. ϓ 3 ಉ͡ʣɽ͜ͷํ๏ͰಘΒΕͨߦྻ. 2. evalc (k4 ,k5 ;e)= cminc U c −Wec u =B4k ξ. ഉআɼͷޮՌΛௐΔͨΊɼ࣍ͷ 3 ͭͷΞϧΰϦζϜΛߏ. (23). . ξ∈Rm. ஙͯ͠ཏతͳ Koizumi ͷख๏ͷ࣮ߦ࣌ؒΛൺֱ͢Δɽ. Algorithm A Algorithm 1ʢߦྻ B ैདྷ๏Ͱࢉܭʣ*2. Λ ఆ ٛ ͢ Δ ɽU p ͷ ࣌ ͱ ಉ ༷ ͷ ٞ ʹ Α Γ ɼ͜ ͷ 2. eval(k1 , k2 , k3 , k4 ; j) ͷ U c − Wec ෦ͷԼքΛ༩͑Δɽ. Algorithm B Algorithm 1ʢޮԽ (1) Λಋೖʣ Algorithm C Algorithm 2ʢޮԽ (1) ͱ (2) Λಋೖʣ ඪਤ ͯ͠ͱܗ2 छྨͷਤ“ ܗcat” ͱ “hippocampus”. ࣜ (22)ɼ(23) ΑΓɼeval(k1 , k2 , k3 , k4 ; j) ͷԼք. Λ༻͍ɼͦΕͧΕ n = 60 ͓Αͼ 120 ͰۉʹΛஔ͠. evalp (k1 , k2 , k3 ; j) + evalc (k4 , k5 ; e). (24). Ͱ༩͑ΒΕΔɽͨͩ͠ɼe = (j +2k1 +k2 +k3 +5) (subtract. n if e > n)ɼk5 = n − 6 − (2k1 + k2 + k3 + k4 ) Ͱ͋Δɽ ͜ͷԼքΛར༻ͯ͠ɼAlgorithm 1 ͷ࣮ߦաఔʹ͓͍ͯɼ. evalp (k1 , k2 , k3 ; j) + evalc (k4 , k5 ; e) ≥ evalmin Ͱ͋Δ͜ͱ ͕͔ͬͨ߹ɼeval(k1 , k2 , k3 , k4 ; j) (= evalikj ) ͷࢉܭ Λলུ͢Δ͜ͱ͕Ͱ͖Δɽ͜ͷࢉܭΛޮతʹߦ͏ͨΊʹɼ ࠷ॳʹ evalc (k4 , k5 ; e) ͷΛશͯͷʢ0 ≤ k4 + k5 ≤ n − 6,. 1 ≤ e ≤ n) ʹ͍͓ͭͯͯ͘͠ࢉܭɽ Algorithm 2 : Efficient algorithm (IH4) 1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17:. evalmim := ∞ (or inherited from the preceding search); Compute evalc (k4 , k5 ; e) for all combinations of k4 , k5 , e; for 0 ≤ 2k1 + k2 + k3 ≤ n − 6 (triple for-loop) do Compute evalp (k1 , k2 , k3 ; j) → evalj (1 ≤ j ≤ n) for 0 ≤ k4 ≤ n − 6 − (2k1 + k2 + k3 ) do for j = 1, 2, . . . , n do if evalj + evalc (k4 , k5 ; e) < evalmin then Construct B4k if not yet constructed; Compute eval(k1 , k2 , k3 , k4 ; j) → eval if eval < evalmin then evalmin := eval; u∗ := B4k ξ∗ (ξ∗ = B4k wj ); end if end if end for end for end for. ⓒ 2018 Information Processing Society of Japan. ͨଟ֯ ͰܗW Λߏ͢Δɽ ิతͳࣄ߲ͱͯ͠ɼKi ͷΦʔμʔ IH4 Ͱ O(n4 )ɼ. IH5 ͱ IH6 Ͱ O(n3 )ɼͦͷଞͷ 7 छྨͷ IH λΠϓͰ O(n2 ) Ͱ͋Δɽ·ͨɼIH4 ͰϢʔΫϦουڑɼIH5 ͱ IH6 Ͱ ϓϩΫϥεςεڑΛ༻͍ͯࢉܭڑΛߦ͏ɽ. 4.2 ࣮݁ݧՌ ਤ 6 ʹ 2 ͭͷඪਤ( ܗn = 60) ͱɼIH4, IH5, IH6 Ͱಘ ΒΕͨλΠϧਤܗɼ͓ΑͼλΠϦϯάͷ݁Ռ (IH4 ͷ߹ ͷΈʣΛࣔ͢ɽλΠϧਤܗͷઢͷ৭ਤ 2 ͷςϯϓϨʔτ ʹରԠ͍ͯ͠Δɽ·ͨɼࢀߟͱͯ͠ΦϦδφϧͷ Koizumi Βͷํ๏ͱಉ༷ʹɼ֤λΠϦϯάลʹಉ͡ͷΛஔ͠ ͨ߹ͷ݁Ռʢ28 छྨͷ IH λΠϓΛࢼͯ͠ಘΒΕͨ࠷ద ਤܗʣࣔ͢ɽैདྷͷ Koizumi Βͷํ๏Ͱඪਤ ܗS Λۙࣅ͢Δଟ֯ܗΛߏ͢ΔΛ͏·͘બͿඞཁ͕͋ͬ ͕ͨɼཏతͳ Koizumi ͷํ๏ʹΑΓɼ୯ʹۉʹΛ ஔ͢Δ͚ͩͰྑͳ݁Ռ͕ಘΒΕ͍ͯΔࣄ͕͔Δɽͳ ͓ɼൺֱ݁Ռলུ͢Δ͕ɼ͜ΕΒͷ 3 ͭͷ IH λΠϓͰ ಘΒΕΔλΠϧਤܗଟ͘ͷ߹ɼͦͷଞͷ 7 छྨͷ IH λΠϓͰಘΒΕΔλΠϧਤܗΑΓྑ͍݁ՌΛಘΔʢඪ ਤ ܗW ͱͷ͕ڑগͳ͍ʣɽ͜ͷཧ༝͜ΕΒ 3 ͭͷ IH λΠϓͦͷଞͷ IH λΠϓΑΓ Ki ͷΦʔμʔ͕ߴ͘ɼ ՄೳͳλΠϧܗঢ়ͷࣗ༝͕ߴ͍ͨΊͰ͋Δɽ *2. ͜ͷΞϧΰϦζϜʹϓϩΫϥεςεڑΛ O(n) ࣌ؒͰ͢ࢉܭ ΔޮԽ͕࠾༻͞Ε͓ͯΓɼैདྷͷࢉܭ๏ΑΓߴͰ͋Δɽ. 7.
(8) Vol.2018-AL-166 No.1 2018/1/28. ใॲཧֶձڀݚใࠂ IPSJ SIG Technical Report. cat(60). hippocampus(60). IH4. IH5. IH6. Original. ਤ 6 ඪਤ ܗcat ͱ hippocampus (n = 60) ʹର͢Δ࠷దλΠϧܗঢ়ͱλΠϦϯά (IH4)ɽ ද 1. IHi IH4 IH5 IH6 IH1 IH2 IH3 IH7 IH8 IH21 IH28 All. 3 छྨͷΞϧΰϦζϜͷ࣮ߦ࣌ؒʢඵʣɽ cat(60) cat(120) Alg. A Alg. B Alg. C Alg. A Alg. B Alg. C 88.76 3.65 0.20 11187.72 194.22 3.99 5.44 0.70 0.10 333.07 18.83 1.28 5.44 0.70 0.13 333.82 18.83 2.54 0.24 0.02 =B 7.26 0.18 =B 0.29 0.04 =B 8.37 0.53 =B 0.30 0.04 =B 8.53 0.53 =B 0.49 0.03 =B 14.42 0.40 =B 0.30 0.02 =B 9.24 0.16 =B 0.48 0.03 =B 14.26 0.39 =B 0.49 0.03 =B 14.22 0.39 =B 102.40 5.15 0.57 11884.40 235.60 9.17. ද 1 ʹඪਤ ܗcat (n = 60, 120) ʹରͯ͠ Algorithm. Koizumi ͷํ๏Λޮతʹ࣮ߦ͢ΔΞϧΰϦζϜΛ։ ൃͨ͠ɽఏҊ๏Ͱߦྻ B Λ O(n) ࣌ؒʢैདྷ O(n3 )ʣ Ͱߏங͢Δ͢Δ͜ͱ͕ग़དྷΔɽ·ͨɼevalikj ͷࢉܭΛ O(n) ࣌ؒͰߦ͏͜ͱՄೳͱͳͬͨʢैདྷ O(n2 )ʣ ɽ͞Βʹɼ ແବͳ evalikj ͷࢉܭΛলུ͢ΔͨΊʹɼevalikj ͷԼքΛ ޮతʹͯ͠ࢉܭར༻͢Δํ๏ΛఏҊͨ͠ɽ͜ΕΒͷํ๏ ʹΑΓɼn = 60 Ͱ 0.6 ඵɼn = 120 Ͱ 10 ඵఔͰཏ తͳ Koizumi ͷํ๏Λ࣮ߦ͢Δ͜ͱ͕ՄೳͰ͋Δɽ ࢀߟจݙ [1] [2]. A, B, C Λ༻͍ͯཏతͳ Koizumi ͷख๏Λ࣮ߦͨ͠߹ ͷؒ࣌ࢉܭʢඵʣΛࣔ͢ɽ࣮ߦ֤࣌ؒ IH λΠϓ͝ͱʹݸ ผʹ࣮ߦͨ͠߹ͱɼશͯΛ௨࣮ͯ͠ߦͨ͠߹ʹ͍ͭͯ ࣔ͢ɽAlgorithm C Ͱ IH λΠϓ͕มΘͬͯ evalmin ͷ͕Ҿ͖͕ܧΕΔͨΊɼτʔλϧͷؒ࣌ࢉܭ IH λΠϓ. [3]. [4]. ͝ͱͷؒ࣌ࢉܭΛ͠߹Θͤͨ߹ΑΓ͘ͳ͍ͬͯΔɽ ·ͨɼඪਤ ܗhippocampus ͷ݁Ռ cat ͷ߹ͱ΄΅ಉ. [5]. ͡Ͱ͋ͬͨͨΊলུ͢Δɽද 1 ΑΓͲͷΞϧΰϦζϜʹ͓ ͍ͯɼKi ͷΦʔμʔ͕େ͖͍΄Ͳؒ࣌ࢉܭΛཁ͢Δ͜ͱ. [6]. ͕͔Δɽn = 60 ͷ߹ Algorithm A ͷτʔλϧͷࢉܭ ࣌ؒ 102 ඵͰ͋Δ͕ɼAlgorithm B Ͱ 20 ഒߴԽ͞. [7]. Εͯ 5.15 ඵʹ͞ݮΕ͍ͯΔɽ͞ΒʹɼAlgorithm C Ͱ ࣮ߦ࣌ؒ 0.57 ඵ·Ͱ͞ݮΕɼAlgorithm A ͱ B ʹର͠. [8]. ͯɼͦΕͧΕ 9 ഒ 180 ഒͷߴԽΛୡͨ͠ɽn = 120 ͷ߹ɼߴԽͷޮՌΑΓݦஶͱͳΓɼAlgorithm A Ͱ 11884.4 ඵཁ͍ͯͨؒ࣌͠ࢉܭΛ Algorithm C Ͱ 9.17 ʹ·Ͱ͠ݮɼ 1300 ഒͷߴԽΛ࣮͍ͯ͠ݱΔɽ. 5. ͓ΘΓʹ. [9]. B. Gr¨ unbaum, and G. Shephard. Tilings and patterns. A Series of Books in the Mathematical Sciences, 1989. S. Imahori and S. Sakai. A local-search based algorithm for the Escherization problem. Proc. of the IEEE Int. Conf. on Industrial Engineering and Engineering Management, pp. 151–155, 2012. ࠓງ ৻࣏, ञҪᠳฏ. Τογϟʔ෩λΠϦϯάʹର͢ Δࡧ୳ॴہ๏. ใॲཧֶձڀݚใࠂ, Vol.2013-AL-144 No.14, 2013. S. Imahori, S. Kawade and Y. Yamakata. Escher-like Tilings with Weights. Discrete and Computational Geometry and Graphs, pp. 132–142, 2015. C. S. Kaplan and D. H. Salesin. Escherization. Proc. of the 27th annual conf. on Computer graphics and interactive techniques, pp. 499–510, 2000. ग़ ੩ɼࠓງ ৻࣏. 2 छྨͷਤʹܗΑΔλΠϦϯάੜ ʹ͓͚Δਤܗͷબํ๏. ཧղੳڀߨॴڀݚ, ୈ 1931 ר, pp. 107-128, 2015. H. Koizumi and K. Sugihara. Maximum eigenvalue problem for Escherization. Graphs and Combinatorics, 27(3):431–439, 2011. S. Ono, M. Kisanuki, H. Machii, and K. Mizuno. Figure pattern creation support for escher-like tiling by interacitive genetic algorithms. Proc. of the 18th Asia Pacific Symposium on Intelligent and Evolutionary Systems, pp. 421.432, 2014. M. Werman and D. Weinshall. Similarity and affine invariant distances between 2d point sets. IEEE Transactions on Pattern Analysis and Machine Intelligence, 17(8):810–814, 1995.. ຊ ߘ Ͱ Escherization problem ʹ ର ͢ Δ ཏ త ͳ ⓒ 2018 Information Processing Society of Japan. 8.
(9)
関連したドキュメント
A number of qualitative studies have revealed that Japanese railroad enthusiasts have low self-esteem, are emotionally distant from others, and possess
既存の尺度の構成概念をほぼ網羅する多面的な評価が可能と考えられた。SFS‑Yと既存の
算処理の効率化のliM点において従来よりも優れたモデリング手法について提案した．lMil9f
（１）〈添加・例示・提題などをあらわすもの〉では、Ａ〈添加〉Ｌ「風三二」の「さ
当該不開示について株主の救済手段は差止請求のみにより、効力発生後は無 効の訴えを提起できないとするのは問題があるのではないか
of IEEE 51st Annual Symposium on Foundations of Computer Science (FOCS 2010), pp..
CSPF︓Cooling Seasonal Performance Factor（冷房期間ｴﾈﾙｷﾞｰ消費効率）.. 個々のお客様ニーズへの
需要動向に対応して，長期にわたる効率的な安定供給を確保するため， 500kV 基 幹系統を拠点とし，地域的な需要動向，既設系統の状況などを勘案のうえ，需要
