Грамзиви алгоритми

Увод

Динамичко програмирање увек сагледава ширу слику и решава све подпроблеме, пре него што конструише решење проблема. Овај поступак је исправан и увек води ка тачном решењу, јер проверава све случајева, али је често његова сложеност висока. Са друге стране, грамзиви алгоритми никада не разматрају све могуће подпроблеме, већ увек као решење узимају оно што им у датом тренутку делује најбоље, без разматрања осталих могућности.

Грамзиви алгоритми у сваком кораку праве локално оптимални избор без икакве гаранције да ће таква стратегија довести до оптималног решења целог проблема. За разлику од динамичког програмирања које проверава све подпроблеме и комбинује их, грамзиви алгоритам никада не преиспитује своје одлуке. Грамзиви алгоритми прате следећу стратегију:

Кандидати за решење - У текућем кораку дефинишемо могући скуп кандидата за решење према неком критеријуму.
Функција избора - Из скупа кандидата бирамо онога који је у том тренутку најбољи (најскупљи, најјефтинији, најкраћи, најдужи итд).
Провера исправности избора - Проверавамо да ли избор који смо направили крши правила проблема који се решава.
Провера решења - Проверавамо да ли смо стигли до краја, тј. да ли смо решили проблем.

Најочигледнији пример грамзивог алгоритма је враћање кусура у продавници са што мање апоена. Очигледна грамзива стратегија је да сваки пут узимамо највећи могући апоен све док не вратимо кусур. Нека су нам дати апоени 20,10,5,1 и нека је износ кусура 36 динара. Очигледно је да пратећи описану стратегију узми највећи, кусур можемо да вратимо са по једним апоеном сваком типа, тј. са укупно четири апоена.

Иако је било лако уочити грамзиву стратегију за претходно описани проблем, то није увек случај. Грамзиви алгоритми су по правилу једноставни, али су често жртве своје локалне природе. Због локалности, грамзиви алгоритми су кратковиди и не виде ширу слику, због чега често не могу одредити оптимално решење полазног проблема. Најчешће је врло лако дизајнирати алгоритам који ће пратити неку грамзиву стратегију, али је још чешће изузетно тешко дизајнирати грамзиву стратегију која ће одредити оптимално решење датог проблема.

Кратковидост грамзивих алгоритама и склоност ка грешкама можемо да илуструјемо идентичним проблемом, али са различитим вредностима. Доступни су апоени 25, 20 и 1.

Можемо да пробамо да решимо задатак истом грамзивом стратегијом од малопре. Стратегија каже да у сваком тренутку узимамо апоен највеће вредности. На тај начин, кусур ћемо вратити уз помоћ једног апоена од 25 и још 15 тегова апоена од 1, Дакле, грамзиви алгоритам каже да је потребно укупно 16 апоена да бисмо вратили кусур. Међутим, оптимално решење је употреба два апоена од по 20.

Из овог примера треба да закључимо да су грамзиви алгоритми подједнако опасни колико су и примамљиви. Да бисмо проблем могли да решавамо грамзивим алгоритмима он мора да испуњава својство грамзивог избора, тј. локално оптимални избор мора водити ка глобално оптималном решењу.

Предности грамзивих алгоритама су перформансе (много бржи од динамичког програмирања), једноставност (лаки за разумевање), потрошња меморије (не чувају резултате свих подпроблема). Мане грамзивих алгоритама су нетачност (често не дају оптимална решења, већ само решења), слабост (једном направљена грешка се не може исправити), локалност (одлуке се доносе без сагледавања шире слике), доказивање коректности (често је тешко показати да грамзива стратегија води ка глобалном решењу у сваком случају).

Иако често не доводе до тачних решења, грамзиви алгоритми су једни од најпопуларнијих, јер се многи проблеми из праксе не могу другачије решавати, али и зато што нам често ни не треба оптимално решење, већ само решење које је довољно добро.

Напомена: У свим решењима бавићемо се искључиво алгоритмима, док учитавање и штампање резултата препуштамо читаоцу за вежбу.

Задатак 1

Камење је постављено дуж позитивног дела $x$ -осе и за сваки камен је позната његова координата $x$ . Жаба креће да скаче са првог камена који се налази у координатном почетку и жели да у што мање скокова дође до последњег камена. У сваком скоку она може да прескочи највише растојање $r$ (а може да скочи и мање, ако је то потребно). Написати програм који одређује да ли жаба може стићи до последњег камена и ако може у колико најмање скокова то може учинити.

Улаз: Са стандардног улаза се уноси број $n$ $(1 \leq n \leq 50000)$ , а затим у наредних $n$ редова по један позитиван цео број (у питању је растуће сортиран низ бројева који представља координате камења). У последњем реду се налази позитиван цео број $r$ .

Излаз: На стандардни излаз исписати најмањи број скокова потребан да жаба стигне до последњег камена или $-1$ ако то није могуће.

Решење

