Състезателна система | ||||||||||||||
|
Задача 3 от брой 12/2004 - ПОДАРЪК - Анализ Повечето състезатели
вероятно са забелязали, че не може да се напише решение, което да работи
оптимално винаги. Причината за това е, че в дадена карта не е ясно от къде
започва търсенето на пътя към целта (партито). За да покажем верността на
твърдението ни, нека разгледаме възможно най-опростения пример. Ако всички видими
клетки около началната са еднакви и една от съседните четири е целта, то
програмата може да я достигне с един ход, но не знае кой е този ход.
Следователно не може да се направи само един ход, с който да си гарантираме
достигането на целта. Ето защо, от участниците се очакваше да напишат решения,
които работят колкото се може по-добре за колкото се може повече тестови
примери. Една добра програма трябва да се стреми към намаляване броя на ходовете
в общия случай. Да разделим задачата на две
– първо да разберем къде сме в момента, след което да се придвижим възможно
най-бързо от текущата си позиция до целта. Втората част се реализира лесно
използвай алгоритъм намиращ най-късите пътища от целта до всички позиции на
картата (например, алгоритъм на Dijkstra за най-къси пътища в граф от един
връх до всички останали). Така, когато разберем къде сме били в началото и
съответно къде сме сега, ще можем веднага да се придвижим по най-късия възможен
път от текущата позиция до целта. Сега остава да разберем началната/текущата
позиция – двете са взаимно определящи се, защото поредицата от направени ходови
ни дава как сме се изместили спрямо началната позиция и съответно как да се
върнем до нея, ако знаем текущата. Нека да приемем, че търсим
къде е текущата позиция в картата. За целта поддържаме списък с възможните текущи
позиции – отначало това са всички проходими полета, които имат същата околност
като тази, която се „вижда” около началната позиция. На всяка стъпка избираме
посока, в която да се движим, гледайки попътните неизвестни позиции. Гледането
не ни струва нищо и няма причина да не видим какви са неизвестните позиции около
нас, защото те увеличават нашето знание за картата, а от там и възможността да
определим текущата позиция. Изборът на посока, в която да се движим, зависи от реализирания
алгоритъм (или комбинация между тях). Може да изберем:
Така след няколко стъпки на алгоритъма ще сме разбрали еднозначно къде е
началната и съответно къде е текущата позиция, и ще можем лесно да се придвижим
до целта. Ето накратко идеята на Ростислав Руменов, заел второ място на 0.741
точки от победителя: „След като прочета картата, знам какво съдържа тя. После
за всяка клетка която не е "нула" намирам минимално време, за което
ще се стигне до партито. След това правя нещо като вълна, в която първоначално
са всички клетки и на всеки ход на вълната след като огледам терена премахвам
някои от тези клетки и така поддържам списък с възможни местоположения, който все
повече и повече намалява. Изборът на ход правя като вземам някое от възможните
местоположения и избера посоката, с която най-бързо ще стигна до партито, като
си отбелязвам клетки, през които съм минал защото не е рационално да минавам
пак през тях.” Тестовите примери бяха
избрани така, че да поставят програмите на състезателите при различни условия и
да се провери доколко те правят предварителен анализ на картата и доколко
тръгват наслуки към целта. Ето кратки описания за осемте тестови примера (gif изображения, визуализиращи
самите карти, може да намерите в архива с тестове). Карта 1. Карта с 5 идентични стаи. Тъй като за три от стаите верният
път е наляво, а за две – надясно, логично би било решенията да тръгнат първо
наляво. Отново, тъй като за три от стаите верният път е нагоре, а за 2 –
надолу, програмите трябва да тръгнат нагоре. Решенията на голяма част от
участниците успяха да намерят оптималния път за достигане до целта. Карта 2. Карта с 8 идентични стаи. Тук само решението на Ростислав
Руменов намери оптималния отговор, останалите решения се представиха минимум
два пъти по-зле. Карти 3 и 4. Целта на тези две карти беше да се провери доколко
участниците правят предварителен анализ на картата. Вижда се, че има три
еднакви стаи, които се различават само с едно квадратче. Ако някой състезател
тръгне първо надолу и програмата му работи детерминирано, т.е. за еднакви
входни данни получава еднакви изходни данни и няма елемент на случаен избор, то
той ще загуби време. Причината затова е че тест 3 и тест 4 представляват
еднакви карти, но с различни начални и крайни позиции. По този начин ако след
като състезателят е вървял надолу той тръгне надясно, ще получи добър отговор
на единия, но слаб на другия, и обратно. Затова, с цел да се спести време, една
“умна” програма би трябвало да анализира картата около себе си, а именно да
разбере в коя от трите стаи се намира чрез ходове наляво и един ход нагоре.
След това, използвайки алгоритъм на Dijkstra, да намери най-краткия път до
целта. Карта 5. Празна карта. Резултатите варираха от 255 до 951, но никой
състезател не намери най-доброто решение. Карта 6. При тази карта липсва моментът на определяне на
местоположението по картата, защото Мечо Пух се намира в квадратче, чиято
околност е уникална. Така остава само да се изпълни алгоритъмът на Dijkstra, с
които да се определи оптималният път до партито. Въпреки това имаше програми,
които не намират оптималното решение. Карта 7. Един малък квадрат 3 на 3 е размножен 3 пъти по
хоризонтална и 3 по вертикала, формирайки квадрат 9 на 9. Този квадрат е
размножен много пъти по случаен начин върху картата, а партито се намира в
долния десен ъгъл на картата. Тук има два подхода за решаване – първо да се
определи местоположението на Пух и после да се изпълни алгоритъма на Dijkstra,
или направо да се тръгне към партито, т.е. да се върви винаги надолу и надясно,
понеже следвайки тази логика със сигурност ще се стигне до целта ( както се
вижда, по картата няма препятствия). Карта 8. Също както на карта 7 е получен квадрат 9 на 9, от който
после е получен един по-голям правоъгълник, който пък е размножен много пъти.
Така по картата има много еднакви участъци. Тук само програмата на Васил Жеков
единствена дава далеч по-добър отговор от програмите на останалите състезатели. Победител в кръга е Деян
Чакъров от София с 82.454 точки. Честито! За въпроси можете да ни пишете на адрес: konkurs@musala.com. Copyright 2000-2010 by Musala Soft Ltd. All rights reserved. |