Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (1185330), страница 62

Файл №1185330 Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf) 62 страницаЕ. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008) (1185330) страница 622020-08-252020-08-25СтудИзба

Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Регистрация/авторизация

Текст из файла (страница 62)

ê‡ÒÒÚÓﬂÌËﬂ Ì‡ ‰ÂÈÒÚ‚ËÚÂÎ¸ÌÓÈ Ë ˆËÙÓ‚ÓÈ ÔÎÓÒÍÓÒÚﬂı279‰Îﬂ x ≠ y (Ë ‡‚Ì‡ﬂ 0, ËÌ‡˜Â). í‡Í, ˜ÂÎÓ‚ÂÍ, ÊË‚Û˘ËÈ ‚ ÚÓ˜ÍÂ ı, ÍÓÚÓ˚È ıÓ˜ÂÚÔÓÒÂÚËÚ¸ ÍÓ„Ó-ÚÓ, ÊË‚Û˘Â„Ó ‚ ÚÓ˜ÍÂ y, ÒÌ‡˜‡Î‡ Á‡ıÓ‰ËÚ ‚ f, ˜ÚÓ·˚ ÍÛÔËÚ¸ ˆ‚ÂÚ˚.Ç ÒÎÛ˜‡Â ÂÒÎË d ( x, f ) = || x − y ||, ‡ ÚÓ˜Í‡ f ﬂ‚ÎﬂÂÚÒﬂ Ì‡˜‡ÎÓÏ ÍÓÓ‰ËÌ‡Ú, Ï˚ ÔÓÎÛ˜‡ÂÏÏÂÚËÍÛ ·ËÚ‡ÌÒÍÓÈ ÊÂÎÂÁÌÓÈ ‰ÓÓ„Ë.ÖÒÎË ËÏÂÂÚÒﬂ k > 1 ˆ‚ÂÚÓ˜Ì˚ı Ï‡„‡ÁËÌÓ‚ f1 ,…, fk, ÚÓ ˜ÂÎÓ‚ÂÍ ÍÛÔËÚ ˆ‚ÂÚ˚ ‚ ·ÎËÊ‡È¯ÂÏ Ï‡„‡ÁËÌÂ Ò ÏËÌËÏ‡Î¸Ì˚Ï ÓÚÍÎÓÌÂÌËÂÏ ÓÚ Ò‚ÓÂ„Ó Ï‡¯ÛÚ‡, Ú.Â. ‡ÒÒÚÓﬂÌËÂ ÏÂÊ‰Û ‡ÁÎË˜Ì˚ÏË ÚÓ˜Í‡ÏË x, y ‡‚ÌÓ min l ≤ i ≤ k ( d ( x, fi ) + d ( fi , y)).åÂÚËÍ‡ ˝Í‡Ì‡ ‡‰‡‡ÑÎﬂ ÌÓÏ˚ || ⋅ || Ì‡ 2 (‚ Ó·˘ÂÏ ÒÎÛ˜‡Â Ì‡ n ) ÏÂÚËÍÓÈ ˝Í‡Ì‡ ‡‰‡‡ Ì‡Á˚‚‡ÂÚÒﬂ ÏÂÚËÍ‡ Ì‡ 2 (‚ Ó·˘ÂÏ ÒÎÛ˜‡Â Ì‡ n), ÓÔÂ‰ÂÎÂÌÌ‡ﬂ Í‡Ímin{1,|| x − y ||}.åÂÚËÍ‡ ÍÓ‚‡ êËÍÏ‡Ì‡ÑÎﬂ ˜ËÒÎ‡ α ∈ (0, 1) ÏÂÚËÍÓÈ ÍÓ‚‡ êËÍÏ‡Ì‡ ﬂ‚ÎﬂÂÚÒﬂ ÏÂÚËÍ‡ Ì‡ 2, ÓÔÂ‰ÂÎÂÌÌ‡ﬂ Í‡Íx1 − y1 + x 2 − y2α.ùÚÓ ﬂ‚ÎﬂÂÚÒﬂ ÒÎÛ˜‡ÂÏ n = 2 Ô‡‡·ÓÎË˜ÂÒÍÓ„Ó ‡ÒÒÚÓﬂÌËﬂ („Î. 6; ÒÏ.

Ú‡Ï ÊÂ ‰Û„ËÂÏÂÚËÍË Ì‡ n, n ≥ 2).åÂÚËÍ‡ ÅÛ‡„Ó–à‚‡ÌÓ‚‡å Â Ú  Ë Í Ó È Å Û  ‡ „  Ó – à ‚ ‡ Ì Ó ‚ ‡ ([BuIv01]) Ì‡Á˚‚‡ÂÚÒﬂ ÏÂÚËÍ‡ Ì‡ 2 , ÓÔÂ‰ÂÎÂÌÌ‡ﬂ Í‡Í|| x ||2 − || y ||2 + min{|| x ||2 ⋅ ||| y ||2 } ⋅ ∠( x, y),„‰Â ∠(x, y) – Û„ÓÎ ÏÂÊ‰Û ‚ÂÍÚÓ‡ÏË ı Ë Û Ë || ⋅ || – Â‚ÍÎË‰Ó‚‡ ÌÓÏ‡ Ì‡ 2 . ëÓÓÚ‚ÂÚÒÚ‚Û˛˘‡ﬂ ‚ÌÛÚÂÌÌﬂﬂ ÏÂÚËÍ‡ Ì‡ 2 ‡‚Ì‡ || x ||2 − || y ||2 , ÂÒÎË ∠(x, y) = 0, Ë ‡‚Ì‡|| x ||2 − || y ||2 , ËÌ‡˜Â.åÂÚËÍ‡ 2n-Û„ÓÎ¸ÌËÍ‡ÑÎﬂ ˆÂÌÚ‡Î¸ÌÓ ÒËÏÏÂÚË˜ÌÓ„Ó Ô‡‚ËÎ¸ÌÓ„Ó 2n-Û„ÓÎ¸ÌËÍ‡ K Ì‡ ÔÎÓÒÍÓÒÚË ÏÂÚËÍÓÈ 2n-Û„ÓÎ¸ÌËÍ‡ Ì‡Á˚‚‡ÂÚÒﬂ ÏÂÚËÍ‡ Ì‡ 2 , ÓÔÂ‰ÂÎÂÌÌ‡ﬂ ‰Îﬂ Î˛·˚ı x,y ∈ 2Í‡Í Ì‡ËÍ‡Ú˜‡È¯‡ﬂ Â‚ÍÎË‰Ó‚‡ ‰ÎËÌ‡ ÎÓÏ‡ÌÓÈ ÎËÌËË ÓÚ ı Í Û, Í‡Ê‰ÓÂ ËÁ Á‚ÂÌ¸Â ÍÓÚÓÓÈ Ô‡‡ÎÎÂÎ¸Ì‡ ÌÂÍÓÚÓÓÏÛ ËÁ Â·Â ÏÌÓ„ÓÛ„ÓÎ¸ÌËÍ‡ ä.ÖÒÎË ä ÂÒÚ¸ ÔﬂÏÓÛ„ÓÎ¸ÌËÍ Ò ‚Â¯ËÌ‡ÏË {(±1, ±1)}, ÚÓ Ï˚ ÔÓÎÛ˜‡ÂÏ ÏÂÚËÍÛå‡Ìı˝ÚÚÂÌ‡.

