本文主要是介绍稳定婚姻问题，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

稳定婚姻问题指的是一定数量的男士按照自己的喜好程度对相同数量的女士进行排序，然后进行配对形成稳定婚姻关系。这种配对关系对双方都是比较满意的。

一、基本概念

为了介绍稳定婚姻问题中的“稳定”的意思，我们先介绍一下什么是“不稳定”：在当前所有匹配中存在A男士和B女士，他们没有配对，但是比起当前的伴侣，他们更加喜欢对方。不存在这种情况的配对就是稳定婚姻。稳定婚姻问题就是要根据给定的男士和女士的优先选择，求出一个稳定的婚姻匹配。

例如，男士有小王、小李、小赵，女士有翠花、舒敏、月儿，下面是他们各自对异性的喜好排序情况，求出一个稳定婚姻匹配。

二 、使用方法及步骤

步骤一：从自由男士中选择一个，向他的优先列表中的没有拒绝过他且优先权最高的女士求婚，如果该女士未配对，则接受，如果该女士已配对，则女士比较该自由男士和当前与她配对的男士的优先权，选择优先权高的男士；

步骤二：继续下一次配对。

三 、伪代码

Initialize all men and women to free
while there exist a free man m who still has a woman w to propose to 
{
    w = m's highest ranked such woman to whom he has not yet proposed
    if w is free
       (m, w) become engaged
    else some pair (m', w) already exists
       if w prefers m to m'
          (m, w) become engaged
           m' becomes free
       else
          (m', w) remain engaged    
}

翻译伪代码
假设m代表男人，w代表女人
1、初始化假设所有男女都未配对
2、当有一位男生未配对同时有一位女士未被追求（或者说未被提出配对要求）
执行循环
{
w=男人首先选择心目中的最佳人选（女人），同时这位女士未被追求（或者说未被提出配对要求）
如果这个女士暂未配对
那么使(m，w)配对
否则 已经存在配对（m’,w），通俗地讲就是人家有男朋友了
如果 这个女士更喜欢m，而不是m’，
那么（m，w）就重新配对，
m’就自由了，也就是陪抛弃了
否则 （m’,w）任然配对
}
下面用代码实现下

# Python3 program for stable marriage problem

# Number of Men or Women
N = 4

# This function returns true if
# woman 'w' prefers man 'm1' over man 'm'
def wPrefersM1OverM(prefer, w, m, m1):
	
	# Check if w prefers m over her
	# current engagment m1
	for i in range(N):
		
		# If m1 comes before m in lisr of w,
		# then w prefers her current engagement,
		# don't do anything
		if (prefer[w][i] == m1):
			return True

		# If m cmes before m1 in w's list,
		# then free her current engagement
		# and engage her with m
		if (prefer[w][i] == m):
			return False

# Prints stable matching for N boys and N girls.
# Boys are numbered as 0 to N-1.
# Girls are numbereed as N to 2N-1.
def stableMarriage(prefer):
	
	# Stores partner of women. This is our output
	# array that stores paing information.
	# The value of wPartner[i] indicates the partner
	# assigned to woman N+i. Note that the woman numbers
	# between N and 2*N-1. The value -1 indicates
	# that (N+i)'th woman is free
	wPartner = [-1 for i in range(N)]

	# An array to store availability of men.
	# If mFree[i] is false, then man 'i' is free,
	# otherwise engaged.
	mFree = [False for i in range(N)]

	freeCount = N

	# While there are free men
	while (freeCount > 0):
		
		# Pick the first free man (we could pick any)
		m = 0
		while (m < N):
			if (mFree[m] == False):
				break
			m += 1

		# One by one go to all women according to
		# m's preferences. Here m is the picked free man
		i = 0
		while i < N and mFree[m] == False:
			w = prefer[m][i]

			# The woman of preference is free,
			# w and m become partners (Note that
			# the partnership maybe changed later).
			# So we can say they are engaged not married
			if (wPartner[w - N] == -1):
				wPartner[w - N] = m
				mFree[m] = True
				freeCount -= 1

			else:
				
				# If w is not free
				# Find current engagement of w
				m1 = wPartner[w - N]

				# If w prefers m over her current engagement m1,
				# then break the engagement between w and m1 and
				# engage m with w.
				if (wPrefersM1OverM(prefer, w, m, m1) == False):
					wPartner[w - N] = m
					mFree[m] = True
					mFree[m1] = False
			i += 1

			# End of Else
		# End of the for loop that goes
		# to all women in m's list
	# End of main while loop

	# Prthe solution
	print("Woman ", " Man")
	for i in range(N):
		print(i + N, "\t", wPartner[i])

# Driver Code
prefer = [[7, 5, 6, 4], [5, 4, 6, 7],
		[4, 5, 6, 7], [4, 5, 6, 7],
		[0, 1, 2, 3], [0, 1, 2, 3],
		[0, 1, 2, 3], [0, 1, 2, 3]]

stableMarriage(prefer)

# This code is contributed by Mohit Kumar

参考文献
1、稳定婚姻问题
2、Stable Marriage Problem

这篇关于稳定婚姻问题的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！