Murdkotiprobleem: Ahne algoritm koos näitega
Mis on ahne strateegia?
Ahned algoritmid on nagu dünaamilised programmeerimisalgoritmid, mida sageli kasutatakse optimaalsete probleemide lahendamiseks (leiab ülesandele parimaid lahendusi vastavalt konkreetsele kriteeriumile).
Ahned algoritmid rakendavad optimaalseid kohalikke valikuid lootuses, et need valikud viivad lahendatava probleemi jaoks optimaalse globaalse lahenduseni. Ahneid algoritme pole sageli liiga raske seadistada, need on kiired (aja keerukus on sageli lineaarne funktsioon või väga palju teist järku funktsioon). Pealegi pole neid programme raske siluda ja need kasutavad vähem mälu. Kuid tulemused ei ole alati optimaalsed lahendused.
Kombinatoorse optimeerimise probleemi lahendamiseks kasutatakse sageli ahneid strateegiaid, luues valiku A. Variant A konstrueeritakse, valides A iga komponendi Ai kuni täieliku valmimiseni (piisavalt n komponenti). Iga Ai jaoks valite Ai optimaalselt. Sel viisil on võimalik, et viimases etapis pole teil muud valida, kui nõustuda viimase allesjäänud väärtusega.
Ahnetel otsustel on kaks kriitilist komponenti:
- Ahne valiku viis. Saate valida, milline lahendus on hetkel parim ja seejärel lahendada viimase valiku tegemisel tekkinud alamprobleem. Ahnete algoritmide valik võib sõltuda varasematest valikutest. Kuid see ei saa sõltuda tulevasest valikust ega sõltuda alamprobleemide lahendustest. Algoritm areneb viisil, mis teeb valikud tsüklis, vähendades samal ajal antud probleemi väiksemateks alamülesanneteks.
- Optimaalne aluskonstruktsioon. Te teostate ülesande optimaalse alamstruktuuri, kui selle ülesande optimaalne lahendus sisaldab optimaalseid lahendusi selle alamprobleemidele.
Ahne algoritm koosneb viiest komponendist:
- Kandidaatide komplekt, millest lahendusi luua.
- Valikufunktsioon parima kandidaadi valimiseks, mida lahendusele lisada.
- Teostatavat funktsiooni kasutatakse selleks, et otsustada, kas kandidaati saab kasutada lahenduse koostamiseks.
- Objektifunktsioon, mis fikseerib lahenduse või mittetäieliku lahenduse väärtuse.
- Hindamisfunktsioon, mis näitab, kui leiate tervikliku lahenduse.
Ahne idee
Esimese ideega on teil Greedy One'i järgmised sammud:
- Sordi väärtuste mittekasvavas järjekorras.
- Arvestage omakorda tellitud pakid, pange kaaluv pakk seljakotti, kui seljakoti järelejäänud mahust on selle mahutamiseks piisav (see tähendab, et seljakotti pandud pakkide kogukaal ja kaalutavate pakkide kaal ei ületa seljakoti mahutavus).
See ahne algoritm ei anna aga alati optimaalset lahendust. Siin on vastunäide:
- Ülesande parameetrid on: n = 3; M = 19.
- Pakendid: {i = 1; W[i] = 14; V[i] = 20}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 8} -> Suurepärane väärtus, aga ka suur kaal.
- Algoritm valib paketi 1 koguväärtusega 20, samas kui ülesande optimaalne lahendus (pakett 2, pakett 3) koguväärtusega 24.
Ahne kahe idee
Teise ideega on teil Greedy Two järgmised sammud:
- Sorteeri kaalude mittekahanevas järjekorras.
- Arvestage omakorda tellitud pakid, pange kaaluv pakk seljakotti, kui seljakoti järelejäänud mahust on selle mahutamiseks piisav (see tähendab, et seljakotti pandud pakkide kogukaal ja kaalutavate pakkide kaal ei ületa seljakoti mahutavus).
See ahne algoritm ei anna aga alati optimaalset lahendust. Siin on vastunäide:
- Ülesande parameetrid on: n = 3; M = 11.
- Pakendid: {i = 1; W[i] = 5; V[i] = 10}; {i = 2; W[i] = 6; V[i] = 16}; {i = 3; W[i] = 10; V[i] = 28} -> Kerge kaal, kuid väärtus on ka väga kerge.
- Algoritm valib (pakett 1, pakett 2) koguväärtusega 26, samas kui ülesande optimaalne lahendus on (pakett 3) koguväärtusega 28.
Ahne Kolmiku idee
Kolmanda ideega on teil järgmised Greedy Three'i sammud. Tegelikult on see kõige laialdasemalt kasutatav algoritm.
- Sorteeri pakid ühikuhinna väärtuse mittetõusu järjekorras . Teil on:
- Arvestage omakorda tellitud pakid, pange kaaluv pakk seljakotti, kui seljakoti järelejäänud mahust on selle mahutamiseks piisav (see tähendab, et seljakotti pandud pakkide kogukaal ja kaalutavate pakkide kaal ei ületa seljakoti mahutavus).
Mõte: Selle probleemi ahne idee on arvutada iga suhe . Seejärel sortige need suhted kahanevas järjekorras. Valite kõrgeima pakett ja seljakoti mahutavus võib seda pakendit sisaldada (ülejäänud > wi). Iga kord, kui pakk seljakotti pannakse, vähendab see ka seljakoti mahtu.
Pakettide valimise viis:
- Mõelge ühikukulude massiivile. Paketid valite vastavalt vähenevatele ühikukuludele.
- Oletame, et leidsite osalise lahenduse: (x1,…, Xi).
- Seljakoti väärtus saadakse:
- Vastavalt seljakotti pandud pakendite kaalule:
- Seetõttu on seljakoti järelejäänud kaalupiirang:
Algoritmi sammud
See on probleem max. Paketite loend on sorteeritud ühikuhinna kahanevas järjekorras, et kaaluda hargnemist.
- Samm 1: Sõlme juur tähistab seljakoti algolekut, kus te pole ühtegi paketti valinud.
- TotalValue = 0.
- Juursõlme ülemine piir UpperBound = M * Maksimaalne ühikukulu.
- Samm 2: Sõlme juurel on alamsõlmed, mis vastavad võimalusele valida suurima ühikuhinnaga pakett. Iga sõlme jaoks arvutate parameetrid uuesti:
- TotalValue = TotalValue (vana) + valitud pakettide arv * iga paketi väärtus.
- M = M (vana) – valitud pakendite arv * iga paki kaal.
- UpperBound = TotalValue + M (uus) * Järgmisena võetakse arvesse pakitud ühiku maksumus.
- Samm 3: alamsõlmedes eelistate hargnemist suurema ülemise piiriga sõlme jaoks. Selle sõlme lapsed vastavad võimalusele valida järgmine suure ühikuhinnaga pakett. Iga sõlme jaoks peate uuesti arvutama parameetrid TotalValue, M, UpperBound vastavalt punktis 2 nimetatud valemile.
- Samm 4: Korrake 3. sammu märkusega: sõlmede puhul, mille ülemine piir on leitud valiku ajutise maksimaalse maksumusega madalam või sellega võrdne, ei pea te enam selle sõlme jaoks hargnema.
- Samm 5: Kui kõik sõlmed on hargnenud või ära lõigatud, on kõige kallim variant, mida otsida.
Algoritmi pseudokood:
Fractional Knapsack (Array W, Array V, int M) 1. for i <- 1 to size (V) 2. calculate cost[i] <- V[i] / W[i] 3. Sort-Descending (cost) 4. i ← 1 5. while (i <= size(V)) 6. if W[i] <= M 7. M ← M – W[i] 8. total ← total + V[i]; 9. if W[i] > M 10. i ← i+1
Algoritmi keerukus:
- Kui kasutada lihtsat sortimisalgoritmi (valik, mull…), siis on kogu ülesande keerukus O(n2).
- Kui kasutate kiirsortimist või liitmissortimist, on kogu probleemi keerukus O(nlogn).
Java kood Greedy Three jaoks
- Esiteks määratlete klassi KnapsackPackage. Sellel klassil on järgmised omadused: iga pakendi kaal, väärtus ja vastav maksumus. Selle klassi vara maksumust kasutatakse põhialgoritmis sorteerimisülesande jaoks. Iga kulu väärtus on iga pakendi suhe.
public class KnapsackPackage { private double weight; private double value; private Double cost; public KnapsackPackage(double weight, double value) { super(); this.weight = weight; this.value = value; this.cost = new Double(value / weight); } public double getWeight() { return weight; } public double getValue() { return value; } public Double getCost() { return cost; } }
- Seejärel loote funktsiooni Greedy Three algoritmi täitmiseks.
public void knapsackGreProc(int W[], int V[], int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int i = 0; i < n; i ++) { packs[i] = new KnapsackPackage(W[i], V[i]); } Arrays.sort(packs, new Comparator<KnapsackPackage>() { @Override public int compare(KnapsackPackage kPackA, KnapsackPackage kPackB) { return kPackB.getCost().compareTo(kPackA.getCost()); } }); int remain = M; double result = 0d; int i = 0; boolean stopProc = false; while (!stopProc) { if (packs[i].getWeight() <= remain) { remain -= packs[i].getWeight(); result += packs[i].getValue(); System.out.println("Pack " + i + " - Weight " + packs[i].getWeight() + " - Value " + packs[i].getValue()); } if (packs[i].getWeight() > remain) { i ++; } if (i == n) { stopProc = true; } } System.out.println("Max Value:\t" + result); }
Koodi selgitus:
- Lähtestage iga seljakoti pakendi kaal ja väärtus.
- Sorteerige seljakottide pakendid hinna järgi kahanevas järjekorras.
- Kui valite paketi i.
- Kui valite paki arvu, piisab i.
- Peatage kõigi pakettide sirvimisel.
Selles õpetuses on kaks näidet. Siin on java kood ülaltoodud programmi käivitamiseks kahe näitega:
public void run() { /* * Pack and Weight - Value */ //int W[] = new int[]{15, 10, 2, 4}; int W[] = new int[]{12, 2, 1, 1, 4}; //int V[] = new int[]{30, 25, 2, 6}; int V[] = new int[]{4, 2, 1, 2, 10}; /* * Max Weight */ //int M = 37; int M = 15; int n = V.length; /* * Run the algorithm */ knapsackGreProc(W, V, M, n); }
Teil on väljund:
- Esimene näide:
Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 0 - Weight 10.0 - Value 25.0 Pack 2 - Weight 4.0 - Value 6.0 Pack 3 - Weight 2.0 - Value 2.0 Max Value: 83.0
- Teine näide:
Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 0 - Weight 4.0 - Value 10.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Pack 1 - Weight 1.0 - Value 2.0 Max Value: 36.0
Analüüsige esimest näidet:
- Ülesande parameetrid on: n = 4; M = 37.
- Pakendid: {i = 1; W[i] = 15; V[i] = 30; Maksumus = 2.0}; {i = 2; W[i] = 10; V[i] = 25; Maksumus = 2.5}; {i = 3; W[i] = 2; V[i] = 4; Maksumus = 1.0}; {i = 4; W[i] = 4; V[i] = 6; Maksumus = 1.5}.
- Sorteerite pakid ühikuhinna väärtuse suurenemise järjekorras. Teil on: {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
Esimese näite jaoks algoritmi rakendamise sammud:
- Defineeri x1, x2, x3, x4 on iga valitud paketi number, mis vastab paketile {i = 2} -> {i = 1} -> {i = 4} -> {i = 3}.
- Sõlme juur N tähistab olekut, et te pole ühtegi paketti valinud. Seejärel:
- TotalValue = 0.
- M = 37 (nagu välja pakutud).
- Ülemine piir = 37 * 2.5 = 92.5, millest 37 on M ja 2.5 on paketi {i = 2} ühiku maksumus.
- Pakendiga {i = 2} on teil 4 võimalust: valige 3 paketti {i = 2} (x1 = 3); vali 2 paketti {i = 2} (x1 = 2); valida 1 pakett {i = 2} (x1 = 1) ja mitte valida paketti {i = 2} (x1 = 0). Vastavalt nendele neljale võimalusele hargnete juursõlme N 4 alamsõlmeks N[4], N[1], N[2] ja N[3].
- Alamsõlme N1 jaoks on teil:
- TotalValue = 0 + 3 * 25 = 75, kus 3 on valitud paketi {i = 2} arv ja 25 on iga paketi {i = 2} väärtus.
- M = 37 – 3 * 10 = 7, kus 37 on seljakoti algkogus, 3 on paki arv {i = 2}, 10 on iga paki kaal {i = 2}.
- UpperBound = 75 + 7 * 2 = 89, kus 75 on TotalValue, 7 on seljakoti järelejäänud kaal ja 2 on pakendi ühiku maksumus {i = 1}.
- Samamoodi saate arvutada sõlmede N[2], N[3] ja N[4] parameetreid, mille ülemine piir on vastavalt 84, 79 ja 74.
- Sõlmede N[1], N[2], N[3] ja N[4] hulgas on sõlmel N[1] suurim ülemine piir, seega hargnete kõigepealt sõlme N[1] lootuses, et seal on hea plaan sellest suunast.
- Sõlmest N[1] on teil ainult üks alamsõlm N[1-1], mis vastab x2 = 0 (seljakoti ülejäänud kaalu tõttu on 7, samas kui iga paki kaal {i = 1} on 15) . Pärast nupu N[1-1] parameetrite määramist on N[1-1] ülemine piir 85.5.
- Jätkate sõlme N[1-1] hargnemist. Sõlmel N[1-1] on 2 last N[1-1-1] ja N[1-1-2], mis vastavad x3 = 1 ja x3 = 0. Pärast nende kahe sõlme parameetrite määramist näete, et N[1-1-1] ülempiir on 84 ja N[1-1-2] 82, seega jätkate sõlme N[1-1-1] hargnemist.
- Sõlmel N[1-1-1] on kaks last, N[1-1-1-1] ja N[1-1-1-2], mis vastavad x4 = 1 ja x4 = 0. Need on kaks lehesõlme (esindab valikut), sest iga sõlme jaoks on valitud pakettide arv. Milles sõlm N[1-1-1-1] tähistab valikut x1 = 3, x2 = 0, x3 = 1 ja x4 = 1 83 jaoks, samas kui sõlm N[1-1-1-2] tähistab valikut x1 = 3, x2 = 0, x3 = 1 ja x4 = 01 81 juures. Seega on ajutine maksimumväärtus siin 83.
- Pöörates tagasi sõlme N[1-1-2] juurde, näete, et sõlme N[1-1-2] ülempiir on 82 < 83, nii et trimmite sõlme N[1-1-2].
- Pöörates tagasi sõlme N2 juurde, näete, et N2 ülempiir on 84 > 83, seega jätkate sõlme N2 hargnemist. Sõlmel N2 on kaks last N[2-1] ja N[2-2], mis vastavad x2 = 1 ja x2 = 0. Pärast N[2-1] ja N[2-2] parameetrite arvutamist näete N[2-1] ülemine piir on 83 ja N[2-2] ülemine piir on 75.25. Kumbki neist väärtustest ei ole suurem kui 83, nii et mõlemad sõlmed on kärbitud.
- Lõpuks kärbitakse ka sõlmed N3 ja N4.
- Seega on kõik puu sõlmed hargnenud või kärbitud, nii et parim ajutine lahendus on see, mida otsida. Vastavalt sellele peate valima 3 pakki {i = 2}, 1 paki {i = 4} ja ühe paki {i = 3} koguväärtusega 83, kogukaal on 36.
Teise näite sama analüüsiga on teil tulemus: valige pakett 4 (3 korda) ja pakett 5 (3 korda).
Python3 kood Greedy Three jaoks
- Esiteks määratlete klassi KnapsackPackage.
class KnapsackPackage(object): """ Knapsack Package Data Class """ def __init__(self, weight, value): self.weight = weight self.value = value self.cost = value / weight def __lt__(self, other): return self.cost < other.cost
- Seejärel loote funktsiooni Greedy Three algoritmi täitmiseks.
class FractionalKnapsack(object): def __init__(self): def knapsackGreProc(self, W, V, M, n): packs = [] for i in range(n): packs.append(KnapsackPackage(W[i], V[i])) packs.sort(reverse = True) remain = M result = 0 i = 0 stopProc = False while (stopProc != True): if (packs[i].weight <= remain): remain -= packs[i].weight; result += packs[i].value; print("Pack ", i, " - Weight ", packs[i].weight, " - Value ", packs[i].value) if (packs[i].weight > remain): i += 1 if (i == n): stopProc = True print("Max Value:\t", result)
Koodi selgitus:
- Lähtestage iga seljakoti pakendi kaal ja väärtus.
- Sorteerige seljakottide pakendid hinna järgi kahanevas järjekorras.
- Kui valite paketi i.
- Kui valite paki arvu, piisab i.
- Peatage kõigi pakettide sirvimisel.
Siin on Python3 kood ülaltoodud programmi käivitamiseks esimese näitega:
if __name__ == "__main__": W = [15, 10, 2, 4] V = [30, 25, 2, 6] M = 37 n = 4 proc = FractionalKnapsack() proc.knapsackGreProc(W, V, M, n)
Teil on väljund:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
C# kood Greedy Three jaoks
- Esiteks määratlete klassi KnapsackPackage.
using System; namespace KnapsackProblem { public class KnapsackPackage { private double weight; private double value; private double cost; public KnapsackPackage(double weight, double value) { this.weight = weight; this.value = value; this.cost = (double) value / weight; } public double Weight { get { return weight; } } public double Value { get { return value; } } public double Cost { get { return cost; } } } }
- Seejärel loote funktsiooni Greedy Three algoritmi täitmiseks.
using System; namespace KnapsackProblem { public class FractionalKnapsack { public FractionalKnapsack() { } public void KnapsackGreProc(int[] W, int[] V, int M, int n) { KnapsackPackage[] packs = new KnapsackPackage[n]; for (int k = 0; k < n; k++) packs[k] = new KnapsackPackage(W[k], V[k]); Array.Sort<KnapsackPackage>(packs, new Comparison<KnapsackPackage>( (kPackA, kPackB) => kPackB.Cost.CompareTo(kPackA.Cost))); double remain = M; double result = 0d; int i = 0; bool stopProc = false; while (!stopProc) { if (packs[i].Weight <= remain) { remain -= packs[i].Weight; result += packs[i].Value; Console.WriteLine("Pack " + i + " - Weight " + packs[i].Weight + " - Value " + packs[i].Value); } if (packs[i].Weight > remain) { i++; } if (i == n) { stopProc = true; } } Console.WriteLine("Max Value:\t" + result); } } }
Koodi selgitus:
- Lähtestage iga seljakoti pakendi kaal ja väärtus.
- Sorteerige seljakottide pakendid hinna järgi kahanevas järjekorras.
- Kui valite paketi i.
- Kui valite paki arvu, piisab i.
- Peatage kõigi pakettide sirvimisel.
Siin on C# kood ülaltoodud programmi käivitamiseks esimese näitega:
public void run() { /* * Pack and Weight - Value */ int[] W = new int[]{15, 10, 2, 4}; //int[] W = new int[] { 12, 2, 1, 1, 4 }; int[] V = new int[]{30, 25, 2, 6}; //int[] V = new int[] { 4, 2, 1, 2, 10 }; /* * Max Weight */ int M = 37; //int M = 15; int n = V.Length; /* * Run the algorithm */ KnapsackGreProc(W, V, M, n); }
Teil on väljund:
Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 0 - Weight 10 - Value 25 Pack 2 - Weight 4 - Value 6 Pack 3 - Weight 2 - Value 2 Max Value: 83
Ahne Kolmiku vastunäide
Greedy Three algoritm laheneb kiiresti ja võib mõnel juhul olla ka optimaalne. Kuid mõnel erijuhtumil ei anna see optimaalset lahendust. Siin on vastunäide:
- Ülesande parameetrid on: n = 3; M = 10.
- Pakendid: {i = 1; W[i] = 7; V[i] = 9; Maksumus = 9/7}; {i = 2; W[i] = 6; V[i] = 6; Maksumus = 1}; {i = 3; W[i] = 4; V[i] = 4; Maksumus = 1}.
- Algoritm valib (pakett 1) koguväärtusega 9, samas kui ülesande optimaalne lahendus on (pakett 2, pakett 3) koguväärtusega 10.
Siin on java kood ülaltoodud programmi käivitamiseks koos vastunäidisega:
public void run() { /* * Pack and Weight - Value */ int W[] = new int[]{7, 6, 4}; int V[] = new int[]{9, 6, 4}; /* * Max Weight */ int M = 10; int n = V.length; /* * Run the algorithm */ knapsackGreProc(W, V, M, n); }
Siin on tulemus:
Pack 0 - Weight 7.0 - Value 9.0 Max Value: 9.0
See on kõik fraktsionaalse seljakoti probleemiga.