KöMaL - Középiskolai Matematikai és Fizikai Lapok
Belépés
Regisztráció
 English
Információ
A lap
Pontverseny
Cikkek
Hírek
Fórum
Versenykiírás
Tudnivalók
Nevezési lap
Feladatok
Eredmények
Korábbi évek
Arcképcsarnok
Munkafüzet

Rendelje meg a KöMaL-t!

VersenyVizsga portál

Kísérletek.hu

Matematika oktatási portál

Az S. 2. feladat értékelése és megoldása

Az egyszerű megoldáshoz a dinamikus programozást volt célszerű használni. Miről is szól a dinamikus programozás? Ezt először egy példán keresztül világítjuk meg.

Feladat: Számítsuk ki az n. Fibonacci számot!

Első megoldás:

#include <stdio.h>
#include <sys/types.h>

int n;

long int fib(int n1)
{
  if (n1 < 2) return(n1);
  return(fib(n1-1)+fib(n1-2));
}

main()
{
  scanf("%d",&n);
  printf("F(%d)=%d\n",n,fib(n));
}

Ez a kézenfekvő, a definíciónak megfelelő rekurzív program. Ha teszteljük a futását, már n=45 esetén nagy meglepetések érnek! Ha kiszámoljuk, hogy hány lépést tesz meg a program, azt kapjuk, hogy F(n) kiszámolásához legalább F(n) lépés kell, ami nagyobb mint an-2 (ahol a~=1.618), tehát exponenciálisan nagy. Már F(45) kiszámításához is 42 másodpercre van szükség, mivel több, mint F(45)=1134903170 lépés kell. Ha megvizsgáljuk, hogy miért ilyen lassú a program, rájöhetünk, hogy az az oka, hogy bizonyos dolgokat (pld. F(2) értékét) ez a program rengetegszer -- újra meg újra -- kiszámolja.

Azt a módszert, ami ezt a hibát kiküszöböli, dinamikus programozásnak nevezzük. A módszer lényege, hogy ha valamit már egyszer kiszámoltunk, annak eredményét írjuk fel, és eszünkbe se jusson még egyszer kiszámolni, hanem helyette nézzük meg a felírtak között. Persze a módszerhez még az is hozzátartozik, hogy a részfeladatok eredményét jó sorrendben kell kiszámolni, ügyesen a kisebbektől a nagyobbakig, hogy minden pillanatban a felhasználandó részeredmények már fel legyenek írva.

Mit jelent ez a fenti példára? Azt, hogy jobban járunk, ha sorban kiszámoljuk minden i-re F(i) értékét, mint pl. az alábbi programban:

#include <stdio.h>
#include <sys/types.h>

long int F[50], n, i;

main()
{
  scanf("%d",&n);
  F[0]=0;
  F[1]=1;
  for (i=2; i<=n; i++) F[i]=F[i-1]+F[i-2];
  printf("F(%d)=%d\n",n,F[n]);
}

Ez a program már kevesebb, mint 0,01 másodperc alatt kiszámolja F(45) értékét, és nyilván F(n) kiszámításához csak n+1 lépésre van szükség.


A hátizsák feladat megoldása dinamikus programozással

Először a megoldandó részfeladatokat kell jól definiálni. Minden 0≤i<n-re és minden j≤w-re kiszámítjuk, hogy az első i+1 darab tárgy felhasználásával maximum mennyi értéket lehet bepakolni egy j tömeget elbíró hátizsákba. (A tárgyakat 0-tól n-1-ig sorszámozzuk.) Ezt egy T tömbben fogjuk eltárolni, tehát adott i érték mellett T[j] fogja jelölni, hogy az első i+1 darab tárgy felhasználásával maximum mennyi értéket lehet bepakolni egy j tömeget elbíró hátizsákba. Persze ha minden i-re ugyanazt a T tömböt használjuk, oda kell figyelni, hogy az új T[j] értékeket jó sorrendben számoljuk ki.

Egy új T[j] érték kiszámolásához azt kell észrevenni, hogy két eset lehetséges:

  • Az első i+1 tárgyból ugyanannyi értéket lehet legfeljebb j tömegbe berakni, mint az első i tárgyból, ekkor T[j] értéke nem változik, vagy
  • Nagyobb értéket tudunk berakni, ekkor persze használnunk kell az i. tárgyat, és így T[j]=E[i]+T[j-V[i]], ha T[j-V[i]] még az első i tárgyra vonatkozó optimumot tartalmazza. (Itt E[i] jelöli az i. tárgy értékét, V[i] pedig a tömegét. Felhasználjuk a szuboptimalitás elvét, ami durván azt mondja ki, hogy egy optimális megoldásban egy részmegoldás szükségképpen a megfelelő részfeladatnak optimális megoldását adja. Ahol ez nem teljesül, ott esélyünk sincs dinamikus programozással megtalálni az optimumot!)