åÂÚËÍÛ å‡Ìı˝ÚÚÂÌ‡ Ú‡ÍÊÂ ÏÓÊÌÓ ‡ÒÒÏ‡ÚË‚‡Ú¸ Í‡Í ÏÂÚËÍÛ åËÌÍÓ‚ÒÍÓ„Ó Ò Â‰ËÌË˜Ì˚Ï ¯‡ÓÏ ‚ ‚Ë‰Â ·ËÎÎË‡ÌÚ‡, Ú.Â. Í‚‡‰‡Ú‡ Ò ‚Â¯ËÌ‡ÏË{(1,0(0,1), (–1,0),(0,–1)}.åÂÚËÍ‡ ˆÂÌÚ‡Î¸ÌÓ„Ó Ô‡Í‡åÂÚËÍÓÈ ˆÂÌÚ‡Î¸ÌÓ„Ó Ô‡Í‡ Ì‡Á˚‚‡ÂÚÒﬂ ÏÂÚËÍ‡ Ì‡ 2, ÓÔÂ‰ÂÎÂÌÌ‡ﬂ Í‡Í ‰ÎËÌ‡ Ì‡ËÍ‡Ú˜‡È¯Â„Ó l1 -ÔÛÚË (ÔÛÚË å‡Ìı˝ÚÚÂÌ‡) ÏÂÊ‰Û ‰‚ÛÏﬂ ÚÓ˜Í‡ÏË, x, y ∈ 2 ÔËÌ‡ÎË˜ËË ‰‡ÌÌÓ„Ó ÏÌÓÊÂÒÚ‚‡ ÁÓÌ, ˜ÂÂÁ ÍÓÚÓ˚Â ÔÓıÓ‰ﬂÚ Í‡Ú˜‡È¯ËÂ Â‚ÍÎË‰Ó‚˚ÔÛÚË (Ì‡ÔËÏÂ, ñÂÌÚ‡Î¸Ì˚È Ô‡Í ‚ å‡Ìı˝ÚÚÂÌÂ).ê‡ÒÒÚÓﬂÌËÂ ËÒÍÎ˛˜ÂÌËﬂ ÒÚÓÎÍÌÓ‚ÂÌËÈèÛÒÚ¸ = {O1 ,…,Om} – ÒÓ‚ÓÍÛÔÌÓÒÚ¸ ÔÓÔ‡ÌÓ ÌÂÔÂÂÒÂÍ‡˛˘ËıÒﬂ ÏÌÓ„ÓÛ„ÓÎ¸ÌËÍÓ‚ Ì‡ Â‚ÍÎË‰Ó‚ÓÈ ÔÎÓÒÍÓÒÚË, ÔÂ‰ÒÚ‡‚Îﬂ˛˘ÂÂ ÒÓ·ÓÈ ÏÌÓÊÂÒÚ‚Ó ÔÂÔﬂÚÒÚ‚ËÈ,ÍÓÚÓ˚Â ﬂ‚Îﬂ˛ÚÒﬂ Ó‰ÌÓ‚ÂÏÂÌÌÓ ÌÂÔÓÁ‡˜Ì˚ÏË Ë ÌÂÔÓıÓ‰ËÏ˚ÏË.280ó‡ÒÚ¸ V.

ê‡ÒÒÚÓﬂÌËﬂ ‚ ÍÓÏÔ¸˛ÚÂÌÓÈ ÒÙÂÂê‡ÒÒÚÓﬂÌËÂÏ ËÒÍÎ˛˜ÂÌËﬂ ÒÚÓÎÍÌÓ‚ÂÌËÈ (ËÎË ‡ÒÒÚÓﬂÌËÂÏ ÌÓÒËÎ¸˘ËÍÓ‚ ÔË‡ÌËÌÓ, ÏÂÚËÍÓÈ Í‡Ú˜‡È¯Â„Ó ÔÛÚË Ò ÔÂÔﬂÚÒÚ‚ËﬂÏË) Ì‡Á˚‚‡ÂÚÒﬂ ÏÂÚËÍ‡ Ì‡ ÏÌÓÊÂÒÚ‚Â 2\{}, ÓÔÂ‰ÂÎÂÌÌ‡ﬂ ‰Îﬂ Î˛·˚ı x, y ∈ 2\{} Í‡Í ‰ÎËÌ‡ Í‡Ú˜‡È¯Â„Ó ËÁ‚ÒÂı ‚ÓÁÏÓÊÌ˚ı ÌÂÔÂ˚‚Ì˚ı ÔÛÚÂÈ, ÒÓÂ‰ËÌﬂ˛˘Ëı ı Ë Û Ë ÌÂ ÔÂÂÒÂÍ‡˛˘Ëı ÔÂÔﬂÚÒÚ‚Ëﬂ Oi\∂Oi (ÔÛÚ¸ ÏÓÊÂÚ ÔÓıÓ‰ËÚ¸ ˜ÂÂÁ ÚÓ˜ÍË Ì‡ „‡ÌËˆÂ ∂Oi ÔÂÔﬂÚÒÚ‚Ëﬂ∂Oi), i = 1,…,m.èﬂÏÓÛ„ÓÎ¸ÌÓÂ ‡ÒÒÚÓﬂÌËÂ Ò ·‡¸Â‡ÏËèÛÒÚ¸ = {O1,…,Om} – ÒÓ‚ÓÍÛÔÌÓÒÚ¸ ÔÓÔ‡ÌÓ ÌÂÔÂÂÒÂÍ‡˛˘ËıÒﬂ ÓÚÍ˚Ú˚ıÏÌÓ„ÓÛ„ÓÎ¸Ì˚ı ·‡¸ÂÓ‚ Ì‡ 2. èﬂÏÓÛ„ÓÎ¸Ì˚È ÔÛÚ¸ (ËÎË ÔÛÚ¸ å‡Ìı˝ÚÚÂÌ‡)Px y ÓÚ x Í y ÂÒÚ¸ ÒÓ‚ÓÍÛÔÌÓÒÚ¸ „ÓËÁÓÌÚ‡Î¸Ì˚ı Ë ‚ÂÚËÍ‡Î¸Ì˚ı ÓÚÂÁÍÓ‚Ì‡ ÔÎÓÒÍÓÒÚË, ÒÓÂ‰ËÌﬂ˛˘Ëı ı Ë Û.

èÛÚ¸ Pxy Ì‡Á˚‚‡ÂÚÒﬂ ÓÒÛ˘ÒÚ‚ÎﬂÂÏ˚Ï ÂÒÎËm Pxy ∩  Bi  = 0/ . i =1 èﬂÏÓÛ„ÓÎ¸ÌÓÂ ‡ÒÒÚÓﬂÌËÂ Ò ·‡¸Â‡ÏË (ËÎË ÔﬂÏÓÛ„ÓÎ¸ÌÓÂ ‡ÒÒÚÓﬂÌËÂ ÔËÌ‡ÎË˜ËË ·‡¸ÂÓ‚) ÂÒÚ¸ ÏÂÚËÍ‡ Ì‡ 2\{}, ÓÔÂ‰ÂÎÂÌÌ‡ﬂ ‰Îﬂ Î˛·˚ı x, y ∈ 2\{}Í‡Í ‰ÎËÌ‡ Í‡Ú˜‡È¯Â„Ó ÓÒÛ˘ÂÒÚ‚ËÏÓ„Ó ÔﬂÏÓÛ„ÓÎ¸ÌÓ„Ó ÔÛÚË ÓÚ ı Í Û.èﬂÏÓÛ„ÓÎ¸ÌÓÂ ‡ÒÒÚÓﬂÌËÂ Ò ·‡¸Â‡ÏË ﬂ‚ÎﬂÂÚÒﬂ ÒÛÊÂÌËÂÏ ÏÂÚËÍË å‡Ìı˝ÚÚÂÌ‡Ë Ó·˚˜ÌÓ ‡ÒÒÏ‡ÚË‚‡ÂÚÒﬂ Ì‡ ÏÌÓÊÂÒÚ‚Â {q1 , …, qr } ⊂ 2 ËÁ n ÚÓ˜ÂÍ "ÓÚÔ‡‚ËÚÂÎ¸ÔÓÎÛ˜‡ÚÂÎ¸": Á‡‰‡˜‡ Ì‡ıÓÊ‰ÂÌËﬂ ÔÛÚÂÈ Ú‡ÍÓ„Ó ÚËÔ‡ ‚ÓÁÌËÍ‡ÂÚ, Ì‡ÔËÏÂ, ÔË Ó„‡ÌËÁ‡ˆËË Ú‡ÌÒÔÓÚÌ˚ı ÔÂÂ‚ÓÁÓÍ ‚ „ÓÓ‰ÒÍËı ÛÒÎÓ‚Ëﬂı, ‡ Ú‡ÍÊÂ ÔË ÔÎ‡ÌËÓ‚ÍÂÁ‡‚Ó‰Ó‚ Ë ÒÓÓÛÊÂÌËÈ (ÒÏ., Ì‡ÔËÏÂ, [LaLi81]).Uê‡ÒÒÚÓﬂÌËÂ Ò‚ﬂÁËèÛÒÚ¸ P ⊂ 2 – ÏÌÓ„ÓÛ„ÓÎ¸Ì‡ﬂ Ó·Î‡ÒÚ¸ (Ì‡ n ‚Â¯ËÌ‡ı Ò h ‰˚‡ÏË), Ú.Â.

Á‡ÏÍÌÛÚ‡ﬂ ÏÌÓ„ÓÒ‚ﬂÁÌ‡ﬂ Ó·Î‡ÒÚ¸, „‡ÌËˆ‡ ÍÓÚÓÓÈ – Ó·˙Â‰ËÌÂÌËÂ n ÎËÌÂÈÌ˚ı ÓÚÂÁÍÓ‚,Ó·‡ÁÛ˛˘Ëı n + 1 Á‡ÏÍÌÛÚ˚ı ÏÌÓ„ÓÛ„ÓÎ¸Ì˚ı ˆËÍÎÓ‚. ê‡ÒÒÚÓﬂÌËÂÏ Ò‚ﬂÁË Ì‡Á˚‚‡ÂÚÒﬂ ÏÂÚËÍ‡ Ì‡ ê, ÓÔÂ‰ÂÎÂÌÌ‡ﬂ ‰Îﬂ Î˛·˚ı x, y ∈ P Í‡Í ÏËÌËÏ‡Î¸ÌÓÂ ˜ËÒÎÓÂ·Â ÏÌÓ„ÓÛ„ÓÎ¸ÌÓ„Ó ÔÛÚË ÓÚ ı Í Û ‚ ÔÂ‰ÂÎ‡ı ÏÌÓ„ÓÛ„ÓÎ¸ÌÓÈ Ó·Î‡ÒÚË ê.ÖÒÎË ‡ÁÂ¯ÂÌ˚ ÚÓÎ¸ÍÓ ÔﬂÏÓÛ„ÓÎ¸Ì˚Â ÔÛÚË, Ï˚ ÔÓÎÛ˜‡ÂÏ ÔﬂÏÓÛ„ÓÎ¸ÌÓÂ ‡ÒÒÚÓﬂÌËÂ Ò‚ﬂÁË. ÖÒÎË ÔÛÚË ë-ÓËÂÌÚËÓ‚‡Ì˚ (Ú.Â. Í‡Ê‰ÓÂ Â·Ó Ô‡‡ÎÎÂÎ¸ÌÓ Ó‰ÌÓÏÛ ËÁ Â·Â ÏÌÓÊÂÒÚ‚‡ ë Ò Á‡‰‡ÌÌÓÈ ÓËÂÌÚ‡ˆËÂÈ), ÚÓ Ï˚ ËÏÂÂÏ ë-ÓËÂÌÚËÓ‚‡ÌÌÓÂ ‡ÒÒÚÓﬂÌËÂ Ò‚ﬂÁË.ê‡ÒÒÚÓﬂÌËﬂ ÔÎ‡ÌËÓ‚ÍË ÒÓÓÛÊÂÌËÈèÎ‡ÌËÓ‚Í‡ – ˝ÚÓ ‡Á·ËÂÌËÂ ÔﬂÏÓÛ„ÓÎ¸ÌÓÈ ÔÎÓÒÍÓÈ Ó·Î‡ÒÚË Ì‡ ÔﬂÏÓÛ„ÓÎ¸ÌËÍË ÏÂÌ¸¯Â„Ó ‡ÁÏÂ‡, Ì‡Á˚‚‡ÂÏ˚Â ÓÚ‰ÂÎÂÌËﬂÏË, ÎËÌËﬂÏË, ÔÓıÓ‰ﬂ˘ËÏËÔ‡‡ÎÎÂÎ¸ÌÓ ÒÚÓÓÌ‡Ï ËÒıÓ‰ÌÓ„Ó ÔﬂÏÓÛ„ÓÎ¸ÌËÍ‡.

ÇÒÂ ‚ÌÛÚÂÌÌËÂ ‚Â¯ËÌ˚‰ÓÎÊÌ˚ ·˚Ú¸ ÚÂı‚‡ÎÂÌÚÌ˚ÏË, ‡ ÌÂÍÓÚÓ˚Â ËÁ ÌËı, ÔÓ Í‡ÈÌÂÈ ÏÂÂ Ó‰Ì‡ Ì‡ „‡ÌËˆÂ Í‡Ê‰Ó„Ó ÓÚ‰ÂÎÂÌËﬂ, ﬂ‚Îﬂ˛ÚÒﬂ ‰‚ÂﬂÏË, Ú.Â. ÏÂÒÚ‡ÏË ‚ıÓ‰‡-‚˚ıÓ‰‡. èÓ·ÎÂÏ‡Á‡ÍÎ˛˜‡ÂÚÒﬂ ‚ ÒÓÁ‰‡ÌËË ÔÓ‰ıÓ‰ﬂ˘Â„Ó ÔÂ‰ÒÚ‡‚ÎÂÌËﬂ Ó ‡ÒÒÚÓﬂÌËË d(x, y) ÏÂÊ‰Û ÓÚ‰ÂÎÂÌËﬂÏË ı Ë Û, ÍÓÚÓÓÂ ÏËÌËÏËÁËÓ‚‡ÎÓ ·˚ ÙÛÌÍˆË˛ ˆÂÌ˚F( x, y)d ( x, y), „‰Â∑x, yF(x, y) – ÌÂÍËÈ Ï‡ÚÂË‡Î¸Ì˚È ÔÓÚÓÍ ÏÂÊ‰Û ı Ë Û. éÒÌÓ‚Ì˚ÏË ËÒÔÓÎ¸ÁÛÂÏ˚ÏË ‰Îﬂ˝ÚÓ„Ó ‡ÒÒÚÓﬂÌËﬂÏË ﬂ‚Îﬂ˛ÚÒﬂ:– ‡ÒÒÚÓﬂÌËÂ ˆÂÌÚÓË‰‡, Ú.Â. Í‡Ú˜‡È¯ÂÂ Â‚ÍÎË‰Ó‚Ó ‡ÒÒÚÓﬂÌËÂ ËÎË ‡ÒÒÚÓﬂÌËÂå‡Ìı˝ÚÚÂÌ‡ ÏÂÊ‰Û ˆÂÌÚÓË‰‡ÏË (ÔÂÂÒÂ˜ÂÌËﬂ ‰Ë‡„ÓÌ‡ÎÂÈ) ı Ë Û;– ‡ÒÒÚÓﬂÌËÂ ÔÂËÏÂÚ‡, Ú.Â.

Í‡Ú˜‡È¯ÂÂ ÔﬂÏÓÛ„ÓÎ¸ÌÓÂ ‡ÒÒÚÓﬂÌËÂ ÏÂÊ‰Û‰‚ÂﬂÏË ı Ë Û, ÔÓıÓ‰ﬂ˘ÂÂ ÚÓÎ¸ÍÓ ‚‰ÓÎ¸ ÒÚÂÌ, Ú.Â. ÔÂËÏÂÚÓ‚ ÓÚ‰ÂÎÂÌËÈ.281ÉÎ‡‚‡ 19. ê‡ÒÒÚÓﬂÌËﬂ Ì‡ ‰ÂÈÒÚ‚ËÚÂÎ¸ÌÓÈ Ë ˆËÙÓ‚ÓÈ ÔÎÓÒÍÓÒÚﬂıåÂÚËÍ‡ ·˚ÒÚÂÈ¯Â„Ó ÔÛÚËåÂÚËÍ‡ ·˚ÒÚÂÈ¯Â„Ó ÔÛÚË (ËÎË ÏÂÚËÍ‡ ÒÂÚË) – ÏÂÚËÍ‡ Ì‡ 2 (ËÎË Ì‡ ÔÓ‰ÏÌÓÊÂÒÚ‚Â 2) ÔË Ì‡ÎË˜ËË ‰‡ÌÌÓÈ ÒÂÚË, Ú.Â. ÔÎÓÒÍÓ„Ó ‚Á‚Â¯ÂÌÌÓ„Ó „‡Ù‡ G(V, E).ÑÎﬂ Î˛·˚ı x, y ∈ 2 ˝ÚÓ ﬂ‚ÎﬂÂÚÒﬂ ‚ÂÏÂÌÂÏ ·˚ÒÚÂÈ¯Â„Ó ÔÛÚË ÏÂÊ‰Û ı Ë Û ‚ ÔËÌ‡ÎË˜ËË ÒÂÚË G, Ú.Â. ÔÛÚË, Ï‡ÍÒËÏ‡Î¸ÌÓ ÒÓÍ‡˘‡˛˘Â„Ó ‚ÂÏﬂ ÔÂÂÏÂ˘ÂÌËﬂ ÏÂÊ‰Ûı Ë Û. èÓÒÎÂ ÔÓÎÛ˜ÂÌËﬂ ‰ÓÒÚÛÔ‡ ‚ ÒÂÚ¸ G ‰‡ÎÂÂ ÏÓÊÌÓ ÔÂÂÏÂ˘‡Ú¸Òﬂ Ò ÌÂÍÓÚÓÓÈÒÍÓÓÒÚ¸˛ v > 1 ‚‰ÓÎ¸ ÂÂ Â·Â. Ñ‚ËÊÂÌËÂ ‚ÌÂ ÒÂÚË ÓÒÛ˘ÂÒÚ‚ÎﬂÂÚÒﬂ Ò Â‰ËÌË˜ÌÓÈÒÍÓÓÒÚ¸˛ ÓÚÌÓÒËÚÂÎ¸ÌÓ Á‡‰‡ÌÌÓÈ ÏÂÚËÍË d Ì‡ ÔÎÓÒÍÓÒÚË (Ì‡ÔËÏÂ, Â‚ÍÎË‰Ó‚ÓÈÏÂÚËÍË ËÎË ÏÂÚËÍË å‡Ìı˝ÚÚÂÌ‡).åÂÚËÍ‡ ‚ÓÁ‰Û¯Ì˚ı ÔÂÂ‚ÓÁÓÍ ÂÒÚ¸ ÏÂÚËÍÓÈ ·˚ÒÚÂÈ¯Â„Ó ÔÛÚË Ì‡ 2 ÔË Ì‡ÎË˜ËË ÒÂÚË ‡˝ÓÔÓÚÓ‚, Ú.Â.

ÔÎÓÒÍÓ„Ó „‡Ù‡ G(V, E) Ì‡ n ‚Â¯ËÌ‡ı (‡˝ÓÔÓÚ‡ı) ÒÔÓÎÓÊËÚÂÎ¸Ì˚ÏË ‚ÂÒ‡ÏË Â·Â (w e)e∈E (‚ÂÏﬂ ÔÓÎÂÚ‡). ÇÓÈÚË Ë ‚˚ÈÚË ËÁ „‡Ù‡ÏÓÊÌÓ ÚÓÎ¸ÍÓ ˜ÂÂÁ ‡˝ÓÔÓÚ˚. Ñ‚ËÊÂÌËÂ ‚ÌÂ ÒÂÚË ÓÒÛ˘ÂÒÚ‚ÎﬂÂÚÒﬂ Ò Â‰ËÌË˜ÌÓÈÒÍÓÓÒÚ¸˛ ÓÚÌÓÒËÚÂÎ¸ÌÓ Â‚ÍÎË‰Ó‚ÓÈ ÏÂÚËÍË. èÂ‰ÔÓÎ‡„‡ÂÚÒﬂ, ˜ÚÓ ‰‚ËÊÂÌËÂ Ì‡‡‚ÚÓÏÓ·ËÎÂ ÔÓ ‚ÂÏÂÌË ‡‚ÌÓ ÏÂÚËÍÂ Â‚ÍÎË‰Ó‚‡ ‡ÒÒÚÓﬂÌËﬂ dE, ÚÓ„‰‡ Í‡Í ÔÓÎÂÚ‚‰ÓÎ¸ Â·‡ e = uv „‡Ù‡ G Á‡ÈÏÂÚ ‚ÂÏﬂ we < d E (u, v). Ç ÔÓÒÚÂÈ¯ÂÏ ÒÎÛ˜‡Â, ÍÓ„‰‡ÓÒÛ˘ÂÒÚ‚ÎﬂÂÚÒﬂ ÔÂÂ‚ÓÁÍ‡ ÔÓ ‚ÓÁ‰ÛıÛ ÏÂÊ‰Û ‰‚ÛÏﬂ ÚÓ˜Í‡ÏË a, b ∈ 2, ‡ÒÒÚÓﬂÌËÂÏÂÊ‰Û ı Ë Û ‡‚ÌÓmin{d E ( x, y), d E ( x, a) + w + d E (b, y), d E ( x, b) + w + d E ( a, y)},„‰Â w < d2 (a, b) ÂÒÚ¸ ÔÓ‰ÓÎÊËÚÂÎ¸ÌÓÒÚ¸ ÔÓÎÂÚ‡ ÏÂÊ‰Û a Ë b.åÂÚËÍ‡ „ÓÓ‰‡ – ÏÂÚËÍ‡ ·˚ÒÚÂÈ¯Â„Ó ÔÛÚË Ì‡ 2 ÔË Ì‡ÎË˜ËË ÒÂÚË Ó·˘ÂÒÚ‚ÂÌÌÓ„Ó Ú‡ÌÒÔÓÚ‡, Ú.Â.

ÔÎÓÒÍÓ„Ó „‡Ù‡ G Ò „ÓËÁÓÌÚ‡Î¸Ì˚ÏË ËÎË ‚ÂÚËÍ‡Î¸Ì˚ÏË Â·‡ÏË. G ÏÓÊÂÚ ÒÓÒÚÓﬂÚ¸ ËÁ ÏÌÓ„Ëı Ò‚ﬂÁÌ˚ı ÍÓÏÔÓÌÂÌÚ Ë ÒÓ‰ÂÊ‡Ú¸ˆËÍÎ˚. ä‡Ê‰˚È ÏÓÊÂÚ ÔÓÔ‡ÒÚ¸ ‚ G ‚ Î˛·ÓÈ ÚÓ˜ÍÂ, ·Û‰¸ ÚÓ ‚Â¯ËÌ‡ ËÎË Â·Ó(‚ÓÁÏÓÊÌÓ Ì‡ÁÌ‡˜ËÚ¸ Ú‡ÍÊÂ Ë ÒÚÓ„Ó ÙËÍÒËÓ‚‡ÌÌ˚Â ÚÓ˜ÍË ‚ıÓ‰‡). ÇÌÛÚË G‰‚ËÊÂÌËÂ ÓÒÛ˘ÂÒÚ‚ÎﬂÂÚÒﬂ Ò Á‡‰‡ÌÌÓÈ ÒÍÓÓÒÚ¸˛ v > 1 ‚ Ó‰ÌÓÏ ËÁ ‰ÓÒÚÛÔÌ˚ıÌ‡Ô‡‚ÎÂÌËÈ. Ñ‚ËÊÂÌËÂ ‚ÌÂ ÒÂÚË ÓÒÛ˘ÂÒÚ‚ÎﬂÂÚÒﬂ Ò Â‰ËÌË˜ÌÓÈ ÒÍÓÓÒÚ¸˛ ÓÚÌÓÒËÚÂÎ¸ÌÓ ÏÂÚËÍË å‡Ìı˝ÚÚÂÌ‡ (‚ Ì‡¯ÂÏ ÒÎÛ˜‡Â ÔÓ‰‡ÁÛÏÂ‚‡ÂÚÒﬂ ÍÛÔÌ˚ÈÒÓ‚ÂÏÂÌÌ˚È „ÓÓ‰ Ò ÔﬂÏÓÛ„ÓÎ¸ÌÓÈ ÔÎ‡ÌËÓ‚ÍÓÈ ÛÎËˆ ÔÓ Ì‡Ô‡‚ÎÂÌËﬂÏ ÒÂ‚Â–˛„Ë ‚ÓÒÚÓÍ–Á‡Ô‡‰).åÂÚËÍ‡ ÏÂÚÓ – ÏÂÚËÍ‡ ·˚ÒÚÂÈ¯Â„Ó ÔÛÚË Ì‡ 2, ÍÓÚÓ‡ﬂ ﬂ‚ÎﬂÂÚÒﬂ ‚‡Ë‡ÌÚÓÏÏÂÚËÍË „ÓÓ‰‡: ÏÂÚÓ (‚ ‚Ë‰Â ÎËÌËË Ì‡ ÔÎÓÒÍÓÒÚË) ËÒÔÓÎ¸ÁÛÂÚÒﬂ ‰Îﬂ ÒÓÍ‡˘ÂÌËﬂıÓ‰¸·˚ ÔÂ¯ÍÓÏ ‚ ÔÂ‰ÂÎ‡ı „ÓÓ‰ÒÍÓÈ ÒÂÚÍË ÍÓÓ‰ËÌ‡Ú.èÂËÓ‰Ë˜ÂÒÍ‡ﬂ ÏÂÚËÍ‡åÂÚËÍ‡ d Ì‡ 2 Ì‡Á˚‚‡ÂÚÒﬂ ÔÂËÓ‰Ë˜ÂÒÍÓÈ, ÂÒÎË ÒÛ˘ÂÒÚ‚Û˛Ú ‰‚‡ ÎËÌÂÈÌÓ ÌÂÁ‡‚ËÒËÏ˚ı ‚ÂÍÚÓ‡ v Ë u, Ú‡ÍËÂ ˜ÚÓ ÔÂÂÌÓÒ ÔÓ Î˛·ÓÏÛ ‚ÂÍÚÓÛ w = mv + nu,m,n ∈ ÒÓı‡ÌﬂÂÚ ‡ÒÒÚÓﬂÌËﬂ, Ú.Â.

d ( x, y) = d ( x + w, y + w ) ‰Îﬂ Î˛·˚ı x, y ∈ 2 (ÒÏ. àÌ‚‡Ë‡ÌÚÌ‡ﬂ ÏÂÚËÍ‡ ÔÂÂÌÓÒ‡, „Î. 5)è‡‚ËÎ¸Ì‡ﬂ ÏÂÚËÍ‡åÂÚËÍ‡ d Ì‡ 2 Ì‡Á˚‚‡ÂÚÒﬂ Ô‡‚ËÎ¸ÌÓÈ, ÂÒÎË Ó·Î‡‰‡ÂÚ ÒÎÂ‰Û˛˘ËÏË Ò‚ÓÈÒÚ‚‡ÏË:1) d ÔÓÓÊ‰‡ÂÚ Â‚ÍÎË‰Ó‚Û ÚÓÔÓÎÓ„Ë˛;2) d-ÓÍÛÊÌÓÒÚË Ó„‡ÌË˜ÂÌ˚ ÓÚÌÓÒËÚÂÎ¸ÌÓ Â‚ÍÎË‰Ó‚ÓÈ ÏÂÚËÍË;3) ÂÒÎË x, y ∈ 2 Ë x ≠ y, ÚÓ ÒÛ˘ÂÒÚ‚ÛÂÚ ÚÓ˜Í‡ z, z ≠ x, z ≠ y, Ú‡Í‡ﬂ ˜ÚÓ ‚˚ÔÓÎÌﬂÂÚÒﬂ‡‚ÂÌÒÚ‚Ó d ( x, y) = d ( x, z ) + d ( z, y);4) ÂÒÎË x, y ∈ 2, x p y („‰Â p ÙËÍÒËÓ‚‡ÌÌ˚È ÔÓﬂ‰ÓÍ Ì‡ 2, Ì‡ÔËÏÂ, ÎÂÍÒËÍÓ„‡ÙË˜ÂÒÍËÈ ÔÓﬂ‰ÓÍ), C( x, y) = {z ∈ 2 : d ( x, z ) ≤ d ( y, z )},D( x, y) = {z ∈ 2 : d ( x,282ó‡ÒÚ¸ V. ê‡ÒÒÚÓﬂÌËﬂ ‚ ÍÓÏÔ¸˛ÚÂÌÓÈ ÒÙÂÂz ) < d ( y, z )} Ë D( x, y) – Á‡Ï˚Í‡ÌËÂ D(x,y), ÚÓ J ( x, y) = C( x, y) ∩ D( x, y) ÂÒÚ¸ ÍË‚‡ﬂ,„ÓÏÂÓÏÓÙÌ‡ﬂ (0,1).

