Fórum Root.cz
Hlavní témata => Server => Téma založeno: Karel.hu 11. 12. 2014, 21:24:29
-
Zdravim mistni matematiky.
Mam hromadu virtualnich serveru, kazdy jinak velky, o velikostech X1, X2, X3, X4... az Xn 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.
-
https://en.wikipedia.org/wiki/Knapsack_problem
-
Snad ne sám Mr.Uloz to? :o
Pokud ano, tak tohle by zajímalo asi 100+1 člověda!
-
Lol, jako že uloz.to jede na virtuálech? :D
Sry ale sedí tam pár kluků a kdyby si chodili pro rady na root, těžko by pořád vydělávali a dostali se tak daleko. ;)
-
https://en.wikipedia.org/wiki/Knapsack_problem
Klasickej baťoh to není. Pokud by postupoval postupně po jednotlivých batozích, tak imho nutně nedostane optimální řešení.
Pro OP: ne že bych chtěl snižovat snahu o optimalizaci, ale pokud těch virtuálů nemáš milion a nepočítáš rekonfiguraci každých sto milisekund, tak si úplně v klidu vystačíš s bruteforce řešením - prostě si z těch virtuálů udělej všechny permutace a v tomhle pořadí je (virtuálně) naláduj do úložišť uspořádaných v jakémkoli neměnném pořadí - pokud se už virtuál do úložiště nevejde, dáš ho už do následujícího. K mírné optimalizaci pak můžeš použít nějaký stupidní prořezávání - např. pokud přetečeš do baťohu s číslem větším než na kolik batohů už jsi našel řešení, nepokračuješ. Tímhle způsobem musíš být schopnej to spočítat pro tisíce strojů během zlomku sekundy.
Vzhledem k tomu, že ten problém je (odhaduju) určitě NP-úplný, bude rozdíl mezi tímhle stupidním řešením a optimálním algoritmem prakticky stejně zanedbatelný, takže bych si s tím vůbec hlavu nelámal ;)
-
Tímhle způsobem musíš být schopnej to spočítat pro tisíce strojů během zlomku sekundy.
Pardon, tisíce určitě ne, faktoriál je svině ;) ale pro nějaké rozumné množství určitě.
-
Prymek: nevim nevim - faktorial roste o dost rychleji nez exponencialni funkce
zajimavy by mohlo byt vyzkouset nejaky evolucni algoritmus.
-
Prymek: nevim nevim - faktorial roste o dost rychleji nez exponencialni funkce
Jasně. Ale rozhodující je, jakou část prostoru vážně projdeš a jaká se odřízne. Pokud budeš permutace generovat postupně, budeš tímpádem procházet strom a můžeš jedním krokem odříznout obrouvskou část prostoru.
Taky si můžeš pomoct nějakou další stupidní heuristikou - jako např. že si předem spočítáš, pod jaký číslo se zaručeně nedostaneš a jakmile najdeš řešení jenom o x horší, skončíš, protože takhle ti to prostě stačí. "Inženýrských" možností je spousta ;)
zajimavy by mohlo byt vyzkouset nejaky evolucni algoritmus.
Buď, anebo simulované žíhání. Tyhle metody se AFAIK na tyhle typy problémů používají.
-
Ale rozhodující je, jakou část prostoru vážně projdeš a jaká se odřízne.
...a samozřejmě hlavně jde o to, o jakých číslech se bavíme. Jestli je těch virtuálů deset, tak není co řešit že jo :)
-
Prakticky to bude vyreseno, jak jsem psal na zacatku - asi stupidni, ale rychle a snadne reseni. Jde jen o uklid pred rekonfiguraci pole a jedna se o pouhych 105 stroju. Jen me zajimalo (ciste teoreticky), jak se podobna uloha resi "spravne", protoze, jak rikam, nejsem matematik.
V kazdem pripade diky.
-
Jedna se o tzv. Bin-packing problem (viz wiki).
Jedine mne zname algoritmy pro exaktni optimalni reseni jsou:
- MTP (napr. strana 237/17/ zde http://www.or.deis.unibo.it/kp/Chapter8.pdf)
- Exhaustive search (brute force) - pro pocet VM < 1000 je to asi to nejrychlejsi, co muzes udelat - zkusit si vsechny kombinace. Sice to nejakou dobu pobezi, ale neni to tak hrozne.
Randolf
-
https://en.wikipedia.org/wiki/Knapsack_problem
Klasickej baťoh to není. Pokud by postupoval postupně po jednotlivých batozích, tak imho nutně nedostane optimální řešení.
Pro OP: ne že bych chtěl snižovat snahu o optimalizaci, ale pokud těch virtuálů nemáš milion a nepočítáš rekonfiguraci každých sto milisekund, tak si úplně v klidu vystačíš s bruteforce řešením - prostě si z těch virtuálů udělej všechny permutace a v tomhle pořadí je (virtuálně) naláduj do úložišť uspořádaných v jakémkoli neměnném pořadí - pokud se už virtuál do úložiště nevejde, dáš ho už do následujícího. K mírné optimalizaci pak můžeš použít nějaký stupidní prořezávání - např. pokud přetečeš do baťohu s číslem větším než na kolik batohů už jsi našel řešení, nepokračuješ. Tímhle způsobem musíš být schopnej to spočítat pro tisíce strojů během zlomku sekundy.
Vzhledem k tomu, že ten problém je (odhaduju) určitě NP-úplný, bude rozdíl mezi tímhle stupidním řešením a optimálním algoritmem prakticky stejně zanedbatelný, takže bych si s tím vůbec hlavu nelámal ;)
+1
-
ano bin packing problem:
http://en.wikipedia.org/wiki/Bin_packing_problem
pozry do software nieco najdes.
-
zajimavy by mohlo byt vyzkouset nejaky evolucni algoritmus.
Buď, anebo simulované žíhání. Tyhle metody se AFAIK na tyhle typy problémů používají.
Ani jedno bych nedoporucil.
- Pobezi to v tomto pripade zbytecne dlouho (velky overhead navstivenim mnohokrat stejneho reseni
- Nezarucena optimalita reseni... a pokud to optimalni byt nemusi, pak opravdu bude fungovat ten jednoduchy algoritmus ktery autor naznacil v prvnim prispevku
- Dost pracne na implementaci
- V pripade simulovaneho zihani to nejspis skonverguje do nejakeho lokalne optimalniho reseni, ktere ale bude daleko od globalniho optima (ale to je jen intuitivni hodnoceni, mozna by to slo nejak vyresit)
-
Ani jedno bych nedoporucil.
- Pobezi to v tomto pripade zbytecne dlouho (velky overhead navstivenim mnohokrat stejneho reseni
- Nezarucena optimalita reseni... a pokud to optimalni byt nemusi, pak opravdu bude fungovat ten jednoduchy algoritmus ktery autor naznacil v prvnim prispevku
- Dost pracne na implementaci
Myslel jsem to jako metodu druhe volby - pokud by tech virtualu bylo tolik, ze brute-force by byl neumerne narocny a timpadem by se clovek smiril se suboptimalnim resenim...
Ten Karlem zmineny postup by myslim pro nektera data mohl davat docela slabe vysledky. Mozna by bylo lepsi udelat neco na tenhle zpusob: 1) odhadnu, kolik budu zhruba potrebovat bucketu 2) virtualy seradim podle velikosti 3) postupne davam jednotlive virtualy do bucketu *poporade* - nejvetsi do prvniho, druhy nejvetsi do druheho atd. 3) jestli se mi takhle nepodari virtualy rozprostrit, zvysim pocet bucketu o jeden a jedu cely znovu
Tohle by myslim mohlo davat docela dobre vysledky zvlast pokud jsou buckety stejne velke.
- V pripade simulovaneho zihani to nejspis skonverguje do nejakeho lokalne optimalniho reseni, ktere ale bude daleko od globalniho optima (ale to je jen intuitivni hodnoceni, mozna by to slo nejak vyresit)
AFAIK se tam da pridat nahoda, ktera resenim obcas "zatrese" - stejne jako u GA.
-
Problém je zcela jistě NP-úplný, takže to nelze řešit přesně.
Doporučoval bych problém rozdělit na X problémů baťohů, s postupnou aplikaci dynamického programování na jednotlivé "batohy" s tím, že bych z batohu už "nevytahoval předměty", jejichž velikost je x*větší než velikost volného místa (čímž se vyloučí některá optimální řešení, ale velmi zkrátí doba výpočtu).
-
Jasně. Ale rozhodující je, jakou část prostoru vážně projdeš a jaká se odřízne. Pokud budeš permutace generovat postupně, budeš tímpádem procházet strom a můžeš jedním krokem odříznout obrouvskou část prostoru.
Tak pokud hledáte optimum, tak neuříznete skoro nic. Že se nějaká permutace zdá býti dobrá na začátku, ještě neznamená, že bude dobrá na konci. Tenhle problém jsme měli v semestrálce na VŠ a byly tam speciálně připravené desítky zadání, na kterých se pak ukazovaly takovéhle chyby. Nevím, zda to dám z hlavy správně, ale zkusím:
X1 = 40
X2 = 40
X3 = 20
X4 = 75
X5 = 55
X6 = 55
Velikost úložiště je 100.
Na začátku stromu dám U1 = X1 + X2 + X3, plně využité. Pokud zbytek stromu uříznu, tak skončím s tím, že X4, X5 i X6 budou mít úložiště vlastní. Celkem 4 úložiště. Přitom stačí 3 (X1 + X5, X2 + X6, X3 + X4), z nichž ale ani jedno nebude plné. Fakt, že se mi ten první "baťoh" podaří krásně na 100% vyplnit, ještě nic neznamená, řezat nesmím. A teď opačné cvičení - na všech permutacích zjistit prostor. Zjistíte, že jich polovina bude 4 a méně. Pokud tedy jako první netrefíte právě to optimální, tak oříznete jen necelou polovinu listů.
Nenechte se zmást hledáním do hloubky, to sice obecně řeže, ale vy se v něm budete pohybovat hodně hluboko a řezat jen zbytky. A pak dospějete ke zjištění, že díky algoritmu to není O(2^n), ale "jen" O(2^(n/2)) = O(2^n)
-
Naivní algoritmus dle selského rozumu, zato snadno implementovatelný:
- Seřadit VM podle velikosti sestupně, tedy od největšího k nejmenšímu. Projít všechny VM v pořadí od největšího po nejmenší a pro každé VM udělat následující:
- Projít všechny již založené hosty v pořadí od 1 do N a pokusit se umístit VM do prvního kde to lze.
- Pokud nelze umístit, založit nový host N + 1 a umístit VM do něj.
-
Problém není NP-úplný, ani není ve třídě NP - je složitější.
Pokud by byl ve třídě NP, pak existuje polynomiální algoritmus, který ověří správnost řešení.
-
Problém není NP-úplný, ani není ve třídě NP - je složitější.
Pokud by byl ve třídě NP, pak existuje polynomiální algoritmus, který ověří správnost řešení.
A jak víte že neexisuje polynomiální algoritmus který ověří správnost řešení?
-
Že se nějaká permutace zdá býti dobrá na začátku, ještě neznamená, že bude dobrá na konci.
Rezani se ale pouziva k tomu, aby se neprohledavala *spatna* reseni, o dobrych to nic nerika. Ja jsem rikal rezat vetve, ktere zarucene *nemuzou* vest k *lepsimu* reseni, nez jake uz mam. Napr. pokud uz jsem nasel reseni s peti buckety a soucasne prochazena vetev jich uz ted potrebuje pet a jeste jsem neumistil vsechno, tak dal proste pokracovat nemusim, protoze vsechna reseni v danem podstromu uz budou zarucene HORSI nez to uz nalezene. Takze zadne dalsi permutace v danem podstromu uz proste neprochazim.
Nakolik je prorezavani efektivni je dany typem tech dat - pro kazdy set bude jinak uspesne.
-
A jak víte že neexisuje polynomiální algoritmus který ověří správnost řešení?
Ja nevim, skoly nemam, ale overit, ze v kazdem bucketu je soucet velikosti mensi nez velikost bucketu a ze v bucketech jsou fakt vsechny prvky, ktere jsem na zacatku mel, mi neprijde jako polynomialne neresitelny ;)
-
Klasickej baťoh to není. Pokud by postupoval postupně po jednotlivých batozích, tak imho nutně nedostane optimální řešení.
Vzhledem k tomu, že ten problém je (odhaduju) určitě NP-úplný, bude rozdíl mezi tímhle stupidním řešením a optimálním algoritmem prakticky stejně zanedbatelný, takže bych si s tím vůbec hlavu nelámal ;)
Dělali jsme to tím dynamickým programováním podobně jak je to na Wikipedii, ale formální důkaz se mi vymýšlet nechce.
Je NP-úplný, ale jak si taky můžeš na Wikipedii přečíst, existuje algoritmus polynomiální v GCD(velikosti virtuálů). Takže pokud toho máš třeba 20 TB a budeš to počítat v GB, máš polynom a vstup velký 20000.
-
Je NP-úplný
Tak ne, no :)
-
A jak víte že neexisuje polynomiální algoritmus který ověří správnost řešení?
Ja nevim, skoly nemam, ale overit, ze v kazdem bucketu je soucet velikosti mensi nez velikost bucketu a ze v bucketech jsou fakt vsechny prvky, ktere jsem na zacatku mel, mi neprijde jako polynomialne neresitelny ;)
Tím ověřujete jinou úlohu.
-
A jak víte že neexisuje polynomiální algoritmus který ověří správnost řešení?
Ja nevim, skoly nemam, ale overit, ze v kazdem bucketu je soucet velikosti mensi nez velikost bucketu a ze v bucketech jsou fakt vsechny prvky, ktere jsem na zacatku mel, mi neprijde jako polynomialne neresitelny ;)
Nedovoluji si soudit zda by se to zlepšilo tím kdybyste měl školy, ale pro jistotu si zopakujme zadání:
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.
To je přeci něco úplně jiného než o čem píšete!
-
!!! HINT HINT HINT !!!
podivejte se do kalendare. zacala lovecka sezona. tak ne ze sem nekdo pastne reseni.
-
To je přeci něco úplně jiného než o čem píšete!
Nevim, asi je nejaka pozdni hodina a neco mi nedochazi, ale je pak teda tohle spatne?
http://www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/bin_packing.pdf - "The Bin Packing problem is NP-complete."
A tohle?
https://people.cs.umass.edu/~barring/cs311/disc/11.html - ukol 1)
Nebo se tady bavime o nejakem jinem problemu, ktery na ty popsane neni redukovatelny?
-
Ad zdroje:
Zdroj 1: http://www2.informatik.hu-berlin.de/alcox/lehre/lvws1011/coalg/bin_packing.pdf
Theorem dokazuje převod NP-úplné úlohy na bin packing problém. Tj. dokazuje, že minimalizační bin packing je alespoň NP, ale nedokazuje, že je není složitější.
Zdroj 2: https://people.cs.umass.edu/~barring/cs311/disc/11.html - ukol 1)
Opět - "decision version of BIN-PACKING is NP-complete", nám jde ale o minimalizační úlohu. Decision problém je "lze naskládat věci do maximálně N binů?" Zde se polynomiální ověření přímo nabízí. Stačí spočítat počet košů.
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
-
To je přeci něco úplně jiného než o čem píšete!
Nevim, asi je nejaka pozdni hodina a neco mi nedochazi, ale je pak teda tohle spatne?
Odkazované dokumenty řeší jiný problém. Tam stačí splnit toto:
Chci virtualni stroje poskladat vedle sebe tak, aby idealne vyplnily vsechna uloziste
ale už vůbec neřeší druhou část zadání:
a pritom zbylo co nejvic volneho mista na konci
-
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.
-
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? :-))
-
jj, cyr,logik,
kdo neskladal eternity, nevi, co je vyzva ;)
-
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.
-
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
-
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í).
-
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 :)
-
rozdil je v tom "optimalni". porad nic ?
-
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.
-
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?
-
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]
-
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 ;)
-
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 :)
-
Zdravim mistni matematiky.
Mam hromadu virtualnich serveru, kazdy jinak velky, o velikostech X1, X2, X3, X4... az Xn 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...
-
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.
-
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.
Myslim ze aby problem byl NP, tak overeni reseni musi byt P.
Dejme tomu ze mam funkci "f(O, B)", ktere predam objekty a batohy a ona me rekne jak je tam mam naskladat aby se tam vesly, nebo rekne ze se tam nevejdou. Kdyz rekne ze se tam vejdou, a da me nejaky reseni, tak overit ze se tam fakt vejdou je otazka jednoduchyho P algoritmu - proste je tam zkusim naskladat jak me rika a uvidim.
Kdyz ale budu mit druhou funkci "g(O)" ktera me rekne minimalni pocet batohu, tak overeni je slozitejsi. Napr bych mohl opakovane volat funkci f:
f(O, 1 batoh)
f(O, 2 batohy)
...
problem je ze funkce f neni P, takze overeni by nebylo P.
-
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.
Nie, to by nešlo. Ten optimalizačný algoritmus dostane predmety a ako výsledok vráti - tieto predmety viem umiestniť do 4 batohov, a to tak a tak. Váš polynomiálny verifikátor vie zistiť, či sa tie predmety naozaj dajú tak poukladať, ale už s ním neviete zistiť, či by sa tie predmety nejako nevošli aj do 3 batohov.
Tu je dôležité, že ten algoritmus vracia nie len počet, ale aj presné rozdelenie jednotlivých predmetov (predmet A ide do batohu č.3, atď) - ak by algoritmus vrátil len počet, polynomiálne to verifikovať neviete.
Ak by bol počet batohov súčasťou vstupu pre algoritmus ("umiestni tieto predmety do maximálne štyroch batohov"), tak to stále nejde - viete overiť pozitívne riešenie, nie však riešenie negatívne. Teda ak algoritmus povie "dá sa to takto", viete overiť, či je to pravda. Ale ak algoritmus vráti "nedá sa to", neviete polynomiálne overiť, či sa to naozaj nedá.
-
Muze puvodni tazatel nahodit vzorovy vstup? Tj konkretni X0-XN a Y. Mozna z duvodu budouci kompatibility spise X0..N + Y0..N
-
ak by algoritmus vrátil len počet, polynomiálne to verifikovať neviete.
No prave! Decision varianta mi rekne "ANO, do 5ti bucketu se to vejde" - jak muzu odpoved polynomialne overit, aniz bych to (nepolynomialne) vyresil?
-
No prave! Decision varianta mi rekne "ANO, do 5ti bucketu se to vejde" - jak muzu odpoved polynomialne overit, aniz bych to (nepolynomialne) vyresil?
Navic mi tam jeste neni jasna jedna vec, ale to je dany mou neznalosti:
Jestlize mi algoritmus A1 da odpoved, ktera "obsahuje vic informaci", tak je pro me snadnejsi odpoved overit. Zatimco kdyz mi algoritmus A2 da jenom odpoved ANO-NE, tak je to tezsi overit. A pritom podle toho, co tady bylo napsaný, by A2 měl mít *menší* složitost než A1.
Prostě já osobně jsem se do toho teda nějak zamotal a není mi to vůbec jasný.
-
Cyr:
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.
A to zas prrrr. :-) Součástí odpovědi je vždy "certifikát", proč tomu tak je a ověřuje se ten certifikát. Vždyť u decision problému by čistá odpověď ANO (kterou získáš "v čase NP") přeci také nelze ověřit "v čase P". To by to nebyl NP, ale P problém. To, co jde ověřit v čase P je certifikát (např. to jde definovat pomocí DTS s orákulem, kdy orákulum nejdřív "uhádne" certifikát a pak jej v P ověří). V případě decision problému je daným certifikátem rozložení do kyblíků.
A problém je v tom, že pro odpověď NE evidetně neexistuje stroj, který by to v čase NP spočítal, tedy není možno vytvořit "certifikát", který by šel v P čase ověřit. Tedy decision problém je v třídě NP, ale není v třídě co-NP. Proto také asi nefunguje Mirkův postup, kdy to ověřím pro 1 až k. Protože pro ty 1-(k-1) neexistují certifikáty ověřující NE u decision problému.
Mirek:
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]
A zas prrrr. :-) Pokud dokážu, že je ten program v NP, tak musím dokázat existenci polynomu, který zhora omezuje nejdelší možný běh pro odpověď ANO. Takže (pominu-li hustokrutý důkazy typu: "polynom existuje ale neznám ho" :-) který se v algoritmech skoro nevyskytují) znám horní hranici doby běhu. Takže to opravdu omezit můžu. Zpravidla je totiž ten algoritmus nějaké prohledávání stromu a ten certifikát je kterou cestou se mám dát v grafu. A hloubka grafu jde zpravidla odhadnout snadno.
Problém bude v tom, že to počítání nejde asi v polynomiálním čase udělat - jen nevím proč. Představuju si to tak, že každý druhý pole na pásce vyhradím na počítání počtu kroků. Čili každej originální krok se skládá z max 4*O(n) kroků (dojdu na konec počítadla, zapíšu další čárku, 2* kvůli zdvojeným polím, 2*cesta tam a zpět), čili zůstávám v polynomiální složitosti.
U výše uvedeného postupu nevidím, co je certifikátem toho řešení. Ale definice NP nevyžadují explicitně existenci certifikátu. Ta by měla jen vyplývat z toho řešení pomocí NTS v polynomiálním čase. Někde tam asi problém bude, ale kde?
-
Takže (pominu-li
To jsem měl namysli - že tenhle postup nemusí fungovat obecně, protože je myslitelná situace, kdy vím, že je něco polynom, ale nevím, jakého tvaru. Pokud konkrétní polynom znám, tak to jde, to je jasný.
-
Tak to jo :-)
Ale důkazy, že je něco polynomiální, se v podstatě vždy dělají konstrukcí algoritmu, takže polynom je znám.