Algoritmus nejlepšího zaplnění disků – .NET – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu
Reklama
Reklama

Algoritmus nejlepšího zaplnění disků – .NET – Fórum – Programujte.comAlgoritmus nejlepšího zaplnění disků – .NET – Fórum – Programujte.com

 

Hledá se programátor! Plat 1 800 € + bonusy (firma Boxmol.com)
Tx
~ Anonymní uživatel
11 příspěvků
13. 6. 2013   #1
-
0
-

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.

Nahlásit jako SPAM
IP: 178.72.192.–
Reklama
Reklama
Tx
~ Anonymní uživatel
11 příspěvků
13. 6. 2013   #2
-
0
-

Ještě doplním. Soubory i disky jsou různých velikostí.

Nahlásit jako SPAM
IP: 178.72.192.–
nosko
~ Anonymní uživatel
136 příspěvků
13. 6. 2013   #3
-
0
-
Nahlásit jako SPAM
IP: 193.87.78.–
Tx
~ Anonymní uživatel
11 příspěvků
13. 6. 2013   #4
-
0
-

Děkuji, ale o tomto algoritmu vím a nelze ho příliš použít, ani pro inspiraci. Hlavní problém je v tom, že batoh je pouze jeden.

Nahlásit jako SPAM
IP: 178.72.192.–
m4r100
Návštěvník
13. 6. 2013   #5
-
0
-

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

Nahlásit jako SPAM
IP: 78.102.208.–
Tx
~ Anonymní uživatel
11 příspěvků
13. 6. 2013   #6
-
0
-

#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í.

Nahlásit jako SPAM
IP: 178.72.192.–
m4r100
Návštěvník
13. 6. 2013   #7
-
0
-


#6 Tx
Pokud ty soubory prichazeji ve streamu, jaky je problem vzdycky ten prichozi soubor hodit na ten nejmene vytizeny disk? Nebude to uplne idealne rozdelene, ale zase tam nemusi byt zadne vypocty navic.

Nahlásit jako SPAM
IP: 78.102.208.–
Temp
~ Anonymní uživatel
8 příspěvků
13. 6. 2013   #8
-
0
-

#7 m4r10
Bohužel problém nelze obejít tímto způsobem.

Nahlásit jako SPAM
IP: 89.31.10.–
Tx
~ Anonymní uživatel
11 příspěvků
17. 6. 2013   #9
-
0
-

Předpokládal jsem, že jde o nějaký obecně používaný optimalizační algoritmus. Nějaké nasměrování tedy nemáte?

Nahlásit jako SPAM
IP: 89.31.10.–
Tx
~ Anonymní uživatel
11 příspěvků
17. 6. 2013   #10
-
0
-

Zdá se, že jde o "Problém dvou loupežníků". :-)

Nahlásit jako SPAM
IP: 89.31.10.–
RomanZ
~ Anonymní uživatel
244 příspěvků
17. 6. 2013   #11
-
0
-

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.

Nahlásit jako SPAM
IP: 90.176.60.–
RomanZ
~ Anonymní uživatel
244 příspěvků
17. 6. 2013   #12
-
0
-

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?

Nahlásit jako SPAM
IP: 90.176.60.–
Tx
~ Anonymní uživatel
11 příspěvků
17. 6. 2013   #13
-
0
-

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).

Nahlásit jako SPAM
IP: 89.31.10.–
RomanZ
~ Anonymní uživatel
244 příspěvků
17. 6. 2013   #14
-
0
-

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.

Nahlásit jako SPAM
IP: 90.176.60.–
Tx
~ Anonymní uživatel
11 příspěvků
17. 6. 2013   #15
-
0
-

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.

Nahlásit jako SPAM
IP: 89.31.10.–
Tx
~ Anonymní uživatel
11 příspěvků
17. 6. 2013   #16
-
0
-

Toto byl příklad z praxe. Jak je vidět, délky ústřižků mohou být delší, než součet kabelů na cívkách.

Nahlásit jako SPAM
IP: 89.31.10.–
JardaJirava0
Stálý člen
18. 6. 2013   #17
-
0
-

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,

Nahlásit jako SPAM
IP: 77.78.85.–
MCAD, MCPD
http://jirava.net/blog
http://xaml.cz - Magazín moderních technologií založených na XAML
Tx
~ Anonymní uživatel
11 příspěvků
18. 6. 2013   #18
-
0
-

Hledat jsem zkoušel, ale odkaz by taky nebyl k zahození. :-)

Nahlásit jako SPAM
IP: 89.31.10.–
peter
~ Anonymní uživatel
2547 příspěvků
18. 6. 2013   #19
-
0
-

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

Nahlásit jako SPAM
IP: 193.84.207.–
Tx
~ Anonymní uživatel
11 příspěvků
18. 6. 2013   #20
-
0
-

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.

Nahlásit jako SPAM
IP: 89.31.10.–
Grungy0
Super člen
18. 6. 2013   #21
-
0
-

#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.

Nahlásit jako SPAM
IP: 37.61.165.–
Prvý náznak hlúposti, je pocit geniality.
peter
~ Anonymní uživatel
2547 příspěvků
21. 6. 2013   #22
-
0
-
Nahlásit jako SPAM
IP: 193.84.207.–
peter
~ Anonymní uživatel
2547 příspěvků
Nahlásit jako SPAM
IP: 193.84.207.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 52 hostů

Podobná vlákna

Formatovanie disku — založil lolik

Sprava disku — založil hrach

Rozdelenie disku — založil Santas

OS na přenosném disku — založil yaqwsx

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032016 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý