Optimální algoritmus výpočtu

[Logik]

Tak, jak je definována složitost v NP úplnosti (pokud bude vstup zadanej efektivně), tak to polynomiální nebude. Viz předchozí post.

[Reklama]

[Paja]

Proc by nebylo ? Ted to je O((n+max(pocet_v_baleni))^2)

Pridavam predelany kod ktery respektuje vyse zminenou diskuzi

Kód: [Vybrat]

<?

  // definice baleni dle zadani. Klic je pocet ks, hodnota je cena za ks
  $baleni=array(1=>20,5=>18,10=>19,50=>17);
  // zadany pocet ks
  $ks=78;
  // priznak zda muzu vyhodit nejake kusy. Napriklad celkova cena pro 49 je vetsi nez pro 50ks
  // vyplati se koupit 50 a 1 vyhodit  
  $muzuvyhazovat=true;
  // nadale budu pouzivat baleni od nejvetsiho poctu kusu v baleni. Na objednavce to bude vypadat lepe.
  krsort($baleni);
  // kontrola jestli je zadane baleni 1ks. To zaruci moznost poskladat jakykoliv pocet ks
  // cena za nejmensi baleni - budu ji potrebovat
  end($baleni);
  $nejmensibalenicena=current($baleni)*key($baleni);
  if (!isset($baleni[1])) {
    if ($muzuvyhazovat) {
      // naplnim baleni mensi nez nejmensi s tim ze se musi vyhodit nejake kusy
      for ($i=key($baleni)-1;$i>=1;$i--) {
        $baleni[$i]=$nejmensibalenicena;
      }
    } else {
      // zkontroluju zda to muzu vubec dodat z dannych baleni
      $deleno=false;
      foreach ($baleni as $pocet=>$tmp)
        if (!$deleno and ($ks % $pocet==0)) $deleno=true;
      if (!$deleno) die("pocet neni mozno poskladat z moznych baleni");
    }  
  }  
  // pokud je pocet ks vetsi nez nejmensi spolecny nasobek baleni (nsnb), staci pocitat optimalni ceny pro nsbn a zbytek po deleni
  // poctu nsbn. Napr. pokud chci 738 baleni a nsnb je 70, tak vysledek bude 10*cena(nsnb)+cena(38)
  // Proc? protoze mnozstvi nsbn lze poskladat z kterehokoliv baleni, lze ho poskladat i z baleni s nejnizi cenou za kus
  
  // nebudu tady psat eukliduv algoritmus at to neni dlouhe, spokojim se s kratkym orientacnim vypoctem. Kdyztak si ho sem dopiste.
  $nsnb=1;
  foreach ($baleni as $pocet=>$tmp) 
   if (($nsnb % $pocet) !=0) $nsnb*=$pocet;
   
  // pocet kombinaci ktery musim spocitat. Je to bud ks nebo nsbn - co je mensi
  $n=$ks<$nsnb?$ks:$nsnb;
  // jestli muzu vyhazovat, pridam jeste nejvetsi baleni k vypoctu
  reset($baleni);
  if ($muzuvyhazovat) $n+=current($baleni);

  /* ceny je pole, kde budu ukladat navrhy kombinaci pro jednotlive pocty.
   * klic bude pocet, hodnoty budou mit nasledujici strukturu   
   * cena .. celkova cena
   * index .. prvni index ze ktereho se sklada. Pokud jde o baleni, nebude existovat
   * viz nasledny vypocet. Druhy index je pocet-index. Napr. 42 s indexem 15 znamena ze
   * se sklada z vypoctenych kombinaci baleni 15 a (42-15) tj. 27   
   * pokud muzu vyhazovat, a bude index zaporny, znamena to ze mam koupit klic - index a zbytek vyhodit    
   */
  $ceny=array();
  // baleni 1ks je nutno vzit z definice. 
  if (isset($baleni[1])) {
    $ceny[1]["cena"]=$baleni[1];
  } else {
    $ceny[1]["cena"]=$nejmensibalenicena*2;
  }  
  // vyplnim hodnoty pro vsechny ostatni pocty az po n
  for ($i=2;$i<=$n;$i++) {
    // kazde baleni lze vyjadrit jako kombinaci dvou jinych baleni o mensich mnozstvich
    // je jasne ze kombinaci je mnozstvi/2. A take je jasne ze jedna z techto kombinaci je nejlepsi
    // jako vychozi nejlepsi kombinaci ulozim soucet baleni 1 a o 1 mensi nez hledane
    $nejindex=1;
    $nejcena=$ceny[1]["cena"]+$ceny[$i-1]["cena"];
    // staci prohledavat do poloviny hodnoty
    for ($j=2;$j<intval($i/2);$j++) {
      if ($nejcena>$ceny[$j]["cena"]+$ceny[$i-$j]["cena"]) {
         $nejcena=$ceny[$j]["cena"]+$ceny[$i-$j]["cena"];
         $nejindex=$j; 
      } 
    }
    // ted zjistim jestli nahodou neni baleni o hledanem mnozstvi a nema lepsi cenu nez nalezena kombinace
    // pozor musim dat na prepocet celkove ceny a ceny za kus
    if (isset($baleni[$i]) and ($baleni[$i]*$i<$nejcena)) {
      // mam baleni a vychazi lepe
      $ceny[$i]["cena"]=$baleni[$i]*$i;
    } else {
      // ne, je potreba to poskladat
      $ceny[$i]["cena"]=$nejcena;
      $ceny[$i]["index"]=$nejindex;
    }
  }  
  
  // v pripade ze mam povoleno vyhazovat, zjistim jestli je vyssi cena pro nizsi index. Pokud ano, tak nastavuju zaporny index
  if ($muzuvyhazovat) {
    for ($i=$n-1;$i>=1;$i--)
      if ($ceny[$i+1]["cena"]<=$ceny[$i]["cena"]) {
        // vyplati se vyhodit, vyhazuju i v pripade ze je cena stejna
        if (!isset($ceny[$i+1]["index"]) or ($ceny[$i+1]["index"]>0)) {
          // je to cele baleni, napr. 50ks, nebo kladny index v baleni
          $ceny[$i]["index"]=-1;
        } else {
          // uz o 1 vyssi pocet je lepe vyhodit, takze index dam rovnou na to puvodni
          // napr zkoumam 48. 49 melo index -1 a ukazovalo na 50. Spoctena cena je porad vyssi nez pro 50, index dam -2 (=-1-1)
          $ceny[$i]["index"]=$ceny[$i+1]["index"]-1;
        }
        // a dosadim novou cenu
        $ceny[$i]["cena"]=$ceny[$i-$ceny[$i]["index"]]["cena"];
      }
  } 
  
  // ted musim udelat vysledky
  // do pole objednat naskladam vsechny indexy baleni, hodnota bude pocet baleni
  // nastavim na 0
  $objednat=array();
  foreach ($baleni as $pocet=>$tmp) $objednat[$pocet]=0;
  
  // na naplneni si udelam rekurentni funkci (zabere to mene radku)
  // misto global to muze byt predavano odkazem, tohle je hezci 
  function pridej($mnozstvi) {
    global $objednat,$ceny;
    if (!isset($ceny[$mnozstvi]["index"])) {
      // je to cele baleni
      $objednat[$mnozstvi]++;
    } else {
      pridej($mnozstvi-$ceny[$mnozstvi]["index"]);
      if ($ceny[$mnozstvi]["index"]>0) {
        // u slozeneho bez vyhazovani i druhou cast
        pridej($ceny[$mnozstvi]["index"]);
      }
    }
  }
  
  // pokud je ks>nsnb tak nejprve pridam nsnb nasobene poctem nsnb v ks
  $x=$ks;
  if ($x>$nsnb) {
    pridej($nsnb);
    $nasob=intval($ks/$nsnb);
    foreach ($objednat as $pocet=>$tmp) $objednat[$pocet]*=$nasob;
    $x-=$nasob*$nsnb;
  }
  pridej($x);
  
  // uz jen ukazat vysledky
  $celkem=0;
  echo "Objednavka:<hr>\n";
  foreach ($objednat as $pocet=>$chceme) 
    if ($chceme) {
      echo "$chceme x baleni $pocet ks<br>\n";
      $celkem+=$baleni[$pocet]*$pocet*$chceme;
    } 
  echo "<hr>CELEKEM $celkem penez<br>\n";
       

