Задача 1 от брой 10/2005 - ТИЧАНЕ - Анализ

В дадената задача, за да се намери най-доброто решение може да се направи пълно изчерпване и да се избере най-дългият възможен път. Това решение обаче е прекалено бавно и за определените ограничения не е приемливо.

Участниците в конкурса трябваше да измислят подходи, които да намират достатъчно дълги пътища тъй като оценяването е релативно и се прави спрямо най-добрия намерен резултат.

Орлин Колев, който зае третото място предлага подход, при който на всяка стъпка от ситуацията, в която е мечето се търси най-добър път из картата и се тръгва по него. Това се прави докато не може да се продължи. За намиране на пътищата може да се използва алгоритъмът на Дейкстра. Интересно е как да се оценява оптималността на пътищата. Най-тривиалният начин е оценяване по енергията, която печели мечето, когато мине по пътя. Въпреки, че алгоритъмът на Дейкстра при наличието на отрицателни ребра не винаги намира най-оптималния път, резултатие получени чрез него са достатъчно добри. Друг подход за оценяване предложен от Орлин Колев е по средната енергия, която се печели за едно квадратче от даден път. В повечето случаи този подход се справя подобно на споментия по-рано, но има тестове, при които полученият резултат е по-добър. Времевото ограничение позволява да се комбинират в едно решение и двете оценяващи функции. По-подробно за решението реализирано от Орлин, можете да прочетете в анализа му.

Алтернативен подход е след намирането на оптимален път да се прави ход само към първото квадратче от него. След което се прилага наново алгоритъма на Дейкстра. Така на всяка стъпка ще се изминава само първото квадрадче вместо целият път. С този подход може да се избегнат някои ситуации, при които пътят, който е оптимален закарва мечето в неизгодна позиция - такава, от която няма добро продължение. Правейки само по една стъпка, в даден момент може да се появи нов най-оптимален път и Мечо Пух да продължи по него.

Едно тривиално решение на поставената задача е да се използва рекурсия, за да се направи пълно изчерпване. За съжаление този подход работи твърде бавно за поставените ограничения. Рекурсията може да се ограничи откъм време за работа и да се извежда най-добрият резултат намерен до момента. Друга оптимизация е да се използва критерий, с помощта, на който да се определи в какъв ред да се обходят съседните квадрачета на позицията на Пух. Един начин е да се използва вече споменатият алгоритъм на Дейкстра. В дадена ситуация се намират оптималните пътища от текущото квадратче до всички други. За всяка от съседните позиции се определя най-добрият път, който започва с нея. След това съседните квадратчета се обхождат като се започне от най-оптималното и се завърши с най-неперспективното. Тук пак могат да се приложат различни подходи за оценяване. В доста от случаите това решение осигурява добри резултати. Освен това може да не се обхождат всичките съседни квадратчета, а само най-добрите две или три от тях.

Реализирайки трите метода описани по-горе в една програма се получава едно сполучливо решение. Алгоритмите трябва да бъдат изпълнявани в реда, в който бяха описани, съобразявайки се с факта, че първите два приключват сравнително бързо, докато третият използва цялото му предоставено време.

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

Интересен е и четвъртият реализиран подход. Там авторът използва обхождане в дълбочина. Дефинират се ситуации, които се определят от дължината на пътя изминат досега, моментната позиция и състоянието на картата. На всяка ситуация се съпоставя стойност, която се получава с помощта на хеш функция. За всяка такава стойност се помни с колко най-много калории е била достигната. Ако за хеш стойността на дадена ситуация резултатът е вече пресметнат и той е по-добър от моментния, се приема, че тази ситуация вече е била достигната с по-голяма енергия и няма смисъл рекурсията да продъжава по натакък. Така клоновете на обхождането се орязват.

Реализациите на подходите следят за изминалото време, за да се вместят в поставения времеви лимит. За подробно описание на решението на Веселин Георгиев можете да прочетете анализа му.

Вторият в класирането, Ивайло Бояджиев, предлага решение с обхождане, но с по-различен подход. В началото решението му се опитва да намери най-добрия път с дължина MAXP хода. Най-добър е пътят, при който е минимална разликата E1 – E2, където E1 е енергията за преминаване по даден път, а E2 е енергията, която Мечо Пух печели при преминаване по дадения път. Нека F[i][j][p][0] е изразходваната от мечето енергия за достигане на клетка (i,j) с p хода. А F[i][j][p][1] е придобитата енергия при изминаването на този път. Като са пресметнати стойностите за всички клетки с p хода, използвайки тези стойности могат да се намерят резултатите за всички клетки с p+1 хода. Ако в клетка (i,j) има храна и пътят с дължина p до някой от съседите му не преминава през клетката (i,j), то тази храна се взема от мечето. Ако обаче пътят вече поне веднъж е минавал през клетката (i,j) се смята, че тази храна вече е взета.

Когато се пресметнат стойностите за всички клетки с MAXP хода, се избира тази от тях, до която пътят е най-добър. За нея се изпълнява същата процедура както за началната клетка. Това се прави докато свърши времето за изпълнение или ако Мечо Пух не може да продължи.

В решението си Ивайло Бояджиев е поставил MAXP = 200.

Авторът предлага някои подобрения, които обаче не е резлизирал в решението си. Едното е да се пази за всяка клетка най-добрият път с p хода от всеки от съседите му. Това се прави, защото е възможно например до дадена клетка с p хода да се достига с еднакво добри пътища от различни съседи. Също така ако с MAXP хода може да се стигне до няколко клетки с еднакво добри пътища, които са минимални, може да се пробва на следващият етап от изпълненнието на алгоритъма да се тръгне от всяка от тях, като се направи рекурсия с връщане назад и се спира, когато изтече даденото време от 5 секунди.

За въпроси можете да ни пишете на адрес: konkurs@musala.com.

Supported by Musala Soft Ltd.

Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.