Алчни алгоритми

---

Съществуват редица задачи, главно оптимизационни, при които се търси най-доброто решение измежду множество възможни. Най-елементарният подход в този случай е търсенето с връщане, при което систематично се пораждат и разглеждат всички решения на задачата (не непременно оптимални) и измежду тях се избира най-доброто. Очевидно това не винаги е практически възможно, особено когато броят на възможните решения е огромен (а би могъл да бъде и безкраен). Често нещата се влошават допълнително от евентуалното многократно пораждане на някои от решенията. Понякога това може да се избегне, като се прило-жи методът на динамичното оптимиране, но за съжаление последното е свързано с необходимост от достатъчно памет за запазване на резултатите, а и не винаги е възможно (съществуват някои необходими условия: като оптимална подструктура и др.). Друг възможен (и далеч по-радикален) изход предлагат евристичните алгоритми: те се насочват към един от всичките подслучаи на задачата и решават единствено него, с надеждата, че той ще се окаже правилният. По-долу ще разгледаме специален вид евристични алгоритми: алчни алгоритми. Основният принцип при тях (както подсказва и самото им име) е, че се насочват винаги към най-добрия за момента избор, погледнато локално. Съвсем естествено на по-късен етап може да се окаже, че този избор не е бил най-добрият, погледнато глобално.
Алчните алгоритми се съставят лесно, съответната реализация на алгоритъма не е сложна и единственият недостатък е, че понякога не гарантират правилното решение. Последното обаче не намалява ползата от тях - за евристичните алгоритми (и в частност за алчните) е характерно, че бързо успяват да намерят решение, близко до оптималното. В много практически задачи е невъзможно да се изследват всички случаи и често съставянето на алгоритъм, който намира с 5% по-лошо решение от оптималното, се счита за успех, сравнено с алтернативата за (почти) безкрайно и безперспективно претърсване за истинско оптимално решение.
Ще илюстрираме как алчните алгоритми се прилагат върху някои конкретни примери. Да започнем със следния проблем:
Задача 1: Да се намери начин за получаване на дадена сума m (m е естествено число), като се използват минимален брой банкноти, с номинали от множеството C = {a1, a2, ..., an}. Например за българската национална валута стойностите на банкнотите са 1, 2, 5, 10, 20 и 50 лева.
Да разгледаме следния алгоритъм:
1) Инициализираме s = 0.
2) Намираме банкнотата i с максимална стойност ai (aiОC) такава, че s + ai Ј m.
2.1) Ако няма банкнота, за която s + ai Ј m, следва, че задачата няма решение. Край.
2.2) Иначе вземаме банкнотата i и увеличаваме s с ai.
2.2.1) Ако s = n, следва, че задачата е решена. Край.
2.2.2) Ако s < n, още не сме получили цялата сума и повтаряме стъпка 2).
Така например за сумата 298 лева ще бъдат избрани последователно пет банкноти от по 50 лева, две от 20, една от 5 и по една банкнота от два и един лев (общо 250 + 40 + 5 + 2 + 1 = 298).
Очевидно описаният алгоритъм отговаря на критериите за алчен алгоритъм: на всяка стъпка той избира максималната по стойност банкнота, като по този начин се стреми да постигне възможно най-бързо търсената сума. В конкретния пример той намира оптималното решение на задачата. (Защо?)
За съжаление не съществуват достатъчно общи схеми за това какви да бъдат номиналите на банкнотите, за които да може да се твърди, че алчният алгоритъм ще работи правилно за всяка сума. Да разгледаме случая, при който възможните стойности за банкноти са 2, 5, 20 и 30 и искаме да получим сума 40. Алчният алгоритъм първо ще избере банкнота от 30 (максималното възможно), след което ще избере две банкноти по 5, т. е. общо 3 банкноти. Очевидно обаче съществува и по-добро решение: две банкноти по 20. Освен че може да не намери оптималното решение, възможно е алчният алгоритъм изобщо да не намери решение. Така например, ако искаме да получим сума 6: след банкнотата със стойност 5 пред алгоритъма не остава никаква възможност за следващ избор (а сумата все пак може да бъде получена с 3 банкноти от по 2 лева). Все пак нещата не винаги са толкова лоши и съществуват редица задачи, при които може да се покаже, че алчният алгоритъм винаги намира правилното решение.
Да разгледаме друга задача: Древните египтяни са използвали означение само за дробите с числител единица. Всяка друга дроб p/q представяли и записвали като сума от такива дроби. Например 7/9 може да се представи по някой от следните начини:

7/9 = 1/3 + 1/3 + 1/9
7/9 = 1/2 + 1/4 + 1/36
7/9 = 1/9 + 1/9 + 1/9 + 1/9 + 1/9 + 1/9 + 1/9

Задача 2: Дадени са две естествени числа p и q (q № 0, p < q; p,qОN). Да се намери представяне на дробта p/q във вид на сума:
p/q = 1/a1 + 1/a2 + ... + 1/an,
при което знаменателите да бъдат различни (ai № aj, 1 Ј i, j Ј n, i № j, ai і 2, aj і 2, ai, ajОN).

