O que é o problema do casamento estável?

É o problema de emparelhar membros de dois grupos de mesmo tamanho, cada um com preferências classificadas sobre o outro grupo, de forma que não haja duas pessoas que não estejam correspondidas entre si e que ambas prefeririam estar — uma correspondência 'estável' sem incentivo para desertar.

Como funciona o algoritmo de Gale-Shapley?

Proponentes não correspondidos propõem repetidamente ao seu revisor mais preferido que ainda não tentaram; cada revisor mantém a melhor oferta recebida até o momento e rejeita as piores, até descartando uma correspondência anterior se um proponente melhor aparecer, até que todos os proponentes estejam correspondidos.

Uma correspondência estável sempre existe?

Sim — o algoritmo de Gale-Shapley é uma prova construtiva de que uma correspondência estável sempre existe para qualquer conjunto de listas de preferências completas, não importa como as preferências estejam organizadas.

O que significa 'ótimo para o proponente'?

Significa que cada proponente termina com o melhor parceiro possível que poderia obter em qualquer correspondência estável — a contrapartida é que os revisores, simetricamente, obtêm seu pior resultado entre todas as correspondências estáveis em comparação com executar o algoritmo com os papéis invertidos.

As listas de preferências precisam classificar todos?

Sim — esta calculadora exige que a lista de preferências de cada participante seja uma classificação completa de cada membro do grupo oposto sem repetições, correspondendo à formulação clássica do problema.

A correspondência estável é única?

Não necessariamente — diferentes correspondências estáveis válidas podem existir para as mesmas preferências; Gale-Shapley encontra especificamente a ótima para o proponente, não uma correspondência estável arbitrária entre possivelmente várias.

Quantos participantes esta calculadora pode processar?

Esta calculadora suporta até 15 participantes por lado, mantendo o algoritmo e a validação de listas de preferências instantâneos enquanto cobre exemplos típicos inseridos manualmente.

Onde o problema do casamento estável é usado na vida real?

O mesmo algoritmo (e sua variante de muitos para um) é usado para emparelhar residentes médicos com hospitais (o Programa Nacional de Correspondência de Residentes), estudantes com escolas, e em algumas plataformas de troca de rins e correspondência de empregos.

Solucionador do Problema do Casamento Estável — Encontre uma Correspondência Estável Entre Dois Grupos

Nosso Solucionador do Problema do Casamento Estável encontra uma correspondência entre dois grupos de mesmo tamanho — proponentes e revisores — de forma que nenhum par preferiria estar junto em vez de com sua parceria atribuída, usando o algoritmo de aceitação adiada de Gale-Shapley, dada a lista de preferências classificada de cada participante sobre o outro grupo.

Resposta rápida

Insira listas de preferências classificadas para dois grupos de mesmo tamanho para encontrar instantaneamente uma correspondência estável via o algoritmo de Gale-Shapley.

Preferências dos proponentes

Uma linha por proponente: Nome: pref1, pref2, ... classificando cada revisor, ex. A1: B2, B1, B3.

Preferências dos revisores

Uma linha por revisor: Nome: pref1, pref2, ... classificando cada proponente, ex. B1: A3, A1, A2.

Como usar Solucionador do Problema do Casamento Estável — Algoritmo de Gale-Shapley Online

1
Insira as preferências de cada proponente como uma linha: Nome: pref1, pref2, pref3, ... (classificadas da mais para a menos preferida).
2
Insira as preferências de cada revisor da mesma forma, classificando cada proponente.
3
Clique em 'Calcular' para encontrar uma correspondência estável via o algoritmo de Gale-Shapley.

Por que usar Solucionador do Problema do Casamento Estável — Algoritmo de Gale-Shapley Online?

Uma correspondência entre dois grupos é 'estável' se não houver nenhum par que preferiria estar emparelhado um com o outro em vez de com seus parceiros atribuídos atuais — tal par teria um incentivo para romper suas correspondências existentes, tornando o emparelhamento instável. O algoritmo de Gale-Shapley sempre encontra uma correspondência estável (um resultado fundamental que rendeu o Prêmio Nobel de Economia de 2012): cada proponente não correspondido propõe à sua melhor escolha restante, cada revisor aceita provisoriamente sua melhor oferta até o momento e rejeita o resto (até substituindo uma correspondência anterior se chegar uma oferta melhor), e isso se repete até que todos estejam correspondidos. O resultado não é apenas estável, mas ótimo para o proponente — cada proponente obtém o melhor parceiro possível que poderia ter em qualquer correspondência estável.

Perguntas frequentes

Ferramentas relacionadas

Calculadora de Fluxo de Rede — Fluxo Máximo via Edmonds-Karp Online

Encontre o fluxo máximo de uma origem a um destino em um grafo direcionado com capacidades usando o algoritmo de Edmonds-Karp. Calculadora gratuita com uma lista de arestas simples.

Calculadora de Coloração de Grafos — Algoritmo de Welsh-Powell Online

Colora os vértices de um grafo de modo que nenhum dois nós conectados compartilhem uma cor, usando o algoritmo guloso de Welsh-Powell. Calculadora gratuita com uma entrada simples de lista de arestas.

Calculadora de Permutação — Calcule P(n,r) Online

Calcule permutações P(n,r) — o número de formas de organizar r itens de um total de n onde a ordem importa. Calculadora gratuita com soluções passo a passo e explicação da fórmula.