Задача 5 - ПРОТИВОПОЖАРНА ИНСТАЛАЦИЯ - Анализ |
|
Петата задача от нашия конкурс се оказа истинско
предизвикателство, както за участниците, така и за Журито на конкурса. Да започнем
с класическата задача: дадено е множество от точки, лежащи във вътрешността или
по контура на зададен правоъгълник; да се намери точка, максимално отдалечена от
зададено множество точки, която се намира в правоъгълника. Тя ни отвежда до известна
теория - диаграмите на Вороной. Една много добра статия от Franz Aurenhammer и Rolf
Klein, посветена на темата диаграми на Вороной може да намерите на http://wwwpi6.fernuni-hagen.de/Publikationen/tr198.pdf.
Предложеният в статията алгоритъм решава задачата със сложност O(n.log
n), за произволно множество от n точки, с много голяма константа,
която умножава n.log n. В конкурсната задача, обаче, става дума не
за произволно множество от точки, а за точки, които образуват изпъкнал многоъгълник.
За този случай алгоритъмът с използване на диаграмата на Вороной ще даде решение,
което трудно ще се вмести в ограничението по време, поставено от Журито. Проблемът
за намиране на решение, когато множеството от точки отговаря на някои допълнителни
условия е изследван от математическа гледна точка (включително и с участието на
българския учен Христо Джиджев). Например, в статията “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. Както при всеки евристичен алгоритъм и при този сигурно могат да се намерят редица
други съображения за ускоряване на работата му. Едно от тях е да се намали броя
на точките, от които се намира най-близката. След извършената проверка на решенията,
безспорен победител в кръга е миналогодишния участник във финалния кръг Владимир
Молотков. Ето какво казва победителят за своето решение тук. |
Анализи на решения изпратени от участници:
|
Владимир Молотков
|
За въпроси можете да ни пишете на адрес: konkurs@musala.com.
Supported by Musala Soft Ltd.
Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.
|