VIII конкурспо програмиране<br> PC Magazine Bulgaria и Musala Soft Ltd.
Категория: Интернет
неделя, 10 Февруари 2002 0:00ч
Проблемът за намиране на решение, когато множеството от точки отговаря на някои допълнителни условия, е изследван от математическа гледна точка (включително и с участието на българския учен Христо Джиджев). Например в статията “A Linear-Time Randomized Algorithm for the Bounded Voronoi Diagram of a Simple Polygon” от R. Klein и A. Lingas се предлага алгоритъм със сложност O(n) за следната задача: дадено е множество от точки, които образуват неизроден (несамопресичащ се и несамодопиращ се) многоъгълник; да се намери диаграма на Вороной за вътрешността на многоъгълника. Очевидно този алгоритъм решава нашата задача, в случай че търсената най-отдалечена точка е във вътрешността на изпъкналия (и следователно неизроден) многоъгълник. В случай че търсената точка е извън многоъгълника, не е трудно да се докаже, че това ще бъде точка, лежаща на страна на правоъгълника и това ще е или някой от върховете му или пресечна точка на контура със симетрала на страна на многоъгълника. Лесно се вижда, че и в този случай решението се намира със сложност O(n). Решението на нашата задача е или вътрешно (за многоъгълника) най-отдалечената или външно най-отдалечената точка. Така получаваме решение със сложност O(n).
Трудността на такова решение се състои в имплементацията на алгоритъма на R. Klein и A. Lingas, който не е никак лесен за разбиране и програмиране. Затова в авторското решение се прави опит да се намери по-лесен начин за получаване на вътрешно най-отдалечената точка, без скоростта на алгоритъма да пострада сериозно. Да разгледаме функцията f(P)=mini=1,2,...,n d(P,Ai), където d(P,Ai) е разстоянието от точка P до точка Ai - една от зададените точки. В задачата се търси такава точка P от правоъгълника, за която f(P) е максимално. От теоретичните изследвания на проблема става ясно, че функцията f(P) е непрекъсната. При условие, че точката с търсените свойства е единствена, за намирането й може да се използва класическият евристичен подход, известен като “изкачване на хълм” (hill climbing). Избираме начална точка P(x,y) във вътрешността на многоъгълника по известния начин (x=(x1+ x2+...+ xn)/n, x=(y1+ y2+...+ yn)/n) и стъпка на изкачването S (в началото достатъчно голяма). На всяка стъпка на изкачването избираме M точки, разположени равномерно по окръжността с център P и радиус S (един добър вариант е М=8, разположени в основните посоки - нагоре, нагоре-вдясно, надясно и т.н.). От всички такава точки избираме точка P’ такава, че стойността f(P’) е максимална. Ако f(P’)>f(P), заменяме P с P’ и продължаваме изкачването. Ако не, намаляваме стъпката на половина. Ако стъпката е станала по-малка от Z/2 - намерили сме точка с исканите свойства. В противен случай отново се връщаме към основната стъпка на изкачването.
Както при всеки евристичен алгоритъм и при този много важно е да се подберат числата M и S. Например много голямо M ще доведе до по-бързо налучкване на посоката на изкачване, но ще забави пресмятанията, докато по-малко M ще доведе до бързо пресмятане, но по-голямо лутане в избора на посока за изкачване. Много малко M може дори да доведе до невъзможност да се намери посоката на изкачване. Подобни съображения могат да се формулират и за избора на S. Както при всеки евристичен алгоритъм и при този сигурно могат да се намерят редица други съображения за ускоряване на работата му. Едно от тях е да се намали броят на точките, от които се намира най-близката.
След извършената проверка на решенията безспорен победител в кръга е миналогодишният участник във финалния кръг Владимир Молотков. Надяваме се победителят да направи и изпрати коментар на решението си, който с удоволствие ще публикуваме в сайта на конкурса www.konkurs.musala.com.
