 |
 |
 |
 |
 |
 |
         |
 |
 |
 |
 |
 |
Задача 1 от брой 10/2005 - ТИЧАНЕ - Анализ
Веселин Георгиев
За дадената задача не съществува “най-добро” решение, тъй като единственият
алгоритъм, който гарантира получаване на оптималния отговор
(най-дългия път) е пълното изчерпване. Дори и да се приложат
оптимизации на изчерпването, то в голяма част от
случаите то няма да успее
да приключи работа при зададените
ограничения.
На такива задачи практиката
показва, че е подходящо да се
изпробват много различни методи за решение. Обикновено те не гарантират
оптимален отговор, но затова пък
работят задоволително бързо. В моето
решение има точно 4 различни подхода за решаването
на задачата.
Първият, Greedy(), няма нужда да
разисквам в детайли. Ако обозначим с goods[N][M] масивът със стойностите на лакомствата, а със spend[N][M] – масивът с изразходваните калории за прекосяване, то Greedy() избира този съсед, при
който goods[y][x] – spend[y][x] е максимално.
Разбира се, взима се
под внимание дали вече не
е минавано през квадратчето. След което прави избрания ход и отново, по “лаком”
начин, избрира следващия.
Вторият метод е RandomWalk().
Той представлява хибрид между “лакомо” и “случайно” решение. Избора на ход се
прави по следния начин. Четирите съседа се сортират по
“апетитност” като се ползва същия
критерий както при Greedy(). След което,
в зависимост от една промелнива, наречена tolerance, се взимат тези съседи,
които са с не повече от
tolerance точки от най-”апетитния” съсед. От така избраните съседи се взима
произволен и се прави съответния ход.
Държанието на този алгоритъм
силно зависи от tolerance. При малки стойности
на промелнивата, метода се държи
като чисто Greedy, а при големи – като
чисто “случайно-вървящо” решение. Изпробват се всички възможности за tolerance от 1 до 60.
Проверката ми показва,
че тези два
метода не дават по-добри резултати от изчерпването
на нито един
тест, използван от журито, но
в голяма част от тестовете дават
еднакви резултати, което е добре за
методи, работещи около 0.1 секунда, сравнени с изчерпването, което аз съм
ограничил до 3 секунди.
Третия метод е BFS().
Идеята е подобна на изчерпващо
търсене в ширина, с една съществена разлика. И тя е следната: Ако до
едно и също квадратче стигат два пътя с еднаква
дължина и еднаква стойност остатъчни калории, те се
считат за еднакви (макар, че може да
не са – например,
ако картата с неизядените квадратчета е различна). Ето и псевдокод на алгоритъма:
// situaciq
::= poziciq + karta s izqdeni lakomstwa + ostavashti kalorii
P,
Q – opashki ot situacii
A[N][M]
– masiv s naj-dobrite kalorii do wsqka kletka
P[0]
= nachalnata_situaciq;
dyljina_na_nameriniq_pyt
= 0
while
(P ne e prazna) {
Q
stawa praznata opashka
Zarejdame
kletkite na masiva A s -infinity
while
(P ne e prazna) {
P.pop(S);
if
(S e kraina situaciq) {
if
(dyljina_na_namereniq_put > nai_dobra_dyljina) {
saved_best
= S
}
}
else {
za_wseki_sysed
D na S {
if
(kaloriite_s_koito_stigame_v_D > A[D.y][D.x]) {
if
(A[D.y][D.x] = -infinity)
Q.push(D);
else
{
namirame
elementa v Q, koito e podobril
A[D.y][D.x]
predniq pyt i go zamestwame s
D
}
podobrqwame
A[D.y][D.x]
zapisvame
che v (D.y, D.x) sme doshli ot S
}
}
}
}
P
= Q
dyljina_na_namereniq_put
= dyljina_na_namereniq_put+1
}
vuzstanovqvame
nai-dobriq pyt, polzwaiki zapisanoto saved_best
Последният метод е Backtrace().
Иначе казано – търсене в дълбочина. За разлика от предния метод обаче,
пази се пълен
запис на ситуацията и така два пътя, които
се различават само в картата с изядените лакомства се считат за
различни и се разглеждат отделно.
Търсенето обхожда съседите в ред, съобразен с критерия, ползван от Greedy(),
почва се от най-”апетитния” съсед и се върви
към най-безперспективния. За да не се
разглеждат две еднакви ситуации (които съвпадат 1:1) се използва хеш-таблица
със затворено хеширане. Методът за хеширане е заимстван
от някой реализации на шах-алгоритми
и представлява следното:
Създават се 4 таблици,
xor_X[M],
xor_Y[N], xor_Length[MAXLEN]
и xor_pos[N][M]. Тук MAXLEN се
избира да съвпада с най-дългия възможен път, който
за тази задача
е 32768. Тези таблици се запълват със случайни
числа. Хеш ключа се изчислява
като побитово изключващо или (xor) на xor_X[<текущо
x>], xor_Y[<текущо
y>], xor_Lenght[<текуща
дължина на пътя>] и xor_pos[y][x] за всеки (y, x), които още не
са изядени. Полученото
32-битово число е напълно случайно, но съответства
еднозначно на ситуацията, като две сходни ситуации
(при съвсем малки разлики) ще имат напълно
различни хеш-ключове.
Така полученият ключ се дели с остатък
на големината на хеш-таблицата. Тази големина е просто число, подбрано така, че хеш-таблицата
да заема около 230 Мегабайта оперативна памет. Всеки елемент от
хеш-таблицата представлява следната структура:
typedef struct{
unsigned stop_key;
int energy;
} hash_entry;
където energy пази с колко остатъчни
калории може да се стигне
до тази ситуация,
а полето stop_key се използва за
справяне с колизиите. Това се прави по
следният начин. При разглеждане на ситуация, освен първия ключ, който
в последствие се взима под модул
големината на таблицата, се прави
и втори ключ. Вторият ключ се
създава по абсолютно същият начин, само че
се използват различни таблици със случайни числа
(т.е. за всяка таблица xor_...[...] има две
версии – едната се ползва за
първото хеширане, другата – за второто).
Вторият ключ няма нищо
общо с първия и именно той се
записва в stop_key. Идеята на stop_key е, че ако две
ситуации са различни, но са
съвпаднали по първия ключ (колизия),
шансовете са изключително малки те да съвпаднат
и по втория ключ (като вероятността
за съвпадение е под 2-60). В началото
хеш таблицата се запълва с нули,
като хеширащата функция е модифицирана така, че никога
не създава ключове със стойност
0. Това позволява да се разпознават “незапълнените” клетки в хеш-таблицата. Ако се е получила
“лоша” колизия – съвпадащ първи и несъвпадащ втори ключ – няма какво
да се прави
– рекурсията продължава напред.
Сега, когато изчерпването
стигне до ситуация, която съвпада по първи
и по втори ключ в хеш таблицата,
алгоритъма приема, че такава ситуация
вече е разглеждана и в зависимост от полето
energy (ако то е по-голямо или равно
на текущо оставащите калории) рекурсията може да се “отреже”.
Вкарани са и някои други оптимизации,
като например, че хеширането не
се прави на всяко извикване
на рекурсията (защото то е с тежест
N*M операции), а се пазят изчислени двата ключа и при
преминаване в друга ситуация само се
un-xor-ват старите x, y,
length и се xor-ват новите (използва се изключително свойството, че (A xor B) xor B = A).
Това е подробно решението ми. Greedy() и RandomWalk() вървият без ограничение по време. BFS()
е отрязан на 1.2 секунди, а на Backtrace()
му се отпускат
3 секунди. Ако се поиграе с тези ограничения, вероятно могат да се постигнат
по-добри резултати. BFS() е по-бързо от Backtrace() в 7 тестови примера, по-бавно в 2 теста и са равни в останалите
11 теста.
Автор: Веселин Георгиев
За въпроси можете да ни пишете на адрес: konkurs@musala.com.
Copyright 2000-2010 by Musala Soft Ltd. All rights reserved.