PALMA junior
Úloha o nakladaní vagónov

Autorské riešenie
[stiahni imp : py]

• Počet riešiteľov: 0 / 2 = 0 %

• Úspešnosť riešenia: 0 / 0 =  NaN %

Toto je veľmi zaujímavý problém. Na internete alebo v učebniciach programovania ho nájdeme v rôznych obmenách (napr. spravodlivé rozdelenie lupu medzi dvoch lúpežníkov). V  tomto prípade je to skôr problém nájdenia vhodného postupu rozdeľovania tovarov než programovania samotného. Pri hľadaní riešenia môžeme vyskúšať rôzne prístupy prerozdelenie tovarov do skupín. Pozrime sa na niektoré z nich:

• Hmotnosti usporiadame vzostupne a striedavo ich budeme rozdeľovať do dvoch skupín.

  Hmotnosti: [1, 4, 5] rozdelíme nasledovne: [1, 5] a [4]. Táto stratégia nefunguje, pretože rozdelenie [5] a [1, 4] je lepšie.

• Hmotnosti usporiadame vzostupne a postupne ich prideľujeme do tej skupiny, v ktorej je súčet hmotností menší.

  Hmotnosti [1, 2, 3, 4] prerozdelíme nasledovne: [1, 3] a [2, 4]. Táto stratégia tiež nefunguje, pretože rozdelenie [1 ,4] a [2, 3] je lepšie.

• Hmotnosti usporiadame vzostupne a budeme párovať začiatok s koncom. Tieto dvojice striedavo priraďujeme do skupín.

  Hmotnosti [1, 5, 6, 12] prerozdelíme nasledovne: [1, 12] a [5, 6]. Ani táto stratégia nefunguje, pretože rozdelenie [1, 5, 6] a [12] je lepšie.

• Hmotnosti usporiadame naopak, od najväčšej po najmenšiu, a postupne prideľujeme do tej skupiny, v ktorej je súčet hmotností menší..

  Hmotnosti [9, 9, 7, 6, 5] prerozdelíme nasledovne: [9, 7] a [9, 6, 5]. Ani táto stratégia nefunguje, pretože rozdelenie [9, 9] a [7, 6, 5] je lepšie.

Zrejme by sme mohli objaviť aj ďalšie postupy založené na tom, že sa snažíme priebežne, spravodlivo rozdeľovať tovary do skupín. Pravdepodobne by sme pre každý z nich našli aj kontrapríklad, kedy postup nefunguje. Ich problém je v tom, že hmotnosti posledných tovarov nám môžu celý doterajší výber pokaziť. Napriek tomu, že tieto postupy nevedú k správnemu riešeniu, ešte ich nezahadzujme. Vrátime sa k nim neskôr.

Poznámka: Stratégie, pri ktorých sa snažíme nájsť globálne najlepšie riešenie tak, že vyberáme v každom kroku lokálne najlepšiu možnosť sa označujú ako pažravé (ang. greedy algorithm).

V prípadoch ako je tento, keď nevieme nájsť nejaké šikovné riešenie môžeme postupovať aj inak. Vyskúšajme všetky možnosti ako tovar rozdeliť do dvoch skupín a z nich vyberme tú najlepšiu. Tento prístup určite nájde najlepšie riešenie, pretože overujeme všetky riešenia a medzi nimi bude určite aj to najlepšie. Otázka je, ako všetky možnosti nájsť?

Ak delíme tovar do dvoch skupín, každý z tovarov skončí buď v skupine prvej alebo v skupine druhej. Označme si kvôli jednoduchosti tieto skupiny 0 a 1. Ak máme napr. štyri tovary a všetky by sme vložili do skupiny 0, vieme to vyjadriť nasledovne: 0000. Ak by sme štvrtý tovar vložili do skupiny 1, vieme to vyjadriť nasledovne: 0001. Inak povedané, každá štvorica z 0 a 1 predstavuje nejaké prerozdelenie štyroch tovarov do dvoch skupín. Ak chceme nájsť všetky prerozdelenia, ktoré to sú? Tieto:

0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

Teraz však máme iný problém. Ako vygenerovať všetky postupnosti z 0 a 1 takej dĺžky, aký je počet tovarov? Pozrime si ešte raz vyššie uvedené štvorice. Nepripomína nám to niečo? Vyzerá to ako zápis čísiel v dvojkovej sústave (gymnazisti sa s nimi pravdepodobne stretnú v 1. ročníku na hodinách informatiky). Ak sú uvedené štvorice zápismi čísiel, ktoré čísla reprezentujú? Tieto:

