Итак, мой вопрос относится к тому, что именно является «стабильным соответствием»? Я знаю о проблеме «Стабильный брак», и все решения, похоже, указывают на то, что вы заканчиваете «Стабильное соответствие». Но я не уверен, что это на самом деле означает.Что такое стабильное соответствие?
Я бы уставился на .gif из вики, потому что на самом деле это отличное объяснение механики.
В стабильной соответствия мы гарантируем, что все элементы из двух наборов (мужчины & женщины, дети & игрушки, человек & отдых места, что угодно) ставятся в паре с элементом из другого набора и эта пара является «лучшим доступное совпадение «
Способ определения того, что является« наилучшим доступным совпадением », представляет собой то, что каждый элемент набора оценивает их предпочтение для элементов противоположного множества. Цель состоит в том, чтобы удовлетворить предпочтения каждого. Придерживаясь проблемы брака, представьте себе, что у каждого человека есть список женщин, и у каждой женщины есть список мужчин. Цель состоит в том, чтобы согласовать их вместе, чтобы каждый мог получить наивысшего человека в своем списке.
Помните, что для этого требуется несколько шагов (или раундов). В примере с браком еще одна вещь, о которой следует помнить, состоит в том, что каждая сторона может делать только одно. Поэтому в нашем примере женщины принимают, предлагают мужчины. Кроме того, это предложение не является обязательным. Это означает, что если в первом раунде женщина получает предложение от своего лучшего мужчину 2, и в следующем раунде она получает предложение от своего №1, она может отклонить №2 и принять №1. Вики сказали, что это лучше, чем я мог ...
По завершении алгоритма Алиса и Боб не могут предпочесть друг другу своих партнеров. Если Боб предпочитает Алису своему нынешнему партнеру, он, должно быть, предложил Алисе, прежде чем он предложил своему нынешнему партнеру. Если Алиса приняла его предложение, но в конце концов не была замужем за ним, она, должно быть, бросила его для кого-то, кому она больше нравится, и поэтому не любит Боб больше, чем ее нынешнего партнера. Если Алиса отвергла его предложение, она уже была с кем-то, кому она больше нравилась Бобу.
В принципе, никто не получает вал в браке, потому что пара была наивысшим предпочтением друг другу, учитывая ограниченные возможности.
Спасибо, я думаю, вы очистили предметы, на которых я был смущен! –
+1 для «никто не получает вал». Это суммирует стабильное соответствие. – glh
В каком контексте? – Femaref
это помогает? http://en.wikipedia.org/wiki/Stable_marriage_problem –
Вы запрашиваете объяснение неспециалиста по ссылке wiki выше? – tyh