Třídicí algoritmus pro disková pole

[Mirek Prýmek]

Tohle je ale problém, kterej tu autor řeší a verdikt zní: "Bin packing is strongly NP-HARD": http://link.springer.com/chapter/10.1007/3-540-29297-7_18

K placenemu Springeru uz nemam pristup a v nahledu to nevidim, ale budu ti verit

ale už vůbec neřeší druhou část zadání:

a pritom zbylo co nejvic volneho mista na konci

Ok, tak to mi asi teda uniklo. Diky za upresneni.

[Reklama]

[Logik]

Z toho co jsem našel, tak

Decision problem (vejde se to do X binů) je NP-complete.
Optimální řešení je strongly NP-hard (tzn. není NP) nezávisle na tom, jestli je požadavek
na nejvíce zbylého místa k posledním kontejneru.

Požadavek na nejvíce místa v posledním kontejneru nebude měnit třídu problému, protože
to určitě půjde "NP-převést" na problém s N+1 předměty, kde ten N+první představuje volné
místo. Ale důkaz po mě nechtějte (což znamená, že to možná nejde? :-))

[jenda]

jj, cyr,logik,
kdo neskladal eternity, nevi, co je vyzva

[Mirek Prýmek]

Decision problem (vejde se to do X binů) je NP-complete.
Optimální řešení je strongly NP-hard (tzn. není NP)

Mne porad neni uplne jasny rozdil mezi temihle dvema problemy. Nemel jsem cas se na to poradne podivat kvuli pareni XComu se synem Muzete mi to nekdo nejak polopaticky, ale presne vysvetlit?

Ten prvni problem je predpokladam otazka "Mam mnozinu bucketu a mnozinu predmetu, vejdou se predmety do bucketu?" s odpovedi ano/ne.

A ten druhy problem je teda presne jak? Protoze jestli to je "Jak naskladat predmety do nejmensiho poctu bucketu", tak pak nerozumim tomu, proc bych nemohl pouzit ten decision problem k tomu, abych se ptal "Vejde se to do jednoho? Vejde se to do dvou? atd." - coz by bylo jenom polynomialni rozsireni, takze mi porad neni jasne, jak muze ten problem skocit do jine slozitosti.

[anonym]

A) hladovym algoritmem (tedy vzdy vezmes disk a postupne koukas kam ho muzes vrazit) dostanes nejhure 2x horsi reseni
B) s iterativnim resenim batohu (ktere co si pamatuju je v celych cislech polynomialni) by ses mel dostat na velice blizkou aproximaci

[Reklama]

[Cyr]

Decision problem (vejde se to do X binů) je NP-complete.
Optimální řešení je strongly NP-hard (tzn. není NP)

... abych se ptal "Vejde se to do jednoho? Vejde se to do dvou? atd." - coz by bylo jenom polynomialni rozsireni, takze mi porad neni jasne, jak muze ten problem skocit do jine slozitosti.

Problém je, že z definice NP problémů, musí být odpověď (tzv. ANO-instance) ověřitelná v polynomiálním čase. Jednoduchý popis třídy NP lze najít na http://www.algoritmy.net/article/5774/Tridy-slozitosti - pro detaily bych Vás odkázal na Teorii algoritmů od prof. Demlové - celé tohle vychází z principu definice NP problémů - tj. z výpočtu na nedeterministickém Turingvu stroji.

Výsledek Vašeho algoritmu by byl: optimální počet kyblíků je N. Jak ale ověříte v polynomiálním čase, že to není méně? Jak v polynomiálním čase ověříte, že neexistuje lepší řešení, např. N-1, N-2 atd. - to je ten problém a důvod, proč úloha nepatří do NP (samozřejmě pokud někdo nedokáže, že existuje polynomiální ověření řešení).

[Mirek Prýmek]

Výsledek Vašeho algoritmu by byl: optimální počet kyblíků je N. Jak ale ověříte v polynomiálním čase, že to není méně? Jak v polynomiálním čase ověříte, že neexistuje lepší řešení, např. N-1, N-2 atd. - to je ten problém a důvod, proč úloha nepatří do NP (samozřejmě pokud někdo nedokáže, že existuje polynomiální ověření řešení).

Slo mi o to, v cem presne je rozdil tech dvou uloh. Ale to je jedno, zas tak moc mi to zily netrha

[jenda]

rozdil je v tom "optimalni". porad nic ?

[Mirek Prýmek]

rozdil je v tom "optimalni". porad nic ?

nerozumim tomu, proc bych nemohl pouzit ten decision problem k tomu, abych se ptal "Vejde se to do jednoho? Vejde se to do dvou? atd." - coz by bylo jenom polynomialni rozsireni, takze mi porad neni jasne, jak muze ten problem skocit do jine slozitosti.