Једно очигледно решење би било да проверимо све могуће комбинације скокова. Сложеност овог приступа је превелика, али се на срећу задатак може много лакше решити. Применићемо грамзиву стратегију. Очигледно је да увек треба да направимо највећи могући скок. Овакав приступ ће нам гарантовати најмањи број скокова, јер ћемо у сваком скоку покрити највећи могући део пута који жаба треба да пређе.

Ако жаба стоји на камену $i$ , увек ћемо скочити на најудаљенији камен који нам је у домету. Ако такав камен не постоји, то значи да жаба не може да стигне до последњег камена. Грамзиво решење је у наставку:

static int najmanji_broj_skokova(int[] kamenje, int r)
{
    // иницијализујемо почетне вредности
    int brojSkokova = 0;
    // камен на којем стојимо
    int i = 0; 
    // крећемо од почетног камена
    while (i < kamenje.Length - 1)
    {
        // индекс најудаљенијег камена на који можемо да скочимо, 
        // тј. индекс следећег камена
        int j = i;
        // ако можемо да скочимо на камен
        while (j + 1 < kamenje.Length && kamenje[j + 1] - kamenje[i] <= r)
        {
            // прелазимо на њега
            j++;
        }
        // ако следећи камен не постоји, прекидамо претрагу
        // и враћамо сигнал да пут не постоји
        if (j == i)
            return -1;
        // следећи камен постаје текући
        i = j;
        // увећавамо број скокова
        brojSkokova++;
    }
    // враћамо резултат
    return brojSkokova;
}

Временска сложеност решења је линеарна, јер сваки камен разматрамо највише једанпут. Просторна сложеност је константна.

Задатак 2

Такмичари на сајту “Петља” решавају задатке и тако стичу свој рејтинг. Одлучено је да искуснији такмичари помажу млађима, тако што ће им бити ментори. Да би један такмичар могао да буде ментор другоме, његов рејтинг треба да буде бар два пута већи него рејтинг првога. Ако су познати рејтинзи свих такмичара, одреди- ти који је највећи број парова ученик-ментор који се може формирати, при чему такмичар може истовремено бити и ученик и ментор (ментор ономе ко има бар два пута мањи рејтинг од њега, а ученик ономе који има бар два пута већи рејтинг од њега), али ни један такмичар не може да има два ученика нити два ментора.

Улаз: У једној линији стандардног улаза налази се број такмичара $N$ , а затим се, у свакој од $N$ наредних линија стандардног улаза, налази по један цео број који представља рејтинг такмичара.

Излаз: На стандардни излаз исписати само један цео број који представља највећи могући број парова који се могу формирати.

Решење

Наивно решење би било да генеришемо сва могућа упаривања такмичара и да из тог скупа издвојимо оно које има највише парова који испуњавају дати услов. Овакав алгоритам је неефикасан и можемо га убрзати. Потребно је да уочимо следеће:

Ментор и ученик не смеју бити преблизу. Прецизније, такмичар са малим рејтингом који може бити ментор за неког другог такмичара са још нижим рејтингом је можда кориснији као ученик за неког такмичара са великим рејтингом. Одавде закључујемо да би нам било згодно да такмичаре упоређујемо према растућем рејтингу.
Приликом упаривања ученика са менторима можемо да користимо следећу грамзиву стратегију: најмањег могућег ментора упарујемо са најмањим могућим учеником, чиме чувамо јаке менторе за јаке ученике.
Након сортирања, низ ћемо да поделимо на две половине и ученике из доње половине ћемо да упарујемо са менторима из горње половине низа.

static int najveci_broj_operacija(int[] rejtinzi)
{
    // памтимо број елемената у низу
    int n = rejtinzi.Length;
    // сортирамо низ по рејтинзима
    Array.Sort(rejtinzi);
    // број парова је на почетку нула
    int brojParova = 0;
    // на почетку, ученици су у левој половини, 
    // а ментори у десној
    int u = 0;
    int m = n/2;
    // упарујемо ученике
    while (u < n/2 && m < n)
    {
        // ако пар испуњава услов из задатка
        if (rejtinzi[m] >= 2*rajtinzi[u])
        {
            // увећавамо број парова
            brojParova++;
            // и прелазимо на наредног ученика
            u++;
        }
        // ментора свакако померамо унапред
        m++;
    }
    return brojParova++;
}

Задатак 3

У једном кабинету се суботом одржава обука програмирања. Сваки наставник је написао термин у ком жели да држи наставу (познат је сат и минут почетка и сат и минут завршетка часа). Одреди како је могуће направити распоред часова тако да што више наставника буде укључено.

Улаз: Са стандардног улаза се учитава прво број $n$ (укупан број наставника, $1 \leq n \leq 50000)$ , а затим у $n$ наредних редова по четири броја раздвојена размацима који представљају сат и минут почетка тј. завршетка часа (претпоставити да је завршетак увек иза почетка).

Излаз: На стандардни излаз исписати највећи број наставника који могу да одрже своје часове.

Решење

Сваки час у распореду можемо представити уређеним паром бројева који редом представљају време почетка и време краја часа. Ради једноставности репрезентације, времена у дану можемо представљати бројем минута од претходне поноћи.

Наивно решење можемо врло лако да конструишемо. Потребно је да испитамо све подскупове скупа часова и да из њих издвојимо највећи подскуп такав да се сви часови у њему могу одржати. Генерисање подскупова можемо да извршимо рекурзивно применом укључи-искључи принципа. Прецизније, прво разматрамо подскуп који не садржи текући час, а затим подскуп који садржи текући час. Час ћемо додавати у распоред само ако није у конфликту са раније додатим часовима

// креирамо помоћни тип за представљање часова
class Cas 
{
    // почетак и крај часа у минутима
    public int Pocetak {get; set;}
    public int Kraj {get; set;}
    // конструктор
    public Cas(int p, int k)
    {
        Pocetak = p;
        Kraj = k;
    }
    // провера пресека
    public bool presek(Cas c)
    {
        // пресек постоји ако је каснији почетак часа пре ранијег краја часа
        return Math.Max(Pocetak, c.Pocetak) < Math.Min(Kraj, c.Kraj);
    }
}
static int najvise_casova(Cas[] casovi, int i, Cas[] raspored, int k)
{
    // ако смо проверили све часове
    if (i == casovi.Length)
    {
        // можемо одржати највише k часова 
        return k;
    }
    // иначе, разматрамо i-ти час
    else 
    {
        // рачунамо највећи број часова који се може одржати без тог часа
        int bezCasa = najvise_casova(casovi, i+1, raspored, k);
        // на старту претпостављамо да не можемо да одржимо тај час
        int rez = bezCasa;
        // проверавамо да ли текући час можемо да додамо у распоред
        bool mozeDaSeOdrzi = true;
        for (int j = 0; j < k; j++)
        {
            // ако постоји пресек са неким часом који је већ у распореду
            // заустављамо претрагу
            if (casovi[i].presek(raspored[j]))
            {
                mozeDaSeOdrzi = false;
                break;
            }
        }
        // ако час може да се одржи
        if (mozeDaSeOdrzi) 
        {
            // додајемо час у распоред
            raspored[k] = casovi[i];
            // одређујемо максимални број часова са укљученим текућим часом
            int saCasom = najvise_casova(casovi, i+1, raspored, k+1);
            // резултат је већи од два случаја
            rez = Math.Max(rez, saItim);
        }
        // враћамо резултат
        return rez;
    }
}
static int najvise_casova(Cas[] casovi)
{
    Cas[] raspored = new Cas[casovi.Length];
    return najvise_casova(casovi, 0, raspored, 0);
}

Приказано решење је експоненцијалне временске сложености и није применљиво у пракси. Ефикасније решење се може добити грамзивим приступом. Часове можемо сортирати неопадајуће на основу времена њиховог завршетка и обилазити их у том редоследу. Од свих нераспоређених часова бирамо онај који се најраније завршава и који се може одржати (не сече се са до сада одржаним часовима, тј. почиње након завршетка претходног часа). Интуитивно, таквим избором остављамо већу могућност за распоређивање накнадних часова.

Формално, претпоставимо да је $O = {c_1 , \ldots , c_k}$ , скуп часова који представља неко оптимално решење, при чему су часови $c_1$ до $c_k$ сортирани неопадајуће по времену њиховог завршетка. Пошто се сви ти часови могу одржати, између њих нема преклапања и сваки наредни час почиње након завршетка претходног. Нека је $c_i$ први час у овом скупу који не би био изабран нашом стратегијом. Претпоставимо да би наша стратегија уместо њега одабрала час $c′_i$ . Покажимо да се заменом часа $c_i$ часом $c′_i$ добија такође распоред који је оптималан. Покажимо да се $c i$ завршава после $c′_i$ . Заиста, ако је $i = 0$ , тада наша стратегија бира $c′_i$ који се први завршава, па се стога $c_i$ не може завршавати пре њега. Ако је $i > 0$ , тада знамо да $c_i$ мора да почиње после $c_{i−1}$ , међутим, наша стратегија за $c′_i$ бира онај час који почиње након $c_{i−1}$ који се први завршава, па се $c_i$ ни у овом случају не може завршавати пре $c′_i$ . Ако постоје часови у $O$ пре часа $c_i$ , они остају непромењени и час $c′_i$ није у конфликту са њима (јер је одабран тако да почиње након завршетка часа $c_{i−1}$ ). Пошто се $c′_i$ не завршава касније него $c_i$ он се сигурно не судара ни са једним часом из $O$ који иде после $c_i$ (јер сви они почињу и завршавају се након краја часа $c_i$ ). Дакле, када се $c_i$ замени са $c′_i$ и даље се добија исправан распоред са истим бројем одржаних часова као $O$ за који смо претпоставили да је оптималан. По истом приницпу можемо мењати наредне часове (ово се мора зауставити јер у сваком наредном оптималном скупу имамо по један час више који је у складу са нашом стратегијом) и тако показати да ће наша стратегија вратити оптималан скуп. Могуће је применити и дуално решење у којем се бира онај час који последњи почиње и часови се обилазе уназад, по нерастућем редоследу њиховог почетка.