A megfelelő programrészlet:
for (i=0; i<=w; i++) T[i] = 0;
for (i=0; i<n; i++) {
  for (j=w; j>=V[i]; j--) {
    if (T[j-V[i]]+E[i] > T[j]) {
      T[j] = T[j-V[i]]+E[i];
    }
  }
}
printf("Elerheto ertek: %d\n", T[w]);
Akik erre rájöttek, már 9 pontot szerezhettek. Ez a program csak akkor működik jól, ha a w össztömeg elég kicsi. Ha w nagy, de a szobajöhető összérték kicsi, akkor egy másik hasonló dinamikus programot írhatunk. Jelölje osszertek a tárgyak értékeinek összegét (ha tudunk jobb felső becslést az optimum értékre, azt is írhatjuk ide). Most az i. iterációban T[j] értéke azt fogja tartalmazni, hogy az első i+1 tárgyból pontosan j értéket legkevesebb mennyi tömegben tudunk összerakni. Ha egyáltalán nem tudunk, akkor (végtelen helyett) a w+1 értéket tároljuk. Itt is igaz, hogy az új T[j] kiszámításakor az optimális megoldás vagy nem tartalmazza az i. tárgyat, ekkor T[j] értéke nem változik, vagy tartalmazza, és ekkor T[j]=T[j-E[i]]+V[i]. A megfelelő programrészlet:
for (i=1; i<=osszertek; i++) T[i] = w+1;
T[0] = 0;
for (i=0; i<n; i++) {
  for (j=osszertek; j>=E[i]; j--) {
    if ((T[j-E[i]]+V[i] < T[j])) {
      T[j] = T[j-E[i]]+V[i];
    }
  }
}
for (i=osszertek; i>=0; i--) {
  if (T[i] <= w) {
    max = i;
    i = 0;
  }
}
printf("Elerheto ertek: %d\n", max);
A kétféle megoldás közül nyilván célszerű azt választani, amelyik várhatóan gyorsabb. A teljes program C nyelven innen tölthető le.

Értékelés

Összesen 17 megoldás érkezett. Sokan exponenciális idejű algoritmust adtak (minden lehetőség kipróbálása, vagy rekurzív eljárás), ezek a kis tesztekre se tudtak 10 percen belül lefutni. Így nulla pontot kapott Gyüre Balázs, Koszó Norbert, Maróti Árpád, Ozsvárt László (nála picire is rossz az eredmény), Szánthó Csaba és Szoldatics András. Szintén nulla pontot kapott Ökrös Tamás, akinek a programja minden kis tesztre hibás végeredményt adott. Kicsit ügyesebben megírt exponenciális algoritmust adott Filus Tamás, az Ő programja a kis tesztek felén lefutott, ezért 2 pontot kapott.

A legérdekesebb Engedy Balázs ún. backtrack algoritmusa volt, ez az óriás teszteken minden más versenyzőénél sokkal gyorsabban futott le (2.2 ill. 1.1 másodperc), viszont például az egyik kicsi teszten (100 tárgy, minden tömeg és érték <210) 22 óra alatt sem tudott lefutni. Ezt a teljesítményt -- hosszas vívódás után -- 6 ponttal jutalmaztuk.

A többiek dinamikus programozást használtak. Deák Áron programja a T tömb újrahasznosítása helyett egy mátrixban tárolta az összes i-re az értékeket, ezért a nagy teszteken már nem futott le. Ezenkívül a program egy kisebb hibát is tartalmazott (az iii változó a while ciklusban fel tudott venni n-nél nagyobb értékeket is), ezért 4 pontot kapott. Vincze János és Strenner Balázs programja egyik óriás teszten se futott le, Strenner Balázs 8, Vincze János 7 pontot kapott (a kétmondatnyi leírás miatt). Kuti József szintén 7 pontot kapott (bár az egyik óriás teszten 55 perc alatt lefutott, de az algoritmus leírása hiányzott, a programba írt commentek nem voltak jól érthetőek). Acsai Péter, Földényi Miklós és Nikházy László 9 pontot kaptak, az első óriás tesztre háromnegyed órán belül jól lefutott a programjuk. 10 pontos lett Stippinger Marcell programja, az óriás teszteken 19 illetve 8.5 perc alatt lefutott. Ez a program egy kicsit bonyolultabb, rendezi a tárgyakat érték és tömeg szerint is, és ezt használva bizonyos tárgyakról már eleve tudja, hogy nem lehetnek benne az optimumban. Az 5 pontnál többet elérő versenyzőknek gratulálunk!

Aki kiváncsi egy profi programra is, megtalálhatja David Pisinger programjait a http://www.diku.dk/~pisinger/codes.html oldalon, az itt található MINKNAP program az első óriás teszten 0.04, a másodikon 0.15 másodperc alatt futott le! (A programokat AMD 1800+ processzoron futtattuk).

Támogatóink:   Ericsson   Cognex   Emberi Erőforrás Támogatáskezelő   Emberi Erőforrások Minisztériuma   Nemzeti Tehetség Program    
MTA Energiatudományi Kutatóközpont   MTA Wigner Fizikai Kutatóközpont     Nemzeti
Kulturális Alap   ELTE   Morgan Stanley