Musala Soft Logo Конкурс по програмиране на Musala Soft и PC Magazine Bulgaria PC Magazine Bulgaria Logo
  Състезателна система
Сезон 2010 - 2011
Сезон 2009 - 2010
Сезон 2008 - 2009
Сезон 2007 - 2008
Сезон 2006 - 2007
Сезон 2005 - 2006
Сезон 2004 - 2005
Сезон 2003 - 2004
Сезон 2002 - 2003
Сезон 2001 - 2002
Правила
Задача 1
Задача 2
Задача 3
Задача 4
Задача 5
Задача 6
Класиране
Финален кръг
Сезон 2000 - 2001
Задача 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.