Грамзиво решење које користи описани поступак је у наставку.

// креирамо помоћни тип за представљање часова
class Cas 
{
    // почетак и крај часа у минутима
    public int Pocetak {get; set;}
    public int Kraj {get; set;}
    // конструктор
    public Cas(int p, int k)
    {
        Pocetak = p;
        Kraj = k;
    }
    // провера пресека
    public bool presek(Cas c)
    {
        // пресек постоји ако је каснији почетак часа пре ранијег краја часа
        return Math.Max(Pocetak, c.Pocetak) < Math.Min(Kraj, c.Kraj);
    }
}
static int najvise_casova(Cas[] casovi)
{
    // на почетку сортирамо низ часова неоподајуће према времену
    // завршетка
    Array.Sort(casovi, (x,y) => {
        return x.Kraj.CompareTo(y.Kraj);
    });
    // први час увек можемо да одржимо
    int brojOdrzanih = 1;
    int kraj = casovi[0].Kraj;
    // тражимо први час који можемо додати у распоред
    for (int i = 1; i < casovi.Length; i++)
    {
        if (casovi[i].Pocetak >= kraj)
        {
            kraj = casovi[i].Kraj;
            brojOdrzanih++;
        }
    }
    return brojOdrzanih;
}

Задатак 4

У познатој продавници робе на меру се организује наградна игра са следећим правилима:

Сваки учесник ће добити ранац чија је носивост $W$ .
У наградној игри учествује $n$ различитих артикала.
За сваки артикал позната је његова цена по јединици мере $c_i$ и доступна количина $w_i$ .
Сваки учесник може да изабере од сваке врсте артикала највише онолико колико је тог артикла доступно.
Задатак је изабрати количине артикала тако да њихова укупна маса не пређе дозвољену носивост ранца.
Победник је такмичар који у ранцу буде имао највећу могућу вредност артикала.

Перица је препознао да се у наградној игри заправо ради о добро познатом проблему оптимизације који се назива разломљени проблем ранца и замолио нас је да напишемо програм који ће му помоћи да победи у наградној игри.

Улаз: У првој линији стандардног улаза се учитава реалан број који представља носивост ранца $W$ . У следећој линији се учитава природан број $n$ који представља број артикала који учествују у наградној игри. У следећих $n$ линија учитавају се по два реална броја раздвојена једним размаком који редом представљајју цену по јединици мере $c_i$ и доступну количину $w_i$ $i$ -тог артикла.

Излаз: На стандардни излаз исписати максималну вредност артикала која се може наћи у ранцу, као и количине артикала којима је та цена постигнута.

Решење

За разлику од обичног 0-1 ранца где ствари морамо узети целе или никако, овде можемо захватити колико год желимо грама или килограма неког артикла док не попунимо капацитет. Да бисмо ефикасно решили проблем, можемо да применитмо грамзиву стратегију. Увек ћемо узимати онај предмет који има највећу цену по јединици мере.

Логика решења је једноставна. За сваки артикал у општем случају треба да израчунамо његову вредност по јединици мере, што нам је већ дато у задатку. Артикле сортирамо опадајуће према њиховој вредности. Ранац попуњавамо редом од највреднијег ка мање вредним артиклима. Ако читава доступна количина текућег артикла стаје у ранац, узимамо све. Ако не стаје све, узимамо само онолико колико је преостало до попуњавања читавог ранца носивости $W$ . Грамзиво решење је у наставку:

// помоћни тип података за представљање артикала
class Artikal 
{
    // атрибути класе
    public double Vrednost {get; set;}
    public double Kolicina {get; set;}
    // конструктор
    public Artikal(double v, double k)
    {
        Vrednost = v;
        Kolicina = k;
    }
}
static double najveca_vrednost(Artikal[] niz, double W)
{
    // сортирамо низ опадајуће по вредностима артикала
    Array.Sort(niz, (x,y) => {
        return y.Vrednost.CompareTo(x.Vrednost);
    });
    // на старту су вредност и маса у ранцу 0
    double ukupnaVrednost = 0;
    double ukupnaTezina = 0;
    // редом у ранац додајемо артикле почевши од највреднијих
    for (int i = 0; i < niz.Length; i++)
    {
        // ако можемо да додамо укупно колицину артикла типа i
        if (ukupnaTezina + niz[i].Kolicina <= W)
        {
            // додајемо све и увећавамо вредност и масу у ранцу
            ukupnаVrednost += niz[i].Vrednost * niz[i].Kolicina;
            ukupnaTezina += niz[i].Kolicina;
        }
        // ако не можемо
        else {
            // додајемо само количину која може да стане у ранац
            double preostalo = W - ukupnaTezina;
            // увећавамо вредност и тежину
            ukupnaVrednost += preostalo * niz[i].Vrednost;
            ukupnaTezona += preostalo;
            // на крају овог корака ранац је пун, па прекидамо итерацију
            break;
        }
    }
    // враћамо резултат
    return ukupnaVrednost;
}

