Search
 
 
  Engleski
 
 
 
Open in this window (click to change)
Forum@DeGiorgi: Početna
Forum za podršku nastavi na PMF-MO
Login Registracija FAQ Smajlići Članstvo Pretražnik Forum@DeGiorgi: Početna

Sparivanje s preferencijama

Moja sarma
 
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Matematičko modeliranje
Prethodna tema :: Sljedeća tema  
Autor/ica Poruka
caklovic
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 16. 10. 2002. (12:08:55)
Postovi: (80)16
Sarma = la pohva - posuda
= 21 - 14

PostPostano: 17:59 čet, 28. 11. 2002    Naslov: Sparivanje s preferencijama Citirajte i odgovorite

Sparivanje s preferencijama

Pretpostavimo da $n$ momaka i $n$ djevojaka izrazavaju svoje medjusobne simpatije na nacin da svaki momak i svaka djevojka imaju svoju rang listu simpatija. Na primjer, u matrici

M_1 M_2 M_3

D_1 1,3 2,2 3,1

D_2 3,1 1,3 2,2

D_3 2,2 3,1 1,3

rang lista simpatija od M_2 je D_3D_1D_2, a za djevojku D_3 rang lista simpatija je M_3M_1M_2.

Definicija.
Kazemo da je sparivanje stabilno ako ne postoji par (D,M) izvan sparivanja koji bi bili zadovoljniji u braku s nekim drugim nego sto su sada.

Na primjer sparivanje D_1-M_1, D_2-M_3, D_3-M_2 nije stabilno jer D_1 i M_2 bi bili zadovoljniji da su zajedno.

Probem: Naci algoritam koji rjesava gornji problem. Relacija preferencije moze biti i slaba preferencija, tj. dozvoljava se isti rang za dvije alternative.[/u][/b]
Sparivanje s preferencijama

Pretpostavimo da $n$ momaka i $n$ djevojaka izrazavaju svoje medjusobne simpatije na nacin da svaki momak i svaka djevojka imaju svoju rang listu simpatija. Na primjer, u matrici

M_1 M_2 M_3

D_1 1,3 2,2 3,1

D_2 3,1 1,3 2,2

D_3 2,2 3,1 1,3

rang lista simpatija od M_2 je D_3D_1D_2, a za djevojku D_3 rang lista simpatija je M_3M_1M_2.

Definicija.
Kazemo da je sparivanje stabilno ako ne postoji par (D,M) izvan sparivanja koji bi bili zadovoljniji u braku s nekim drugim nego sto su sada.

Na primjer sparivanje D_1-M_1, D_2-M_3, D_3-M_2 nije stabilno jer D_1 i M_2 bi bili zadovoljniji da su zajedno.

Probem: Naci algoritam koji rjesava gornji problem. Relacija preferencije moze biti i slaba preferencija, tj. dozvoljava se isti rang za dvije alternative.[/u][/b]


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
Night
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 28. 11. 2002. (10:00:42)
Postovi: (3)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 12:12 uto, 3. 12. 2002    Naslov: Citirajte i odgovorite

Problem uopce nije tako jednostavan kako se cini ili nisam dovoljno duboko promislio o samoj biti problema?! :roll:

Na pamet mi pada samo neki teski backtracking algoritam ili mozda neki geneticki algoritam koji nikako nece svaki put davati tocan rezultat..

Moze neki hint?
Problem uopce nije tako jednostavan kako se cini ili nisam dovoljno duboko promislio o samoj biti problema?! Rolling Eyes

Na pamet mi pada samo neki teski backtracking algoritam ili mozda neki geneticki algoritam koji nikako nece svaki put davati tocan rezultat..

Moze neki hint?



_________________
Ce grand malheur, de ne pouvoir etre seul
[Vrh]
Korisnički profil Pošaljite privatnu poruku
caklovic
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 16. 10. 2002. (12:08:55)
Postovi: (80)16
Sarma = la pohva - posuda
= 21 - 14

