Introdução
O problema do emparelhamento estável (stable marriage problem), é de forma resumida o problema de encontrar um emparelhamento estável entre dois elementos de dois conjuntos de elementos, dada a ordem de preferências de cada elemento do conjunto.
Este problema é normalmente apresentado da seguinte forma: Dados n Reis e n Damas de um conjunto de cartas, cada Rei e cada Dama estabelece uma ordem de preferência para cada um dos elementos “opostos” (reis ou damas), com quem gostaria de estabelecer um “relacionamento”, ou por outras palavras, tomar um café e trocar uns bytes de código! Os pares são estabelecidos de forma a que os pares de elementos opostos prefiram estar “juntos” no par estabelecido, do que estar com qualquer outro elemento. Quando não existirem pares que cumpram estes requisitos o conjunto de pares é considerado estável.
Para que um “par” não seja considerado estável, as seguintes premissas são observáveis:
- Um dado elemento A do primeiro conjunto de pares, prefere um elemento B do segundo conjunto de pares, ao elemento com que se encontra emparelhado, e
- O elemento B também prefere A, ao elemento ao qual B se encontra emparelhado.
[...]