Задатак 5

Напиши програм који елементе датог низа распоређује тако да се након израчунавања низа апсолутних разлика суседних елемената добијеног низа добија неопадајући низ.

Улаз: Са стандардног улаза се учитава дужина низа $n$ $(1 \leq n \leq 50000)$ , а затим и елементи низа (цели бројеви између $−10^9$ и $10^9$ , сваки у посебном реду).

Излаз: На стандардни излаз исписати елементе низа у редоследу добијеном након траженог распоређивања, раздвојене са по једним размаком. Ако постоји више таквих распореда, исписати било који.

Решење

Наивно решење би се свело на испитивање свих пермутација полазног низа и издвајање прве пермутације која испуњава услов задатка. Сложеност овог приступа је експоненцијална и нећемо га даље разматрати. Уместо тога, размотрићемо алтернативну стратегију.

Да би апсолутне разлике суседних елемената биле у неопадајућем редоследу, тј. такви да је свака следећа разлика већа или једнака претходној, елементи морају „осцилирати“. Најбољи начин да ово постигнемо је да прво сортирамо оригинални низ, а затим нове елементе бирамо са крајева према средини, али на специфичан начин.

Можемо да замислимо сортиран низ. Најмање разлике су између суседних бројева у средини низа, док су највеће разлике између екстремних вредности у низу, тј. између најмањег и највећег елемента. Задатак можемо решити следећим приступом:

Сортирамо полазни низ.
Користимо технику два показивача да бисмо обилазили низ са крајева. Леви показивач поставимо на почетак низа, а десни показивач поставимо на крај низа.
Наизменично узимамо елементе са леве и десне стране и стављамо их у нови низ, али уназад (од краја ка почетку).

На овај начин ће прве две разлике бити најмање могуће, а последње две разлике највеће могуће. Решење је у наставку:

static int[] neopadajuce_razlike(int[] niz)
{
    // низ у који ћемо уписати резултат
    int[] rezultat = new int[niz.Length];
    // сортирамо полазни низ растуће    
    Array.Sort(niz);
    // иницијализујемо десни и леви показивач
    int l = 0;
    int d = n - 1;
    // резултат попуњавамо уназад
    for (int i = niz.Length - 1; i >= 0; i--)
    {
        // на парна места постављамо елементе из десног подниза
        if ((n-1-i) % 2 == 0)
        {
            rezultat[i] = niz[d];
            d--;
        }
        // на непарна места постављамо елементе из левог подниза
        else {
            rezultat[i] = niz[l];
            l++;
        }
    }
    // враћамо резултат
    return rezultat;
}

Иако је решење једноставно, треба образложити зашто даје тражени резултат. Замислимо бројеве као тачке на правој. Најмање могуће разлике добијамо када одузимамо бројеве који су у сортираном низу један до другог, тј. када одузимамо суседе. највеће разлике добијамо када скачемо са једног краја низа на други крај.

Описани алгоритам ради, јер конструишемо низ тако да се интервали прескакања елемената у полазном низу постепено повећавају:

На почетку конструисаног низа ће се налазити елементи који су у сортираном низу били близу средине. Њихова међусобна резлика је најмања.
Како се крећемо ка крају низа, наизменично узимамо све мање и све веће бројеве. Сваким новим кораком, размак између најмањег преосталог и највећег преосталог је све већи.
На самом крају низа, спајамо минимални и максимални елемент. Та разлика је највећа могућа у целом скупу података и она природно мора бити на крају низа.

Оваквим слагањем елемената од средине ка крајевима, гледано по вредностима из сортираног полазног низа, ми заправо конструишемо амплитуду скока између суседних елемената.

На крају, треба објаснити зашто је ово решење грамзиво. Описано решење испуњава критеријуме описане у уводном делу:

Локалност избора - У сваком кораку попуњавања низа, идући уназад ми грамзиво бирамо највећи и најмањи расположиви елемент како бисмо осигурали да је тренутна разлика коју правимо већа од претходне. Да бисмо направили избор, ми уопште не разматрамо ни претходне ни будуће изборе, већ га правимо тако да будемо сигурни да је разлика већа од претходне.
Оптимална подструктура - У конструкцији решења, ми не испробавамо све могуће пермутације низа. Уместо тога, систематски искоришћавамо следеће правило: “Ако на крај поставимо највећу могућу разлику, а пре ње следећу највећу, остаће нам простора да на почетак поставимо најмање разлике.”

