Diskuze: Branch and bound a simplexová metóda
Ú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ť?
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).
Drahomír Hanák:26.9.2015 19:42
'Teď jsem si uvědomil, že stačí transpozice té matice.
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.
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)
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.
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 sumaVyskúš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.
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 sumaA 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áš.
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]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žší.
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.
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
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í)
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
Zobrazeno 16 zpráv z 16.