際際滷

際際滷Share a Scribd company logo

2020 03-31-lection

Download as PPT, PDF
O
Olga Leshchenko

12

1 of 43
Download to read offline
弌从仆亶 亳仆亠亰 亳 仗仍舒仆亳仂于舒仆亳亠 于亳仍亠仆亳亶 仂亠仆从仂 舒仍亠亳亶 仍亠从亠亠于亳 kost@cs.msu.su
亳从仍舒亟仆亠 仂弍仍舒亳 仆仂仄舒亳仂仆仆仂-仗舒于仍ﾑ亳亠 亳亠仄 亠舒仍仆仂亞仂 于亠仄亠仆亳 (于仂亠仆仆亠 亳亠仄): 舒于亳舒亳仂仆仆亠, 从仂舒弍亠仍仆亠, 舒于仂仄仂弍亳仍仆亠, 仂弍仂, 舒于仂仄舒亳亰亳仂于舒仆仆亠 亳亠仄 仗舒于仍亠仆亳 亠仆仂仍仂亞亳亠从亳仄亳 仗仂亠舒仄亳. 丶亠仆 仂弍舒弍仂从亳 亟舒仆仆 于 仂仄 亳仍亠 亳 舒仗亠亟亠仍亠仆仆亠 丶. 亠亟仂舒于仍亠仆亳亠 于亳仍亳亠仍仆 亠仂于 仗仂仍亰仂于舒亠仍礆 (仆舒仗亳仄亠, 束仂亠仍亠从仂仄損). 仗仂仍亰仂于舒仆亳亠 丶 亟仍 仂弍亠仗亠亠仆亳 仂弍于亠仆仆 仗仂亠弍仆仂亠亶 于 于亳仍亠仆亳 (仆舒仗亳仄亠, 束弌弍亠弍舒仆从損).
舒亟舒亳 从仂仄弍亳仆舒仂仆仂亶 仂仗亳仄亳亰舒亳亳 仆仂亢亠于仂 亠亠仆亳亶 于从仍ﾑ舒亠 于亠于仂亰仄仂亢仆亠: 舒亰仄亠亠仆亳 亳仂亟仆仂 亰舒亟舒仆仆 仂弍亠从仂于, 仗仂磲仂亳于舒仆亳 亳仂亟仆仂 亰舒亟舒仆仆 仂弍亠从仂于, 舒亰弍亳亠仆亳 仆舒 亞仗仗 亳仂亟仆仂 亰舒亟舒仆仆 仂弍亠从仂于. 仂仄弍亳仆舒仂仆舒 仂仗亳仄亳亰舒亳 于从仍ﾑ舒亠 于 亠弍 亰舒亟舒亳 仂仗亳仄亳亰舒亳亳, 于 从仂仂 仄仆仂亢亠于仂 亟仂仗亳仄 亠亠仆亳亶 亟亳从亠仆仂 亳仍亳 仄仂亢亠 弍 于亠亟亠仆仂 从 亟亳从亠仆仂仄 仄仆仂亢亠于.
亅舒仗 亠亠仆亳 亰舒亟舒亳 弌仂亟亠亢舒亠仍仆舒 仂仄仍亳仂于从舒 亰舒亟舒亳 舒亠仄舒亳亠从舒 仂仄仍亳仂于从舒 亰舒亟舒亳 仆舒仍亳亰 于仂亶于 亰舒亟舒亳 弍仂 从仍舒舒 舒仍亞仂亳仄仂于 (亳仍亳 于弍仂 亳亰于亠仆仂亞仂 舒仍亞仂亳仄舒) 舒亰舒弍仂从舒 亳 亠舒仍亳亰舒亳 舒仍亞仂亳仄舒 仍亠亟仂于舒仆亳亠 于仂亶于 舒仍亞仂亳仄舒
舒亟舒舒 仂 ﾐ歳経夷歳 (仂亟亠亢舒亠仍仆舒 仂仄仍亳仂于从舒) 舒仆 ﾐ歳経夷 亰舒亟舒仆仆仂亞仂 仂弍亠仄舒 亳 仆舒弍仂 仗亠亟仄亠仂于. 舒亢亟亶 仗亠亟仄亠 舒舒从亠亳亰亠: 仂亳仄仂 亳 仂弍亠仄仂仄. 丐亠弍亠 仗舒从仂于舒 ﾐ歳経夷 舒从, 仂弍: 仄仄舒仆舒 仂亳仄仂 仗舒从仂于舒仆仆 仗亠亟仄亠仂于 弍仍舒 仄舒从亳仄舒仍仆仂亶; 仄仄舒仆亶 仂弍亠仄 仗舒从仂于舒仆仆 仗亠亟仄亠仂于 仆亠 仗亠于舒仍 仂弍亠仄 ﾐ歳経夷歳.
舒亟舒舒 仂 ﾐ歳経夷歳 (仄舒亠仄舒亳亠从舒 仂仄仍亳仂于从舒) 舒仆仂: b - 仂弍亠仄 ﾐ歳経夷歳, {(ai , ci), I = 1,,n} n 亳仍仂 仗亠亟仄亠仂于, ai 亳 ci. - 仂弍亠仄 亳 仂亳仄仂 仗亠亟仄亠舒 i. 亠亠仆亳亠 弍亟亠仄 仂仗亳于舒 于亠从仂仂仄: X = (x1,, x2, .,xn) 仍亳 仗亠亟仄亠 仗舒从仂于舒仆 于 ﾐ歳経夷, 仂 xi=1, 亠仍亳 仆亠 xi=0.
舒亟舒舒 仂 ﾐ歳経夷歳 (仄舒亠仄舒亳亠从舒 仂仄仍亳仂于从舒) 丶亠仍亠于舒 仆从亳: 个仆从亳 仂亞舒仆亳亠仆亳亶: . )(max 1 ワ n i ii X xc bxa n i ii ｏワ1
舒亟舒舒 仂 ﾐ歳経夷歳 (舒仆舒仍亳亰 于仂亶于 亰舒亟舒亳) 仍亳 于亠 从仂亳亳亠仆 ai 亠仍亠 亳仍舒 亳 b 亠仍仂亠 亳仍仂, 仂 亰舒亟舒舒 磦仍磳 NP-亟仆仂亶. 仍亳 于亠 从仂亳亳亠仆 ai 于亠亠于亠仆仆亠, 仂 亰舒亟舒舒 仄仂亢亠 弍 亠亠仆舒 亢舒亟仆仄 舒仍亞仂亳仄仂仄 仍仂亢仆仂亳 O(nlog n).
舒亟舒舒 仂 ﾐ歳経夷歳 (舒仍亞仂亳仄 亠亠仆亳 仆亠仗亠于仆仂亶 亰舒亟舒亳) 亳仍亳仄 仂仆仂亳亠仍仆 仂亳仄仂 于亠 仂于舒仂于 于 舒亠亠 仆舒 亠亟亳仆亳 仂弍亠仄舒: 仗亳仄舒仍仆亶 亢舒亟仆亶 舒仍亞仂亳仄 亟仍 仆亠仗亠于仆仂亶 亰舒亟舒亳 亰舒从仍ﾑ舒亠 于 仍亠亟ﾑ亠仄: 仆舒舒仍舒 于 ﾐ歳経夷 从仍舒亟于舒亠 仗仂 仄舒从亳仄仄 仂于舒 舒仄仂亶 亟仂仂亞仂亶 仂仆仂亳亠仍仆仂亶 仂亳仄仂, ∃却仍亳 仂于舒 亰舒从仂仆亳仍, 舒 ﾐ歳経夷 仆亠 亰舒仗仂仍仆亠仆, 仂 从仍舒亟于舒亠 仍亠亟ﾑ亳亶 仗仂 仂仆仂亳亠仍仆仂亶 仂亳仄仂亳 仂于舒, 亰舒亠仄 仍亠亟ﾑ亳亶, 亳 舒从 亟舒仍亠亠, 仗仂从舒 仆亠 仆舒弍舒仆 于亠 b . ii ac
舒亟舒舒 从仂仄仄亳于仂礀亠舒 舒亟舒 从仂仄仄亳于仂礀舒 仄仂亢仆仂 仗亠亟舒于亳 于 于亳亟亠 仆舒仂亢亟亠仆亳 仄舒舒 仆舒 亞舒亠. 亠亳仆 亞舒舒 亞仂仂亟舒. 亠弍舒 - 仗亳 仂仂弍亠仆亳 仄亠亢亟 亳仄亳 亞仂仂亟舒仄亳. 舒亢亟仂仄 亠弍 仂仗仂舒于仍亠仆 于亠. 舒亟舒舒 亰舒从仍ﾑ舒亠 于 仂从舒仆亳亳 从舒舒亶亠亞仂 仄舒舒, 于 从仂仂亶 于仂亟亳 仗仂 仂亟仆仂仄 舒亰 从舒亢亟舒 于亠亳仆舒 亞舒舒. 仍亳仆舒 仄舒舒 - 仄仄舒 于亠仂于 于仂亟亳 于 仆亠亞仂 亠弍亠.
舒亟舒舒 从仂仄仄亳于仂礀亠舒 舒 仄仂亢亠 弍 仂仗亳舒仆 亳从仍亳亠从仂亶 仗亠亠舒仆仂于从仂亶 仆仂仄亠仂于 亞仂仂亟仂于: 亞亟亠 - 仆仂仄亠 亞仂仂亟舒 仆舒仂亟亳亶 于 i 仂亶 仗仂亰亳亳亳 仗亠亠舒仆仂于从亳. 仂舒仆于仂仄 仗仂亳从舒 亠亠仆亳亶 磦仍磳 仄仆仂亢亠于仂 仗亠亠舒仆仂于仂从 n 亞仂仂亟仂于, 舒从亳, 仂 于亠 舒亰仆亠 亳 舒仆仆舒 亰舒亟舒舒 仗亳仆舒亟仍亠亢亳 从 从仍舒 NP-亟仆 亰舒亟舒. ),,,( 121 nn jjjjJ ij njjj ,, 21 11 njj
亠舒亳仂仆仆亠 舒仍亞仂亳仄 仗仂仂亠仆亳 舒仗亳舒仆亳亶 仍亞仂亳仄 仍舒亶仆仂亞仂 仗仂亳从舒 仄亳舒亳 仂亢亳亞舒 舒于亳仆亠 舒仍亞仂亳仄 亠仆亠亳亠从亳亠 亳 于仂仍ﾑ亳仂仆仆亠 舒仍亞仂亳仄 f(HP) HPHP1 HP2 HP3
仍亞仂亳仄 亳仄亳舒亳亳 仂亢亳亞舒 仍亞仂亳仄 亳仄亳舒亳亳 仂亢亳亞舒 仆亠从仂仂仂亶 于亠仂仆仂 亟仂仗从舒ﾑ 仗亠亠仂亟 于 仂仂礌亳亠 弍仂仍亠亠 于仂从亳仄 亰仆舒亠仆亳亠仄 亠仍亠于仂亶 仆从亳亳: 亞亟亠 T - 仆亠从仂仂舒 亠仄仗亠舒舒, - 亳亰仄亠仆亠仆亳亠 亠仍亠于仂亶 仆从亳亳. 仂亟亠 舒弍仂 舒仍亞仂亳仄舒 亠仄仗亠舒舒 仗仂亠仗亠仆仆仂 仆亳亢舒亠. 常 ｏ 緒 0),exp( 0,1 )( 1 F T F F XXP kk F
亠仆亠亳亠从亳亶 舒仍亞仂亳仄 丱仂仍仍舒仆亟舒 (SGA) Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.
亠仆亠亳亠从亳亶 舒仍亞仂亳仄 丱仂仍仍舒仆亟舒 (SGA) 仆仂于舒仆 仆舒 亳仗仂仍亰仂于舒仆亳亳 仄亠舒仆亳亰仄仂于 亠亠于亠仆仆仂亶 于仂仍ﾑ亳亳: 1. 亰仄亠仆亳于仂 仂仗亠舒亳 仄舒亳亳 2. 舒仍亠亟于亠仆仆仂 仂仗亠舒亳 从亠亳于舒仆亳 3. 亠于亠仆仆亶 仂弍仂 仂仗亠舒亳 亠仍亠从亳亳
仆仂于仆亠 仗仂仆亳 仂仗仍亳 - 仂 仄仆仂亢亠于仂 弍亳仂于 仂从. 舒亢亟舒 仂从舒 - 仂亟仆仂 亳亰 于仂亰仄仂亢仆 亠亠仆亳亶 亰舒亟舒亳. 仂 仂从亠 仄仂亢亠 弍 于亳仍亠仆舒 仆从亳 于亢亳于舒亠仄仂亳, 从仂仂舒 舒舒从亠亳亰亠 从舒亠于仂 亠亠仆亳. 仆仂于仆亠 仂仗亠舒亳亳 舒仍亞仂亳仄舒: 亠仍亠从亳, 从亠亳于舒仆亳亠 亳 仄舒亳 于仗仂仍仆ﾑ 仆舒亟 仍亠仄亠仆舒仄亳 仗仂仗仍亳亳.
弌亠仄舒 1. 弌亞亠仆亠亳仂于舒 仍舒亶仆仄 仂弍舒亰仂仄 仆舒舒仍仆 仗仂仗仍亳. 2. 亳仍亳 仆从亳 于亢亳于舒亠仄仂亳 亟仍 从舒亢亟仂亶 仂从亳 仗仂仗仍亳亳. 3. 仗仂仍仆亳 仂仗亠舒亳 亠仍亠从亳亳. 4. 仗仂仍仆亳 仂仗亠舒亳 从亠亳于舒仆亳: 弍舒 仗舒 亟仍 从亠亳于舒仆亳. 仍 从舒亢亟仂亶 于弍舒仆仆仂亶 仗舒 于仗仂仍仆亳 从亠亳于舒仆亳亠, 仗仂仍亳 亟于 仗仂仂仄从仂于 亳 仗仂亳亰于亠亳 于 仗仂仗仍亳亳 亰舒仄亠仆 仂亟亳亠仍亠亶 仆舒 亳 仗仂仂仄从仂于. 5. 仗仂仍仆亳 仂仗亠舒亳 仄舒亳亳. 6. 仍亳 从亳亠亳亶 仂舒仆仂于舒 仆亠 亟仂亳亞仆, 仗亠亠亶亳 从 仗.2, 亳仆舒亠 亰舒于亠亳 舒弍仂.
仗亠舒亳 亠仍亠从亳亳 弌亠仄舒 仗仂仗仂亳仂仆舒仍仆仂亶 亠仍亠从亳亳: 弌亠仄舒 仍亠从亳:
仗亠舒亳 从亠亳于舒仆亳
仗亠舒亳 仄舒亳亳
亳亠亳亶 仂舒仆仂于舒 仂亠 仗仂亟仂仍亢舒亠 亳亠舒亳仂仆仆仂 舒亳舒仆 从亳亠亳 仂舒仆仂于舒: 仗仂仍仆亠仆亳亠 亰舒亟舒仆仆仂亞仂 亳仍舒 亳亠舒亳亶 仗仂仍仆亠仆亳亠 亰舒亟舒仆仆仂亞仂 亳仍舒 亳亠舒亳亶 弍亠亰 仍亠仆亳 仆从亳亳 于亢亳于舒亠仄仂亳 仂亳亢亠仆亳亠 亰舒亟舒仆仆仂亞仂 亰仆舒亠仆亳 仆从亳亳 于亢亳于舒亠仄仂亳
舒于亳仆亠 舒仍亞仂亳仄
舒于亳仆亠 舒仍亞仂亳仄 (弍亳仂仍仂亞亳亠从舒 仄仂亟亠仍) 1. 亰仆舒舒仍仆仂 于亠仂仆仂亳 于弍仂舒 仄舒仂于 舒于仆 2. 舒于亳, 于弍舒于亳亠 从舒舒亶亳亶 仄舒, 于仂亰于舒舒ﾑ 弍亠亠, 从仂仍亳亠于仂 亠仂仄仂仆舒 仆舒 从仂仂从亳 仄舒舒 弍仂仍亠 3. 亠仂仆仂 于弍仂舒 从舒舒亶亠亞仂 仄舒舒 仗仂于舒亠
舒于亳仆亠 舒仍亞仂亳仄 ( 亟仍 亠亠仆亳 亰舒亟舒亳 从仂仄仄亳于仂礀亠舒) 弍舒 亠仄舒 亳亠舒亳亳: 束弌仂亰亟舒仆亳亠損 仄舒于亠于 仂仂亠仆亳亠 仄舒仂于 仄舒于礆亳 弍仆仂于仍亠仆亳亠 亠仂仄仂仆仆仂亞仂 仍亠亟舒 仆舒 仆舒亶亟亠仆仆 仄舒舒
舒于亳仆亠 舒仍亞仂亳仄 (仗仂仂亠仆亳亠 仄舒舒) - 从仂仍亳亠于仂 亠仂仄仂仆舒 仆舒 亠弍亠 (i,j), ij(t) - 亰仆舒亠仆亳亠 仍仂从舒仍仆仂亶 亠仍亠于仂亶 仆从亳亳 仆舒 亠弍亠 (i,j), Lk 仄仆仂亢亠于仂 于亠亳仆, 于从仍ﾑ亠仆仆 于 舒弍-仗亳仂从 仄舒于 k, a 0 亳 b 0 - 仗舒舒仄亠 舒仍亞仂亳仄舒, 仂仗亠亟亠仍ﾑ亳亠 于舒亢仆仂 亠仂仄仂仆仆仂亞仂 仍亠亟舒 亳 仍仂从舒仍仆仂亶 亠仍亠于仂亶 仆从亳亳. )(tij
舒于亳仆亠 舒仍亞仂亳仄 (仗仂仂亠仆亳亠 仄舒舒) k k Jl ilil ijij kij Lj Lj tt tt tP k ,0 , , ii j
舒于亳仆亠 舒仍亞仂亳仄 (仂弍仆仂于仍亠仆亳亠 亠仂仄仂仆仂于) Tk(t) 仄舒, 仗仂仂亠仆仆亶 k-仄 仄舒于亠仄, F(Tk(t)) 亠仍亠于舒 仆从亳, 仂仗亠亟亠仍ﾑ舒 从舒亠于仂 仗亳, m 从仂仍亳亠于仂 仄舒于亠于, p [0,1] 从仂亳亳亠仆 亳仗舒亠仆亳 亠仂仄仂仆仂于.
舒于亳仆亠 舒仍亞仂亳仄 (仂弍仆仂于仍亠仆亳亠 亠仂仄仂仆仂于) ii j 緒 m k kijijij ttpt 1 ,11 器器 緒 tTji tTjitTF t k kk kij ,,0 ,, ,
舒于亳仆亠 舒仍亞仂亳仄 (亳仗仂仍亰仂于舒仆亳亠 亟仍 仗仂仂亠仆亳 舒仗亳舒仆亳亶) 仂仂亠仆亳亠 仄舒仂于 仂仂亠仆亳亠 舒仗亳舒仆亳亶 仗仂 仄舒舒仄 弍仆仂于仍亠仆亳亠 亠仂仄仂仆仆仂亞仂 仍亠亟舒 亳仍亠仆亳亠 亠仍亠于 仆从亳亳 仂舒仆仂于? 仆亠 亟舒
仂仆从亳于仆亠 舒仍亞仂亳仄 仗仂仂亠仆亳 舒仗亳舒仆亳亶 舒亟仆亠 舒仍亞仂亳仄 亠仂亟 于亠于亠亶 亳 亞舒仆亳 仍亞仂亳仄 仂亠舒ﾑ亳亠 亢舒亟仆亠 舒亠亞亳亳 亳 舒亠亞亳亳 仂亞舒仆亳亠仆仆仂亞仂 仗亠亠弍仂舒 523 76 2 4 t 1 2 3 4 t 1 2 3 5 4 t 1 6 7
舒亟舒舒 仗仂仂亠仆亳 舒仗亳舒仆亳 于仗仂仍仆亠仆亳 舒弍仂 于 仂亟仆仂仗亳弍仂仆仂仄 仂亶于亠 丿亳仆舒 仄仂亢亠 舒仄舒亳于舒 从舒从 仂亟仆仂仗亳弍仂仆仂亠 仂亶于仂, 仂弍仍亢亳于舒ﾑ亠亠 亳仂亟仆仂 亰舒亟舒仆仆亶 仆舒弍仂 舒弍仂 弍亠亰 仗亠于舒仆亳亶. 舒仗亳舒仆亳亠 于仗仂仍仆亠仆亳 舒弍仂, 仗亠亟舒于仍磳 仂弍仂亶 仗仂磲仂亠仆仆仂亠 仄仆仂亢亠于仂 - 亳仂亟仆仂 亰舒亟舒仆仆亶 仆舒弍仂 舒弍仂 JjsH HN kj ,1 * )},,{( jjj fstJ
舒亟舒舒 仗仂仂亠仆亳 舒仗亳舒仆亳 于仗仂仍仆亠仆亳 舒弍仂 于 仂亟仆仂仗亳弍仂仆仂仄 仂亶于亠 仆仂亢亠于仂 从仂亠从仆 舒仗亳舒仆亳亶 仂仗亠亟亠仍亳仄 仆舒弍仂仂仄 仂亞舒仆亳亠仆亳亶: * ' H ))()(())()((),),((: )(: )()()(: 3 2 1 常ｏ鰹種刻 緒 ｏ鰹 ljljljlj jjj jjjj ffsffsssljHljg tsfHjg ffssHjg
舒亟仆亠 舒仍亞仂亳仄 (仗仂仂亠仆亳亠 舒仗亳舒仆亳 于仗仂仍仆亠仆亳 舒弍仂 于 仂亟仆仂仗亳弍仂仆仂仄 仂亶于亠) 仍 舒仆仂亶 亰舒亟舒亳: 亳亰于亠亠仆 仂仗亳仄舒仍仆亶 亢舒亟仆亶 舒仍亞仂亳仄 仍仂亢仆仂亳 O(nlog n). jjj HH sftj H 緒 : max*'
舒亟仆亠 舒仍亞仂亳仄 (GrA - 舒仍亞仂亳仄 仗仂仂亠仆亳 舒仗亳舒仆亳 亟仍 仂亟仆仂仗亳弍仂仆仂亞仂 仂亶于舒) 1. 丕仗仂磲仂亳于舒亠仄 舒弍仂 仗仂 于仂亰舒舒仆亳 fj. 舒磦从亳 仂亟亳仆舒从仂于仄 亰仆舒亠仆亳亠仄 fj 舒仗仂仍舒亞舒亠仄 于 仗仂亳亰于仂仍仆仂仄 仗仂磲从亠. 弌仍仂亢仆仂 - O(nlog n). 2. 舒亰仄亠舒亠仄 于 舒仗亳舒仆亳亠 舒弍仂 j=1. 3. 亠仄 仗亠于 舒弍仂 亟仍 从仂仂仂亶 si fj , 舒亰仄亠舒亠仄 亠亠 于 舒仗亳舒仆亳亠 亳 j=i. 4. 丿舒亞亳 2, 3 仗仂于仂磳仄 仗仂从舒 仗亳仂从 仆亠 亳亠仗舒仆. 仂仍亳亠于仂 仗仂于仂仂于 - O(n).
仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 s2 f2 f3s3
仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 s2 f2 f3s3
仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 s2 f2 f3s3 弌仗亳仂从 仆亠 舒亰仄亠亠仆仆 舒弍仂
仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 f3s3
仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 f3s3
仍亞仂亳仄 仂亠舒ﾑ亳亠 亢舒亟仆亠 舒亠亞亳亳 亳 舒亠亞亳亳 仂亞舒仆亳亠仆仆仂亞仂 仗亠亠弍仂舒 弍仂 仂亠亠亟仆仂亶 (k1) 仂仂亠仆亳亠 仄仆. 亟仂仗亳仄 亠于亠仂于 () 亟仍 舒亰仄亠亠仆亳 =0 舒亰仄亠亳 弍仂 仄亠舒 舒亰仄亠亠仆亳 (k2) 亰仂于 仗仂亠亟 仂亞舒仆亳亠仆仆仂亞仂 仗亠亠弍仂舒 仆亠 亟舒
亞舒仆亳亠仆仆亶 仗亠亠弍仂 4 3 5 2 3 5 2 4 4 1 1 R1 R2 R3 5 n=2 (R1,R2) R1: 5, 5 R2: 3, 3, 4 R3: 4, 4, 1 n=3 (R1,R2, R3) R1: 5, 5 R2: 3, 3, 4 R3: 4, 1, 5
舒仗舒于仍亠仆亳 舒弍仂 舒亰舒弍仂从舒 舒仍亞仂亳仄仂于 亠亠仆亳 从仂仆从亠仆 亰舒亟舒 从仆仂亞仂 亳仆亠亰舒 亳 仗仍舒仆亳仂于舒仆亳 于亳仍亠仆亳亶: 亳仆仂仄舒亳仂仆仆仂-仗舒于仍ﾑ亳亠 亳亠仄 亠舒仍仆仂亞仂 于亠仄亠仆亳, 亠仆 仂弍舒弍仂从亳 亟舒仆仆. 舒亰舒弍仂从舒 仆仂于 仗仂亟仂亟仂于 从 仗仂仂亠仆亳 舒仍亞仂亳仄仂于 亳 仄仂亟亳亳从舒亳亶 亳亰于亠仆 从仍舒仂于 舒仍亞仂亳仄仂于. 亳仄亠: 亞亠仆亠亳亠从亳亶 舒仍亞仂亳仄 舒仄仂仂弍亠仆亳亠仄, 仄亠仂亟 仗仂仂亠仆亳 舒仍亞仂亳仄仂于 仂亠舒ﾑ亳 亢舒亟仆亠 舒亠亞亳亳 亳 仂亞舒仆亳亠仆仆亶 仗亠亠弍仂. 舒亳仆仆仂亠 仂弍亠仆亳亠: 舒仍亞仂亳仄 仗仂仂亠仆亳 亳 仂弍亠仆亳 仆亠亶仂亠亠亶 亟仍 于仂亠仆仆 亳亠仄; 舒仍亞仂亳仄 仗仂仂亠仆亳 亳 仂弍亠仆亳 仆亠亶仂亠亠亶 亟仍 弍仂仍亳 弍舒亰 亟舒仆仆.
仂亠仆从仂 舒仍亠亳亶 仍亠从亠亠于亳 kost@cs.msu.su

More Related Content

2020 03-31-lection

  • 1. 弌从仆亶 亳仆亠亰 亳 仗仍舒仆亳仂于舒仆亳亠 于亳仍亠仆亳亶 仂亠仆从仂 舒仍亠亳亶 仍亠从亠亠于亳 kost@cs.msu.su
  • 2. 亳从仍舒亟仆亠 仂弍仍舒亳 仆仂仄舒亳仂仆仆仂-仗舒于仍ﾑ亳亠 亳亠仄 亠舒仍仆仂亞仂 于亠仄亠仆亳 (于仂亠仆仆亠 亳亠仄): 舒于亳舒亳仂仆仆亠, 从仂舒弍亠仍仆亠, 舒于仂仄仂弍亳仍仆亠, 仂弍仂, 舒于仂仄舒亳亰亳仂于舒仆仆亠 亳亠仄 仗舒于仍亠仆亳 亠仆仂仍仂亞亳亠从亳仄亳 仗仂亠舒仄亳. 丶亠仆 仂弍舒弍仂从亳 亟舒仆仆 于 仂仄 亳仍亠 亳 舒仗亠亟亠仍亠仆仆亠 丶. 亠亟仂舒于仍亠仆亳亠 于亳仍亳亠仍仆 亠仂于 仗仂仍亰仂于舒亠仍礆 (仆舒仗亳仄亠, 束仂亠仍亠从仂仄損). 仗仂仍亰仂于舒仆亳亠 丶 亟仍 仂弍亠仗亠亠仆亳 仂弍于亠仆仆 仗仂亠弍仆仂亠亶 于 于亳仍亠仆亳 (仆舒仗亳仄亠, 束弌弍亠弍舒仆从損).
  • 3. 舒亟舒亳 从仂仄弍亳仆舒仂仆仂亶 仂仗亳仄亳亰舒亳亳 仆仂亢亠于仂 亠亠仆亳亶 于从仍ﾑ舒亠 于亠于仂亰仄仂亢仆亠: 舒亰仄亠亠仆亳 亳仂亟仆仂 亰舒亟舒仆仆 仂弍亠从仂于, 仗仂磲仂亳于舒仆亳 亳仂亟仆仂 亰舒亟舒仆仆 仂弍亠从仂于, 舒亰弍亳亠仆亳 仆舒 亞仗仗 亳仂亟仆仂 亰舒亟舒仆仆 仂弍亠从仂于. 仂仄弍亳仆舒仂仆舒 仂仗亳仄亳亰舒亳 于从仍ﾑ舒亠 于 亠弍 亰舒亟舒亳 仂仗亳仄亳亰舒亳亳, 于 从仂仂 仄仆仂亢亠于仂 亟仂仗亳仄 亠亠仆亳亶 亟亳从亠仆仂 亳仍亳 仄仂亢亠 弍 于亠亟亠仆仂 从 亟亳从亠仆仂仄 仄仆仂亢亠于.
  • 4. 亅舒仗 亠亠仆亳 亰舒亟舒亳 弌仂亟亠亢舒亠仍仆舒 仂仄仍亳仂于从舒 亰舒亟舒亳 舒亠仄舒亳亠从舒 仂仄仍亳仂于从舒 亰舒亟舒亳 仆舒仍亳亰 于仂亶于 亰舒亟舒亳 弍仂 从仍舒舒 舒仍亞仂亳仄仂于 (亳仍亳 于弍仂 亳亰于亠仆仂亞仂 舒仍亞仂亳仄舒) 舒亰舒弍仂从舒 亳 亠舒仍亳亰舒亳 舒仍亞仂亳仄舒 仍亠亟仂于舒仆亳亠 于仂亶于 舒仍亞仂亳仄舒
  • 5. 舒亟舒舒 仂 ﾐ歳経夷歳 (仂亟亠亢舒亠仍仆舒 仂仄仍亳仂于从舒) 舒仆 ﾐ歳経夷 亰舒亟舒仆仆仂亞仂 仂弍亠仄舒 亳 仆舒弍仂 仗亠亟仄亠仂于. 舒亢亟亶 仗亠亟仄亠 舒舒从亠亳亰亠: 仂亳仄仂 亳 仂弍亠仄仂仄. 丐亠弍亠 仗舒从仂于舒 ﾐ歳経夷 舒从, 仂弍: 仄仄舒仆舒 仂亳仄仂 仗舒从仂于舒仆仆 仗亠亟仄亠仂于 弍仍舒 仄舒从亳仄舒仍仆仂亶; 仄仄舒仆亶 仂弍亠仄 仗舒从仂于舒仆仆 仗亠亟仄亠仂于 仆亠 仗亠于舒仍 仂弍亠仄 ﾐ歳経夷歳.
  • 6. 舒亟舒舒 仂 ﾐ歳経夷歳 (仄舒亠仄舒亳亠从舒 仂仄仍亳仂于从舒) 舒仆仂: b - 仂弍亠仄 ﾐ歳経夷歳, {(ai , ci), I = 1,,n} n 亳仍仂 仗亠亟仄亠仂于, ai 亳 ci. - 仂弍亠仄 亳 仂亳仄仂 仗亠亟仄亠舒 i. 亠亠仆亳亠 弍亟亠仄 仂仗亳于舒 于亠从仂仂仄: X = (x1,, x2, .,xn) 仍亳 仗亠亟仄亠 仗舒从仂于舒仆 于 ﾐ歳経夷, 仂 xi=1, 亠仍亳 仆亠 xi=0.
  • 7. 舒亟舒舒 仂 ﾐ歳経夷歳 (仄舒亠仄舒亳亠从舒 仂仄仍亳仂于从舒) 丶亠仍亠于舒 仆从亳: 个仆从亳 仂亞舒仆亳亠仆亳亶: . )(max 1 ワ n i ii X xc bxa n i ii ｏワ1
  • 8. 舒亟舒舒 仂 ﾐ歳経夷歳 (舒仆舒仍亳亰 于仂亶于 亰舒亟舒亳) 仍亳 于亠 从仂亳亳亠仆 ai 亠仍亠 亳仍舒 亳 b 亠仍仂亠 亳仍仂, 仂 亰舒亟舒舒 磦仍磳 NP-亟仆仂亶. 仍亳 于亠 从仂亳亳亠仆 ai 于亠亠于亠仆仆亠, 仂 亰舒亟舒舒 仄仂亢亠 弍 亠亠仆舒 亢舒亟仆仄 舒仍亞仂亳仄仂仄 仍仂亢仆仂亳 O(nlog n).
  • 9. 舒亟舒舒 仂 ﾐ歳経夷歳 (舒仍亞仂亳仄 亠亠仆亳 仆亠仗亠于仆仂亶 亰舒亟舒亳) 亳仍亳仄 仂仆仂亳亠仍仆 仂亳仄仂 于亠 仂于舒仂于 于 舒亠亠 仆舒 亠亟亳仆亳 仂弍亠仄舒: 仗亳仄舒仍仆亶 亢舒亟仆亶 舒仍亞仂亳仄 亟仍 仆亠仗亠于仆仂亶 亰舒亟舒亳 亰舒从仍ﾑ舒亠 于 仍亠亟ﾑ亠仄: 仆舒舒仍舒 于 ﾐ歳経夷 从仍舒亟于舒亠 仗仂 仄舒从亳仄仄 仂于舒 舒仄仂亶 亟仂仂亞仂亶 仂仆仂亳亠仍仆仂亶 仂亳仄仂, ∃却仍亳 仂于舒 亰舒从仂仆亳仍, 舒 ﾐ歳経夷 仆亠 亰舒仗仂仍仆亠仆, 仂 从仍舒亟于舒亠 仍亠亟ﾑ亳亶 仗仂 仂仆仂亳亠仍仆仂亶 仂亳仄仂亳 仂于舒, 亰舒亠仄 仍亠亟ﾑ亳亶, 亳 舒从 亟舒仍亠亠, 仗仂从舒 仆亠 仆舒弍舒仆 于亠 b . ii ac
  • 10. 舒亟舒舒 从仂仄仄亳于仂礀亠舒 舒亟舒 从仂仄仄亳于仂礀舒 仄仂亢仆仂 仗亠亟舒于亳 于 于亳亟亠 仆舒仂亢亟亠仆亳 仄舒舒 仆舒 亞舒亠. 亠亳仆 亞舒舒 亞仂仂亟舒. 亠弍舒 - 仗亳 仂仂弍亠仆亳 仄亠亢亟 亳仄亳 亞仂仂亟舒仄亳. 舒亢亟仂仄 亠弍 仂仗仂舒于仍亠仆 于亠. 舒亟舒舒 亰舒从仍ﾑ舒亠 于 仂从舒仆亳亳 从舒舒亶亠亞仂 仄舒舒, 于 从仂仂亶 于仂亟亳 仗仂 仂亟仆仂仄 舒亰 从舒亢亟舒 于亠亳仆舒 亞舒舒. 仍亳仆舒 仄舒舒 - 仄仄舒 于亠仂于 于仂亟亳 于 仆亠亞仂 亠弍亠.
  • 11. 舒亟舒舒 从仂仄仄亳于仂礀亠舒 舒 仄仂亢亠 弍 仂仗亳舒仆 亳从仍亳亠从仂亶 仗亠亠舒仆仂于从仂亶 仆仂仄亠仂于 亞仂仂亟仂于: 亞亟亠 - 仆仂仄亠 亞仂仂亟舒 仆舒仂亟亳亶 于 i 仂亶 仗仂亰亳亳亳 仗亠亠舒仆仂于从亳. 仂舒仆于仂仄 仗仂亳从舒 亠亠仆亳亶 磦仍磳 仄仆仂亢亠于仂 仗亠亠舒仆仂于仂从 n 亞仂仂亟仂于, 舒从亳, 仂 于亠 舒亰仆亠 亳 舒仆仆舒 亰舒亟舒舒 仗亳仆舒亟仍亠亢亳 从 从仍舒 NP-亟仆 亰舒亟舒. ),,,( 121 nn jjjjJ ij njjj ,, 21 11 njj
  • 12. 亠舒亳仂仆仆亠 舒仍亞仂亳仄 仗仂仂亠仆亳 舒仗亳舒仆亳亶 仍亞仂亳仄 仍舒亶仆仂亞仂 仗仂亳从舒 仄亳舒亳 仂亢亳亞舒 舒于亳仆亠 舒仍亞仂亳仄 亠仆亠亳亠从亳亠 亳 于仂仍ﾑ亳仂仆仆亠 舒仍亞仂亳仄 f(HP) HPHP1 HP2 HP3
  • 13. 仍亞仂亳仄 亳仄亳舒亳亳 仂亢亳亞舒 仍亞仂亳仄 亳仄亳舒亳亳 仂亢亳亞舒 仆亠从仂仂仂亶 于亠仂仆仂 亟仂仗从舒ﾑ 仗亠亠仂亟 于 仂仂礌亳亠 弍仂仍亠亠 于仂从亳仄 亰仆舒亠仆亳亠仄 亠仍亠于仂亶 仆从亳亳: 亞亟亠 T - 仆亠从仂仂舒 亠仄仗亠舒舒, - 亳亰仄亠仆亠仆亳亠 亠仍亠于仂亶 仆从亳亳. 仂亟亠 舒弍仂 舒仍亞仂亳仄舒 亠仄仗亠舒舒 仗仂亠仗亠仆仆仂 仆亳亢舒亠. 常 ｏ 緒 0),exp( 0,1 )( 1 F T F F XXP kk F
  • 14. 亠仆亠亳亠从亳亶 舒仍亞仂亳仄 丱仂仍仍舒仆亟舒 (SGA) Holland J.N. Adaptation in Natural and Artificial Systems. Ann Arbor, Michigan: Univ. of Michigan Press, 1975.
  • 15. 亠仆亠亳亠从亳亶 舒仍亞仂亳仄 丱仂仍仍舒仆亟舒 (SGA) 仆仂于舒仆 仆舒 亳仗仂仍亰仂于舒仆亳亳 仄亠舒仆亳亰仄仂于 亠亠于亠仆仆仂亶 于仂仍ﾑ亳亳: 1. 亰仄亠仆亳于仂 仂仗亠舒亳 仄舒亳亳 2. 舒仍亠亟于亠仆仆仂 仂仗亠舒亳 从亠亳于舒仆亳 3. 亠于亠仆仆亶 仂弍仂 仂仗亠舒亳 亠仍亠从亳亳
  • 16. 仆仂于仆亠 仗仂仆亳 仂仗仍亳 - 仂 仄仆仂亢亠于仂 弍亳仂于 仂从. 舒亢亟舒 仂从舒 - 仂亟仆仂 亳亰 于仂亰仄仂亢仆 亠亠仆亳亶 亰舒亟舒亳. 仂 仂从亠 仄仂亢亠 弍 于亳仍亠仆舒 仆从亳 于亢亳于舒亠仄仂亳, 从仂仂舒 舒舒从亠亳亰亠 从舒亠于仂 亠亠仆亳. 仆仂于仆亠 仂仗亠舒亳亳 舒仍亞仂亳仄舒: 亠仍亠从亳, 从亠亳于舒仆亳亠 亳 仄舒亳 于仗仂仍仆ﾑ 仆舒亟 仍亠仄亠仆舒仄亳 仗仂仗仍亳亳.
  • 17. 弌亠仄舒 1. 弌亞亠仆亠亳仂于舒 仍舒亶仆仄 仂弍舒亰仂仄 仆舒舒仍仆 仗仂仗仍亳. 2. 亳仍亳 仆从亳 于亢亳于舒亠仄仂亳 亟仍 从舒亢亟仂亶 仂从亳 仗仂仗仍亳亳. 3. 仗仂仍仆亳 仂仗亠舒亳 亠仍亠从亳亳. 4. 仗仂仍仆亳 仂仗亠舒亳 从亠亳于舒仆亳: 弍舒 仗舒 亟仍 从亠亳于舒仆亳. 仍 从舒亢亟仂亶 于弍舒仆仆仂亶 仗舒 于仗仂仍仆亳 从亠亳于舒仆亳亠, 仗仂仍亳 亟于 仗仂仂仄从仂于 亳 仗仂亳亰于亠亳 于 仗仂仗仍亳亳 亰舒仄亠仆 仂亟亳亠仍亠亶 仆舒 亳 仗仂仂仄从仂于. 5. 仗仂仍仆亳 仂仗亠舒亳 仄舒亳亳. 6. 仍亳 从亳亠亳亶 仂舒仆仂于舒 仆亠 亟仂亳亞仆, 仗亠亠亶亳 从 仗.2, 亳仆舒亠 亰舒于亠亳 舒弍仂.
  • 18. 仗亠舒亳 亠仍亠从亳亳 弌亠仄舒 仗仂仗仂亳仂仆舒仍仆仂亶 亠仍亠从亳亳: 弌亠仄舒 仍亠从亳:
  • 21. 亳亠亳亶 仂舒仆仂于舒 仂亠 仗仂亟仂仍亢舒亠 亳亠舒亳仂仆仆仂 舒亳舒仆 从亳亠亳 仂舒仆仂于舒: 仗仂仍仆亠仆亳亠 亰舒亟舒仆仆仂亞仂 亳仍舒 亳亠舒亳亶 仗仂仍仆亠仆亳亠 亰舒亟舒仆仆仂亞仂 亳仍舒 亳亠舒亳亶 弍亠亰 仍亠仆亳 仆从亳亳 于亢亳于舒亠仄仂亳 仂亳亢亠仆亳亠 亰舒亟舒仆仆仂亞仂 亰仆舒亠仆亳 仆从亳亳 于亢亳于舒亠仄仂亳
  • 23. 舒于亳仆亠 舒仍亞仂亳仄 (弍亳仂仍仂亞亳亠从舒 仄仂亟亠仍) 1. 亰仆舒舒仍仆仂 于亠仂仆仂亳 于弍仂舒 仄舒仂于 舒于仆 2. 舒于亳, 于弍舒于亳亠 从舒舒亶亳亶 仄舒, 于仂亰于舒舒ﾑ 弍亠亠, 从仂仍亳亠于仂 亠仂仄仂仆舒 仆舒 从仂仂从亳 仄舒舒 弍仂仍亠 3. 亠仂仆仂 于弍仂舒 从舒舒亶亠亞仂 仄舒舒 仗仂于舒亠
  • 24. 舒于亳仆亠 舒仍亞仂亳仄 ( 亟仍 亠亠仆亳 亰舒亟舒亳 从仂仄仄亳于仂礀亠舒) 弍舒 亠仄舒 亳亠舒亳亳: 束弌仂亰亟舒仆亳亠損 仄舒于亠于 仂仂亠仆亳亠 仄舒仂于 仄舒于礆亳 弍仆仂于仍亠仆亳亠 亠仂仄仂仆仆仂亞仂 仍亠亟舒 仆舒 仆舒亶亟亠仆仆 仄舒舒
  • 25. 舒于亳仆亠 舒仍亞仂亳仄 (仗仂仂亠仆亳亠 仄舒舒) - 从仂仍亳亠于仂 亠仂仄仂仆舒 仆舒 亠弍亠 (i,j), ij(t) - 亰仆舒亠仆亳亠 仍仂从舒仍仆仂亶 亠仍亠于仂亶 仆从亳亳 仆舒 亠弍亠 (i,j), Lk 仄仆仂亢亠于仂 于亠亳仆, 于从仍ﾑ亠仆仆 于 舒弍-仗亳仂从 仄舒于 k, a 0 亳 b 0 - 仗舒舒仄亠 舒仍亞仂亳仄舒, 仂仗亠亟亠仍ﾑ亳亠 于舒亢仆仂 亠仂仄仂仆仆仂亞仂 仍亠亟舒 亳 仍仂从舒仍仆仂亶 亠仍亠于仂亶 仆从亳亳. )(tij
  • 26. 舒于亳仆亠 舒仍亞仂亳仄 (仗仂仂亠仆亳亠 仄舒舒) k k Jl ilil ijij kij Lj Lj tt tt tP k ,0 , , ii j
  • 27. 舒于亳仆亠 舒仍亞仂亳仄 (仂弍仆仂于仍亠仆亳亠 亠仂仄仂仆仂于) Tk(t) 仄舒, 仗仂仂亠仆仆亶 k-仄 仄舒于亠仄, F(Tk(t)) 亠仍亠于舒 仆从亳, 仂仗亠亟亠仍ﾑ舒 从舒亠于仂 仗亳, m 从仂仍亳亠于仂 仄舒于亠于, p [0,1] 从仂亳亳亠仆 亳仗舒亠仆亳 亠仂仄仂仆仂于.
  • 28. 舒于亳仆亠 舒仍亞仂亳仄 (仂弍仆仂于仍亠仆亳亠 亠仂仄仂仆仂于) ii j 緒 m k kijijij ttpt 1 ,11 器器 緒 tTji tTjitTF t k kk kij ,,0 ,, ,
  • 29. 舒于亳仆亠 舒仍亞仂亳仄 (亳仗仂仍亰仂于舒仆亳亠 亟仍 仗仂仂亠仆亳 舒仗亳舒仆亳亶) 仂仂亠仆亳亠 仄舒仂于 仂仂亠仆亳亠 舒仗亳舒仆亳亶 仗仂 仄舒舒仄 弍仆仂于仍亠仆亳亠 亠仂仄仂仆仆仂亞仂 仍亠亟舒 亳仍亠仆亳亠 亠仍亠于 仆从亳亳 仂舒仆仂于? 仆亠 亟舒
  • 30. 仂仆从亳于仆亠 舒仍亞仂亳仄 仗仂仂亠仆亳 舒仗亳舒仆亳亶 舒亟仆亠 舒仍亞仂亳仄 亠仂亟 于亠于亠亶 亳 亞舒仆亳 仍亞仂亳仄 仂亠舒ﾑ亳亠 亢舒亟仆亠 舒亠亞亳亳 亳 舒亠亞亳亳 仂亞舒仆亳亠仆仆仂亞仂 仗亠亠弍仂舒 523 76 2 4 t 1 2 3 4 t 1 2 3 5 4 t 1 6 7
  • 31. 舒亟舒舒 仗仂仂亠仆亳 舒仗亳舒仆亳 于仗仂仍仆亠仆亳 舒弍仂 于 仂亟仆仂仗亳弍仂仆仂仄 仂亶于亠 丿亳仆舒 仄仂亢亠 舒仄舒亳于舒 从舒从 仂亟仆仂仗亳弍仂仆仂亠 仂亶于仂, 仂弍仍亢亳于舒ﾑ亠亠 亳仂亟仆仂 亰舒亟舒仆仆亶 仆舒弍仂 舒弍仂 弍亠亰 仗亠于舒仆亳亶. 舒仗亳舒仆亳亠 于仗仂仍仆亠仆亳 舒弍仂, 仗亠亟舒于仍磳 仂弍仂亶 仗仂磲仂亠仆仆仂亠 仄仆仂亢亠于仂 - 亳仂亟仆仂 亰舒亟舒仆仆亶 仆舒弍仂 舒弍仂 JjsH HN kj ,1 * )},,{( jjj fstJ
  • 32. 舒亟舒舒 仗仂仂亠仆亳 舒仗亳舒仆亳 于仗仂仍仆亠仆亳 舒弍仂 于 仂亟仆仂仗亳弍仂仆仂仄 仂亶于亠 仆仂亢亠于仂 从仂亠从仆 舒仗亳舒仆亳亶 仂仗亠亟亠仍亳仄 仆舒弍仂仂仄 仂亞舒仆亳亠仆亳亶: * ' H ))()(())()((),),((: )(: )()()(: 3 2 1 常ｏ鰹種刻 緒 ｏ鰹 ljljljlj jjj jjjj ffsffsssljHljg tsfHjg ffssHjg
  • 33. 舒亟仆亠 舒仍亞仂亳仄 (仗仂仂亠仆亳亠 舒仗亳舒仆亳 于仗仂仍仆亠仆亳 舒弍仂 于 仂亟仆仂仗亳弍仂仆仂仄 仂亶于亠) 仍 舒仆仂亶 亰舒亟舒亳: 亳亰于亠亠仆 仂仗亳仄舒仍仆亶 亢舒亟仆亶 舒仍亞仂亳仄 仍仂亢仆仂亳 O(nlog n). jjj HH sftj H 緒 : max*'
  • 34. 舒亟仆亠 舒仍亞仂亳仄 (GrA - 舒仍亞仂亳仄 仗仂仂亠仆亳 舒仗亳舒仆亳 亟仍 仂亟仆仂仗亳弍仂仆仂亞仂 仂亶于舒) 1. 丕仗仂磲仂亳于舒亠仄 舒弍仂 仗仂 于仂亰舒舒仆亳 fj. 舒磦从亳 仂亟亳仆舒从仂于仄 亰仆舒亠仆亳亠仄 fj 舒仗仂仍舒亞舒亠仄 于 仗仂亳亰于仂仍仆仂仄 仗仂磲从亠. 弌仍仂亢仆仂 - O(nlog n). 2. 舒亰仄亠舒亠仄 于 舒仗亳舒仆亳亠 舒弍仂 j=1. 3. 亠仄 仗亠于 舒弍仂 亟仍 从仂仂仂亶 si fj , 舒亰仄亠舒亠仄 亠亠 于 舒仗亳舒仆亳亠 亳 j=i. 4. 丿舒亞亳 2, 3 仗仂于仂磳仄 仗仂从舒 仗亳仂从 仆亠 亳亠仗舒仆. 仂仍亳亠于仂 仗仂于仂仂于 - O(n).
  • 35. 仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 s2 f2 f3s3
  • 36. 仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 s2 f2 f3s3
  • 37. 仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 s2 f2 f3s3 弌仗亳仂从 仆亠 舒亰仄亠亠仆仆 舒弍仂
  • 38. 仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 f3s3
  • 39. 仍仍ﾑ舒亳 舒弍仂 舒仍亞仂亳仄舒 0 1 2 3 7654 8 9 10 11 12 s1 f1 f3s3
  • 40. 仍亞仂亳仄 仂亠舒ﾑ亳亠 亢舒亟仆亠 舒亠亞亳亳 亳 舒亠亞亳亳 仂亞舒仆亳亠仆仆仂亞仂 仗亠亠弍仂舒 弍仂 仂亠亠亟仆仂亶 (k1) 仂仂亠仆亳亠 仄仆. 亟仂仗亳仄 亠于亠仂于 () 亟仍 舒亰仄亠亠仆亳 =0 舒亰仄亠亳 弍仂 仄亠舒 舒亰仄亠亠仆亳 (k2) 亰仂于 仗仂亠亟 仂亞舒仆亳亠仆仆仂亞仂 仗亠亠弍仂舒 仆亠 亟舒
  • 41. 亞舒仆亳亠仆仆亶 仗亠亠弍仂 4 3 5 2 3 5 2 4 4 1 1 R1 R2 R3 5 n=2 (R1,R2) R1: 5, 5 R2: 3, 3, 4 R3: 4, 4, 1 n=3 (R1,R2, R3) R1: 5, 5 R2: 3, 3, 4 R3: 4, 1, 5
  • 42. 舒仗舒于仍亠仆亳 舒弍仂 舒亰舒弍仂从舒 舒仍亞仂亳仄仂于 亠亠仆亳 从仂仆从亠仆 亰舒亟舒 从仆仂亞仂 亳仆亠亰舒 亳 仗仍舒仆亳仂于舒仆亳 于亳仍亠仆亳亶: 亳仆仂仄舒亳仂仆仆仂-仗舒于仍ﾑ亳亠 亳亠仄 亠舒仍仆仂亞仂 于亠仄亠仆亳, 亠仆 仂弍舒弍仂从亳 亟舒仆仆. 舒亰舒弍仂从舒 仆仂于 仗仂亟仂亟仂于 从 仗仂仂亠仆亳 舒仍亞仂亳仄仂于 亳 仄仂亟亳亳从舒亳亶 亳亰于亠仆 从仍舒仂于 舒仍亞仂亳仄仂于. 亳仄亠: 亞亠仆亠亳亠从亳亶 舒仍亞仂亳仄 舒仄仂仂弍亠仆亳亠仄, 仄亠仂亟 仗仂仂亠仆亳 舒仍亞仂亳仄仂于 仂亠舒ﾑ亳 亢舒亟仆亠 舒亠亞亳亳 亳 仂亞舒仆亳亠仆仆亶 仗亠亠弍仂. 舒亳仆仆仂亠 仂弍亠仆亳亠: 舒仍亞仂亳仄 仗仂仂亠仆亳 亳 仂弍亠仆亳 仆亠亶仂亠亠亶 亟仍 于仂亠仆仆 亳亠仄; 舒仍亞仂亳仄 仗仂仂亠仆亳 亳 仂弍亠仆亳 仆亠亶仂亠亠亶 亟仍 弍仂仍亳 弍舒亰 亟舒仆仆.