[Logik]

Problém je v tom, že to, že problém je v NP znamená, že umíme v polynomiálním čase říci, zda ANO. Nikoli zda NE. Takže prozkoumání těch záporných odpovědí může trvat libovolně dlouho a tedy Tvůj stroj nebude polynomiální.

Ale učil jsem se to před pěknou dobou a tak si to také nepamatuju přesně - proč vlastně pro tu odpověď NE nejde udělat modifikovaný TS, který bude vedle počítat čas a když překročí limit tak dá odpověď že NE? Nepamatujete si to někdo? To počítání nejde implementovat v polynomiálním čase? Nebo kde je problém?

[Mirek Prýmek]

Problém je v tom, že to, že problém je v NP znamená, že umíme v polynomiálním čase říci, zda ANO. Nikoli zda NE. Takže prozkoumání těch záporných odpovědí může trvat libovolně dlouho a tedy Tvůj stroj nebude polynomiální.

Myslel jsem, ze "v polynomialnim case overit" znamena, ze mi das vstupni data a odpoved - tzn. "set A se vejde do bucketu B" nebo "set A se do bucketu B NEvejde" - a umim v polynomialnim case overit, ze to je pravda. Pokud budu mit ten druhy pripad ("nevejde"), tak musim umet polynomialne rychle zjistit, ze optimalni reseni MUSI pouzivat vic bucketu. Tim, ze to zopakuju n-krat (-> polynomialni rozsireni) tak zjistim, kolik nejmin bucketu potrebuju. Cili ziskam pocet bucketu optimalniho reseni.

Ale učil jsem se to před pěknou dobou a tak si to také nepamatuju přesně

Ja taky, navic jsem k tomu pristupoval se silnou pasivni resistenci a navic jsem momentalne nachcipanej, takze mi to mozna nemysli - proto jsem se ptal, jestli tady neni nekdo, kdo mi by mi to mohl vysvetlit nejak polopaticky (veci z teoreticke informatiky vetsinou jdou vysvetlit uplne jednoduse, pokud jim clovek dostatecne rozumi).

- proč vlastně pro tu odpověď NE nejde udělat modifikovaný TS, který bude vedle počítat čas a když překročí limit tak dá odpověď že NE? Nepamatujete si to někdo? To počítání nejde implementovat v polynomiálním čase? Nebo kde je problém?

Tohle je podle me zcestna uvaha. Problem bude imho v tom, ze polynomialni algoritmus porad nema zadny presne dany limit, ktery bys mohl detekovat - cili zrejme dalsi [rypnuti]krasna ukazka informaticky-teoretickeho zaveru s obrovskym teoretickym dopadem a nulovou praktickou vyuzitelnosti [/rypnuti]

[Mirek Prýmek]

Od zacatku si rikam, ze by cert mohl by v tomhle:

Cili ziskam pocet bucketu optimalniho reseni.

Pocet bucketu jeste neni konkretni reseni, ze jo. Ale neumim si predstavit algoritmus, kterej by umel spocitat pocet bucketu a zaroven ne rozmisteni predmetu - jak by to delal?

Proste je to nejaky zamotany, asi to necham konovi

[Cyr]

Problém je v tom, že to, že problém je v NP znamená, že umíme v polynomiálním čase říci, zda ANO. Nikoli zda NE. Takže prozkoumání těch záporných odpovědí může trvat libovolně dlouho a tedy Tvůj stroj nebude polynomiální.

Myslel jsem, ze "v polynomialnim case overit" znamena, ze mi das vstupni data a odpoved - tzn. "set A se vejde do bucketu B" nebo "set A se do bucketu B NEvejde" - a umim v polynomialnim case overit, ze to je pravda. Pokud budu mit ten druhy pripad ("nevejde"), tak musim umet polynomialne rychle zjistit, ze optimalni reseni MUSI pouzivat vic bucketu. Tim, ze to zopakuju n-krat (-> polynomialni rozsireni) tak zjistim, kolik nejmin bucketu potrebuju. Cili ziskam pocet bucketu optimalniho reseni.

Ale učil jsem se to před pěknou dobou a tak si to také nepamatuju přesně

Ja taky, navic jsem k tomu pristupoval se silnou pasivni resistenci a navic jsem momentalne nachcipanej, takze mi to mozna nemysli - proto jsem se ptal, jestli tady neni nekdo, kdo mi by mi to mohl vysvetlit nejak polopaticky (veci z teoreticke informatiky vetsinou jdou vysvetlit uplne jednoduse, pokud jim clovek dostatecne rozumi).