èÂÂÒÂ˜ÂÌËÂ ‰‚Ûı Ú‡ÍËı ÍË‚˚ı ÒÓÒÚÓËÚ ËÁ ÍÓÌÂ˜ÌÓ„Ó ˜ËÒÎ‡ÏÌÓ„Ëı Ò‚ﬂÁÌ˚ı ÍÓÏÔÓÌÂÌÚ.ä‡Ê‰‡ﬂ ÏÂÚËÍ‡ ÌÓÏ˚ ËÏÂÂÚ Ò‚ÓÈÒÚ‚‡ 1., 2. Ë 3. ë‚ÓÈÒÚ‚Ó 2. ÓÁÌ‡˜‡ÂÚ, ˜ÚÓ ÏÂÚËÍ‡ d ﬂ‚ÎﬂÂÚÒﬂ ÌÂÔÂ˚‚ÌÓÈ ‚ ·ÂÒÍÓÌÂ˜ÌÓÒÚË ÓÚÌÓÒËÚÂÎ¸ÌÓ Â‚ÍÎË‰Ó‚ÓÈ ÏÂÚËÍË.ë‚ÓÈÒÚ‚ÓÏ 4. Ó·ÂÒÔÂ˜Ë‚‡ÂÚÒﬂ, ˜ÚÓ „‡ÌËˆ˚ ÒÓÓÚ‚ÂÚÒÚ‚Û˛˘Ëı ‰Ë‡„‡ÏÏ ÇÓÓÌÓ„Óﬂ‚Îﬂ˛ÚÒﬂ ÍË‚˚ÏË Ë ˜ÚÓ ÌÂ ÒÎË¯ÍÓÏ ÏÌÓ„Ó ÔÂÂÒÂ˜ÂÌËÈ ÒÛ˘ÂÒÚ‚Ó‚ÛÂÚ ‚ ÓÍÂÒÚÌÓÒÚË ÚÓ˜ÍË ËÎË ‚ ·ÂÒÍÓÌÂ˜ÌÓÒÚË. è‡‚ËÎ¸Ì‡ﬂ ÏÂÚËÍ‡ d ËÏÂÂÚ Ô‡‚ËÎ¸ÌÛ˛ ‰Ë‡„‡ÏÏÛ ÇÓÓÌÓ„Ó: ‚ ‰Ë‡„‡ÏÏÂ ÇÓÓÌÓ„Ó V ( P, d , 2 ) („‰Â P = {p1 , …, pk }, k ≥ 2 – ÏÌÓÊÂÒÚ‚Ó „ÂÌÂ‡ÚÓÓ‚) Í‡Ê‰‡ﬂ Ó·Î‡ÒÚ¸ ÇÓÓÌÓ„Ó V(pi) ﬂ‚ÎﬂÂÚÒﬂ ÔÛÚ¸-Ò‚ﬂÁÌ˚Ï ÏÌÓÊÂÒÚ‚ÓÏ Ò ÌÂÔÛÒÚÓÈ ‚ÌÛÚÂÌÌÓÒÚ¸˛, ‡ ÒËÒÚÂÏ‡ {V ( pi ), …, V ( pk )} Ó·‡ÁÛÂÚ ‡Á·ËÂÌËÂÔÎÓÒÍÓÒÚË.ä‚‡ÁË‡ÒÒÚÓﬂÌËﬂ ÍÓÌÚ‡ÍÚ‡ä‚‡ÁË‡ÒÒÚÓﬂÌËﬂ ÍÓÌÚ‡ÍÚ‡ ÔÂ‰ÒÚ‡‚Îﬂ˛Ú ÒÓ·ÓÈ ÒÎÂ‰Û˛˘ËÂ ‚‡Ë‡ÌÚ˚ ‚˚ÔÛÍÎÓÈÙÛÌÍˆËË ‡ÒÒÚÓﬂÌËﬂ (ÒÏ. „Î. 1), ÓÔÂ‰ÂÎÂÌÌÓÈ Ì‡ 2 (‚ Ó·˘ÂÏ ÒÎÛ˜‡Â Ì‡ n).ÑÎﬂ ÏÌÓÊÂÒÚ‚‡ B ⊂ 2 Í‚‡ÁË‡ÒÒÚÓﬂÌËÂ ÔÂ‚Ó„Ó ÍÓÌÚ‡ÍÚ‡ dB ÓÔÂ‰ÂÎﬂÂÚÒﬂ Í‡Íinf{α > 0 : y − x ∈ α B}(ÒÏ.

ê‡ÒÒÚÓﬂÌËﬂ ÒÂÚË ÒÂÌÒÓÌ˚ı ‰‡Ú˜ËÍÓ‚, „Î. 28).ÅÓÎÂÂ ÚÓ„Ó, ‰Îﬂ ÚÓ˜ÍË b ∈ B Ë ÏÌÓÊÂÒÚ‚‡ A ⊂ 2 Í‚‡ÁË‡ÒÒÚÓﬂÌËÂÏ ÎËÌÂÈÌÓ„ÓÍÓÌÚ‡ÍÚ‡ Ì‡Á˚‚‡ÂÚÒﬂ ‡ÒÒÚÓﬂÌËÂ ÏÂÊ‰Û ÚÓ˜ÍÓÈ Ë ÏÌÓÊÂÒÚ‚ÓÏ, ÓÔÂ‰ÂÎÂÌÌÓÂ Í‡Ídb ( x, A) = inf{α ≥ 0 : αb + x ∈ A}.ä‚‡ÁË‡ÒÒÚÓﬂÌËÂ ÔÂÂı‚‡Ú‡ ‰Îﬂ ÍÓÌÂ˜ÌÓ„Ó ÏÌÓÊÂÒÚ‚‡ Ç ÓÔÂ‰ÂÎﬂÂÚÒﬂ Í‡Ídb ( x , y )∑b ∈B| B|.Ñ‡Î¸ÌÓÒÚ¸ ‡ÒÔÓÁÌ‡‚‡ÌËﬂ ‡‰‡‡Ñ‡Î¸ÌÓÒÚ¸ ‡ÒÔÓÁÌ‡‚‡ÌËﬂ ‡‰‡‡ – ‡ÒÒÚÓﬂÌËÂ Ì‡ 2, ÓÔÂ‰ÂÎÂÌÌÓÂ Í‡Í| ρ x − ρ y + θ xy |,ÂÒÎË x, y ∈ 2 \ {0}, Ë Í‡Í| ρ x − ρ y |,ÂÒÎË x = 0 ËÎË y = 0, „‰Â ‰Îﬂ Í‡Ê‰ÓÈ "ÎÓÍ‡ˆËË" x ∈ 2 ρ x – ‡‰Ë‡Î¸ÌÓÂ ‡ÒÒÚÓﬂÌËÂ ıÓÚ Ì‡˜‡Î‡ ÍÓÓ‰ËÌ‡Ú, Ë ‰Îﬂ Î˛·˚ı x, y ∈ 2 \{0} θ xy – Û„ÓÎ ÏÂÊ‰Û ÌËÏË (‚ ‡‰Ë‡Ì‡ı)˛èÓÎÛÏÂÚËÍ‡ ùÂÌÙﬁıÚ‡–ï‡ÛÒÎÂ‡èÛÒÚ¸ S – ·Û‰ÂÚ ÔÓ‰ÏÌÓÊÂÒÚ‚Ó 2, Ú‡Í ˜ÚÓ x1 ≥ x 2 − 1 ≥ 0 ‰Îﬂ Î˛·Ó„Ó x ∈ S.èÓÎÛÏÂÚËÍ‡ ùÂÌÙﬁıÚ‡–ï‡ÛÒÎÂ‡ ([EhHa88]) Ì‡ S ÓÔÂ‰ÂÎﬂÂÚÒﬂ Í‡Í x  y log 2   1 + 1  1   .  x 2 + 1   y2ÉÎ‡‚‡ 19. ê‡ÒÒÚÓﬂÌËﬂ Ì‡ ‰ÂÈÒÚ‚ËÚÂÎ¸ÌÓÈ Ë ˆËÙÓ‚ÓÈ ÔÎÓÒÍÓÒÚﬂı283íÓÓË‰‡Î¸Ì‡ﬂ ÏÂÚËÍ‡íÓÓË‰‡Î¸Ì‡ﬂ ÏÂÚËÍ‡ – ÏÂÚËÍ‡ Ì‡ ÚÂÎÂ T = [0, 1) × [0, 1) = {x ∈ 2 : 0 ≤ x1 , x 2 < 1},ÓÔÂ‰ÂÎÂÌÌ‡ﬂ Í‡Ít12 + t22‰Îﬂ Î˛·˚ı x, y ∈ 2, „‰Â ti = min{| xi − yi |, | xi − yi + 1 |} ‰Îﬂ i = 1,2 (ÒÏ.

Характеристики

Тип файла

PDF-файл

Размер

3,34 Mb

Материал

Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf

Тип материала

Книга

Предмет

(ММО) Методы машинного обучения

Высшее учебное заведение

МГУ им. Ломоносова

Список файлов книги

e.-deza_-m.m.-deza.-jenciklopedicheskij-slovar-rasstojanij-2008.pdf.rar

Е. Деза_ М.М. Деза. Энциклопедический словарь расстояний (2008).pdf

Поделитесь ссылкой:

Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.

Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.

Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.

Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.

Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.

Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.

Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.

Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.

Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.

Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.

Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.

Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.