Анализ на задача 2 - Ерудит
Резултати от втория кръг на конкурса по програмиране
Във втория кръг на конкурсa по програмиране на PC Magazine Bulgaria и Мусала Софт спечели Александър Георгиев от София, който получи награда, предоставена от редакцията на списанието – най-новата видеокарта на Ati AMD Asus Radeon HD 3850, както и едногодишен абонамент. Наградата беше връчена от главния редактор на PC Magazine Bulgaria Тервел Няголов, а Делян Лилов, изпълнителен директор на Мусала Софт, връчи грамота на победителя. Във втория кръг станахме свидетели на особено трудна задача. Това се потвърждава от броя на участниците, които успяха да предадат работещи решения в срок, и от разпределението на резултатите.
Оценяването стана посредством десет двойки тестове, като във всеки нечетен тест бяха използвани истински думи, а в четните – произволни низове. Тестовете влизат в четири групи. Първа група се състои от два малки по всички показатели теста. Следват две групи от тестове съответно с относително малка дъска и с относително голяма дъска спрямо размера на речника. Последните шест теста са максимално тежки по всички показатели.
Основните трудности идват освен от необозримия брой възможни ходове, от големите размери на дъската и от големия речник. За да може да се напише успешна евристика, която да играе, трябва първо да бъдат решени тези проблеми. Много удобни инструменти за тази цел предлага хеширането[1]. Могат да се хешират всички думи в речника и по този начин да се извърши особено тежката и често повтаряна операция за проверка дали даден низ на дъската е позволен. С хеш таблица може да се представи и самата дъска, което ще предостави константни времена за достъп и необходима памет, зависеща линейно от поставените букви (а те са най-много един милион), вместо от размерите на дъската (достигащи до 231). Качеството на реализация на тези аспекти от задачата е особено важно за цялостния резултат, защото по-бързите инструменти ще оставят повече време за оптимизиране на отговора.
Самото решение е най-удачно да се строи с помощта на различни евристични алгоритми. Ще разгледаме двата подхода, използвани от участниците в този кръг, спечелили най-много точки – Александър Георгиев и Веселин Георгиев.
Решението на Александър Георгиев се възползва от големите ра змери на дъската, като се концентрира върх у избиране то на подходящите думи вместо върху разположението им. За целта всяка следваща дума се пресича с предишната, като се разполага перпендикулярно на нея. Тази стратегия елиминира голяма част от основните трудности – много тежката проверка дали не сме образували низ, който не е дума, както и съхранението на цялата дъска стават излишни. Така почти цялото време остава за лакомия алгоритъм, който избира думите. Този подход осигури победата на Александър Георгиев, като му донесе максимални точки във втората половина от тестовете. Макар че в групата от тестове с малка дъска съвсем не се справи толкова убедително, те не бяха достатъчни останалите да го настигнат.
Решението на Веселин Георгиев, от друга страна, е по-балансирано по отношение стремежа да използва рационално мястото на дъската и да избира добри думи. Както се вижда, то носи доста повече точки на първите осем теста, но не е толкова постоянно в останалите, колкото това на победителя. Алгоритъмът се пуска няколко пъти с различни параметри и накрая се избира най-доброто решение. На първия ход се отделя особено внимание, поради голямата му важност. Думата се избира посредством трите евристики – дължина, носени точки и брой думи, които могат да се получат от нея. При всяко пускане на алгоритъма се избират произволни тежести на трите евристики в интервала [-1, 1]. Това позволява в някои случаи, определенихарактеристики да се превръщат в негативни качества. На всяка следваща стъпка се строи малка група думи, за които има достатъчно букви, и се проверява дали някоя от тях може да се постави някъде на дъската. Тази проверка е особено бавна, но позволява доста рационално използване на свободното пространство.
