Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (1185330), страница 69
Текст из файла (страница 69)
èÛÒÚ¸p Ax – ÔÎÓ˘‡‰¸ ÏÌÓÊÂÒÚ‚‡ {x + v ∈ VAx : x − v ∈ VAx }.ê‡ÒÒÚÓflÌËÂÏ ÓÚ‡ÊÂÌËfl ‰Ó̇–ÇÂθ͇ÏÔ‡ ÏÂÊ‰Û ÍÓ̘Ì˚ÏË Ó·˙‰ËÌÂÌËflÏË Ä Ë Ç ÍË‚˚ı ÔÎÓÒÍËı fl‚ÎflÂÚÒfl ÌÓχÎËÁÓ‚‡ÌÌÓ l1 -‡ÒÒÚÓflÌË ÏÂÊ‰Û ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘ËÏË ÙÛÌ͈ËflÏË p Ax Ë pBx , ÓÔ‰ÂÎÂÌÌÓ ͇Í∫ pA − pB dxxx2∫ max pA ⋅ pB dxx2x.É·‚‡ 21. ê‡ÒÒÚÓflÌËfl ‚ ‡Ì‡ÎËÁ ӷ‡ÁÓ‚ Ë Á‚ÛÍÓ‚307ê‡ÒÒÚÓflÌÌÓ ÔÂÓ·‡ÁÓ‚‡ÌËÂÇÓÁ¸ÏÂÏ ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó ( X = 2 , d ) Ë ‰‚Ó˘ÌÓ ˆËÙÓ‚Ó ËÁÓ·‡ÊÂÌË M ⊂ X. ê‡ÒÒÚÓflÌÌ˚Ï ÔÂÓ·‡ÁÓ‚‡ÌËÂÏ Ì‡Á˚‚‡ÂÚÒfl ÙÛÌ͈Ëfl f M : X → ≥ 0 , „‰Âf M ( x ) = infu ∈M d ( x, u) fl‚ÎflÂÚÒfl ‡ÒÒÚÓflÌËÂÏ ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ d(x, M).ëΉӂ‡ÚÂθÌÓ, ‡ÒÒÚÓflÌÌÓ ÔÂÓ·‡ÁÓ‚‡ÌË ÏÓÊÌÓ ‡ÒÒχÚË‚‡Ú¸ Í‡Í ÔÓÎÛÚÓÌÓ‚Ó ˆËÙÓ‚Ó ËÁÓ·‡ÊÂÌËÂ, ‚ ÍÓÚÓÓÏ Í‡Ê‰ÓÏÛ ÔËÍÒÂβ ÔËÒ‚‡Ë‚‡ÂÚÒfl ÏÂÚ͇(ÛÓ‚Â̸ ÔÓÎÛÚÓ̇), ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘‡fl ‡ÒÒÚÓflÌ˲ ‰Ó ·ÎËÊ‡È¯Â„Ó ÔËÍÒÂÎfl ÙÓ̇.ê‡ÒÒÚÓflÌÌ˚ ÔÂÓ·‡ÁÓ‚‡ÌËfl ‚ ÔÓˆÂÒÒ‡ı Ó·‡·ÓÚÍË ËÁÓ·‡ÊÂÌËÈ Ú‡ÍÊ ̇Á˚‚‡˛ÚÒfl ‡ÒÒÚÓflÌÌ˚ÏË ÔÓÎflÏË Ë, „·‚Ì˚Ï Ó·‡ÁÓÏ, ‡ÒÒÚÓflÌÌ˚ÏË Í‡Ú‡ÏË; Ӊ̇ÍÓÔÓÒΉÌËÈ ÚÂÏËÌ Ï˚ ÂÁ‚ËÛÂÏ ‰Îfl Ó·ÓÁ̇˜ÂÌËfl ˝ÚÓ„Ó ÔÓÌflÚËfl ÔËÏÂÌËÚÂθÌÓÍ Î˛·ÓÏÛ ÏÂÚ˘ÂÒÍÓÏÛ ÔÓÒÚ‡ÌÒÚ‚Û.
ê‡ÒÒÚÓflÌÌÓ ÔÂÓ·‡ÁÓ‚‡ÌË ÙÓÏ˚ –‡ÒÒÚÓflÌÌÓ ÔÂÓ·‡ÁÓ‚‡ÌËÂ, ‚ ÍÓÚÓÓÏ å – „‡Ìˈ‡ ËÁÓ·‡ÊÂÌËfl. ÑÎfl X = 2 „‡Ù{( x, f ( x )) : x ∈ X} ‰Îfl d(x, M) ̇Á˚‚‡ÂÚÒfl ÔÓ‚ÂıÌÓÒÚ¸˛ ÇÓÓÌÓ„Ó ‰Îfl å.ë‰ËÌ̇fl ÓÒ¸ Ë ÒÍÂÎÂÚ̇flèÛÒÚ¸ (X, d) – ÏÂÚ˘ÂÒÍÓ ÔÓÒÚ‡ÌÒÚ‚Ó Ë å – ÔÓ‰ÏÌÓÊÂÒÚ‚Ó ï. ë‰ËÌ̇fl ÓÒ¸ï – ÏÌÓÊÂÒÚ‚Ó MA( X ) = {x ∈ X :| {m ∈ M : d ( x, m) = d ( x, M )} | ≥ 2}, Ú.Â. ‚Ò ÚÓ˜ÍË ï,Ëϲ˘Ë ‚ å Ì ÏÂÌ ‰‚Ûı ˝ÎÂÏÂÌÚÓ‚ ̇ËÎÛ˜¯Â„Ó ÔË·ÎËÊÂÌËfl. MA(X) ÒÓÒÚÓËÚËÁ ‚ÒÂı ÚÓ˜ÂÍ „‡Ìˈ ӷ·ÒÚÂÈ ÇÓÓÌÓ„Ó ‰Îfl ÚÓ˜ÂÍ ËÁ å. ëÍÂÎÂÚ Skel(X) ÏÌÓÊÂÒÚ‚‡ ï ÂÒÚ¸ ÏÌÓÊÂÒÚ‚Ó ˆÂÌÚÓ‚ ‚ÒÂı ¯‡Ó‚ (ÓÚÌÓÒËÚÂÎÌÓ ‡ÒÒÚÓflÌËfl d), ÍÓÚÓ˚‚ÔËÒ‡Ì˚ ‚ ï Ë fl‚Îfl˛ÚÒfl χÍÒËχθÌ˚ÏË, Ú.Â.
Ì ÔË̇‰ÎÂÊ‡Ú ÌË͇ÍÓÏÛ ‰Û„ÓÏÛÚ‡ÍÓÏÛ ¯‡Û. ÉÂÓÏÂÚ˘ÂÒÍÓ ÏÂÒÚÓ ‡ÁÂÁÓ‚ ÏÌÓÊÂÒÚ‚‡ ï – ˝ÚÓ Á‡Ï˚͇ÌËÂMA( X ) Ò‰ËÌÌÓÈ ÓÒË. Ç Ó·˘ÂÏ ÒÎÛ˜‡Â MA( X ) ⊂ Skel( X ) ⊂ MA( X ). èÂÓ·‡ÁÓ‚‡ÌËflÒ‰ËÌÌÓÈ ÓÒË, ÒÍÂÎÂÚ‡ Ë „ÂÓÏÂÚ˘ÂÒÍÓ„Ó ÏÂÒÚ‡ ‡ÁÂÁÓ‚ – ˝ÚÓ ÚӘ˜ÚÌÓ-‚Á‚¯ÂÌÌ˚ ÏÌÓÊÂÒÚ‚‡ÏË MA(X), Skel(X) Ë MA( X ) (ÒÛÊÂÌË ‡ÒÒÚÓflÌÌÓ„Ó ÔÂÓ·‡ÁÓ‚‡ÌËfl ̇ ˝ÚË ÏÌÓÊÂÒÚ‚‡) Ò d(x, M), ‡ÒÒχÚË‚‡ÂÏ˚Ï Í‡Í ‚ÂÒ ÚÓ˜ÍË x ∈ X.é·˚˜ÌÓ X ⊂ n Ë M – „‡Ìˈ‡ ï.
Ç ÒÎÛ˜‡Â ÍÓ„‰‡ å fl‚ÎflÂÚÒfl ÌÂÔÂ˚‚ÌÓÈ „‡ÌˈÂÈ, Ò‰ËÌ̇fl ÓÒ¸ ÏÓÊÂÚ Ò˜ËÚ‡Ú¸Òfl Ô‰ÂÎÓÏ ‰Ë‡„‡ÏÏ˚ ÇÓÓÌÓ„Ó ÔÓ Ï ÚÓ„ÓÍ‡Í ˜ËÒÎÓ ÔÓÓʉ‡˛˘Ëı ÚÓ˜ÂÍ ÒÚ‡ÌÓ‚ËÚÒfl ·ÂÒÍÓ̘Ì˚Ï. ÑÎfl 2D ·Ë̇Ì˚ı ËÁÓ·‡ÊÂÌËÈ ï ÒÍÂÎÂÚ fl‚ÎflÂÚÒfl ÍË‚ÓÈ ÚÓ΢ËÌÓÈ ‚ Ó‰ËÌ ÔËÍÒÂθ ‚ ˆËÙÓ‚ÓÏ ÒÎÛ˜‡Â.ùÍÁÓÒÍÂÎÂÚ ÏÌÓÂÊÒÚ‚‡ ï – ÒÍÂÎÂÚ ‰ÓÔÓÎÌÂÌËfl ÏÌÓÊÂÒÚ‚‡ ï, Ú.Â. ÙÓ̇ ËÁÓ·‡ÊÂÌËfl, ‰Îfl ÍÓÚÓÓ„Ó ï fl‚ÎflÂÚÒfl Ô‰ÌËÏ Ô·ÌÓÏ.èÓÍÛÒÚÓ‚Ó ‡ÒÒÚÓflÌËÂé˜ÂÚ‡ÌË ÙÓÏ˚ (ÍÓÌÙË„Û‡ˆËfl ÚÓ˜ÂÍ ‚ 2), ÍÓÚÓÓ ‡ÒÒχÚË‚‡ÂÚÒfl ͇͂˚‡ÊÂÌË ËÌ‚‡Ë‡ÌÚÌ˚ı Ò‚ÓÈÒÚ‚ ÙÓÏ˚ ÓÚÌÓÒËÚÂθÌÓ ÔÂÂÌÓÒ‡, ‚‡˘ÂÌËfl Ëχүڇ·‡, ÏÓÊÌÓ Ô‰ÒÚ‡‚ËÚ¸ Í‡Í ÔÓÒΉӂ‡ÚÂθÌÓÒÚ¸ ÓËÂÌÚËÓ‚, Ú.Â.
ÒÔˆËÙ˘ÂÒÍËı ÚÓ˜ÂÍ Ì‡ ÙÓÏÂ, ‚˚·‡ÌÌ˚ı ÔÓ ÓÔ‰ÂÎÂÌÌÓÏÛ Ô‡‚ËÎÛ. ä‡Ê‰˚È ÓËÂÌÚˇ ÏÓÊÂÚ ‡ÒÒχÚË‚‡Ú¸Òfl Í‡Í ˝ÎÂÏÂÌÚ ( a ′, a ′′) ∈ 2 ËÎË ˝ÎÂÏÂÌÚ a ′ + a ′′i ∈ .ê‡ÒÒÏÓÚËÏ ‰‚ ÙÓÏ˚ ı Ë Û, Ô‰ÒÚ‡‚ÎÂÌÌ˚ Ëı ÓËÂÌÚËÌ˚ÏË ‚ÂÍÚÓ‡ÏË (x1,…,xn) Ë (y1,…,yn) ËÁ n . è‰ÔÓÎÓÊËÏ, ˜ÚÓ ı Ë Û ÍÓÂÍÚËÛ˛ÚÒfl ‰Îfl ÔÂÂÌÓÒ‡ ÛÒÎÓ‚ËÂÏxt =yt = 0. íÓ„‰‡ Ëı ÔÓÍÛÒÚÓ‚Ó ‡ÒÒÚÓflÌË ÓÔ‰ÂÎflÂÚ-∑t∑tÒfl ͇Ín∑t =1| xt − yt |2 ,308ó‡ÒÚ¸ V.
ê‡ÒÒÚÓflÌËfl ‚ ÍÓÏÔ¸˛ÚÂÌÓÈ ÒÙ„‰Â ‰‚ ÙÓÏ˚ fl‚Îfl˛ÚÒfl, ÓÔÚËχθÌÓ (ÔÓ ÍËÚÂ˲ ̇ËÏÂ̸¯Ëı Í‚‡‰‡ÚÓ‚) ‡ÒÔÓÎÓÊÂÌÌ˚ÏË ÔÓ Ó‰ÌÓÈ ÎËÌËË ‰Îfl ÍÓÂÍÚËÓ‚ÍË Ï‡Ò¯Ú‡·‡ Ë Ëı ‡ÒÒÚÓflÌË ӘÂÚ‡ÌËfl äẨ‡Î· ÓÔ‰ÂÎflÂÚÒfl ͇Íarccos∑ xt yt ∑ yt xt tt∑txt xt ∑tyt yt ,„‰Â α = a ′ − a ′′i fl‚ÎflÂÚÒfl ÍÓÏÔÎÂÍÒÌÓ ÒÓÔflÊÂÌÌ˚Ï ˜ËÒ· α = a ′ − a ′′i.ä‡Ò‡ÚÂθÌÓ ‡ÒÒÚÓflÌËÂÑÎfl β·Ó„Ó x ∈ n Ë ÒÂÏÂÈÒÚ‚‡ ÔÂÓ·‡ÁÓ‚‡ÌËÈ t(x, α), „‰Â α ∈ k – ‚ÂÍÚÓ k Ô‡‡ÏÂÚÓ‚ (̇ÔËÏÂ, ÍÓ˝ÙÙˈËÂÌÚ Ï‡Ò¯Ú‡·ËÓ‚‡ÌËfl Ë Û„ÓÎ ‚‡˘ÂÌËfl), ÏÌÓÊÂÒÚ‚ÓM x = {t ( x, σ ) : α ∈ k } ⊂ n fl‚ÎflÂÚÒfl ÏÌÓ„ÓÓ·‡ÁËÂÏ ‡ÁÏÂÌÓÒÚË Ì ·Óθ¯Â ˜ÂÏ k.ùÚÓ ÍË‚‡fl, ÂÒÎË k = 1.
åËÌËχθÌÓ ‚ÍÎË‰Ó‚Ó ‡ÒÒÚÓflÌË ÏÂÊ‰Û ÏÌÓ„ÓÓ·‡ÁËflÏËMx Ë My fl‚ÎflÂÚÒfl ÔÓÎÂÁÌ˚Ï ‡ÒÒÚÓflÌËÂÏ, ÔÓÒÍÓθÍÛ ÓÌÓ ËÌ‚‡Ë‡ÌÚÌÓ ÓÚÌÓÒËÚÂθÌÓÔÂÓ·‡ÁÓ‚‡ÌËÈ t(x, α). é‰Ì‡ÍÓ ‡ÒÒ˜ËÚ‡Ú¸ Ú‡ÍÓ ‡ÒÒÚÓflÌË ‚ Ó·˘ÂÏ ÒÎÛ˜‡Â Ó˜Â̸ÚÛ‰ÌÓ; ÔÓ˝ÚÓÏÛ M x ‡ÔÔÓÍÒËÏËÛ˛Ú Í‡Í Â„Ó Í‡Ò‡ÚÂθÌÓ ÔÓ‰ÔÓÒÚ‡ÌÒÚ‚Ó ‚kÚӘ͠ı: {x +∑ α k x i : α ∈ k } ⊂ n , „‰Â ÔÓÓʉ‡˛˘ËÂ Â„Ó Í‡Ò‡ÚÂθÌ˚ ‚ÂÍÚÓ˚i =1xi, 1 ≤ i ≤ k, fl‚Îfl˛ÚÒfl ˜‡ÒÚÌ˚ÏË ÔÓËÁ‚Ó‰Ì˚ÏË t(x, α) ÓÚÌÓÒËÚÂθÌÓ α. é‰ÌÓÒÚÓÓÌÌ (ËÎË ÓËÂÌÚËÓ‚‡ÌÌÓÂ) ͇҇ÚÂθÌÓ ‡ÒÒÚÓflÌË ÏÂÊ‰Û ˝ÎÂÏÂÌÚ‡ÏË ı Ë Û ËÁ nÂÒÚ¸ Í‚‡ÁˇÒÒÚÓflÌË d, ÓÔ‰ÂÎÂÌÌÓ ͇Í2kmin x +α∑ αk xi−y .i =1ä‡Ò‡ÚÂθÌÓ ‡ÒÒÚÓflÌË ëËχ‡–ã ä‡Ì‡–ÑÂÌ͇ ÓÔ‰ÂÎflÂÚÒfl ͇Ímin{d ( x, y), d ( y, x )}.Ç Ó·˘ÂÏ ÒÎÛ˜‡Â ͇҇ÚÂθÌÓ ÏÌÓÊÂÒÚ‚Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ ï ‚ÚӘ͠ı ÓÔ‰ÂÎflÂÚÒfl (ÔÓ ÉÓÏÓ‚Û) Í‡Í Î˛·‡fl Ô‰Âθ̇fl ÚӘ͇ ÒÂÏÂÈÒÚ‚‡ Â„Ó ‡ÒÚflÊÂÌËÈ Ò ÍÓ˝ÙÙˈËÂÌÚÓÏ ‡ÒÚflÊÂÌËfl, ÒÚÂÏfl˘ËÏÒfl Í ·ÂÒÍÓ̘ÌÓÒÚË, ÍÓÚÓ‡fl ·ÂÂÚÒfl ‚ ÚӘ˜ÌÓÈ ÚÓÔÓÎÓ„ËË ÉÓÏÓ‚‡–ï‡ÛÒ‰ÓÙ‡ (ÒÏ.
åÂÚË͇ ÉÓÏÓ‚‡–ï‡ÛÒ‰ÓÙ‡, „Î. 1).ê‡ÒÒÚÓflÌË ÔËÍÒÂÎflÇÓÁ¸ÏÂÏ ‰‚‡ ˆËÙÓ‚˚ı Ó·‡Á‡, ‡ÒÒχÚË‚‡ÂÏ˚ı Í‡Í ·Ë̇Ì˚ m × n χÚˈ˚x = ((xij)) Ë y = ((yij)), „‰Â ÔËÍÒÂθ x ij fl‚ÎflÂÚÒfl ˜ÂÌ˚Ï ËÎË ·ÂÎ˚Ï, ÂÒÎË ÓÌ ‡‚ÂÌ 1 ËÎË0 ÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓ. ÑÎfl Í‡Ê‰Ó„Ó ÔËÍÒÂÎfl xij Ó͇ÈÏÎÂÌÌÓ ‡ÒÒÚÓflÌÌÓ ÓÚÓ·‡ÊÂÌËÂ‰Ó ·ÎËÊ‡È¯Â„Ó ÔËÍÒÂÎfl ÔÓÚË‚ÓÔÓÎÓÊÌÓ„Ó ˆ‚ÂÚ‡ DBW(x ij) ÂÒÚ¸ ˜ËÒÎÓ Ó͇ÈÏÎÂÌËÈ(„‰Â ͇ʉÓ Ó͇ÈÏÎÂÌË ÒÓÒÚÓËÚ ËÁ ÔËÍÒÂÎÂÈ, ‡‚ÌÓÛ‰‡ÎÂÌÌ˚ı (i, j)), ÔÓÚflÌÛ‚¯ËıÒfl ÓÚ (i, j) ‰Ó ‚ÒÚÂ˜Ë Ò Ô‚˚Ï Ó͇ÈÏÎÂÌËÂÏ, ÒÓ‰Âʇ˘ËÏ ÔËÍÒÂθ ÔÓÚË‚ÓÔÓÎÓÊÌÓ„Ó ˆ‚ÂÚ‡.ê‡ÒÒÚÓflÌË ÔËÍÒÂÎÂÈ (‚‚‰ÂÌÌÓ ì‡ÈÚÓÏ Ë ‰., 1994) Á‡‰‡ÂÚÒfl ͇Í∑ ∑1≤ i ≤ m 1≤ i ≤ n()| xij − yij | DBW ( xij ) + DBW ( yij ) .309É·‚‡ 21.
ê‡ÒÒÚÓflÌËfl ‚ ‡Ì‡ÎËÁ ӷ‡ÁÓ‚ Ë Á‚ÛÍӂ䂇ÁˇÒÒÚÓflÌË ÍÓ˝ÙÙˈËÂÌÚ‡ ͇˜ÂÒÚ‚‡ÇÓÁ¸ÏÂÏ ‰‚‡ ·Ë̇Ì˚ı ËÁÓ·‡ÊÂÌËfl, ‡ÒÒχÚË‚‡ÂÏ˚ı Í‡Í ÌÂÔÛÒÚ˚ ÍÓ̘Ì˚ÂÔÓ‰ÏÌÓÊÂÒÚ‚‡ Ä Ë Ç ÍÓ̘ÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X, d). ÑÎfl ÌËı Í‚‡ÁˇÒÒÚÓflÌË ÍÓ˝ÙÙˈËÂÌÚ‡ ͇˜ÂÒÚ‚‡ è‡ÚÚ‡ ÓÔ‰ÂÎflÂÚÒfl ͇Í−11 max{| A |,| B |}2 ,1 + αd ( x, A) x ∈B∑„‰Â α – ÍÓÌÒÚ‡ÌÚ‡ χүڇ·ËÓ‚‡ÌËfl (Ó·˚˜ÌÓ1) Ë d ( x, A) = min d ( x, y) – ‡ÒÒÚÓflÌËÂy ∈A9ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ.èËχÏË ÔÓ‰Ó·Ì˚ı Í‚‡ÁˇÒÒÚÓflÌËÈ fl‚Îfl˛ÚÒfl ‡ÒÒÚÓflÌË Ò‰ÌÂÈ Ôӄ¯1ÌÓÒÚË èÂÎË-å‡Î‡ı‡d ( x, A) Ë ‡ÒÒÚÓflÌË Ò‰ÌÂÍ‚‡‰‡Ú˘ÂÒÍÓÈ Ôӄ¯| B | x ∈B1ÌÓÒÚËd ( x , A) 2 .| B | x ∈B∑∑ë‰Ì ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌË -„Ó ÔÓfl‰Í‡ÇÓÁ¸ÏÂÏ ‰‚‡ ·Ë̇Ì˚ı ËÁÓ·‡ÊÂÌËfl, ‡ÒÒχÚË‚‡ÂÏ˚ı Í‡Í ÌÂÔÛÒÚ˚ ÍÓ̘Ì˚ÂÔÓ‰ÏÌÓÊÂÒÚ‚‡ Ä Ë Ç ÍÓ̘ÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (Ò͇ÊÂÏ, ‡ÒÚ‡ ÔËÍÒÂÎÂÈ) (X, d). àı ҉̠ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌË -„Ó ÔÓfl‰Í‡ ÂÒÚ¸ ([Badd92]) ÌÓχÎËÁÓ‚‡ÌÌÓ Lp -‡ÒÒÚÓflÌË ï‡ÛÒ‰ÓÙ‡, ÓÔ‰ÂÎÂÌÌÓ ͇Í1 1pp−| d ( x, A) d ( x, B) | ,| X |x ∈X∑„‰Â d ( x, A) = min d ( x, y) – ‡ÒÒÚÓflÌË ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ.
é·˚˜Ì‡fl ı‡ÛÒy ∈A‰ÓÙÓ‚‡ ÏÂÚË͇ ÔÓÔÓˆËÓ̇θ̇ Ò‰ÌÂÏÛ ı‡ÛÒ‰ÓÙÓ‚Û ‡ÒÒÚÓflÌ˲ ∞-„ÓÔÓfl‰Í‡.Σ-ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌË ÇÂÌ͇ڇÒÛ·‡ÏËÌˇ̇ d d Haus ( A, B) + d d Haus ( B, A) ‡‚ÌÓ∑| d ( x, A) − d ( x, B) |, Ú.Â. fl‚ÎflÂÚÒfl ‚‡Ë‡ÌÚÓÏ L 1 -‡ÒÒÚÓflÌËfl ï‡ÛÒ‰ÓÙ‡.x ∈A ∪ BÑÛ„ËÏ ‚‡Ë‡ÌÚÓÏ Ò‰ÌÂ„Ó ı‡ÛÒ‰ÓÙÓ‚‡ ‡ÒÒÚÓflÌËfl 1-„Ó ÔÓfl‰Í‡ fl‚ÎflÂÚÒfl Ò‰Ìflfl „ÂÓÏÂÚ˘ÂÒ͇fl Ôӄ¯ÌÓÒÚ¸ ãË̉ÒÚfiχ-íÛ͇ ÏÂÊ‰Û ‰‚ÛÏfl ËÁÓ·‡ÊÂÌËflÏË,‡ÒÒχÚË‚‡ÂÏ˚ÏË Í‡Í ÔÓ‚ÂıÌÓÒÚË Ä Ë Ç. é̇ ÓÔ‰ÂÎflÂÚÒfl ͇Í1Area( A) + Area( B) ∫d ( x, B)dS +x ∈Ad ( x, A)dS ,x ∈B∫„‰Â Area( A) – ÔÎÓ˘‡‰¸ ÔÓ‚ÂıÌÓÒÚË Ä. ÖÒÎË ‡ÒÒχÚË‚‡Ú¸ ËÁÓ·‡ÊÂÌËfl Í‡Í ÍÓ̘Ì˚ ÏÌÓÊÂÒÚ‚‡ Ä Ë Ç, ÚÓ Ëı Ò‰Ìflfl „ÂÓÏÂÚ˘ÂÒ͇fl Ôӄ¯ÌÓÒÚ¸ ÓÔ‰ÂÎflÂÚÒfl ͇Í1d ( x, B) +d ( x, A) .| A | + | B | x ∈Ax ∈B∑∑310ó‡ÒÚ¸ V.
ê‡ÒÒÚÓflÌËfl ‚ ÍÓÏÔ¸˛ÚÂÌÓÈ ÒÙÂÂåÓ‰ËÙˈËÓ‚‡ÌÌÓ ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌËÂÇÓÁ¸ÏÂÏ ‰‚‡ ·Ë̇Ì˚ı ËÁÓ·‡ÊÂÌËfl, ‡ÒÒχÚË‚‡ÂÏ˚ı Í‡Í ÌÂÔÛÒÚ˚ ÍÓ̘Ì˚ÂÔÓ‰ÏÌÓÊÂÒÚ‚‡ Ä Ë Ç ÍÓ̘ÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X, d). àı ÏÓ‰ËÙˈËÓ‚‡ÌÌÓ ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌË ÔÓ Ñ˛·˛ÒÒÓÌÛ–ÑÊÂÈÌÛ ÓÔ‰ÂÎflÂÚÒfl Í‡Í Ï‡ÍÒËÏÛÏ ‡ÒÒÚÓflÌËÈ ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ, ÛÒ‰ÌÂÌÌ˚ı ÔÓ Ä Ë Ç:1 1max d ( x, B),d ( x, A).| B | x ∈B | A | x ∈A∑∑ó‡ÒÚ˘ÌÓ ı‡ÛÒ‰ÓÙÓ‚Ó Í‚‡ÁˇÒÒÚÓflÌËÂÇÓÁ¸ÏÂÏ ‰‚‡ ·Ë̇Ì˚ı ËÁÓ·‡ÊÂÌËfl, ‡ÒÒχÚË‚‡ÂÏ˚ı Í‡Í ÌÂÔÛÒÚ˚ ÍÓ̘Ì˚ÂÔÓ‰ÏÌÓÊÂÒÚ‚‡ Ä, Ç ÍÓ̘ÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X, d), Ë ˆÂÎ˚ ˜ËÒ· k, l,Ú‡ÍË ˜ÚÓ 1 ≤ k ≤ | A |, 1 ≤ l ≤ | B | . àı ˜‡ÒÚ˘ÌÓ (k, l)-ı‡ÛÒ‰ÓÙÓ‚Ó Í‚‡ÁˇÒÒÚÓflÌËÂÔÓ ï‡ÚÚÂÌÎÓÍÂÛ–êÛÍÎˉÊÛ ÓÔ‰ÂÎflÂÚÒfl ͇Í{}max kkth∈A d ( x, B), lxth∈B d ( x, A) ,„‰Â kkth∈A d ( x, B) ÓÁ̇˜‡ÂÚ k- (‚ÏÂÒÚÓ, ̇˷Óθ¯Ó„Ó A-„Ó, ‡ÒÔÓÎÓÊÂÌÌÓ„Ó Ô‚˚Ï)ÒÂ‰Ë | A | ‡ÒÒÚÓflÌËÈ d(x, B), ‡ÒÔÓÎÓÊÂÌÌ˚ı ‚ ‚ÓÁ‡ÒÚ‡˛˘ÂÏ ÔÓfl‰ÍÂ.
ëÎÛ˜‡È| A |Bk = , l = ÒÓÓÚ‚ÂÚÒÚ‚ÛÂÚ Ò‰ÌÂÏÛ ÏÓ‰ËÙˈËÓ‚‡ÌÌÓÏÛ ı‡ÛÒ‰ÓÙÓ‚Û Í‚‡ 2 2ÁˇÒÒÚÓflÌ˲.ê‡ÒÒÚÓflÌË ·ÛÚ˚ÎÓ˜ÌÓ„Ó „ÓÎ˚¯Í‡ÇÓÁ¸ÏÂÏ ‰‚‡ ·Ë̇Ì˚ı ËÁÓ·‡ÊÂÌËfl, ‡ÒÒχÚË‚‡ÂÏ˚ı Í‡Í ÌÂÔÛÒÚ˚ ÍÓ̘Ì˚ÂÔÓ‰ÏÌÓÊÂÒÚ‚‡ Ä, Ç Ò | A | = | B | = m ÍÓ̘ÌÓ„Ó ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X, d).àı ‡ÒÒÚÓflÌË ·ÛÚ˚ÎÓ˜ÌÓ„Ó „ÓÎ˚¯Í‡ ÓÔ‰ÂÎflÂÚÒfl ͇Ímin max d ( x, f ( x )),fx ∈A„‰Â f – β·Ó ·ËÂÍÚË‚ÌÓ ÓÚÓ·‡ÊÂÌË ÏÂÊ‰Û Ä Ë Ç.LJˇÌÚ‡ÏË ‚˚¯ÂÔ˂‰ÂÌÌÓ„Ó ‡ÒÒÚÓflÌËfl fl‚Îfl˛ÚÒfl:1) ÒÓÓÚ‚ÂÚÒÚ‚Ë ÏËÌËχθÌÓ„Ó ‚ÂÒ‡: mind ( x, f ( x ));{f∑x ∈A}2) ‡‚ÌÓÏÂÌÓ ÒÓÓÚ‚ÂÚÒÚ‚ËÂ: max d ( x, f ( x )) − min d ( x, f ( x )) ;x ∈Ax ∈A3) ÒÓÓÚ‚ÂÚÒÚ‚Ë ̇ËÏÂ̸¯Â„Ó ÓÚÍÎÓÌÂÌËfl:1min max d ( x, f ( x )) −d ( x, f ( x )).f x ∈A| A | x ∈AÑÎfl ˆÂÎÓ„Ó ˜ËÒ· t, 1 ≤ t ≤ | A |, ‡ÒÒÚÓflÌË t-·ÛÚ˚ÎÓ˜ÌÓ„Ó „ÓÎ˚¯Í‡ ÏÂÊ‰Û Ä ËÇ ([InVe00]) ‡‚ÌÓ ‚˚¯ÂÛÔÓÏflÌÛÚÓÏÛ ÏËÌËÏÛÏÛ, ÂÒÎË f – β·Ó ÓÚÓ·‡ÊÂÌË ËÁ Ä‚ Ç, Ú‡ÍÓ ˜ÚÓ | {x ∈ A : f ( x ) = e} | ≤ t.
ëÎÛ˜‡Ë t = 1 Ë t = | A | ‡Ì‡Îӄ˘Ì˚ ÒÓÓÚ‚ÂÚÒÚ‚ÂÌÌÓ ‡ÒÒÚÓflÌ˲ ·ÛÚ˚ÎÓ˜ÌÓ„Ó „ÓÎ˚¯Í‡ Ë ÓËÂÌÚËÓ‚‡ÌÌÓÏÛ ı‡ÛÒ‰ÓÙÓ‚Û ‡ÒÒÚÓflÌ˲ dd Haus ( A, B) = max min d ( x, y).∑x ∈A y ∈BÉ·‚‡ 21. ê‡ÒÒÚÓflÌËfl ‚ ‡Ì‡ÎËÁ ӷ‡ÁÓ‚ Ë Á‚ÛÍÓ‚311ï‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌËÂ Ò ÚÓ˜ÌÓÒÚ¸˛ ‰Ó GÑÎfl „ÛÔÔ˚ (G, ⋅, id), ‰ÂÈÒÚ‚Û˛˘ÂÈ Ì‡ ‚ÍÎˉӂÓÏ ÔÓÒÚ‡ÌÒÚ‚Â n , ı‡ÛÒ‰ÓÙÓ‚Ó‡ÒÒÚÓflÌËÂ Ò ÚÓ˜ÌÓÒÚ¸˛ ‰Ó G ÏÂÊ‰Û ‰‚ÛÏfl ÍÓÏÔ‡ÍÚÌ˚ÏË ÔÓ‰ÏÌÓÊÂÒÚ‚‡ÏË Ä Ë Ç(ËÒÔÓθÁÛÂÏÓ ÔË Ó·‡·ÓÚÍ ËÁÓ·‡ÊÂÌËÈ) ÂÒÚ¸ Ó·Ó·˘ÂÌÌÓ G-ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌË ÏÂÊ‰Û ÌËÏË, Ú.Â.
ÏËÌËÏÛÏ dHaus ( A, g( B)) ÔÓ ‚ÒÂÏ g ∈ G. é·˚˜ÌÓ G – ÏÌÓÊÂÒÚ‚Ó ‚ÒÂı ËÁÓÏÂÚËÈ ËÎË ‚ÒÂı ÔÂÂÌÓÒÓ‚ ÔÓÒÚ‡ÌÒÚ‚‡ n.ÉËÔ·Ó΢ÂÒÍÓ ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌËÂÑÎfl β·Ó„Ó ÍÓÏÔ‡ÍÚÌÓ„Ó Ó‰ÏÌÓÊÂÒÚ‚‡ Ä ÏÌÓÊÂÒÚ‚‡ n Ó·ÓÁ̇˜ËÏ ˜ÂÂÁåAT(A) Â„Ó ÔÂÓ·‡ÁÓ‚‡ÌË Ò‰ËÌÌÓÈ ÓÒË ÔÓ ÅβÏÛ, Ú.Â. ÔÓ‰ÏÌÓÊÂÒÚ‚Ó X == n × ≥ 0 , ‚Ò ˝ÎÂÏÂÌÚ˚ ÍÓÚÓÓ„Ó fl‚Îfl˛ÚÒfl Ô‡‡ÏË x = ( x ′, rx ) ˆÂÌÚÓ‚ x⬘ ˇ‰ËÛÒÓ‚ rx χÍÒËχθÌ˚ı ‚ÔËÒ‡ÌÌ˚ı ‚ A ¯‡Ó‚ ÔËÏÂÌËÚÂθÌÓ Í Â‚ÍÎˉӂÓÏÛ‡ÒÒÚÓflÌ˲ dE ‚ n (ÒÏ. C‰ËÌ̇fl ÓÒ¸ Ë ÒÍÂÎÂÚ).ÉËÔ·Ó΢ÂÒÍÓ ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌË ([ChSe00]) – ı‡ÛÒ‰ÓÙÓ‚‡ ÏÂÚË͇ ̇ÌÂÔÛÒÚ˚ı ÍÓÏÔ‡ÍÚÌ˚ı ÔÓ‰ÏÌÓÊÂÒÚ‚‡ı åAT(A) ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X, d),„‰Â „ËÔ·Ó΢ÂÒÍÓ ‡ÒÒÚÓflÌË d ̇ ï ÓÔ‰ÂÎflÂÚÒfl ‰Îfl Â„Ó ˝ÎÂÏÂÌÚÓ‚ x = ( x ′, rx )Ë y = ( y ′, ry ) ͇Ímax{0, d E ( x ′, y ′) − (ry − rx )}.çÂÎËÌÂÈ̇fl ı‡ÛÒ‰ÓÙÓ‚‡ ÏÂÚË͇ÑÎfl ‰‚Ûı ÍÓÏÔ‡ÍÚÌ˚ı ÔÓ‰ÏÌÓÊÂÒÚ‚ Ä Ë Ç ÏÂÚ˘ÂÒÍÓ„Ó ÔÓÒÚ‡ÌÒÚ‚‡ (X, d) ËıÌÂÎËÌÂÈÌÓÈ ı‡ÛÒ‰ÓÙÓ‚ÓÈ ÏÂÚËÍÓÈ (ËÎË ‚ÓÎÌÓ‚˚Ï ‡ÒÒÚÓflÌËÂÏ á‡Úχ˖êÂ͘ÍË–êÓÒ͇) ̇Á˚‚‡ÂÚÒfl ı‡ÛÒ‰ÓÙÓ‚Ó ‡ÒÒÚÓflÌË dHaus ( A ∩ B, ( A ∪ B)* ), „‰Â( A ∪ B)* ÂÒÚ¸ ÔÓ‰ÏÌÓÊÂÒÚ‚Ó A ∩ B, Ó·‡ÁÛ˛˘Â Á‡ÏÍÌÛÚÛ˛ ÌÂÔÂ˚‚ÌÛ˛ ӷ·ÒÚ¸Ò A ∩ B Ë ‡ÒÒÚÓflÌËfl ÏÂÊ‰Û ÚӘ͇ÏË ÏÓ„ÛÚ ËÁÏÂflÚ¸Òfl ÚÓθÍÓ ‚‰Óθ ÔÛÚÂÈ,ÔÓÎÌÓÒÚ¸˛ ÔË̇‰ÎÂʇ˘Ëı A ∪ B.åÂÚËÍË Í‡˜ÂÒÚ‚‡ ‚ˉÂÓËÁÓ·‡ÊÂÌËflчÌÌ˚ ÏÂÚËÍË fl‚Îfl˛ÚÒfl ‡ÒÒÚÓflÌËflÏË ÏÂÊ‰Û ‚ıÓ‰ÌÓÈ Ë ÔÓÚÓÚËÔÌÓÈ ÔÓÒΉӂ‡ÚÂθÌÓÒÚflÏË ˆ‚ÂÚÌ˚ı ‚ˉÂÓ͇‰Ó‚, ÍÓÚÓ˚ ӷ˚˜ÌÓ Ô‰̇Á̇˜ÂÌ˚ ‰Îfl ÓÔÚËÏËÁ‡ˆËË ‡Î„ÓËÚÏÓ‚ ÍÓ‰ËÓ‚‡ÌËfl, ÒʇÚËfl Ë ‰ÂÍÓ‰ËÓ‚‡ÌËfl.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