Забележка: Възможно е задачата да има повече от едно решение. Например за дробта 3/7 имаме:
3/7 = 1/3 + 1/11 + 1/231
3/7 = 1/4 + 1/8 + 1/19 + 1/1064
В конкретната задача търсим произволно решение, отговарящо на условието знаменателите на намерените дроби да бъдат различни.
Да разгледаме следния прост алчен алгоритъм: На всяка стъпка поредният член в сумата ще бъде максималната дроб, която може да се добави към текущата сума така, че резултатът да не надвишава p/q (тъй като числителят е винаги 1, това означава дробта с най-малък знаменател). Например за p/q = 7/9 най-голямата възможна дроб е 1/2. По-нататък трябва да изберем нова дроб 1/a2, така че:
1/2 + 1/a2 Ј 7/9, т. е. 1/a2 Ј 7/9 - 1/2, или 1/a2 Ј 5/18.
Най-голямата дроб, отговаряща на това условие, е 1/4, при което получаваме:
1/a3 Ј 7/9 - 1/2 - 1/4 = 5/18 - 1/4 = 2/72,
т. е. максималното a3 е 1/36, с което сумирането приключва: 1/2 + 1/4 + 1/36 = 7/9. Изчисленията в последния пример подсказват каква ще бъде схемата за реализация на алгоритъма:

while (p > 1) {
намира се максималната дроб 1/r, ненадвишаваща p/q;
отпечатва се дробта 1/r;
p/q = p/q - 1/r;
}

Тук трябва да уточним две неща. Първото е как да търсим максималната дроб 1/r, ненадвишаваща p/q (q Ј 0), т. е. минималното r, за което е изпълнено 1/r Ј p/q, r і 2, q і 2. Това е еквивалентно на r і q/p. За да намерим r, можем да извършим делението q/p и да вземем най-малкото цяло число, не по-малко от q/p (в езика Си може да се използва функцията ceil(q/p)). За да избегнем използването на реални числа (за по-голямо бързодействие, както и за да си спестим грешки при закръгляне), ще намерим r, като използваме само целочислено деление: r = (q+p)/p.
Разликата p/q - 1/r се пресмята чрез привеждане под общ знаменател. Така новите стойности за p и q ще бъдат:
p = p*r - q;
q = q*r;
Възможно е след пресмятане на разликата да се получи съкратима дроб. Това ще попречи на правилната работа на алгоритъма единствено в случая, когато се получи дроб p/q, която може да се съкрати до 1/x, т. е. q % p == 0. В този случай, ако не се извърши съкращението, условието p > 1 ще остава изпълнено и търсенето на дроби ще продължава до безкрайност. (Защо?) Следва примерна реализация на алгоритъма, където сме се погрижили за този случай.

#include

/* ако q е кратно на p, се извършва съответно съкращение */
void cancel(unsigned long *p, unsigned long *q) {
if (0 == *q % *p) {
*q /= *p;
*p = 1;
}
}

void solve(unsigned long p, unsigned long q) {
printf(%lu/%lu = , p, q);
cancel(&p, &q);
while (p > 1) {
/* намира максималната дроб 1/r, 1/r<=p/q */
unsigned long r;
r = (q + p) / p;
printf(1/%lu + , r);
/* изчислява p/q - 1/r */
p = p * r - q;
q = q * r;
cancel(&p, &q);
}
if (p > 0)
printf(%lu/%lu , p, q);
printf(
);
}
int main(void) {
solve(3, 7);
return 0;
}

Резултат от изпълнението на програмата:
3/7 = 1/3 + 1/11 + 1/231


Задача 3: Дадени са n лекции, които трябва да бъдат преподадени (дейности, които трябва да бъдат извършени). Всяка лекция i се определя от две числа: фиксирано начало si и фиксиран край fi. Можем да считаме без ограничение на общността, че те са естествени числа. Трябва да се изберат максимален брой лекции, така че никои две от избраните да не се провеждат по едно и също време, т. е. ако приемем, че разполагаме само с една зала за лекции, то във всеки един момент t в залата може да се преподава най-много една лекция i (si Ј t Ј fi, 1 Ј i Ј n).

Фигура 1. Конфигурация от четири лекции: начало и край.

Фигура 2. Граф за конфигурацията.

Задачата е класически пример за ефективен и правилно работещ алчен алгоритъм. Да разгледаме един конкретен пример. На фигура 1 е показана конфигурация от четири лекции. Лекциите с номера 1 и 4 не се пресичат във времето, докато 1 и 2, 2 и 3 и др. се пресичат, т. е. не могат да се проведат едновременно.
Алгоритъм 1:
Построяваме ориентиран граф G(V,E) с n върха, в който на всеки две непресичащи се лекции i, j (fi < sj) съответства реброто (i, j), вж. фигура 2. Ако намерим най-дълъг път в G, ще получим алгоритъм със сложност Q(n2).
Алгоритъм 2:
Възможно е задачата да се реши и без да се строи граф, като се използва динамично оптимиране. Дефинираме целева функция F, максимизираща броя на избраните лекции за време от 0 до t, по следния начин:
F(t) = 0, ако не съществува лекция i, за която fi < t и
F(t) = в противен случай.
Търсеното решение е стойността на функцията F(t0) за .
Ако приложим memoization за горната рекурентна формула, ще се наложи да използваме допълнителна памет. Например можем да въведем масив calc[t], в който да пазим всяка вече пресметната стойност на t. В него ще се използват най-много 2n елемента (може да има съвпадения). Ако t е прекалено голямо число, решение по този начин изобщо няма да бъде възможно. За да решим този проблем, ще използваме списък calc[2*n], всеки елемент на който има две полета: момент calc[i].t и максимален брой лекции, които могат да се изнесат до този мо-мент - calc[i].maxl.
Реализацията на описания по-горе алгоритъм предоставяме на читателя. Умишлено няма да се задълбочаваме повече върху него, тъй като сложността му е квадратична, а използваната допъл-нителна памет - линейна относно броя на лекциите n.