 |
 |
 |
 |
 |
 |
         |
 |
 |
 |
 |
 |
Задача 1 от брой 10/2005 - ТИЧАНЕ - Анализ
Орлин Колев
Най-общо, целта на задачата е да разходим мечето по
дъската по колкото се може по икономичен път, за да ни стигне енергията за
по-дълъг път. Ако трябва да стигнем от квадратчето, където се намираме, до
някое друго, добре е това да стане по най-икономичния възможен път, за да можем
в новата позиция да имаме повече енергия, която после да използваме.
Ще използваме представяне на дъската като
ориентиран граф, в който реброто между всеки две съседни полета има тегло храната
във второто минус проходимостта на първото, тоест енергията, която печелим
(евентуално отрицателна) при преминаване от първото във второто квадратче.
В общи линии, алгоритъмът е следния:
1.
Правим текущата енергия 0, а текущата позиция –
началната.
2.
Ако текущата енергия минус проходимостта на текущата
позициия е по-малка от взетата с отрицателен знак максимална загуба на енергия
– край (не можем да излезем от квадратчето без енергията ни да падне под
допустимото).
3.
Намираме икономични пътища от текущото квадратче до
всички останали.
4.
От намерените пътища избираме този с най-малък разход на
енергия за единица дължина.
5.
Вървим по намерения път (извеждаме го и нулираме храната
по него).
6.
Обратно към стъпка 2.
Интересните моменти са точки 3 и 4.
За намиране на икономични пътища подходящо е да използваме алгоритъма на
Дейкстра за екстремален (в нашия случай – максимален, с най-голяма печалба на
енергия) път в граф. Ако ребрата в нашия граф са само отрицателни, алгоритъмът
ще намери най-икономичния път. В общия случай това няма да е така, но можем да
очакваме, че намерените пътища ще са достатъчно добри. С напредването ни по
дъската ние ще правим все повече ребра отрицателни, защото ще изяждаме част от
храната, така че с Дейкстра ще намираме все по-добри пътища до момента, в който
всички ребра са отрицателни и намерените пътища са вече оптимални.
Избирането на най-добрия измежду намерените пътища
е лесно, но трябва да се съобразим с една особеност. Възможно е да има много
икономичен път, който, обаче, води в труднопроходимо квадратче, излизането от
което би било много скъпо или дори невъзможно. Затова към цената на пътя, която
сме намерили, трябва да прибавим цената на излизането от крайната позиция.
Получената стойност делим на дължината на пътя и получаваме исканото число,
чрез което ще сравняваме пътят с останалите пътища.
Така написаното решение проявява една слабост,
която много ясно си проличава на следния тест:
·
дъска 32 на 32;
·
начална позиция (1; 1);
·
храна – навсякъде 1, освен в началното поле;
·
проходимост – навсякъде 1;
·
максимална енергия – 1.
При този тест пътят ни приключва в момента в който
стъпим във вече посетено поле. Очевидно, най-дългият възможен път е с дължина 1025
– обхождаме цялата дъска зигзагообразно или спираловидно. Така написаното
решение намира път с дължина около 150, което е доста лош резултат. Причината
е, че цената на пътищата от стартовото до всяко друго квадратче е 0, което
означава, че продължението се избира случайно. Как точно, зависи от детайли на
реализацията. Например използваната върху този тест програма намери път, който
стига до долния десен ъгъл на дъската приблизително по главния диагонал, с
което си затваря пътя до половината от дъската. След като направи така още
няколко пъти с оставащата част, обходената област от дъската остава доста
малка.
Намирането на най-икономичните пътища следи да не
посещава вече посетени полета (такава е същността на алгоритъма на Дейкстра),
така че намерените пътища са непресичащи се (освен когато единият се съдържа в
другия). По принцип, алгоритъмът избира най-добрия до момента път и оптимира по
него. В нашия пример всички пътища са еднакво добри и затова оптимирането се
получава на FIFO принцип, което
води до намирането на множество близки по дължина пътища. Ние бихме искали
пътищата да са съществено различни по дължина, за да може най-добрия да бъде
възможно най-дълъг. Бихме могли да променим използватана от алгоритъма оценка
за най-добър път, като вместо просто най-икономичния вземем този с най-малък
разход на единица разстояние, както правим когато избираме път измежду
намерените.
С тази оптимизация в пример, подобен на
разгледания, програмата ще се стреми да продължава най-дългия намерен до
момента път, което ще доведе до исканата по-голяма дължина на максималния път и
ще получим желания отговор 1025.
Тази промяна, обаче, решавайки един проблем,
създава друг. Оценката на пътищата
включва пресмятания с плаваща запетая, а тя се прави многократно, така че това
влошава силно скоростта на програмата (ако използваме целочислено деление,
загубата на точност ще е толкова голяма, че ще обезсмисли цялата оптимизация). Освен
това, понеже посочените две оценки на пътищата обикновено са близки, при
случайни тестове изменената по този начин програма не дава по-добри резултати
от тази с простото избиране на най-евтиния път, а е около пет пъти по-бавна.
Тъй като програмата в първия си вариант беше
достатъчно бърза (около 1 секунда на случаен тест 32x32), бихме могли
да пуснем първо първия вариант, а след това втория, и да вземем по-добрия резултат.
Естествено, ще засечем времето на изпълнение и ще излезем, ако не ни остава
време, за да завършим намирането на път. При това на по-малки тестове, а дори и
на някои 32x32, но с по-малко позволена загуба на енергия (или
специфични, като посочения по-горе), и двата варианта ще успеят да приключат и
ще вземем по-доброто решение от двата. В общия случай варианта с по-бързата
функция за сравнение ще се изпълни докрай, а другия – не, но дори и тогава той
би могъл да подобри стойтостта на първия.
Автор:
Орлин Колев
За въпроси можете да ни пишете на адрес: konkurs@musala.com.
Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.