?>

[Logik]

T a k  j e š t ě  j e d n o u  a  p o m a l u .  : - )

Složitost v NP úplnosti je (trochu zjednodušuji) definována jako složitost na základě BITOVÉ délky vstupu.
n na vstupu bude efektivně kódováno pomocí m=log(n) bitů. Takže zanedbám-li počet
balení, na kterém to roste pomaleji, výsledná složitost je O(exp(m)^2).

edit: oprava log za exp, nějak mi to uteklo :-)

[Paja]

To mi hlava nebere.
Dycky nas ucili, ze treba u bubblesortu je to O(n^2). N je pocet prvku ktere se maji setridit. Quicksort je O(n*log n). Atd ...

Takze pokud je vstup n = pocet_hledanych_ks +  pocet_v_nejvetsim_baleni (nejhorsi pripad) a algoritmus provede maximalne n (inicializace) + n^2/4 (hledani variant) + 2*n (ziskani vysledku vypoctu) kroku je slozitost O(n^2)

Tudiz se jedna po polynomialni problem - narust slozitosti lze vyjadrit polynomem.

[Paja]

Jeste bych dodal ze opravdu nas zajima zavislost casu vypoctu na poctu objednanych ks.
Ne na logaritmu poctu objednanych ks.
Predstavte si kolik vlaku by jste potreboval pro odvoz baleni hmotnosti 1kg a objemu 1l pri poctu n, kdy je logaritmus o zakladu 2 z n je 64 ....

[Reklama]

[Logik]

