|
Figure 10-1. A bipartite graph with a (non-maximal) matching (heavy edges) and an augmenting path from b to f
(highlighted)
1
If you allow them to specify a degree of preference, this turns into the more general min-cost bipartite matching, or the assignment
problem. Although a highly useful problem, it’s a bit harder to solve—I’ll get to that later.
We can continue to use the metaphor from the stable marriage problem—we’ll just drop the stability and try
to get everyone matched with someone they can accept. To visualize what’s going on, let’s say each man has an
engagement ring. What we want is then to have each man give his ring to one of the women so that no woman has
more than one ring. Or, if that’s not possible, we want to move as many rings as possible from the men to the women,
still prohibiting any woman from keeping more than one. As always, to solve this, we start looking for some form of
reduction or inductive step. An obvious idea would be to somehow identify a pair of lovers destined to be together,
thereby reducing the number of pairs we need to worry about. However, it’s not so easy to guarantee that any single
pair is part of a maximum matching, unless, for example, it’s totally isolated, like d and h in Figure
10-1
.
An approach that fits better in this case is iterative improvement, as discussed in Chapter 4. This is closely related
to the use of relaxation in Chapter 9, in that we’ll improve our solution step by step, until we can’t improve it anymore.
We also have to make sure that the only reason the improvement stops is that the solution is optimal—but I’ll get back
to that. Let’s start by finding some step by step improvement scheme. Let’s say that in each round we try to move one
additional ring from the men to the women. If we’re lucky, this would give us the solution straightaway—that is, if
each man gives the ring to the woman he’d be matched to in the best solution. We can’t let any romantic tendencies
cloud our vision here, though. Chances are this approach won’t work quite that smoothly. Consider, once again, the
ChApTeR 10
■
MATChINgs, CuTs, ANd Flows
211
graph in Figure
10-1
. Let’s say that in our first two iterations, a gives a ring to e, and c gives one to g. This gives us a
tentative matching consisting of two pairs (indicated by the heavy black edges). Now we turn to b. What is he to do?
Let’s follow a strategy somewhat similar to the Gale-Shapley algorithm mentioned in Chapter 7, where the
women can change their minds when approached by a new suitor. In fact, let’s mandate that they always do. So when
b asks g, she returns her current ring to c, accepting the one from b. In other words, she cancels her engagement to
c. (This idea of canceling is crucial to all the algorithms in this chapter.) But now c is single, and if we are to ensure that
the iteration does indeed lead to improvement, we can’t accept this new situation. We immediately look around for
a new mate for c, in this case e. But if c passes his returned ring to e, she has to cancel her engagement to a, returning
his ring. He in turn passes this on to f, and we’re done. After this single zigzag swapping session, rings have been
passed back and forth along the highlighted edges. Also, we now have increased the number of couples from two to
three (a + f, b + g, and c + e).
We can, in fact, extract a general method from this ad hoc procedure. First, we need to find one unmatched man.
(If we can’t, we’re done.) We then need to find some alternating sequence of engagements and cancellations so that
we end with an engagement. If we can find that, we know that there must have been one more engagement than there
were cancellations, increasing the number of pairs by one. We just keep finding such zigzags for as long as we can.
The zigzags we’re looking for are paths that go from an unmatched node on the left side to an unmatched node
on the right side. Following the logic of the engagement rings, we see that the path can only move to the right across an
edge that is not already in the matching (a proposal), and it can only move left across one that is in the matching
(a cancellation). Such a path (like the one highlighted in Figure
10-1
) is called an augmenting path, because it augments
our solution (that is, it increments the engagement count), and we can find augmenting paths by traversal. We just need
to be sure we follow the rules—we can’t follow matched edges to the right or unmatched edges to the left.
What’s left is ensuring that we can indeed find such augmenting paths as long as there is room for improvement.
Although this seems plausible enough, it’s not immediately obvious why it must be so. What we want to show is that
if there is room for improvement, we can find an augmenting path. That means that we have a current match M and
that there is some greater matching M’ that we haven’t found yet. Now consider the edges in the symmetric difference
between these two—that is, the edges that are in either one but not in both. Let’s call the edges in M red and the ones
in M’ green.
This jumble of red and green edges would actually have some useful structure. For example, we know that each
node would be incident to at most two edges, one of each color (because it couldn’t have two edges from the same
matching). This means that we’d have one or more connected components, each of which was a zigzagging path or
cycle of alternating color. Because M’ is bigger than M, we must have at least one component with more green than
red edges, and the only way that could happen would be in a path—an odd-length one that started and ended with
a green edge.
Do you see it yet? Exactly! This green-red-…-green path would be an augmenting path. It has odd length, so one
end would be on the male side and one on the female. And the first and last edges were green, meaning they were not
part of our original matching, so we’re free to start augmenting. (This is essentially my take on what’s known as Berge’s
lemma.)
When it comes to implementing this strategy, there is a lot of room for creativity. One possible implementation
is shown in Listing 10-1. The code for the tr function can be found in Listing 5-10. The parameters X and Y are
collections (iterable objects) of nodes, representing the bipartition of the graph G. The running time might not be
obvious, because edges are switched on and off during execution, but we do know that one pair is added to the
matching in each iteration, so the number of iterations is O(n), for n nodes. Assuming m edges, the search for an
augmenting path is basically a traversal of a connected component, which is O(m). In total, then, the running time
is O(nm).
ChApTeR 10
■
MATChINgs, CuTs, ANd Flows
212
Do'stlaringiz bilan baham: |
