TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Hledám algoritmus (který už pravděpodobně existuje) pro následující problém.
Mám 2 až x disků, na které potřebuji umístit 2 až x souborů. A to tak, aby disky byly co nejlépe využity a zbytek co nejmenší. Soubory nelze dělit.
Poradíte mi, jaký algoritmus použít?
Díky.
Mozno by som sa odrazil od tohoto.
Zkuste si vymyslet svuj, myslim, ze pri necem takovem to nebude velky problem. Treba co mne ted na pockani napada, tak:
Soubory bych seradil podle velikosti od nejvetsiho a potom postupne hazel na disky. Vzdycky na ten, ktery ma nejvetsi volny prostor (nejmin zabraneho mista). Priklad:
Disky: A,B,C
Soubory: [100,40,20,10,10,10,8,6,4,2,2,2, 1]
A: 100
B: 40 8 6 2 1
C: 20 10 10 10 4 2 2
A: 100 B: 57 C: 58
#5 m4r10
Vymyslel a naprogramoval jsem svůj algoritmus. Byl funkční, zdálo se, že potřebuje jen trochu doladit. S každým vyřešeným problémem se ale objevil další a nakonec program narostl do takových rozměrů, že výpočet byl nepoužitelně dlouhý (minuty až desítky minut). Proto hledám lepší řešení.
Když jsem před lety zálohoval na cédéčka, potřeboval jsem vymyslet podobný postup - prostě mi bylo jedno, jaký soubor bude na kterém CD, šlo jen o to co nejlépe využít jejich kapacitu. Nakonec jsem ale skončil u jednoduchého postupu, velmi podobného tomu, jaký popsal m4r10. Seřadil jsem soubory podle velikosti. Zjistil jsem volné místo na médiu, dal na něj největší soubor, jaký se do toho místa vešel a tento postup jsem opakoval tak dlouho, dokud na disku bylo místo, do kterého se ještě něco vešlo. Když ne, vypálil jsem cédéčko a začal jsem znovu s dalším čistým médiem. Není to sice úplně to úplně nejhospodárnější řešení, ale dává dostatečně dobré výsledky. Je to rychlé na vyhodnocení, takže se to dá dělat i ručně bez složitých výpočtů - implementace automatem by tedy měla být snadná. Také je důležité, že bylo v jednotce vždy jen jedno médium, se kterým se pracovalo, zatímco postup m4r10 předpokládá, že jsou k počítači připojeny všechny disky současně. V tom mém postupu ale hodně záleží na tom, jakou skladbu mají soubory - jestli je mezi nimi dost velkých i malých. Pokud je malých souborů málo, tak se to zbývající volné místo využívá špatně a chtělo by to vymyslet rafinovanější postup. V případě potřeby lze velké soubory rozdělit na menší (myslím že ZIP nebo RAR umí soubor dělit na části) a tím by se dal jeden soubor rozprášit na víc disků - místo by se sice využilo, ale nechtěl bych pak zažít ten opruz, až bych to potřeboval načíst.
Ještě na to koukám a uvědomil jsem si, že to zadání si lze vykládat několika způsoby. Mám daný (známý) počet disků (znám jejich velikost) a přicházejí mi soubory (dopředu nevím jaké). Nebo mám soubory (znám je všechny i s jejich velikostí od začátku) a potřebuji je našťouchat na nějaké disky (nevím kolik disků budu potřebovat, ale chci jich spotřebovat co nejméně). A nebo je to nějaká kombinace obojího?
Ve skutečnosti nejde o disky, ty jsem použil jen proto, že jsem předpokládal, že právě s nimi už někdo tento problém řešil. Místo zjednodušení se ale zadání zkomplikovalo. :-)
Jde o stříhání kabelů, které jsou navinuty na kabelových cívkách.
Firma potřebuje nastříhat 2-300 kabelů různých délek. Délky si firma sečte a přesně takovou délku objedná v kabelárně.
Kabelárna dodá kabely o celkové délce, ale navinuté na několika cívkách, které nemusí mít stejný návin. Cívek může být až 30.
Teď už zná firma nejen délky kabelů, které bude stříhat, ale i počet cívek a návin na nich.
S těmito informacemi se pustí do stříhání kabelů z jednotlivých cívek.
Je jasné, že vzniknou zbytky. Ty jsou ale dosti drahé, proto se snažím aby byly co nejmenší.
Když kabel pochybí, sáhne se do zbytků, nebo objedná další cívka (to už ale neřeším).
Tak to asi nakonec skončí nějakým algoritmem, který dává přibližné (ne nejlepší) řešení. Aby se dosáhlo dokonalého využití materiálu, muselo by se asi porovnávat hrubou silou všechny možnosti a to je neúnosné. Sám bych použil modifikaci toho postupu, co jsem popisoval výše, takto: seřadil bych požadavky na kabely od nejdelšího k nejkratšímu. Seřadil bych cívky od nejmenší k největší. Vzal bych požadavek na nejdelší kabel a našel nejkratší cívku, ze které lze požadovaný kus ufiknout. Pak bych znovu setřídil cívky podle velikosti a postup opakoval. Určitě to není nejlepší řešení, ale pokud vím, funguje to takto v praxi třeba na stavbách nebo v prodejnách, kde kabely prodávají koncovým zákazníkům na míru. Pokud bys našel nějaký promakanější algoritmus, bylo by dobré ho porovnat s tímto postupem, aby nikdy nevracel horší výsledek.
Vy#14 RomanZ
Vyzkoušel jsem přibližně tvůj postup. Vezmu nejmenší cívku a nejdelší kabel, který se na ni vejde. Potom druhý nejdelší ..
A potom totéž s vetší cívkou.
Kabely: 157;223;217;158;65;65;180;210;80;80
Cívky: 501;500;195;140
Výsledky:
Cívka 501: 210,80,158
Cívka 500: 217,223
Cívka 195: 180
Cívka 140: 80
Zbytek: 157,65,65
Pro první naplnění to stačí, teď bude asi třeba zaměnovat postupně obsah jednotlivých cívek se zbytky.
Ahoj,
mě to přijde, jako klasická úloha lineárního programování (optimalizace). Těch algoritmů, jak takovou úlohu řešit je několik, tak zkus pohledat.
Pěkný den,
a) Pokud ti prichazeji nove a nove soubory, neznas jejich delku, tak to lze rozhazovat jen podle velikosti volneho mista na disku
b) Pokud velikosti znas, pak mi to prijde jako ukol trasy pro obchodniho cestujiciho, projit vsechny moznosti.Prvne bych to ale seradil od nejvetsiho po nejmensi. A stejne to bude treba prizpusobit situaci. Pochybuji, ze by strihac chtel strihat 5, 4, 3, 3, 3, 2, 2, 1 ,ze raci to nastriha 10x 3 metry, treba
Pro konkrétní zakázku je potřeba nastíhat konkrétní délky kabelů, jak jsem popsal výše. Takže nepřicházejí žádné nové kabely a zjednodušení 10x3 metrů také není možné. Stříhají se přesné délky, tedy například 50, 40, 30, 30, 30, 20, 20, 10.
#17 JardaJirava
Áno máte pravdu ide o úlohu lineárneho programovania, problémom v tomto prípade bude asi celočíselnosť dĺžiek káblov, preto bude treba použiť asi metódu vetiev a hraníc, ktorá ale nemusí dať rozumný výsledok v požadovanom čase. Možno by bolo lepšie použiť nejakú heuristiku v podobe genetického algoritmu, alebo niečo na ten spôsob.
http://mj.ucw.cz/vyuka/ga/ - jakasi scripta o algoritmech. Na mne je to moc matematicky pojate :)
Zjistit počet nových příspěvků
Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku
© 2003–2024 Programujte.com
Nahlásit jako SPAM
IP: 178.72.192.–
Návštěvník
Stálý člen
Super člen