NOVINKA! E-learningové kurzy umělé inteligence. Nyní AI za nejlepší ceny. Zjisti více:
NOVINKA – Víkendový online kurz Software tester, který tě posune dál. Zjisti, jak na to!

Diskuze: Branch and bound a simplexová metóda

Aktivity
Avatar
Jozef
Člen
Avatar
Jozef:25.9.2015 19:13

Zdravím,
mohol by mi niekto vysvetliť, ako funguje Metóda vetvenia a hraníc(Branch and bound) a taktiež Simplexovú metódu? Je to prvý krát čo som sa stretol s lineárnym programovaním, takže tomu moc nerozumiem.
Pre úplnosť dodávam, že k týmto metódam/algoritmom ma priviedla nasledujúca úloha:

Máš 2 polia, každé s n číslami, n <= 500. Pre každé číslo z druhého poľa vyber
jedno z prvých troch nepoužitých číslach z prvého  poľa a tieto dve čísla vynásob.
Pokračuj týmto spôsobom, pokým nie sú použité všetky čísla.
Vypíš najväčší možný súčet týchto násobkov.

Príklad:

n = 4;
prvé pole : 16 6 2 10
druhé pole : 3 8 12 9
Output : 336

Vysvetlenie:

Pre prvé číslo v druhom poli - 3 - môžeš vybrať z čísel 16,6 a 2. Najlepšou možnosťou je vybrať 2. Najväčší možný výsledok(ďalej sum) je teraz 3 * 2, teda sum = 6.
Pre druhé číslo v druhom poli - 8 - môžeš vybrať z čísel 16,6,10 (cíšlo 2 už bolo použité). Najlepšou možnosťou je vybrať 6. K vyslednému súčtu pripočítame 8 * 6, teda sum = 54.
Pre tretie číslo - 12 - si môžeš vybrať z čísel 16 a 10 ( 2 a 6 sú už použité). Najlepšou možnosťou je vybrať 16. K vyslednému súčtu pripočítame 12 * 16, teda sum = 246.
Pre posledné číslo - 9 - je možné vybrať iba číslo 10. K vyslednému súčtu tak pripočítame 9 * 10, teda sum = 336.

Neviem, či je toto správna sekcia, mne pripadala najvhodnejšia.

Odpovědět
25.9.2015 19:13
I'm not afraid to die on a treadmill
Avatar
Jozef
Člen
Avatar
Jozef:26.9.2015 17:54

Úloha, ktorú som napísal hore mi pripadá ako Assignment problem . Pre tento problém som našiel Hungarian algorithm. Asi jediný rozdiel je v tom, že pri mojom probléme nedokážem každým bodom z jedného poľa(bipartitného grafu) dosiahnuť na všetky body z druhého grafu. Inak povedané, nie každý "pracovník" dokáže robiť všetky úlohy. Prvý dokáže robiť iba 1.-3. úlohu, druhý 1.-4. úlohu atď. Možno by sa to dalo vyriešiť tak, že by som do 2D poľa s hodnotami pre každého "pracovníka" dal hodnotu 0. Ale aj keby to fungovalo, neviem, či by bol algoritmus dostatočne rýchly. Časovú zložitosť má 0(n3), pričom v mojom prípade je n <= 500.
Taktiež by sa to možno mohlo vyriešiť ako Max Flow problem , ale neviem, či by to spravilo tzv. perfect matching, teda by každému vrcholu(bodu) priradilo iný bod.
Je tu niekto kto by vedel poradiť?

Nahoru Odpovědět
26.9.2015 17:54
I'm not afraid to die on a treadmill
Avatar
Odpovídá na Jozef
Drahomír Hanák:26.9.2015 19:16

Napadlo mě třeba zjistit permutaci pi(x) prvního pole (P), uspořádat čísla druhého pole (Q) vzestupně, a pak je přeuspořádat podle inverze permutace piInv(x). Pro výsledek stačí vynásobit odpovídající indexy v obou polích. Inverzní permutaci můžeš najít třeba umocňováním permutační matice.

Pro optimální výsledek musíme vynásobit nejmenší prvek z P nejmenším prvkem z Q atd. Obecně k nejmenší prvek z P musíme vynásobit k nejmenším prvkem z Q. Tzn. pokud další nepoužitý prvek z pole P je k nejmenší v tom poli, na odpovídajícím indexu v poli Q musí být také k nejmenší prvek toho pole. Uspořádáním Q jeho permutaci změníme na identitu, přeuspořádáním podle inverzní permutace dostaneme stejnou permutaci pi(x).

 
Nahoru Odpovědět
26.9.2015 19:16
Avatar
Odpovídá na Drahomír Hanák
Drahomír Hanák:26.9.2015 19:42

'Teď jsem si uvědomil, že stačí transpozice té matice.

 
Nahoru Odpovědět
26.9.2015 19:42
Avatar
Jozef
Člen
Avatar
Odpovídá na Drahomír Hanák
Jozef:26.9.2015 20:49

Neviem presne ako to myslíš, ale to, že treba vynásobiť najmenší z jedného najmenším druhého atď je jasné. Ale kedže pri prvom môžem vybrať iba prvé tri, potom môžem zasa vyberať iba z troch to robí nemožným. Dokážem utriediť obe polia, a potom každému bodu z druhého poľa priradiť rozsah - napr. rozsah prvého sú od 1.-3.; rozsah druhého je od 1.-4.; rozsah tretieho je od 1.-5. atď - a vyberať najbližšie možné najmenšie číslo, ktoré spadá do tohoto rozsahu - lenže potom môže dojsť k situácii, že nedokážem použiť všetky body. Vymyslel som iný spôsob - ku každému číslu z prvého poľa priradím, aké ideálne číslo by mal dostať (teda najmenšiemu je ideálne najmenšie z druhého poľa atď) a potom v poradí v akom sú body v druhom poli sledovať, kde je toto číslo najbližšie ideálu. Takto by som sa dopracoval k ideálnemu riešeniu. Má to však jeden háčik - ak majú aspoň dve možnosti rovaký ideál, pre ktorý sa rozhodnem? A to je problém. Tam nie je žiadna správna alebo nesprávna možnosť - vždy je to iné. A preto takýto spôsob nebude nikdy fungovať. - môžem pripojiť aj kód pre toto riešenie.

Editováno 26.9.2015 20:51
Nahoru Odpovědět
26.9.2015 20:49
I'm not afraid to die on a treadmill
Avatar
Odpovídá na Jozef
Drahomír Hanák:26.9.2015 21:52

Moje řešení s prvním polem nemanipuluje. Projde ho postupně od 1. do posledního prvku a to je podle zadání platná operace, protože vybírá vždy první z 3 zatím nevybraných čísel z prvního pole.

Co konkrétně není jasné? Permutací jsem zjednodušeně myslel uspořádání prvků v poli. pi(x) = i znamená, že prvek, který je teď na indexu x je v uspořádaném poli na indexu i (jinými slovy je to i nejmenší prvek v tom poli)

 
Nahoru Odpovědět
26.9.2015 21:52
Avatar
Jozef
Člen
Avatar
Odpovídá na Drahomír Hanák
Jozef:26.9.2015 23:06

Tak konkrétne nerozumiem presne tomuto
tomuto,čo by som mal spraviť:

pak je přeuspořádat podle inverze permutace piInv(x). Pro výsledek stačí vynásobit odpovídající indexy v obou polích. Inverzní permutaci můžeš najít třeba umocňováním permutační matice.

Nahoru Odpovědět
26.9.2015 23:06
I'm not afraid to die on a treadmill
Avatar
Odpovídá na Jozef
Drahomír Hanák:26.9.2015 23:39

Mějme třeba pole [16, 6, 2, 10], pak permutace je [3, 1, 0, 2] Prvek na indexu 0 by měl být v uspořádaném poli na indexu 3, prvek na indexu 1 by měl být v uspořádaném poli na indexu 1 atd. Permutace je tak v podstatě funkce (reprezentovaná tím polem [3, 1, 0, 2] - mapuje indexy na odpovídající hodnoty). Můžeme to rozepsat pi(0) = 3, pi(1) = 1, pi(2) = 0 a pi(3) = 2

Inverzní permutaci dostaneš tak, že prohodíš indexy toho pole s jeho hodnotami. Takže inverzní permutace v tomto případě je [2, 1, 3, 0] - piInv(0) = 2, piInv(1) = 1, piInv(2) = 3 a piInv(3) = 0 (všimni si, že pi(piInv(x)) = x, proto inverzní permutace)

Vytvoříš si pomocné pole, projdeš všechny hodnoty v druhém poli a každou hodnotu z toho pole vložíš do pomocného pole na index piInv(I). Tady je pseudokód:

SerazeneDruhePole = sort(DruhePole)
permutace = perm(PrvniPole) // permutaci můžeš zjistit např. při řazení pole
inverze = inv(permutace) // jen prohodíš indexy za hodnoty
PomocnePole = []
suma = 0
pro i v poli SerazeneDruhePole:
        PomocnePole[inverze[i]] = SerazeneDruhePole[i]
pro i v poli PrvniPole:
        suma += PrvniPole[i] * PomocnePole[i]
vrat suma
 
Nahoru Odpovědět
26.9.2015 23:39
Avatar
Jozef
Člen
Avatar
Jozef:27.9.2015 12:25

Vyskúšajme to pre:

prvé pole  R: [1000, 2, 3, 4, 5, 6, 7, 8, 9, 1]
druhé pole  Q: [5, 4, 3, 8, 7, 8, 2, 1, 5, 100]
permutácia prvého poľa [9, 1, 2, 3, 4, 5, 6, 7, 8, 0]
inverzná p. [9, 1, 2, 3, 4, 5, 6, 7, 8, 0] - neviem či toto mám správne, ale kedže pi(0) = 9, tak piInv(9) = 0; pi(9) = 0, tak piInv(0) = 9; či?
Pomocne pole P teda naplníme takto:
P [100, 2, 3, 4, 5, 5, 7, 8, 8,1];
R [1000, 2, 3, 4, 5, 6, 7, 8, 9, 1] //prvé pole, ktorým budeme násobiť

Suma by vyšla asi 100 270 - a to je nemožné. Pozrime sa už len na prvý prvok poľa Q - číslo 5. 5 by malo mať na výber 3 možností - 1000,1,2 - ale tvoje riešenie mu priradilo číslo 5, resp. 6.

Nahoru Odpovědět
27.9.2015 12:25
I'm not afraid to die on a treadmill
Avatar
Odpovídá na Drahomír Hanák
Drahomír Hanák:27.9.2015 12:25

Nevím, proč to tak zbytečně komplikuju. Pomocné pole vůbec není třeba. Tady je upravený kód:

function perm(A):
        p = []
        pro 0 <= i < |A|:
                p[i] = i
        komparator = function(a, b): vrat A[a] - A[b]
        vrat sort(p, komparator)

function inv(P):
        invP = []
        pro 0 <= i < |P|:
                invP[P[i]] = i
        vrat invP

function solve(P, Q):
        suma = 0
        p = inv(perm(P))
        Q = sort(Q)
        pro 0 <= i < |P|:
                suma += P[i] * Q[p[i]]
        vrat suma

A nějaké vlastnosti: podle algoritmu řazení bude časová složitost O(n * log n) (řazení prvního pole + zjištění inverzní permutace + řazení druhého pole + suma) a paměťová složitost O(n) (pole permutace + příp. pomocná paměť při řazení), výsledek je optimální a nezáleží na tom, z kolika prvních prvků prvního pole vybíráš.

 
Nahoru Odpovědět
27.9.2015 12:25
Avatar
Jozef
Člen
Avatar
Odpovídá na Drahomír Hanák
Jozef:27.9.2015 12:44

vyskúšaj aký výsledko ti to dá pre tieto dve polia:

prvé pole  R: [1000, 2, 3, 4, 5, 6, 7, 8, 9, 1]
druhé pole  Q: [5, 4, 3, 8, 7, 8, 2, 1, 5, 100]
Nahoru Odpovědět
27.9.2015 12:44
I'm not afraid to die on a treadmill
Avatar
Odpovídá na Jozef
Drahomír Hanák:27.9.2015 12:50

V tom případě jsem asi špatně pochopil zadání. Zadání, které jsi poslal, totiž umožňuje projít druhé pole v jakémkoli pořadí dokud pro každý prvek z druhého pole vybereš právě 1 prvek z prvních 3 zatím nepoužitých čísel z prvního.

Takže trochu upravíme to řešení: zjistíš permutaci obou polí, postupně projdeš prvky druhého pole a pro každý prvek z druhého pole vybereš číslo z prvních 3 zatím nepoužitých čísel, jehož permutace je nejbližší.

 
Nahoru Odpovědět
27.9.2015 12:50
Avatar
Jozef
Člen
Avatar
Odpovídá na Drahomír Hanák
Jozef:27.9.2015 13:18

Pripomína mi to moje vlastné riešenie - pre každý prvok prvého poľa zistím, aký prvok by dostal v ideálnom prípade - teda že môžem vyberať z celého poľa. Takže najväčšiemu prvku prvého poľa priradím najväčší toho druhého atď. Potom každému prvku z druhého poľa určím rozsah - 1.prvok môže ísť od 1 do 3; druhý prvok od 1 do 4 atď.
Pre:

prvé pole 16 6 2 10 ---> pre 16 je ideál 12; pre 6 je ideál 8; pre 2 je ideál 3 a pre 10 je ideál 9.
druhé pole 3 8 12 9 ----> pre 3 je rozsah 3; pre 8 je rozsah 4; pre 12 a aj pre 9 je rozsah 4

Potom pre každé 3 prvky z prvého poľa pre každý prvok v druhom poli v nezmenenom poradí zisťujem 2 veci - aký je rozdiel medzi ideálom prvku z druhého poľa a skutočnou hodnotou prvku z druhého poľa - zistím to odčítaním ideálu od rozsahu v absolútnej hodnote.

prvý prvok z druhého poľa má 3 možnosti : 16 - ideál 12;6- ideál 8; 3 -ideál 3. Keď odčítam
v aboslútnej hodnote, vyjdú takéto rozdiely - pre 16 je rozdiel 9; pre 6 je rozdiel 5; pre 3 je rozdiel 0.
Vyberem prvok s najmenším rozdielom. Takto pokračujem do konca.

Lenže rozdiel v absolútnej hodnote nestačí - ak by boli dve čísla, pre jedno je ideál 5 a pre druhé je ideál 3 a mám číslo 4. Rozdiel v abs. hodnote je rovnaký - 1. Preto treba vybrať to, čo je menšie. Alebo väčšie, tu už si nie som istý. A čo ak budeme mať 2 čísla, ktorých ideál je pre obe čísla 5? Ktoré vyberieme? A tu je problém - nedá sa vybrať žiadne konkrétne pre každý prípad. Pretože to závisí od iných čísiel. Preto si myslím,že takéto riešenie neexistuje. Ďalšia vec, keby akéto jednoduché riešenie existovalo, existovalo by aj pre assignment problem - a také jednoduché riešenie neexistuje.

Nahoru Odpovědět
27.9.2015 13:18
I'm not afraid to die on a treadmill
Avatar
Jozef
Člen
Avatar
Jozef:27.9.2015 13:27

Pre príklad pri

prvé pole  R: [1000, 2, 3, 4, 5, 6, 7, 8, 9, 1]
druhé pole  Q: [5, 4, 3, 8, 7, 8, 2, 1, 5, 100]

potrebujem vybrať v prípade rovnosti ideálov číslo, ktoré je väčšie.
Pre :

prvé pole  R: [10, 9, 8, 2, 3, 4, 5, 1, 6, 7]
druhé pole  Q: [5, 4, 3, 8, 7, 8, 2, 1, 5, 10]

potrebujem vybrať v prípade rovnosti ideálov číslo, ktoré je menšie.
Týmito príkladmi si teraz nie som úplne istý, ale mali by byť správne

Nahoru Odpovědět
27.9.2015 13:27
I'm not afraid to die on a treadmill
Avatar
Odpovídá na Jozef
Drahomír Hanák:27.9.2015 14:16

Máš samozřejmě pravdu, taky jsem si hned uvědomil, že to nebude optimální. Tvoje řešení vypadá dobře. Co spolu s absolutní hodnotou rozdílu těch čísel zkusit i rozdíl toho pořadí v seřazeném poli? Jde o to, že čím blíž ta čísla budou z hlediska pořadí v seřazeném poli, tím bude větší výsledek (protože tenhle rozdíl by byl 0 pokud by tam nebyla ta omezení)

 
Nahoru Odpovědět
27.9.2015 14:16
Avatar
Jozef
Člen
Avatar
Jozef:27.9.2015 17:17

Ono ten problém spočíva v tom, že výber toho čísla závisí ešte aj od iného čísla. Keby mám napr. na výber čísla 5 a 6, a vyberiem 5, tak to či je to dobre alebo zle závisí od čísla, ktoré si vyberie číslo 6 a opačne. Jediné čo ma napadá by bolo, pre každé takéto rozhodnutie rozdeliť riešenie - do jedného riešenia by som vybral napr. číslo 5, do druhého číslo 6 atď. Inak by bolo určite správnym riešením Hungarian algorithm, len ten je dosť zložitý na implementáciu. Online verzia

Nahoru Odpovědět
27.9.2015 17:17
I'm not afraid to die on a treadmill
Děláme co je v našich silách, aby byly zdejší diskuze co nejkvalitnější. Proto do nich také mohou přispívat pouze registrovaní členové. Pro zapojení do diskuze se přihlas. Pokud ještě nemáš účet, zaregistruj se, je to zdarma.

Zobrazeno 16 zpráv z 16.