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.

Ler mais…