Hogyan működik a bin packing algoritmus?
Szinte ugyanazzal a problémával foglalkozom, mint ez a StackOverFlow-s komment: [link]
Viszont nem teljesen értem a hozzászólást és ebben szeretnék segítséget kérni.
Ha jól értem a következő az algoritmus:
1. Téglalapok rendezése csökkenő sorrendbe.
2. Legelső téglalap elhelyezése a területen (ha ráfér).
3. Következő téglalapot a "legjobb" fentmaradó helyre tenni forgatás nélkül. Ha több lehetőség is van, akkor oda, ahol a legkevesebb hely marad addig, amíg meg nem telik a terület, vagy fel nem használtuk az összes téglalapot.
4. Ha nincs még tele a téglalap, akkor a fel nem használt téglalapokat ugyanabban a sorrendben tegyük fel, de próbáljuk meg forgatni.
Az első két pontot értem.
3. Miért pont arra a helyre kell tenni, ahol a legkisebb hely marad?
4. Mi alapján forgatom? El kellene kezdeni próbálni az összes lehetőséget addig, amíg nem sikerül, vagy meg nem próbáltam az összeset? Vagy honnan tudom, hogy melyiket kell forgatni?
Értem, hogy az algoritmus nem tökéletes, de hogyan kellene kiegészíteni? Valaki dolgozott már hasonló projekten?
válasza: válasza:3. A forgatás nélkül kitételt nem egészen értem, de persze adódhat olyan eset, amikor nem lehet forgatni az objektumokat (pl. konténeres szállítás).
Azért kell oda tenni, ahol a legkisebb hely marad, mert ha a cél mondjuk nyersanyag darabolás, akkor úgy a jó ha minél nagyobb egybefüggő esedék marad.
válasza:Most nézem, hát ott a kérdésedre a megoldás a linkeden.
A magyarázó ábra.
Szépen mutatja, hogy az első esetben a lepakolás után fennmarad az 5 egység méretű "snitt" (kék szinű), de emellett van két esedéked (fehérrel jelezve), amelyek együttes területe az 5 egységet meghaladja.
A második lerakás is hasonlóan rossz eredményt ad és csak a harmadik a megoldás, amit mutat az is, hogy az esedék már mindössze egyetlen egység. Ami korábban lemaradt, kimaradt (kék), az is felfért a táblára.
Nagyon köszönöm!
Ha jól értem a fehér/üres/esedék területeket összeadom és azt próbálom forgatni, ami a legnagyobb a maradékok (amik nem férnének már el benne) közül?
válasza:A fehéret nem tudod forgatni, mert az a teljes tábla még kilátszó, nem fedett része. A szineseket viszont tudod forgatni. Esetenként kell is. Az első lerakásnál a kék maradt ki, a másodiknál a zöld. De a fennmaradó fehér rész nagysága mutatja, hogy ráfért volna ez is, az is a táblára, a többi mellé.
Első lépésként a tábla teljes méretét kell kiszámolni
Másodikként a táblán elhelyezendő négyzetekét összesen.
Utóbbi természetesen kisebb kell legyen a tábla méreténél, mert csak ekkor fél fel a táblára az összes négyzet.
Algoritmus meg több féle van.
Veheted a négyzetek oldalát* (csökkenő sorrendben), vagy veheted a tábla szélességét is alapnak.
De heurisztikusan (próbálkozással) is megoldható a feladat (jó közelítéssel a leglassabban).
* A legnagyobbakból annyit adsz össze -egymás mellé- amennyit a tábla hosszúsága megenged.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!