《算法设计》一书的有关问题，解决马上给分
《算法设计》一书的问题，解决马上给分！
All Executions Yield the Same Matching There are a number of possible
ways to prove a statement such as this, many of which would result in quite
complicated arguments. It turns out that the easiest and most informative approach
for us will be to uniquely characterize the matching that is obtained and
then show that all executions result in the matching with this characterization.
What is the characterization? We’ll show that each man ends up with the
"best possible partner" in a concrete sense. (Recall that this is true if all men
prefer different women.) First, we will say that a woman w is a valid partner
of a man m if there is a stable matching that contains the pair (m, w). We will
say that w is the best valid partner of m if w is a valid partner of m, and no
woman whom m ranks higher than w is a valid partner of his. We will use
best(m) to denote the best valid partner of m.
Now, let S* denote the set of pairs {(m, best(m)) : m 属于 M}. We will prove
the following fact.
(1.7) Every execution of the G-S algorithm results in the set S*:
当两男一女的情况这肯定是不可能实现的吧？(只讨论数学问题，不讨论生活问题。)
This statement is surprising at a number of levels. First of all, as defined,
there is no reason to believe that S* is a matching at all, let alone a stable
matching. After all, why couldn’t it happen that two men have the same best
valid partner? Second, the result shows that the G-S algorithm gives the best
possible outcome for every man simultaneously; there is no stable matching
in which any of the men could have hoped to do better. And finally, it answers
our question above by showing that the order of proposals in the G-S algorithm
has absolutely no effect on the final outcome.
Despite all this, the proof is not so difficult.
Proof. Let us suppose, by way of contradiction, that some execution g of the
G-S algorithm results in a matching S in which some man is paired with a
woman who is not his best valid partner. Since men propose in decreasing
order of preference, this means that some man is rejected by a valid partner
during the execution g of the algorithm. So consider the first moment during
the execution g in which some man, say m, is rejected by a valid partner w.
Again, since men propose in decreasing order of preference, and since this is
the first time such a rejection has occurred, it must be that w is m’s best valid
partner best(m).
The reiection of m by w may have happened either because m proposed
and was turned down in favor of w’s existing engagement, or because w broke
her engagement to m in favor of a better proposal. But either way, at this
moment w forms or continues an engagement with a man m’ whom she prefers
to m.
Since w is a valid parmer of m, there exists a stable matching S’ containing
the pair (m, w). Now we ask: Who is m’ paired with in this matching? Suppose
it is a woman w’!= w.
Since the rejection of m by w was the first rejection of a man by a valid
partner in the execution epsilon, it must be that m’ had not been rejected by any valid
parmer at the point in epsilon when he became engaged to w. Since he proposed in
decreasing order of preference, and since w’ is clearly a valid parmer of m’, it
must be that m’ prefers w to w’. But we have already seen that w prefers m’
to m, for in execution epsilon she rejected m in favor of m’. Since (m’, w) 不属于 S’, it
follows that (m’, w) is an instability in S’.
This contradicts our claim that S’ is stable and hence contradicts our initial
assumption.
------解决方案--------------------
lz先把中文敲上吧，看英文虽说能够锻炼我的阅读能力，但蛋疼
------解决方案--------------------
..你问的问题是什么
两男一女的情况肯定实现啊 1，2男，3女，3的排名（1,2),(1,3）是稳定对（2,3)不稳定，所以三s*包括（1,3）
All Executions Yield the Same Matching There are a number of possible
ways to prove a statement such as this, many of which would result in quite
complicated arguments. It turns out that the easiest and most informative approach
for us will be to uniquely characterize the matching that is obtained and
then show that all executions result in the matching with this characterization.
What is the characterization? We’ll show that each man ends up with the
"best possible partner" in a concrete sense. (Recall that this is true if all men
prefer different women.) First, we will say that a woman w is a valid partner
of a man m if there is a stable matching that contains the pair (m, w). We will
say that w is the best valid partner of m if w is a valid partner of m, and no
woman whom m ranks higher than w is a valid partner of his. We will use
best(m) to denote the best valid partner of m.
Now, let S* denote the set of pairs {(m, best(m)) : m 属于 M}. We will prove
the following fact.
(1.7) Every execution of the G-S algorithm results in the set S*:
当两男一女的情况这肯定是不可能实现的吧？(只讨论数学问题，不讨论生活问题。)
This statement is surprising at a number of levels. First of all, as defined,
there is no reason to believe that S* is a matching at all, let alone a stable
matching. After all, why couldn’t it happen that two men have the same best
valid partner? Second, the result shows that the G-S algorithm gives the best
possible outcome for every man simultaneously; there is no stable matching
in which any of the men could have hoped to do better. And finally, it answers
our question above by showing that the order of proposals in the G-S algorithm
has absolutely no effect on the final outcome.
Despite all this, the proof is not so difficult.
Proof. Let us suppose, by way of contradiction, that some execution g of the
G-S algorithm results in a matching S in which some man is paired with a
woman who is not his best valid partner. Since men propose in decreasing
order of preference, this means that some man is rejected by a valid partner
during the execution g of the algorithm. So consider the first moment during
the execution g in which some man, say m, is rejected by a valid partner w.
Again, since men propose in decreasing order of preference, and since this is
the first time such a rejection has occurred, it must be that w is m’s best valid
partner best(m).
The reiection of m by w may have happened either because m proposed
and was turned down in favor of w’s existing engagement, or because w broke
her engagement to m in favor of a better proposal. But either way, at this
moment w forms or continues an engagement with a man m’ whom she prefers
to m.
Since w is a valid parmer of m, there exists a stable matching S’ containing
the pair (m, w). Now we ask: Who is m’ paired with in this matching? Suppose
it is a woman w’!= w.
Since the rejection of m by w was the first rejection of a man by a valid
partner in the execution epsilon, it must be that m’ had not been rejected by any valid
parmer at the point in epsilon when he became engaged to w. Since he proposed in
decreasing order of preference, and since w’ is clearly a valid parmer of m’, it
must be that m’ prefers w to w’. But we have already seen that w prefers m’
to m, for in execution epsilon she rejected m in favor of m’. Since (m’, w) 不属于 S’, it
follows that (m’, w) is an instability in S’.
This contradicts our claim that S’ is stable and hence contradicts our initial
assumption.
------解决方案--------------------
lz先把中文敲上吧，看英文虽说能够锻炼我的阅读能力，但蛋疼
------解决方案--------------------
..你问的问题是什么
两男一女的情况肯定实现啊 1，2男，3女，3的排名（1,2),(1,3）是稳定对（2,3)不稳定，所以三s*包括（1,3）