Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Revista PROGRAMAR

  • artigos
    181
  • comentários
    0
  • visualizações
    129460

Autores deste blog

  • staff 133
  • jpaulino 17
  • anolsi 16
  • apocsantos 6
  • Rui Carlos 4
  • Hipnoted 2
  • HecKel 1
  • pedrotuga 1
  • _JR_ 1

O problema do casamento estável utilizando o algoritmo Gale-Shapley

staff

411 visualizações

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…

The post O problema do casamento estável utilizando o algoritmo Gale-Shapley appeared first on Revista PROGRAMAR.



×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.