Jak je definovaná složitost jinde je pooměrně irelevantní - pokud se bavíme o NP úplnosti, tak prostě musíme brát složitost tak, jak je definovaná v NP úplnosti.

Jinak problém téí naivní definice je v tom, že to není deinice. Ono podle toho bys moh tvrdit, že složitost je lineární - jde vyjádřit lineární závislostí na počtu nutných prohození prvků aby to bylo setříděné.
Jednoduše řečeno, jiný relevantní údaj než délka vstupu, který bybyl společný pro všechny algoritmy nemáš.

Btw. Složitost bublesortu je i podle definice v NP úplnosti O(n^2), protože délka vstupu je úměrná počtu prvků.

Co jsi chtěl vyjádřit tím vblakem už vůbec nechápu, zaprve výpočet a převoz zboží je jaksi něco jiného, zadruhé pokud bych připustil nějakou analogii, tak na vstupu algoritmu převez
n balíků nemůže být počet balíků, ale ty samotné balíky, takže ne log n prvků, ale n prvků.

Pokud bych měl počet těch balíků, tak jediné co mohu převést je zas jen ten počet balík. A ten jde vyjádřit opravdu v log n bitů, takže pokud bych uměl zabalit jeden bit do jedné krabice, tak bych opravdu musel převést pouze log n krabic.

[Paja]

No proste si predstav, ze delka vstupu v tomto pripade je umerna poctu objednanych ks.

Jina interpretace delky vstupu je iracionalni. Coz jsem popsal variaci na tema sachovnice a zrnka ryze.

Kdyby jsi pouzil stejny pristup jako k tomuto pripadu i k bubblesortu, mohl by jsi prohlasit, ze te zajima zavislost na nizsi z hodnot pocet trizenych cisel, logaritmus z maximalni trizene hodnoty.

Pokud si chces definovat slozitost algoritmu vyse uvedeneho prikladu, jako zavislost na logaritmu poctu kusu, je to tva volba. Ja bych to takto nikdy nedefinoval, protoze to nema zadny smysl.

A za pravdu mi da to, ze pro rozumne priklady vypoctu (tedy fyzikalne realizovatelne dodavky), se to da spocitat v malem case. Na rozdil od obchodniho cestujiciho. U ktereho pro 100 zastavek nebudes schopen spocitat nejlepsi variantu v rozumnem case.

Coz se presne shoduje s definici NP.

[Logik]

No proste si predstav, ze delka vstupu v tomto pripade je umerna poctu objednanych ks.

Ano, pokud by byla, tak by to platilo. Ale vstup by byl velmi neefektivní. Když se baví lidé o algoritmu bez zadaného vstupu, bere se za samozřejmé, že je vstup optimální.

Stejnětak bych mohl tvrdit, že POC není NP, protože můžu vzít jeho vstup, doplnit 2^N bytama redundance a kontrolních součtů a mám z toho polynomiální algoritmus.

Na rozdil od obchodniho cestujiciho. U ktereho pro 100 zastavek...

Ano, ale tam musí být každá zastávka ve vstupu jako samostatnej kus dat se vzdálenostma od ostatních. Nejde napsat vyřeš POC, který má sto zastávek. To je právě ten rozdíl.

Coz se presne shoduje s definici NP.

Neshoduje. Prosím, přečti si definici NP. Tam je složitost prostě definovaná tak jak je. Nemá smysl se bavit o NP, když nevíš, jak je definovaná.

[Paja]

Myslim ze michas pojmy.

Definice slozitosti:
N se většinou myslí velikost vstupních dat. Treba pro trizeni je to pocet prvku. V nasem pripadu to je pocet ks.
Pojem asymptotická složitost znamená, že nás zajímá chování funkce pro velká N. Treba bublesort je O(n^2), quicksort O(n*log n)
Je zrejme ze slozitost vyse uvedeneho algoritmu je O(n^2).

Definice P uloh
Třída P obsahuje problémy, které se dají řešit tak, že není potřeba víc kroků, než kolik se dá vyjádřit polynomem. A n^2 je polynom. Dokonce maly polynom - jen druheho stupne.
Uloha je tedy ze tridy P.

Prozatim se predpoklada ze P je podmnozina NP. A nikdo zatim nedokazal ze P=NP.

[Logik]

To cos napsal není ani definice složitosti (v NP úplnosti), ani definice třídy P. Jestli nevěříš, tak běž na MFF na přednášku Úvod do složitosti a NP úplnosti, nebo si přečti o NP úplnosti nějakou knihu.

PS: http://mj.ucw.cz/vyuka/0910/ads2/11-np.pdf
úloha batoh optimalizace je v podsatatě to samé a je tady uvedena mezi NP-úplnými úlohami.

PPS: To, cos napsal, je parafráze definice asymptotické složitosti. Ta se hodí pro sledování složitosti algoritmů řešících konkrétní problém v závislosti na daném kritériu. Nejde však použít k srovnání různých algoritmů, protože nemusí mít shodné kritérium.... tedy, jedno shodné kritérium dva libovolné algoritmy mají: délku vstupu....