Karike.com je društvena mreža koja ti nudi priliku da komuniciraš sa svojim prijateljima, upoznaš nove ljude, saznaš šta drugi misle o tebi i postaneš zvezda! Za korišćenje sajta uloguj se ili registruj! Besplatno je...
LoST-DReaMeR blog

Interesantan i smesan odlomak iz lekcije o algoritmima :D c/p

Izvor:
"Osnove programiranja" - Dr Milan Popović

...
...

Sada ćemo analizirati jedan nešto složeniji problem i algoritam kojim se on rešava.

Problem stabilnih parova

Pretpostavimo da u jednom gradu na jugu Srbije imamo n mladića i n devojaka. Svi se međusobno poznaju, jer to je jedno malo mesto. Svaki mladić ima rang listu svih devojaka iz tog gradića, tako da se na toj listi na prvom mestu nalazi deveojka koja mu se najviše sviđa, a na poslednjem n-tom mestu devojka koja mu se najmanje sviđa. Istu takvu listu imaju i sve devojke, ali sa rang listom svih n mladića. Te liste su nam unapred poznate na neki način (Radio Milevom).

Cilj nam je da oženimo momke i devojke tako da svi budu sretni, a da brakovi budu
stabilni. Videćemo uskoro šta pod tim podrazumevamo.
Definicija. Skup brakova je stabilan ako ne postoji par mladić-devojka koji se jedno
drugom sviđaju više nego njihovi bračni drugovi.
Na primer, pretpostavimo da su Marko i Jovana u jednom, a Petar i Milica u drugom
braku. Na nesreću Jovani se više sviđa Petar nego Marko, a Petru se sviđa više Jovana nego Milica. Ovo znači da bi Jovana i Petar bili srećniji da su zajedno. To može da bude razlog za bračnu prevaru, pa se njihovi brakovi mogu smatrati nestabilnim.

Matematički se može dokazati da uvek postoji stabilno uparivanje mladića i devojaka, takvo da ne postoji ni jedan nestabilan par. (Takođe se može matematički dokazati da ne postoji stabilno uparivanje ako bi dozvolili da se bračno uparuju osobe istog pola.).
Veoma je interesantno da ovaj algoritam u SAD-u ima jednu veoma praktičnu primenu. Tamo se svake godine svršeni studenti medicine upućuju (mladići) na praksu u bolnice (devojke) upravo korišćenjem ovog algoritma. Inače, algoritam su prvi put opisali D. Gale i L.S. Shapley 1962 godine.
Hajdemo sada da problem razmotrimo na jednom konkretnom slučaju 5 devojaka i 5 mladića. Mladiće ćemo označiti brojevima 1-5, a devojke slovim A-E.

Sledeća tabela
pokazule njihove rang liste.

mladići -------------- devojke
1: CBEAD ------------ A : 35214
2: ABECD ------------ B : 52143
3: DCBAE ------------ C : 43512
4: ACDBE ------------ D : 12345
5: ABDEC ------------ E : 23415

Pokušajmo najpre jednu prostu ( grabljivu ) strategiju. Krenimo redom od prvog mladića i svima dajmo devojku koja je najviše kotirana na njegovoj listi, a još uvek je “raspoloživa”. To bi nam dalo sledeći rezultat uparivanja:

1 -- C
2 -- A
3 -- D
4 -- B
5 -- E

Da proverimo stabilnost ovako napravljenih parova.
Mladići 1, 2 i 3 su dobili svoje omiljene devojke, tako da im neće pasti na pamet da jure za drugima. Mladić 4 može biti problematičan jer mu se više sviđa devojka A od one koju je dobio (B), ali je devojka A njega stavila na poslednje mesto, tako da to nije problem. Međutim mladiću 4 se više sviđa i devojka C one koju je dobio, a devojci C se on takođe više sviđa od onog kojeg je ona dobila (1). Znači mladić 4 i devojka C su potencijalni brakolomci. Uparivanje je, dakle, nestabilno. Mogli bi sada da pokušamo da nekom kombinatorikom to popravimo, ali bi pri tom mogli da formiramo druge nestabilne parove, i da vrteći se u krug ne nađemo rešenje. I to za samo 5 parova. A, šta bi bilo da je 100-tinak (ili više) parova u pitanju. Izgleda kao nemoguć zadatak. Ali, generalno rešenje postoji i to veoma elegantno.

Algoritam

Sada ćemo opisati jedan algoritam koji se odvija u nekoliko dana i koji dovodi do
stabilnog uparivanja.
Svakog dana se ponavlja sledeći ritual (scenario):

Jutro: Svaka devojka izađe na svoj balkon. Svaki mladić dođe ispod balkona devojke koja je na prvom mestu njegove rang liste i peva joj serenadu. Ako mladiću nije ostala ni jedna devojka u listi, on ostaje kod kuće ( i radi domaće zadatke iz programiranja).

Popodne: Svaka devojka koja ispod svog balkona ima udvarače (koji pevaju serenade), jednom od njih koji je najviši na njenoj rang listi kaže: “Možda, dođi sutra.”, a svim ostalima kaže: “Nikad se neću udati za tebe. Šetaj”.

Uveče: Svaki mladić koji je dobio “korpu” iz svoje liste briše devojku kod koje nema
nikakve šanse.
Kada posle nekoliko dana ujutro ispod svakog balkona bude samo po jedan mladić, devojke uzimaju te mladiće i tako se formiraju parovi. Tako formirani parovi biće stabilni u skladu sa našom definicijom stabilnosti. Tu je i kraj našeg algoritma. Algoritam sadrži sve tri vrste koraka: sekvencu, selekciju i repeticiju.

...
...

Tagovi:

 
Interesantno
pozitivni glasovi: 3  |  negativni glasovi: 0

Napiši komentar:

 

Korisnik
offline
offline LoST-DReaMeR (29)
Srbija, Južnobački okrug, Novi Sad



Arhiva unosa