Algoritmo de Gale-Shapley

O algoritmo de Gale-Shapley resolve o problema do casamento estável: como parear dois grupos (por exemplo, residentes médicos a hospitais, alunos a escolas) de forma que nenhum par prefira um ao outro em vez de seus parceiros designados. Introduzido por David Gale e Lloyd Shapley em 1962, o algoritmo garante um pareamento estável em tempo polinomial através de um processo de aceitação diferida, onde um lado propõe sequencialmente e o outro lado responde, revisando escolhas à medida que chegam opções melhores.