Задатак 6

Дуж једног пута налазе се гласници. Поруку први сазнаје гласник на почетку пута и циљ је да сви гласници што пре сазнају поруку. Сваки гласник може викањем пренети поруку свима који се од њега налазе на растојању мањем од задатог домета гласа (истог за све гласнике). При том се сви гласници могу кретати брзином од највише једног метра у секунди у било ком смеру (током времена могу мењати своју брзину и смер кретања, а могу и стајати у месту).

Улаз: Са стандардног улаза се учитава домет гласа $d$ (реалан број, $1 \leq d \leq 10^{6})$ , затим број гласника $n$ $($ цео број, $1 \leq n \leq 10^{5})$ , а након тога положај сваког гласника $g_i$ (реалан број, $0 \leq gi \leq 10^{9}$ , који представља растојање од почетка пута).

Излаз: На стандардни излаз исписати најмање време протекло од тренутка када први гласник сазна поруку до тренутка када поруку сазнају сви гласници, као реалан број заокружен на три децимале (одступање од тачне вредности сме да буде највише $10^{−3}$ ).

Решење

Задатак има веома елегантно грамзиво решење, које је директно, тј. не користи претрагу. Једна оптимална стратегија је да сви гласници који знају поруку трче на десно према онима који не знају поруку, а да они који не знају поруку трче на лево, према онима који знају поруку ако већ нису у њиховом домету, а на десно ако јесу у њиховом домету. При том, гласници који трче на десно све време вичу, тако да се порука сазна чим неки гласник уђе у њихов домет (што је домет најдешњег од њих). У таквој стратегији сваки гласник сазнаје поруку од свог непосредног претходника.

Претпоставимо да је $t_i$ најмање могуће време да гласник $i$ сазна поруку и да је најдаља могућа позиција у којој се он тада налази једнака $G_i$ . Одредимо ове вредности индуктивном конструкцијом.

За првог гласника важи да је $t_0 = 0$ и да је $G_0 = g_0$ .
Одређујемо ове податке за наредног гласника ti+1t_{i+1} и Gi+1G_{i+1}.
- Ако се наредни гласник у времену $t_i$ може наћи у домету гласника $i$ , тада је $t_{i+1} = t_i$ . Једини начин да се то не догоди је да је $G_i + d < g_{i+1} − t_i$ . У том случају је потребно време продужити тако да се гласник $i$ још мало креће на десно, а гласник $i + 1$ још мало креће на лево. С обзиром да је брзина јединична, време након ког порука може бити пренета је $t_{i+1} = t_i + \frac{(g_{i+1} - t_i) - (G_i + d)}{2}$ .
- Вредност $G_{i+1}$ , тј. најдаља тачка на којој гласник $i + 1$ у тренутку $t_{i+1}$ може да прими поруку ће бити десна граница домета $G_i + d$ у свим случајевима, осим ако је гласник $i + 1$ превише лево и не може за време $t_{i+1}$ стићи до ње. Зато важи даје $G_{i+1} = \min (G_i + d, g_{i+1} + t_{i+1}$ ).

Пошто се оптимално решење конструише једним проласком кроз низ гласника, сложеност овог решења је $O(n)$ .

static int najmanje_vreme(double domer, double[] pozicije)
{
    // време је на старту 0
    double t = 0;
    // крећемо од првог гласника
    double p = pozicije[0];
    // пролазимо кроз све гласнике
    for (int i = 0; i < n; i++)
    {
        // у случају да гласник није у домету
        if (pozicije[i] - t - p > domet)
        {
            // продужавамо време према правилу из описа
            t += (pozicije[i] - t - p - domet) / 2;
            // померамо гласника на нову позицију
            p = pozicije[i] - t;
        }
        // ако је у домету, прелажимо на нову позицију
        else 
        {
            p = Math.Min(p + domet, pozicije[i] + t);
        }
    }
    // враћамо потребно време
    return t;
}

Задатак 7

Група људи током ноћи стоји на једној обали реке. Имају само једну светиљку. Преко реке је разапет мост преко ког истовремено могу да пређу највише две особе и то само ако носе светиљку. За сваку особу је познато време потребно за прелазак моста. Ако две особе прелазе мост заједно, крећу се брзином спорије особе. Напиши програм који одређује најмање време потребно да сви људи из групе пређу на другу обалу реке.

Улаз: Са стандардног улаза се учитава број особа $n$ $(1 \leq n \leq 100)$ , а затим, у $n$ наредних редова времена потребна да тих $n$ особа пређе мост.

Излаз: На стандардни излаз исписати најмање време потребно да сви пређу на другу обалу.

Решење

