Psychic Modeling
Projeto e Análise de Algoritmo
Prof. Diane Castonguay
Charles Gomes
Rogério Arantes Gaioso
O que será feito ?
• War Story
• Apresentação do problema
• Alguns conceitos
• A primeira tentativa
• Solução final
• Moral da história
• Referências
War Story
[1]
O que é isso ?????????
Psychic Modeling
Descrição do problema:
A partir de um conjunto de números fornecido pelo jogador,
com garantia que um subconjunto deste contém alguns dos
números vencedores, deseja-se a relação de combinações
possíveis para se obter premiação.
Exemplo Mega Sena:
 Cartela que possui 60 números onde o jogador aposta
6 números, sendo que com 4 números o bilhete ganha
prêmio.
 Jogador informa um subconjunto de 15 números e
garante que quatro deles serão premiados.
 Sistema deve listar as combinações possíveis.
Psychic Modeling

Instância
•
•
•

[1]
Conjunto C = {c1,...,cn}
Subconjunto S = {s1,...,s15}
Subconjunto S’ = {s’1,...,s’4}, sendo S’ ⊆ S
Instância de Set Cover
Classes P, NP e NP-Completo



Classe P
 Problemas que podem ser resolvidos em tempo
polinomial, isto é, O (nk) onde n é o tamanho da
entrada e k é alguma constante
Classe NP
 NP significa “não deterministicamente polinomial”
 Problemas que são verificáveis em tempo polinomial
Classe NP- C
 Um problema é NP - completo se ele é NP e pode ser
reduzido a um outro problema NP - completo
P = NP
Set Cover
•
Instância:
•
•
•
•
[3]
Conjunto E = {e1,...,en}
Subconjunto S = {C1,...,ct}
Função de custo: S -> W
Pergunta
•
Existe uma cobertura de mínima de
conjunto aonde subconjunto S' ⊆ S
Set Cover
[3]
Componentes da solução




[1]
Gerar subconjunto
Definir quais subconjuntos atendem
Uma estrutura de dados necessária
Estratégia de busca
[4]
[6]
[5]
Variáveis
[2]
M = conjunto de números totais existentes
R = quantidade de números por cartela
J = quantidade mínima para acertar e ganhar um prêmio
N = quantidade de números fornecidos pelo adivinho
P = quantidade de números garantidos entre os vencedores
W = quantidade de acertos desejados
J <= P <= R <= N
NC
P
= (N/P!)/(N-P)! combinações possíveis com P números
Primeira tentativa
[1]
• Força bruta
• Resultado final: 28 combinações
Bastavam apenas 5 bilhetes !!!!!!!!
Primeira tentativa (cont.)
[2]
R = 4, J = 2, W = 1, P = 3, N = 5
{1, 2, 4, X }
{1, 2, 3, X }
{1, 2, 5, X }
{1, 3, 5, X }
{1, 3, 4, X }
{1, 4, 5, X }
{2, 3, 5, X }
{2, 3, 4, X }
{2, 4, 5, X }
{3, 4, 5, X }
Primeira tentativa (cont.)
[2]
R = 4, J = 2, W = 1, P = 3, N = 5
{1, 3, 5, X }
{2, 4, 5, X }
Sobreposições
[2]
É possível que entre os subconjuntos possíveis de P números haja
alguns com pelo menos J números diferentes. Quando isso ocorre,
estes subconjuntos se sobrepõem com respeito aos J números, e
apenas um deles deveria ser comprado. Se a diferença entre dois
subconjuntos é maior ou igual a P-J, então eles não se sobrepõem.
NC
P
= (N/P!)/(N-P)! combinações possíveis com P números
2 número total de possível de conjuntos de bilhetes, onde  = NCP
NC
J
subconjuntos possíveis de ocorrer
Complexidade total:
2   N CJ
Segunda tentativa
[2]
• Heurísticas
• Geração Randômica
• Resultados semelhantes ao calculado, com tempo
de execução menor
Comparativo
[2]
R
J
N
P
W
Limite
Inferior
Nº
Bilhetes
Tempo
(seg)
5
5
5
5
6
6
6
6
6
10
4
4
4
5
4
5
6
4
4
6
15
15
15
15
15
15
15
18
18
18
5
5
5
5
5
5
6
5
5
7
1
2
3
1
1
1
1
1
1
1
58
117
176
3003
58
3003
5005
129
129
408
137
218
294
3127
138
3109
5129
330
330
4080
95
147
163
333
145
346
503
432
449
919
Moral da história
[1]
“Tenha certeza que você modelou o problema
corretamente antes de tentar resolvê-lo”.
O sucesso em corrigir o erro foi possível devido à correta
formulação inicial e no uso de rotinas e abstrações bem definidas:
• seleção/eliminação de subconjuntos do resultado final
• a estrutura de dados
• a busca combinatória
[3]
[4]
[5]
Referências
[1] The Algorithm Design Manual, Steven S. Skiena. 1997.
http://www2.toki.or.id/book/AlgDesignManual/
[2] Randomized algorithms for identifying minimal lottery ticket sets
F. Younas, S. Skiena. Journal of Undergraduate Research, 1996.
http://www.cs.sunysb.edu/~skiena/papers/lotto.doc
[3] Set Cover.
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/
NODE201.HTM#setcover
[4] Geração de subconjuntos.
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK4/
NODE152.HTM#generatingsubsets
[5] Estrutura de dados.
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK3/
NODE133.HTM#setdatastructures
[6] Busca combinatória.
http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK2/
NODE92.HTM#simulatedannealing