Задача об устойчивых браках на Prolog'е

  • 07 мая 2014 г.
  • 563 Слова
Предположим, что N мужчин и N женщин желают вступить в брак. Каждый мужчина имеет список всех женщин, упорядоченных по его вкусу. Подобный список, но конечно мужчин, есть у каждой женщины. Задачасостоит в нахождении множества устойчивых браков.
Множество браков неустойчиво, если 2 человека не состоящие в браке, хотят образовать такой союз. Предположим, что например существует двое мужчин (A и B) идве женщины (X и Y), такие что A предпочитает X, а B предпочитает Y, X предпочитает A, Y предпочитает B. Пара браков A-Y, B-X - неустойчива, т.к. A предпочитает X, а не Y, в то время как X отдаетпредпочтение A, а не B.
Программа должна в качестве входных данных иметь списки предпочтений, а результатом ее выполнения должно быть устойчивое множество браков, т.е. множество браков не являющихсянеустойчивыми.
В теории графов есть теорема, в которой утверждается, что это всегда возможно.
Проверить задачу на множестве из 5 мужчин и 5 женщин.
авраам: хана, тамар, звия, руфь, сара
беньямин: звия, руфь, хана, сара,тамар
хайм: хана, руфь, тамар, сара, звия
давид: звия, руфь, хана, сара, тамар
елеазар: тамар, руфь, хана, звия, сара
звия: елеазар, авраам, давид, беньямин, хайм
хана: давид, элеазар, беньямин,авраам хайм
руфь: авраам, давид, беньямин, хайм, элеазар
сара: хайм, беньямин, давид, авраам, элеазар
тамар: давид, беньямин, хайм, элеазар, авраам

Программа работает по принципу генерации всехперестановок, т.е. для каждой перестановки выводятся все устойчивые браки. То есть для трёх мужчин и женщин выводится решение с тремя устойчивыми браками (максимальное), а затем решения с однимустойчивым браком.
Приоритеты я считала немного по-другому. Лучший приоритет - 1.

findall(X, imore(AP,X,IAB),LX) - собираем в список LX всех женщин X, которых A любит больше чем жену B
check(A,LX, Pairs) -проверяем, что ни одна из этих женщин не любит A больше, чем собственного мужа.
Если эта проверка выполнилась, то брак устойчивый.

Программа:
domains
list=symbol*...
tracking img