0000 - 0
0001 - 1
0010 - 2
0011 - 3
0100 - 4
0101 - 5
0110 - 6
0111 - 7
1000 - 8
1001 - 9
1010 - 10
1011 - 11
1100 - 12
1101 - 13
1110 - 14
1111 - 15

Vygenerovať čísla 0 až 15 nie je problém. Stačí nám na to použiť cyklus. Ak ich už ale budeme mať, ako zistíme aká postupnosť z 0 a 1 im zodpovedá? Odpoveď je jednoduchá. Ukážme si to najskôr na desiatkovej sústave. Ak zoberieme ľubovoľné číslo a postupne ho budeme celočíselne deliť 10, zvyšky ktoré dostaneme predstavujú jednotlivé cifry zápisu tohto čísla v desiatkovej sústave. Ak postup zopakujeme, ale deliť budeme 2, dostaneme cifry zápisu čísla v dvojkovej sústave.

Ak vieme, koľko je tovarov, koľko rôznych preusporiadaní existuje? Keďže každý tovar môžeme zaradiť do jednej z dvoch skupín, celkový počet prerozdelení je 2^{počet tovarov}. Pre predchádzajúci prípad 4 tovarov je to 2⁴, t.j. 16.

Zhrňme si to:

1. zistíme, koľko tovarov potrebujeme prerozdeliť,
2. vygenerujme všetky čísla od 0 po 2^{počet tovarov}-1,
3. pre každé číslo zistime jeho zápis v dvojkovej sústave, inak povedané deľme ho 2 a zaznamenávajme si zvyšky,
4. ak je zvyšok 0, tovar zaradíme do prvej skupiny, ak je zvyšok 1, zaradíme ho do druhej skupiny,
   • inak povedané, ak je zvyšok 0, hmotnosť tovaru pripočítajme k prvej skupine, ak je zvyšok 1, jeho hmotnosť pripočítajme k druhej skupine,
5. zistime rozdiel hmotností skupín,
6. ak je tento rozdiel menší ako doteraz najmenší nájdený, zapamätajme si toto rozdelenie,
7. posledné zapamätané rozdelenie je to najmenšie,

Výsledok môže vyzerať nasledovne:

#Python

def rozdiel(vyrobky, rozdelenie):
    hmotnost1 = 0
    hmotnost2 = 0
    for vyrobok in vyrobky:
        if rozdelenie % 2 == 0:
            hmotnost1 = hmotnost1 + vyrobok
        else:
            hmotnost2 = hmotnost2 + vyrobok
        rozdelenie = rozdelenie // 2
    return abs(hmotnost1 - hmotnost2)

def najlepsieRozdel(vyrobky):
    najmensiRozdiel = sum(vyrobky)
    najRozdelenie = 0
    pocetPrerozdeleni = 2 ** len(vyrobky)
    for aktualneRozdelenie in range(pocetPrerozdeleni):
        aktualnyRozdiel = rozdiel(vyrobky, aktualneRozdelenie)
        if aktualnyRozdiel < najmensiRozdiel:
            najmensiRozdiel = aktualnyRozdiel
            najRozdelenie = aktualneRozdelenie

    cast1 = []
    cast2 = []
    for vyrobok in vyrobky:
        if najRozdelenie % 2 == 0:
            cast1.append(vyrobok)
        else:
            cast2.append(vyrobok)
        najRozdelenie = najRozdelenie // 2

    return cast1, cast2 

V procedúre/vo funkcii najlepsieRozdelenie na začiatku zvolíme najhoršie rozdelenie (aby sme ho vedeli postupne vylepšovať). Všetok tovar dáme do jednej skupiny. Potom postupne testujeme každé z možných rozdelení. Ak nájdeme nejaké lepšie rozdelenie, zapamätáme si ho. Pre výpočet rozdielu hmotností skupín sme si vytvorili pomocnú procedúru/funkciu rozdiel. Tá nám vypočíta, aký je rozdiel hmotností skupín pre zadané rozdelenie.

Nakoniec podľa najlepšieho rozdelenia rozdelíme výrobky do dvoch skupín a tieto dve skupiny vrátime ako návratovú hodnotu.

Pozrime sa ešte, či naše riešenie nevieme nejako vylepšiť. Všimnime si prvé a posledné rozdelenie, alebo druhé a predposledné alebo ... Líšia sa len v tom, že skupiny sú navzájom prehodené. To čo bolo v prvej polovici bude v druhej a naopak. Je to prakticky to isté rozdelenie (s tým istým rozdielom hmotností skupín). Nemusíme teda testovať všetky prerozdelenia, ale len polovicu z nich.