Задатак можемо решити експлицитним проверавањем свих могућих парова. Решење грубом силом подразумева да се у сваком кораку размотре све могућности за прелаз на другу обалу. Притом са почетне обале увек пребацујемо две особе, а на почетну враћамо једну особу (тако се након сваког преласка и враћања број људи који су пребачени на другу обалу бива увећан). Прелазак само једне особе нема смисла, јер након враћања светиљке долазимо у исто стање као пре њеног преласка или евентуално у стање где је једна особа замењена другом. Ако смо бржу особу на полазној обали заменили споријом, само смо умањили шансе да обавимо брз прелазак (јер бржа особа може да ради све што може и спорија и то брже), а ако смо спорију особу заменили бржом, знамо да смо у претходним прелазима могли бити ефикаснији да је у самом почетку уместо те спорије особе на другу обалу прешла бржа. Враћање две особе такође нема смисла, јер након тога долазимо у конфигурацију у којој смо могли бити да се једна од те две особе није шетала са једне обале на другу и назад (што је само могло да увећа укупно време).

После сваког преласка и враћања рекурзивно решавамо проблем истог облика, али мање димензије. Рекурзивна функција решава проблем у ком се светиљка налази на полазној обали и анализира све могућности за прелазак светиљке на другу обалу и враћање светиљке назад (након чега се рекурзивно решава проблем из стања у које се на тај начин дошло). Параметар који се мења током рекурзије је скуп особа које се налазе са једне и скуп особа које се налазе са друге стране реке. Излаз из рекурзије је случај када су на почетној обали остале само једна или две особе и они тада заједно прелазе реку завршавајући прелаз.

Пошто се током ове исцрпне претраге много пута долази у исто стање и рекурзивни позиви се понављају. Имплементација се, дакле, може убрзати тако што се примене технике динамичког програмирања (најједноставније је имплементирати мемоизацију). За сваки подскуп скупа особа на полазној обали, у низу памтимо резултат рекурзивног позива тј. најмање време потребно да све особе из тог подскупа пређу на другу обалу (када је светиљка код њих). Сваки такав подскуп можемо кодирати битовима неозначеног целог броја.

Сложеност овог поступка (и уз мемоизацију) је експоненцијална јер постоји $2^n$ подскупова скупа од $n$ особа (већ за скупове са око $15$ особа, функција постаје прилично неефикасна).

Иако постоје начини да се ово решење убрза (на пример, може се приметити да увек треба вратити најбржу пребачену особу), нећемо настављати развој програма у овом смеру, зато што се другачијим приступом могу добити много ефикаснија и једноставнија решења.

Ефикасно решење можемо постићи проналажењем стратегије преласка за који се унапред може доказати да даје оптимално време преласка. Стратегија ће бити заснована на томе да се (грамзиво) најспорија особа пребацује на другу обалу, одакле се даље не помера. Циљ нам је, дакле, да мало по мало повећавамо скуп особа које су трајно премештене. Прилично је јасно да споре особе треба да буду те чије се шетање са једне на другу обалу мора избећи. Најспорија особа кад тад мора бити премештена на долазну обалу. Када се једном премести нема разлога да се враћа назад. Уместо ње, увек је боље да се враћају брже особе. Пошто се најспорија особа мора кад тад пребацити, нема разлога да се то не уради одмах и да се та особа у потпуности избаци из даљег разматрања. Када се након тога лампа врати назад, редукује се димензија проблема и алгоритам се даље наставља по истом принципу.

Претпоставимо да су времена потребна за прелазак сортирана и дата кроз низ $v_0 v_1 v_2 v_{k−1}.

У случају када су на полазној обали највише две особе, задатак се решава директно, тако што те особе прелазе на другу обалу (ако једина преостала особа $i$ прелази сама, потребно је време $v_i$ , а ако су преостале особе $i < j$ , потребно је време $v_j$ ). У супротном покушавамо да пребацимо две најспорије особе и да вратимо светиљку на полазну обалу.

Посебно ћемо размотрити и случај три особе, јер се показује да је и он другачији од општег случаја у коме има бар 4 особе. У том случају лако се види да је најбоље решење да најбржа особа преводи једну по једну од две спорије особе (чиме је време преласка једнако збиру времена те три особе $v_0 + v_1 + v_2$ ). Мост се не може прећи за мање од овог времена, јер ако би две спорије особе ишле заједно, тада би једна од њих морала да се врати по најбржу па би време било или $2v_1 + v_2$ или $2v_2 + v_1$ , што је спорије од $v_0 + v_1 + v_2$ .

Претпоставимо сада да на полазној обали постоје бар $4$ особе и размотримо ефикасне начине да се најспорија особа преведе на другу обалу.