- proč vlastně pro tu odpověď NE nejde udělat modifikovaný TS, který bude vedle počítat čas a když překročí limit tak dá odpověď že NE? Nepamatujete si to někdo? To počítání nejde implementovat v polynomiálním čase? Nebo kde je problém?

Tohle je podle me zcestna uvaha. Problem bude imho v tom, ze polynomialni algoritmus porad nema zadny presne dany limit, ktery bys mohl detekovat - cili zrejme dalsi [rypnuti]krasna ukazka informaticky-teoretickeho zaveru s obrovskym teoretickym dopadem a nulovou praktickou vyuzitelnosti [/rypnuti]

Ad 1) Odpovědí na problém z otázky ale není "set A se vejde do bucketu B", odpovědí je "pro set A je nejmenší počet bucketů B". Jakkoliv implementujete algoritmus - vždy musí odpovídat na "pro set A je nejmenší počet bucketů B" a nic jiného. Pro ověření správnosti odpovědi "pro set A je nejmenší počet bucketů B" nemůžete použít algoritmus ve třídě složitosti P. To je celý problém a důvod, proč to je NP-hard a ne NP.
Ad 2) Přijde mi, že to co píšu v 1) píšu pořád dokola a že to neni žádná velká věda. Je to prostě o definici tříd složitosti a algoritmů na nedeterministickém Turingově stroji a o tom, jak probíhá jeho výpočet. Ale veskrze je to přesně, jak píšete v [rejpnuti] - je to jen teoretické cvičení bez kterého se řešení daného praktického problému vklidu obejde

[Trident]

Zdravim mistni matematiky.

Mam hromadu virtualnich serveru, kazdy jinak velky, o velikostech X₁, X₂, X₃, X₄... az X_n a datova uloziste, vsechna stejne velka, o velikosti Y. Chci virtualni stroje poskladat vedle sebe tak, aby idealne vyplnily vsechna uloziste (zbylo co nejmin volneho mista na kazdem ulozisti) a pritom zbylo co nejvic volneho mista na konci, idealne aby se mi nejake uloziste uplne uvolnilo.

Seradim X podle velikosti. Vezmu nejvetsi X, zkusim k nemu pricist druhe nejvetsi X a zkusim se vejit do Y. Kdyz se mi tam druhe nevejde, zkusim treti nejvetsi X, ctvrte nejvetsi X a tak postupne pricitam mensi a mensi az k nejmensimu a porad zkousim, jestli se jeste vejdu do Y. Pak vezmu zbyla X a zkusim to znova od nejvetsiho k nejmensimu a postupne tak vyplnit dalsi Y a tak dal, az mi dojdou X.

Metoda jednoducha, ale idealni? Ja jsem nematematik. Potrebuju za pochodu prekopat rozlozeni diskovych poli a premyslim, jak to k sobe kratkodobe nahnacat, aby se mohlo ve zbyvajici casti pracovat. Pak dal uz budu s obsahem poli hrat hanojske veze.

Diky predem.

1. Vzal bych naky capacity planning soft - mozna jste koupili k poli a podival bych se co mi z toho vyleze. Tyhle akademicke debaty jsou dost o nicem kdyz prijde na okamzitou ekonomickou vyteznost.
2. Potrebujes tam nejaky redundanci zkrz pole? Napriklad nedelas si raid na poli ale primo z hosta a host si hrabe na jeden pool z pole A a na druhy pool z pole B a pomoci nejakeho mechanismu md/lvm/cojavim si dela sam mirror?
3. Zvazil jsi zestackovani/konsolidaci poli v jedne lokalite dohromady? Dost by ti to ulehcilo praci. Mohl bys mit pooly rozpulene a daly by se treba predelat zaziva - nevim jaky mate srot.  Nejsi jediny kdo neco takoveho potreboval.
4. Nechapu proc firma pronajme dalsi pixlu na premigrovani misto toho aby platila lidi za vymysleni presunuti xn do yn a nekolikanasobnemu ohrozeni produkce. To je mozny jen v cechach nechat technika sroubovat srouby kladivem...

[Mirek Prýmek]

Ad 1) Odpovědí na problém z otázky ale není "set A se vejde do bucketu B", odpovědí je "pro set A je nejmenší počet bucketů B".

Pořád si asi nerozumíme. Bavíme se o DVOU problémech - "decision varianta" (odověď ANO-NE) a "zjištění optima" (odpověď: dej a,b,c do X a d,e do Y). První problém by teda snad měl být NP-complete a druhý těžší než NP-complete.

To, na co teď reaguješ, byla otázka na to, jaktože postup pro *verifikaci* u prvního (který musí existovat, protože je NP-complete) nemůžu použít pro řešení druhého.