Email Jindřichu Prokopovi (cvičícímu ALG) o ALG HW 2

Zkusím vysvětlit rozdíl mezi tím, jak jsem rekurzivně postupoval já a
jak ostatní:

"Můj" postup (chybný pro test09, ale zase rychlý pro pub09):

Pro každý experiment: dám ho nejvíc doleva do rozvrhu kam to jde a
větvím pro ještě nepřidané. Když ho přidat nemůžu vůbec, tak v tomto
místě nevětvím. Z každého větvení dostanu výsledek a vyberu nejlepší.

Jinými slovy, zkouším všechny permutace pořadí (tzn. všechny způsoby
seřazení) experimentů, kde každá permutace jednoznačně odpovídá
nějakému poskládání do rozvrhu v tomto pořadí tak, že každý přidávám na
první možnou pozici nejvíc vlevo.

moje_funkce(rozvrh, experimenty_nepouzite) {
    for(experiment in experimenty_nepouzite) {
         if (vejde_se_kamkoliv_do_rozvrhu(experiment, rozvrh)) {
             # experiment pridavam do rozvrhu na PRVNI VOLNOU POZICI, tj. nejvic vlevo kam se cely vejde
             reseni = moje_funkce(rozvrh + experiment, experimenty_nepouzite - experiment);

             if (reseni.lepsi_nez(nejlepsi_reseni)) nejlepsi_reseni = reseni;
         }
    }

    return nejlepsi_reseni;
}

---------------

Postup kolegů (test09 řeší správně, ale zase pub09 trvá dlouho):

Vezmu *první* experiment, a pro každou jeho pozici v rozvrhu (včetně
varianty "není v rozvrhu vůbec") větvím. Ve větvích stejným způsobem
přidávám druhý experiment, atd. Z každého větvení dostanu výsledek a
vyberu nejlepší.

global experimenty;
moje_funkce(rozvrh, i) {
    podrozvrh = experimenty[i].rozvrh;
    while (podrozvrh != NULL) {
        if (vejde_se_do_rozvrhu(podrozvrh, rozvrh)) {
            # přidávám do rozvrhu na pozici určenou momentálním posunutím
            reseni = moje_funkce(rozvrh + podrozvrh, i + 1);

            if (reseni.lepsi_nez(nejlepsi_reseni)) nejlepsi_reseni = reseni;
        }
        podrozvrh = podrozvrh.posunout();  # dejme tomu že přetečení přes povolený počet dní vrátí NULL
    }

    # varianta, kdy i-tý experiment vynechám úplně - nepřidám do rozvrhu
    reseni = moje_funkce(rozvrh, i + 1);

    if (reseni.lepsi_nez(nejlepsi_reseni)) nejlepsi_reseni = reseni;

    return nejlepsi_reseni;
}

---------------

Pro test09 tedy asi musí platit, že nejlepší řešení obsahuje nějaké
úplně prázdné místo, které by bylo při dosazování striktně zleva (tzn.
1. popsaným postupem) zaplněno.

Bohužel, 2. popsaný způsob funguje vždy, ale pub09 mu trvá velmi
dlouho.

Snad je to srozumitelné.

Jan Neumann

Jindřich Prokop píše v Út 22. 10. 2019 v 14:38 +0200:
> Dobrý den,
>
> děkuji za zprávu, koukal jsem v neděli na vaše řešení a na první
> pohled se mi zdálo správné. V čem spočívala oprava?
>
> S pozdravem
> Jindřich Prokop