Једна могућност је да најспорија особа истовремено пређе реку са другом најспоријом особом и да се ниједна од њих више не враћа назад. Наиме, за прелазак најспорије особе већ је потребно време $v_{k−1}$ и за то време се може истовремено превести и особа $v_{k−2}$ , чиме се постиже то да се време $v_{k−2}$ неће посебно трошити. Ако две најспорије особе пређу заједно, проблем је то што неко од њих мора да врати назад светиљку, а то није ефикасно. Зато је пожељно обезбедити да на другој обали буде неко ко ће вратити светиљку када најспорије две особе заједно пређу мост. То не сме бити ниједна од раније преведених особа (јер смо за њих, као веома споре особе, констатовали да нема сврхе да се враћају назад те да се оне неће померати и да их можемо у потпуности изоставити из разматрања) и морамо ангажовати неког од преосталих особа да то уради. Наравно, те особе треба да буду што брже. Морамо прво пребацити две најбрже особе, затим вратити једну од њих, заједно са светиљком, затим пребацити две најспорије заједно и затим употребити ону другу најбржу особу која и даље чека на супротној обали да врати светиљку. Време потребно да се ово оствари је $v_{k−1} + v_0 + 2v_1$ .
Друга могућност да је да неко преведе најспорију особу и да затим врати светиљку. Да бисмо могли да упоредимо однос ове и претходне могућности, размотримо потезе који би нас довели у исту ситуацију као тамо, тј. размотримо потезе који би довели до тога да су две најспорије особе преведене и да је светиљка враћена. Ако не иду две најспорије особе заједно, тада је најбоље да, слично као у случају три особе, неко преведе једну од две најспорије особе, да затим врати светиљку, затим да неко преведе другу од те две најспорије особе и да затим поново врати светиљку. У оба преласка требало би да учествује што бржа особа (да би што пре вратила светиљку), па је најбоље да оба пута светиљку враћа најбржа особа. Дакле, ако је $v_0$ време потребно да најбржа особа пређе мост, а ако су $v_{k−2}$ и $v_{k−1}$ времена потребна да две најспорије особе пређу мост, укупно време потребно да се оне пребаце и светиљка врати биће $v_{k−2} + v_{k−1} + 2v_0$ .

Након оба приказана сценарија две најспорије особе су пребачене, ниједна од њих се више неће враћати, док је светиљка враћена назад и проблем је сведен на исти облик и две особе мање. Који од два могућа сценарија се користи зависи од тога који захтева мање времена (питање је односа величина $v_0 + v_{k−2}$ и $2v_1$ ).

Пример у коме је прва стратегија оптимална може бити онај у коме је особама потребно $1, 2, 8, 10$ минута, јер удруживањем особа $3$ и $4$ избегавамо посебно шетање у трајању од $8$ минута (што плаћамо додатним преласцима прве две особе, но то се исплати, јер је њима за прелазак потребно јако мало времена). Заиста, важи да је $1 + 8 > 2 \cdot 2$ .

Пример у коме је друга стратегија оптимална може бити онај у коме је особама потребно $1, 4, 5, 6$ минута. Уштеда $5$ минута код треће особе није вредна додатних прелазака друге особе којој је потребно $4$ минута. Заиста, важи да је $1 + 5 < 2 \cdot 4$ .

Може још да се постави питање зашто није узет у обзир сценарио у коме најбржа особа преводи најспорију, враћа лампу, а затим не преводи другу по реду најспорију особу, већ та особа прелази заједно са трећом по реду најспоријом (јер се тако добија боље време). Да би се то догодило мора да важи да је $v_0 + v_{k−2} \le 2v_1$ , а да је $v_0 + v_{k−3} > 2v_1$ , што није могуће, јер је $v_{k−3} \le v_{k−2}$ . Стога је оптимална стратегија таква да се групишу две по две најспорије особе које заједно прелазе мост, све до једног тренутка у ком то престане да буде исплативо и тада најбржа особа креће да преводи једну по једну особу све док сви не пређу.

Грамзиво решење је у наставку:

static void najmanje_vreme(int[] niz)
{
    // памтимо величину низа и сортирамо низ
    // растуће по временима
    int n = niz.Length;
    Array.Sort(niz);
    // укупно време је на почетку нула
    int vreme = 0;
    // све док постоји макар једна особа коју треба пребацити
    while (n > 0) {
        // ако је остала једна особа, ради се о најбржој особи
        // која иде сама
        if (n == 1)
        {
            vreme += niz[0];
            n -= 1;
        }
        // остале су две особе и оне прелазе заједно брзином спорије
        else if (n == 2) 
        {
            vreme += osobe[1];
            n -= 2;
        }
        // остале су три особе 
        else if (n == 3)
        {
            // особа 0 и особа 2 иду прво брзином особе 2
            // особа 0 се враћа назад својом брзином
            // особе 0 и особа 1 иду заједно брзином особе 1
            vreme =+ osobe[0] + osobe[1] + osobe[2];
            n -= 3;
        }
        else 
        {
            // рачунамо две могуће стратегије за пребацивање све најспорије особе
            int vreme1 = osobe[0] + 2*osobe[1] + osobe[n-1];
            int vreme2 = 2*osobe[0] + osobe[n-2] + osobe[n-1];
            // узимамо ефикаснију
            vreme += Math.Min(vreme1, vreme2)
            n -= 2;
        }
    }
    // враћамо резултат
    return vreme;
}