Problém batohu 1

Úloha z předmětu 36PAA

Martin Tůma

Zadání

  1. Naprogramujte řešení 0/1 problému batohu [1] hrubou silou [2]. Na zkušebních datech [4] pozorujte závislost výpočetního času na n.
  2. Naprogramujte řešení 0/1 problému batohu heuristikou podle poměru cena/váha [3]. Pozorujte:
    • závislost výpočetního času na n. Grafy jsou vítány(i pro exaktní metodu).
    • průměrné zhoršení proti exaktní metodě
    • maximální relativní chybu. Absolutní chyba nic neříká!

Řešení

1. Řešení "hrubou silou"

Použitý algoritmus generuje všech 2n kombinací věcí umisťovaných do batohu a testuje obě podmínky (zda zvolená kombinace nepřetíží batoh a zda cenová funkce nabývá maxima). Složitost algoritmu je tedy O(2n).

2. Řešení heuristikou typu nejrychlejšího vzestupu

Věci jsou seřazeny podle daného kritéria (klesající poměr cena/hmotnost). Začíná se s věcí, která má toto kritérium nejlepší, a v každém kroku se do batohu vkládá věc s další nejlepší hodnotou, která se do batohu ještě vejde. Takto se pokračuje až do naplnění batohu. Složitost algoritmu je dána složitostí řazení, v případě použitého quicksortu je tedy O(n·log(n)).

Naměřené hodnoty

Měření probíhala v následujícím prostředí: PC s CPU Celeron M 1.47GHz, Linux 2.6.20, gcc 4.1.2. Naměřené časy u časových závislostí jsou udávány vždy pro celý vstupní soubor, tzn. 50 instancí problému.

Časové závislosti

n410152022 2527
t[s]0.0010.0040.1686.948 29.95268.51158

Graf 1. Řešení "hrubou silou".

n410152022 252730323537 40
t[ms]1.3482.3683.3524.204 4.6965.2165.7526.2526.660 7.3207.8208.393

Graf 2. Řešení heuristikou typu nejrychlejšího vzestupu.

Relativní chyby heuristiky

Vstupní dataPrůměrná relativní chyba Maximální relativní chyba
knap_4.txt 0,0217450,363636
knap_10.txt0,0128620,114801
knap_15.txt0,0047590,085427
knap_20.txt0,0060010,084337
knap_22.txt0,0068670,072289
knap_25.txt0,0049840,036789
knap_27.txt0,0050170,106017
knap_30.txt0,0050740,055138
knap_32.txt0,0034120,033408
knap_35.txt0,0028020,046092
knap_37.txt0,0034360,081967
knap_40.txt0,0019950,023372

Závěr

Řešení pomocí "hrubé síly" potvrdilo svojí výpočetní náročnost, pro n>27 již výpočet jediného řešení trvá řádově minuty. Naopak výpočet pomocí heuristiky typu nejrychlejšího vzestupu podle poměru cena/hmotnost je použitelný i pro řádově vyšší n. Relativní chyba oproti optimu se pro n>10 pohybuje v jednotkách procent a s rostoucím n klesá.

Reference

[1] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html
[2] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html#bruteforce
[3] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html#greedy
[4] http://service.felk.cvut.cz/courses/36PAA/knapsolv.html#bench

Přílohy

1. batoh_brute.c - Program pro řešení problému hrubou silou.
2. batoh_h1.c - Program pro řešení problému pomocí heuristiky.
3. stats.sh - Script na výpočet relativních chyb heuristiky