asked 2014-11-24 11:03:32 +0100
Zdravím, existuje nejaký efektívny spôsob ako overiť, či je nejaké párovanie stabilné? Okrem jednoduchého prípadu, keď je to párovanie výsledkom toho "dvořícího rituálu". Je to totiž v rozstrele, ale nepamätám, že by sme to robili na cviku (aj keď možno som už vtedy nevnímal).
Viz vo vzorovom rozstrele otázku 2.1.
answered 2014-11-24 11:53:19 +0100
To se na cvičení dělat nebude, vše, co je třeba, bylo na přednášce, včetně ukázky běhu algoritmu.
Stabilní párování se pozná buď tak, že ověříte, jestli neobsahuje nestabilní pár, což je pracnější, ale když se to dělá chytře, tak to není taková hrůza. Další možnost je pomocí dvou běhů dvořícího algoritmu (muži na balkóně resp. ženy na balkóně) najít dvě "extrémní" stabilní párování. Pokud jsou shodná, existuje jen jedno stabilní párování a je hotovo. Pokud ne, tak lze využít jejich vlastnosti, že pro ty na balkónech je to to nejhorší možné stabilní párování (tj. v žádném jiném stabilním párování nemají horšího partnera) a pro ty pod balkóny je to naopak to nejlepší (ve stejném smyslu).
Asked: 2014-11-24 11:03:32 +0100
Seen: 604 times
Last updated: Nov 24 '14
Copyright students of FIT CTU and others, 2014. Content on this site is licensed under a Creative Commons Attribution-ShareAlike 4.0 International license.