| dbo:abstract
|
- In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David Gale and Lloyd Shapley who had described it as solving both the college admission problem and the stable marriage problem.It takes polynomial time, and the time is linear in the size of the input to the algorithm. It is a truthful mechanism from the point of view of the proposing participants, for whom the solution will always be optimal. (en)
- L'algorithme de Gale et Shapley est un algorithme qui résout le problème des mariages stables. (fr)
- Algorytm odroczonej akceptacji (inaczej zwany algorytmem Gale’a-Shapleya) jest algorytmem, którego celem jest znalezienie rozwiązania dla problemu trwałego małżeństwa. Algorytm ten prowadzi do utworzenia stabilnych par. W zależności od sposobu użycia algorytm pozwala on znaleźć optymalne rozwiązania dla jednej z dwóch grup uczestników. W 1962 roku David Gale i Lloyd Shapley udowodnili, że dla dowolnej, ale takiej samej liczby mężczyzn i kobiet jest zawsze możliwe znalezienie takiego rozwiązania dla problemu trwałego małżeństwa, aby sprawić, że wszystkie małżeństwa będą trwałe, stabilne. Algorytm w sposób uproszczony został przedstawiony poniżej: 1. Każdy z mężczyzn prosi o rękę tę kobietę, którą preferuje względem innych. 2. Każda kobieta notuje otrzymane propozycje w swoim karnecie. 3. W momencie, gdy każdy mężczyzna złożył propozycje swoim faworytkom, wszystkie kobiety odmawiają wszystkim mężczyznom, od których dostały propozycję, poza jednym, którego preferują ponad innych (nie jest to jednak jeszcze równoznaczne z akceptacją przez kobietę tego preferowanego mężczyzny – chyba że jest to także zalotnik najwyżej w jej rankingu wszystkich potencjalnych kandydatów). 4. Niewybrani mężczyźni oświadczają się następnej kobiecie w ich rankingu. 5. Powrót do punktu numer 2 lub koniec algorytmu, jeżeli każda kobieta odnalazła swojego preferowanego, przyszłego męża. Algorytm zawsze prowadzi do powstania stabilnych par. Aby to udowodnić załóżmy, że – przeciwnie do stwierdzenia zawartego w poprzednim zdaniu – jeden mężczyzna, preferuje inną kobietę względem swojej obecnej partnerki. W takim przypadku oświadczył się jej przed poproszeniem o rękę swojej obecnej narzeczonej. Jednakże gdyby ta kobieta również preferowałaby go względem swojego obecnego partnera, to nie przyjęłaby wcześniej oświadczyn swojego obecnego narzeczonego. Wynikiem algorytmu odroczonej akceptacji są zawsze najlepsze możliwe stabilne pary z punktu widzenia mężczyzn. Oznacza to, że żaden mężczyzna nie zmieniłby swojej pary względem jakiegokolwiek innego stabilnego dopasowania. Odwrócenie ról mężczyzn i kobiet doprowadziłoby do powstania stabilnego dopasowania, które byłoby preferowane przez kobiety. Algorytm zapewnia, że:
* Każdy weźmie ślub Ostatecznie nie może zaistnieć taka sytuacja, że zarówno mężczyzna, jak i kobieta nie są zaręczeni, ponieważ w pewnym momencie ten mężczyzna musiał się oświadczyć tej kobiecie (ostatecznie mężczyzna musiał się oświadczyć każdej kobiecie, jeśli było to konieczne), więc ostatecznie musiała ona przyjąć jego oświadczyny.
* Małżeństwo będzie trwałe Niech kobieta A i mężczyzna B będą zaręczeni, ale nie ze sobą nawzajem. Od zakończenia algorytmu nie jest możliwe, żeby A i B preferowali siebie nawzajem względem swoich obecnych partnerów. Jeśli B wolałby A względem swojej aktualnej partnerki, to musiałby oświadczyć się A przed poproszeniem o rękę swojej obecnej partnerki. Jeśli A przyjęła jego oświadczyny, a ostatecznie nie jest z nim zaręczona, to musiała z nim zerwać na rzecz kogoś, kogo woli, a tym samym preferuje swojego obecnego partnera od mężczyzny B. Jeśli A odrzuciła oświadczyny B, to znaczy, że już była zaręczona z kimś, kogo woli od B. Algorytm ma zastosowanie w rekrutacji do szkół w Nowym Jorku oraz Bostonie, przy przydziale stażystów do szpitali w USA, a nawet do kojarzenia dawców organów z biorcami przeszczepów. (pl)
- Алгоритм Гэйла — Шепли находит стабильное паросочетание.Время выполнения линейно зависит от размера входных данных алгоритма.В зависимости от того, как он используется, он может найти либо решение, оптимальное для участников с одной стороны сопоставления, либо для участников с другой стороны.Алгоритм обеспечивает честный механизм с точки зрения участников, поэтому предоставление участником неверных данных может только ухудшить его результат. Алгоритм назван в честь Дэвида Гэйла и Ллойда Шепли. (ru)
|
| rdfs:comment
|
- In mathematics, economics, and computer science, the Gale–Shapley algorithm (also known as the deferred acceptance algorithm or propose-and-reject algorithm) is an algorithm for finding a solution to the stable matching problem, named for David Gale and Lloyd Shapley who had described it as solving both the college admission problem and the stable marriage problem.It takes polynomial time, and the time is linear in the size of the input to the algorithm. It is a truthful mechanism from the point of view of the proposing participants, for whom the solution will always be optimal. (en)
- L'algorithme de Gale et Shapley est un algorithme qui résout le problème des mariages stables. (fr)
- Алгоритм Гэйла — Шепли находит стабильное паросочетание.Время выполнения линейно зависит от размера входных данных алгоритма.В зависимости от того, как он используется, он может найти либо решение, оптимальное для участников с одной стороны сопоставления, либо для участников с другой стороны.Алгоритм обеспечивает честный механизм с точки зрения участников, поэтому предоставление участником неверных данных может только ухудшить его результат. Алгоритм назван в честь Дэвида Гэйла и Ллойда Шепли. (ru)
- Algorytm odroczonej akceptacji (inaczej zwany algorytmem Gale’a-Shapleya) jest algorytmem, którego celem jest znalezienie rozwiązania dla problemu trwałego małżeństwa. Algorytm ten prowadzi do utworzenia stabilnych par. W zależności od sposobu użycia algorytm pozwala on znaleźć optymalne rozwiązania dla jednej z dwóch grup uczestników. W 1962 roku David Gale i Lloyd Shapley udowodnili, że dla dowolnej, ale takiej samej liczby mężczyzn i kobiet jest zawsze możliwe znalezienie takiego rozwiązania dla problemu trwałego małżeństwa, aby sprawić, że wszystkie małżeństwa będą trwałe, stabilne. (pl)
|