#Python

...
def najlepsieRozdel(vyrobky):
    ...
    pocetPrerozdeleni = 2 ** (len(vyrobky) - 1)
    ...

V tejto chvíli by sme mohli byť s nájdeným riešením spokojní. Ak našou jedinou požiadavkou je nájsť najlepšie prerozdelenie, mohli by sme skončiť. Pre tých, čo radi skúmajú je tu ešte jedna otázka. Ako rýchlo nájdeme najlepšie prerozdelenie tovarov?

Spravme malý experiment. Predpokladajme, že otestovanie jedného prerozdelenia bude trvať 0,001 sekundy. Vieme, že potrebujeme preskúmať polovicu všetkých prerozdelení a to je 2^{počet tovarov - 1}. Ak máme napr. 10 tovarov je to 2⁹ = 512. Bude nám to teda trvať 0,512 sekundy. To nie je také zlé. Ale, čo ak máme tovarov 20 alebo 30? Pri 20 tovaroch je to 2¹⁹ = 524288, to znamená 524,288 sekundy. Pri 30 tovaroch je to 2²⁹ = 536870912, to znamená 536870,912 sekundy. A to je už poriadne veľa. Je to viac ako 6 dní. Sme teda v situácii, že máme síce riešenie, ktoré nám nájde najlepšie rozdelenie ale trvá mu to tak dlho, že niekedy je prakticky nepoužiteľné. Spomeňme si na postupy, ktoré sme uvažovali na začiatku. Tie síce nenašli vždy to najlepšie prerozdelenie, ale boli veľmi rýchle. Boli až také veľmi zlé, aby sme ich nemohli použiť? Overme si to.

Spravme niekoľko testov. Pre rôzne hmotnosti výrobkov nájdime rýchlou stratégiou nejaké "dobré" rozdelenie, porovnajme ho s najlepším rozdelením a zistime ako veľmi sa líšia. Podľa rozdielu sa rozhodneme, či obetujeme čas na nájdenie najlepšieho rozdelenia alebo sa uspokojíme s nejakým "dobrým", ale rýchlo nájditeľným rozdelením. Otestujme nasledovnú stratégiu. Usporiadajme hmotnosti tovarov od najväčšej po najmenšiu a postupne tovary prerozdeľujme do skupín tak, že tovar pridáme do tej skupiny, v ktorej je celková hmotnosť menšia.

#Python

def rychloRozdel(vyrobky):
    vyrobky.sort(reverse = True)
    cast1 = []
    hmotnost1 = 0
    cast2 = []
    hmotnost2 = 0
    for vyrobok in vyrobky:
        if hmotnost1 < hmotnost2:
            cast1.append(vyrobok)
            hmotnost1 = hmotnost1 + vyrobok
        else:
            cast2.append(vyrobok)
            hmotnost2 = hmotnost2 + vyrobok
    return cast1, cast2 

Aby sme túto stratégiu otestovali, náhodne sme vygenerovali 100 množín výrobkov. Každá z nich obsahovala 5 až 20 výrobkov, ktorých hmotnosti sa pohybovali od 20 do 1000. Pre každú množinu sme našli najlepšie a "dobré" rozdelenie. Rozdiel hmotností skupín "dobrého" rozdelenia sa od rozdielu hmotností skupín najlepšieho rozdelenia vzhľadom na celkovú hmotnosťou výrobkov líšil priemerne len o 0,06 %. To nás môže viesť k záveru, že "dobré" rozdelenie je prakticky rovnako dobré ako najlepšie. V  tomto prípade zrejme áno. Toto však nestačí na to, aby sme mohli takýto záver vyhlásiť vo všeobecnosti. Záleží totiž na počte výrobkov ktoré je potrebné prerozdeliť a na rozsahu ich hmotností.

Aký je teda záver? Ak požadujeme najlepšie prerozdelenie, musíme sa uspokojiť s časovo náročným riešením. Ak nám stačí "dobré" prerozdelenie, môžeme využiť rýchle nájdenie riešenia. Či je však v konkrétnom prípade použiteľné si musíme overiť (napr. porovnávacími testami na skupine typických množín, ktoré chceme rozdeliť).

A ešte jedna poznámka na záver. Týmto problémom sa informatici zaoberajú už pomerne dlho. Zatiaľ sa im, až na niektoré špeciálne prípady, nepodarilo nájsť lepšie riešenie ako to naše.

Vaše zaujímavé riešenia a najčastejšie chyby

Do riešenia tejto úlohy sa nezapojil žiaden tím.