 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
         |
|
Анализ на Задача 6 от конкурса на Musala Soft & PC Magazine
Кръг Първото твърдение, което ще изкажем е, че за всяко естествено число N (N > 1) съществува единствен кръг удовлетворяващ условието на задачата - да е с възможно най-малък радиус и да съдържа всички N дадени точки във вътрешността или по контура си. Второто твърдение е, че търсеният кръг съдържа поне две точки от зададените по контура си. Няма да се спираме върху доказателствата на изказаните твърдения, а само върху техните приложения в нашата задача. Нека с t1, t2, t3… tN-1, tN означим точките съответстващи на N-те радиостанции; нека за всяко цяло число i в интервала [2,N] с Ti означим множеството от първите i на брой дадени точки; а с Ri означим най-малкия кръг, съдържащ всички точки от множеството Ti във вътрешността или по контура си. От първото твърдение следва, че Ri е еднозначно определен. За i = 2 единственият кръг, за когото става дума във определението е този с диаметър отсечката свързваща t1 и t2. Нека 2 < i < N. Ако кръгът съдържащ първите i точки съдържа и (i+1)-та точка, то кръговете съдържащи първите i и първите (i+1) точки съвпадат, т.е. ако ti+1 е от Ri, то Ri+1=Ri. Ако кръгът съдържащ първите i точки не съдържа (i+1)-та точка, то (i+1)-та точка е от контура на кръга, съдържащ първите (i+1) точки, т.е. ако ti+1 не е от Ri, то ti+1 е от контура на Ri+1. Няма да се спираме върху доказателството на верността на последното твърдение предвид трудността му, но всеки читател може да се убеди в нея с няколко малки примера. Така можем да напишем следното решение на задачата, използвайки псевдокод, което по зададено множество TN намира най-малкия кръг съдържащ всяка точка от TN: A1. Минимален кръг (TN) 1: Нека R2 е най-малкият кръг съдържащ точките t1 и t2 2: За i от 3 до N ако ti е от Ri-1, то изпълни 2.1, иначе 2.2 2.1: Ri = Ri-1 2.2: Ri = Минимален кръг със зададена една точка от контура (Ti-1,ti) 3: RN е търсеният кръг Очевидно проблематичната стъпка в този алгоритъм е 2.2, за която ни трябва помощен алгоритъм, който намира Ri знаейки, че ti е от контура на кръга. Да приложим още веднъж използваната вече идея. Ще специфицираме алгоритъм, който по зададено множество TM и точка v, намира най-малкия кръг Q съдържащ всяка точка от TM във вътрешността или по контура си, и съдържащ v по контура си: A2. Минимален кръг със зададена една точка от контура (TM,v) 1: Нека Q1 е най-малкият кръг съдържащ точките t1 и v 2: За i от 2 до M ако ti е от Qi-1, то изпълни 2.1, иначе 2.2 2.1: Qi = Qi-1 2.2: Qi = Минимален кръг с две зададени точки от контура (Ti-1,v,ti) 3: QM е търсеният кръг Отново проблематичната стъпка е 2.2, затова и този път използваме помощен алгоритъм, който по зададено множество TL и точките v1 и v2, намира най-малкия кръг P съдържащ всяка точка от TL във вътрешността или по контура си, и съдържащ двете точки (v1 и v2) по контура си: A3. Минимален кръг с две зададени точки от контура (TL,v1,v2) 1: Нека P0 е най-малкият кръг съдържащ точките v1 и v2 2: За i от 1 до L ако ti е от Pi-1, изпълни 2.1, иначе 2.2 2.1: Pi = Pi-1 2.2: Pi = кръгът съдържащ ti, v1 и v2 по контура си 3: PL е търсеният кръг Трите точки (ti, v1 и v2) в стъпка 2.2 на А3 са различни, защото в противен случай нямаше да се изпълни стъпка 2.2, а стъпка 2.1. Кръгът съдържащ три различни точки по контура си е еднозначно определен. С това завършва описанието на алгоритъма за построяване на най-малкия кръг съдържащ N точки в равнината. Остава да видим каква ще е ефективността му. Очевидно е, че в хипотетичен най-лош случай програмата на всяка стъпка 2 на алгоритъма А1 ще влиза в А2, а на всяка стъпка 2 на алгоритъма А2 ще влиза в А3. Ако такъв най-лош случай съществува, сложността на алгоритъма ще бъде с порядък О(N3). Да се посочи такъв случай практически е много трудно. Достатъчно лош случай, обаче, е ако точките са наредени последователно върху права линия. Тогава на всяка стъпка 2 от А1 програмата ще влиза в А2, а А2 никога няма да извиква А3, което ограничава сложността до О(N2). При зададените ограничения за N, това е неприемливо. Обичайна практика в такива случаи е да се разбърка последователността от точки, за да се изключат с голяма вероятност неприятните за алгоритъма подреждания. Нека да използваме произволна наредба на дадените ни N точки. Алгоритъмът Минимален кръг с две зададени точки от контура (TL,v1,v2) винаги работи с линейна сложност спрямо броя на точките в множеството TL - сложност О(|TL|). Да разгледаме множеството от точки Ti и точката v. Нека S е най-малкият кръг съдържащ всяка точка от Тi и имайки v по контура си. Да си представим, че махаме една точка от Ti. Кога S ще се промени? Това ще се случи само когато имаме две точки от Ti по контура и махната точка е от тях. Следователно вероятността махнатата точка да промени кръга е най-много 2/i. От тук следва, че алгоритъмът Минимален кръг със зададена една точка от контура (TM,v) се очаква да работи за време от порядъка на  което е линейно спрямо броя точките в множеството TM. Аналогично се вижда, че очакваното време за работа на алгоритъма Минимален кръг (TN) също е линейно спряно броя на дадените точки. От всичко казано се вижда, че ако наредим точките по произволен (случаен) начин и построим кръга по указания начин ще получим бързо решение в огромна част от случаите. |
За въпроси можете да ни пишете на адрес: konkurs@musala.com.
Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.