PostPostano: 12:29 uto, 3. 12. 2002    Naslov: Citirajte i odgovorite

[quote="Night"]
Moze neki hint?[/quote]

Jedna ideja je da se momci predbiljeze kod svojih simpatija a onda djevojke biraju. U drugom koraku, ako nisu odabrani, ponave isto
kod druge simpatije i tako redom. Treba razraditi i dkazati da se dobije stabilno rjesenje.

Ovaj algoritam ne daje sva rjesenja. Takodjer je pitanje koliko ima stabilnih rjesenja.
Night (napisa):

Moze neki hint?


Jedna ideja je da se momci predbiljeze kod svojih simpatija a onda djevojke biraju. U drugom koraku, ako nisu odabrani, ponave isto
kod druge simpatije i tako redom. Treba razraditi i dkazati da se dobije stabilno rjesenje.

Ovaj algoritam ne daje sva rjesenja. Takodjer je pitanje koliko ima stabilnih rjesenja.


[Vrh]
Korisnički profil Pošaljite privatnu poruku Pošaljite e-mail Posjetite Web stranice
Night
Forumaš(ica)
Forumaš(ica)


Pridružen/a: 28. 11. 2002. (10:00:42)
Postovi: (3)16
Sarma = la pohva - posuda
= 0 - 0

PostPostano: 20:32 sub, 7. 12. 2002    Naslov: Rijesenje? Citirajte i odgovorite

Koliko ima stabilnih rijesenja hmm na to ne znam odgovorit..

A jel moze rijesenje ovako:

Za pocetak neka su nam preference momaka prema djevojkama zapisani u matrici [i]M[/i] i neka su nam u matrici [i]D[/i] preference djevojaka prema momcima.. Uzet cemo da djevojke biraju momke (neka im je tako :lol: zasto bi se uvijek mi mucili 8) ). Sad je ideja da svaka djevojka u jednom krugu trazi momka (kojeg bi najradije ozenila ili kako vec). No "dobro" to bas i nije lijepo receno ajmo ovako. Dakle djevojka (nazovimo je) [i]i[/i] bi najradije bila sa onim momkom koji joj je broj jedan na listi (ocito?!). Ako je taj momak vec u vezi sa nekom drugom djevojkom koja mu je draza od nase djevojke [i]i[/i], onda [i]i[/i] trazi iduceg sa rang liste tj. broj dva, pa tako sve dok ne nadje momka koji je slobodan ili dok ne nadje momka koji je ozenjen ali za djevojku koja mu je nizije na rang listi od djevoke [i]i[/i]. Ako je bio slucaj da je djevojka [i]i[/i] nasla nekog momka koji nije bio u vezi onda stavimo tog momka i djevojku [i]i[/i] u vezu, pa dalje nastavljamo sa iducom djevokom kojoj trebamo naci momka. Ako je sucaj da je momak bio u vezi s nekom djevojkom [i]k[/i] koja je nizije na rang listi momka od djevoke [i]i[/i] to znaci da ce ona (djevojka [i]i[/i]) razoriti vezu izmedju momka i druge djevojke i biti s tim momkom (u vezi). Sada djevojka [i]k[/i] ostaje bez svog momka pa ga opet trazimo za nju i to od mjesta na kojem stala na rang listi svojih momaka. Pri tome mozda unistimo jos neke veze, ali ipak nastavljamo (razarati veze ako treba) dok neka djevojka ne nadje momka koji jos nije u vezi.

E da i time dobivamo stabilne veze. Ovim algoritmom dobivamo jednu postavu, drugu mozemo dobiti tako da zamjenimo ulogu momaka i djevojaka u prici.. za ostale ne znam..

Ipak problem i nije tako tezak kad se o njemu malo razmisli i malo konzultira literatura :oops: .. Ja sam prvo isao gledati problem sa strojevima i ranicima jer mi se cinio laksi, a eto ovaj cak ima linearno rijesenje :?:

Sad jos preostaje to iskodirati recimo u C-u hmm al ne sad mozda poslije kolkovija.. ispricavam se zbog toga vrlo rado bi to sad ali.. :cry:

PS ispricavam se djevojkama [i]i[/i] i [i]k[/i] na skracivanju njihovih imena (hvala Ivani i Katarini) sala..
Koliko ima stabilnih rijesenja hmm na to ne znam odgovorit..

A jel moze rijesenje ovako:

Za pocetak neka su nam preference momaka prema djevojkama zapisani u matrici M i neka su nam u matrici D preference djevojaka prema momcima.. Uzet cemo da djevojke biraju momke (neka im je tako Laughing zasto bi se uvijek mi mucili Cool ). Sad je ideja da svaka djevojka u jednom krugu trazi momka (kojeg bi najradije ozenila ili kako vec). No "dobro" to bas i nije lijepo receno ajmo ovako. Dakle djevojka (nazovimo je) i bi najradije bila sa onim momkom koji joj je broj jedan na listi (ocito?!). Ako je taj momak vec u vezi sa nekom drugom djevojkom koja mu je draza od nase djevojke i, onda i trazi iduceg sa rang liste tj. broj dva, pa tako sve dok ne nadje momka koji je slobodan ili dok ne nadje momka koji je ozenjen ali za djevojku koja mu je nizije na rang listi od djevoke i. Ako je bio slucaj da je djevojka i nasla nekog momka koji nije bio u vezi onda stavimo tog momka i djevojku i u vezu, pa dalje nastavljamo sa iducom djevokom kojoj trebamo naci momka. Ako je sucaj da je momak bio u vezi s nekom djevojkom k koja je nizije na rang listi momka od djevoke i to znaci da ce ona (djevojka i) razoriti vezu izmedju momka i druge djevojke i biti s tim momkom (u vezi). Sada djevojka k ostaje bez svog momka pa ga opet trazimo za nju i to od mjesta na kojem stala na rang listi svojih momaka. Pri tome mozda unistimo jos neke veze, ali ipak nastavljamo (razarati veze ako treba) dok neka djevojka ne nadje momka koji jos nije u vezi.

E da i time dobivamo stabilne veze. Ovim algoritmom dobivamo jednu postavu, drugu mozemo dobiti tako da zamjenimo ulogu momaka i djevojaka u prici.. za ostale ne znam..

Ipak problem i nije tako tezak kad se o njemu malo razmisli i malo konzultira literatura Embarassed .. Ja sam prvo isao gledati problem sa strojevima i ranicima jer mi se cinio laksi, a eto ovaj cak ima linearno rijesenje Question

Sad jos preostaje to iskodirati recimo u C-u hmm al ne sad mozda poslije kolkovija.. ispricavam se zbog toga vrlo rado bi to sad ali.. Crying or Very sad

PS ispricavam se djevojkama i i k na skracivanju njihovih imena (hvala Ivani i Katarini) sala..



_________________
Ce grand malheur, de ne pouvoir etre seul
[Vrh]
Korisnički profil Pošaljite privatnu poruku
Prethodni postovi:   
Započnite novu temu   Odgovorite na temu   printer-friendly view    Forum@DeGiorgi: Početna -> Kolegiji diplomskih i starih studija -> Matematičko modeliranje Vremenska zona: GMT + 01:00.
Stranica 1 / 1.

 
Forum(o)Bir:  
Možete otvarati nove teme.
Možete odgovarati na postove.
Ne možete uređivati Vaše postove.
Ne možete izbrisati Vaše postove.
Ne možete glasovati u anketama.
You can attach files in this forum
You can download files in this forum


Powered by phpBB © 2001, 2002 phpBB Group
Theme created by Vjacheslav Trushkin
HR (Cro) by Ančica Sečan