Анализ на задача 4 – Глобус

---

Връчване на наградите от 4-ти кръг на конкурса по програмиране В редакцията на сп. PC Magazine Bulgaria се състоя церемонията по връчването на наградите на участниците, заели първите три места в четвъртия кръг по програмиране. Този кръг от конкурса беше подпомаган от фирма i:FAO, която състави оригинална задача и осигури апетитни награди за победителите. Наградите бяха връчени от г-н Свежен Василев, управител на i:FAO, който поздрави всеки един от участниците и им пожела да бъдат винаги така креативни в своите дейности и изрази своето задоволство от факта, че в България има толкова способни програмисти. Пламен Томов от София, чието решение бе оценено със 100 точки, получи видеокарта Gigabyte Radeon HD 3870. Изпълнителният директор на фирма Мусала Софт Делян Лилов връчи на победителя и почетна грамота.Петър Иванов от Шумен, чието решение се класира на второ място, получи звукова карта Creative X-Fi Extreme, а участникът, заел третото място, Александър Георгиев от София се сдоби с нова уебкамера с висока разделителна способност.Всички победители получиха и едногодишен абонамент за списание PC Magazine Bulgaria.

• Борис Караджов
• Development Manager
• i:FAO

Предложената в четвъртия кръг задача може да се разглежда като конкретен проблем на клъстерния анализ [1,2] с наложени специфични условия:

• Твърдо асоцииране на всеки град към точно един клъстер (за разлика от т.нар. fuzzy clustering[3]).
• Клъстери с формата на кръгове и с еднакъв радиус.
• Цeнтърът на всеки клъстер трябва да съвпада с някой от зададените градове. Съответно един възможен подход към решаване на проблема е адаптирането на някой от съществуващите алгоритми [4].

Например:

• Групиране в малки клъстери на базата на локална близост и след това проверяване на възможностите за сливането им в по-големи. Такова първоначалното групиране ще намали броя комбинации на втория етап, но може да доведе до изпускане на някои решения с малък брой области.
• Пълно обхождане на оставащите валидни кандидати за центрове с връщане (backtracking) при достигане на нерешима конфигурация. Например избира се център и радиус R на първата област. Всички оставащи градове извън областта, които са по-близо от R до град от тази област, не могат да бъдат кандидати за центрове на друга област. Ако освен това един такъв все още неасоцииран с област град се намира и по-далеч от R от всички оставащи кандидати за областни центрове, решение с направеното до този момент разбиване не може да бъде намерено и е необходимо връщане.

Заслужава да се отбележи, че избраната повърхност (сфера) играе роля само до момента, в който бъде изчислена симетричната матрица на разстоянията между всички двойки градове. Най-лесно това може да стане с изчисляване на декартовите координати на градовете при единичен радиус на сферата и определяне на разстоянието (или квадрата на разстоянието, което спестява операцията извличане на квадратен корен) по Питагоровата теорема.Алгоритъмът, който след това ги групира в области, може да се окаже приложим със същия успех към обекти, разположени върху равнина, цилиндър, тор и т.н.Във всички случаи задачата има тривиално решение, което се състои в обособяването на всеки град в самостоятелна област. Следователно добра стратегия е малко преди изтичане на лимита от 10 секунди програмата да генерира такова тривиално решение, ако по-добро не е било намерено.Тестовете се състояха от три групи:

• Реални координати на земни градове – тестове 1 - 4 и 16.
• Синтетични тестове – градове, равномерно разположени върху паралели, меридиани и др. – тестове 5 - 10. Тук заслужава да се отбележи тест №9, който демонстрира една „патологична“ конфигурация – градовете са равномерно разположени върху окръжност. В такъв случай максималният брой градове в една област е най-големият нечетен делител на техния брой. За конкретния тест със 720 града минималният брой области е 720 / 45 = 16.
• Полисинтетични тестове – градовете са случайно разположени във вътреш- ността на правилни геометрични фигури – тестове 11 - 15.

Линкове:

• 1. http://en.wikipedia.org/wiki/Cluster_analysis
• 2. http://www.fmi.uni-sofia.bg/fmi/statist/ Personal/Vandev/lectures/applstat2.pdf
• 3. http://en.wikipedia.org/wiki/Fuzzy_clustering
• 4. http://cs.joensuu.fi/pages/franti/vq/algorithms.htm

М.	Име	Град	Общо
1	Пламен Томов	София	100
2	Петър Иванов	Шумен	76.07
3	Александър Георгиев	София	69.385
4	Господин Бодуров	Бургас	46.334*
5	Йордан Маджунков	Плевен	36.611
6	Тодор Цонков	София	33.365
6	Деян Дойчев	Ст. Загора	33.365
7	Георги Пройков	София	32.356
8	Велислав Николов	София	26.331
9	Веселин Георгиев	София	25.952
10	Румен Христов	Шумен	16.682*
11	Божидар Пенчев	София	14.438
12	Стоян Георгиев	Сливен	0
12	Иван Тодоров	Бургас	0

* Точките на Румен Христов и Господин Бодуров бяха намалени с 50%, защото програмата чете от грешен входен файл.