Um problema difícil de resolver e que já tomou algumas horas de sono dos computeiros, inclusive minha nessa semana, é o problema da loteria.
A ideia (nova regra diz que não tem acento, certo?!) é selecionar dentre tickets de jogos possíveis, quais, em quantidade mínima, deve-se jogar para se ganhar na loteria. Infelizmente, você não irá ficar rico dessa vez, pois é muito difícil criar um algoritmo que ache um resultado ótimo, além de que, geralmente, esse resultado ultrapassa e muito o valor que você poderia ganhar, jogando.
O problema é descrito assim: dado um conjunto T de tamanho n, qual é o subconjunto mínimo de tickets de T, onde cada ticket possui tamanho k, e garante cobrir p números no resultado final.
Exemplificando, se n = 5, k = 3 e p = 2, temos as seguintes possíveis combinações:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Sendo que uma solução seria: (1, 2, 3) e (3, 4, 5), dois conjuntos distintos que garantem a vitória, para um jogo nessa configuração. Mas de que forma eles garantem, você pode estar se perguntando? Bom, precisamos acertar dois números, no mínimo, então:
1 2 3 (X)
1 2 4 - (a seleção já possui 1 e 2)
1 2 5 - (a seleção já possui 1 e 2)
1 3 4 - (a seleção já possui 1 e 3)
1 3 5 - (a seleção já possui 1 e 3)
1 4 5 - (a seleção (de baixo) possui 4 e 5)
2 3 4 - (a seleção possui 3 e 4)
2 3 5 - (a seleção possui 2 e 3)
2 4 5 - (a seleção possui 4 e 5)
3 4 5 (X)
"Ahhh, legal, vou jogar!" heheh... cuidado! Para adaptar o problema para obter uma solução da mega-sena, teríamos: n = 60, k = 6, p = 4 (quadra).
Se combinarmos todas as possibilidades de agrupamentos de 60 números em 6 casas, teríamos a pequena quantia de 50.063.860 tickets possíveis. Ok, pode ser até fácil de gerar utilizando dos computadores atuais, mas para calcular a quantidade mínima de tickets é outra coisa...
Existem vários algoritmos, mas não lembro de nenhum ótimo no momento. Por acaso, eu inventei um olhando os resultados, coisa besta, nem sempre ótima, mas funciona. Chamei ele de BlockBreaker, então se esse algoritmo realmente existe peço desculpas pela frase, mas eu não o conhecia.
Assimindo que todos os tickets são um bloco, temos o bloco massisso, com 3 colunas de números:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Seguimos na primeira coluna de cima pra baixo, até que o valor muda com relação ao ticket anterior, quando isso acontecer quebramos o bloco:
Bloco gerado 1 - coluna 1:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
Analisamos o bloco recém criado da seguinte forma: se o bloco possui tamanho 1 e não conflita em pelo menos de p unidades com os já selecionados, selecionados o ticket do bloco (marcando X). Nesse caso, não temos nada nessas condições, seguimos adiante:
Bloco gerado 2 - coluna 1:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5
O bloco recém criado não possui, mas o último bloco possui tamanho 1, como não temos nenhum marcado ainda, marcamos ele e seguimos da mesma forma na segunda coluna.
Bloco gerado 1 - coluna 2:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5 (X)
Bloco gerado 2 - coluna 2:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5 - (conflita em 2 números, 2 >= p)
2 3 4
2 3 5
2 4 5
3 4 5 (X)
Bloco gerado 3 - coluna 2:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5 -
2 3 4
2 3 5
2 4 5 -
3 4 5 (X)
Bloco gerado 4 - coluna 2:
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5 -
2 3 4
2 3 5
2 4 5 -
3 4 5 (X)
Seguimos para a última coluna:
Bloco gerado 1 - coluna 3:
1 2 3 (X)
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5 -
2 3 4
2 3 5
2 4 5 -
3 4 5 (X)
Até que no final temos:
1 2 3 (X)
1 2 4 -
1 2 5 -
1 3 4 -
1 3 5 -
1 4 5 -
2 3 4 -
2 3 5 -
2 4 5 -
3 4 5 (X)
O algoritmo é besta e bem fácil de entender, implementar tb, e achou a solução ótima para essa situação, mas infelizmente não garante sempre a solução ótima.
Outro detalhe interessante é com relação a geração dos números dos tickets, se você conhece o algoritmo de enumeração por ordem lexicográfica, vai ver que o conjunto de todos os tickets é dado pela geração de todos os subconjuntos de tamanho k, dentre os subconjuntos possíveis de n. Olhem só:
1
12
123 (1)
1234
12345
1235
124 (2)
1245
125 (3)
13
134 (4)
1345
135 (5)
14
145 (6)
15
2
23
234 (7)
2345
235 (8)
24
245 (9)
25
3
34
345 (10)
35
4
45
5
Exatamente os 10 tickets possíveis, ;) !! Lógico que essa é a ordem original, que poderia ser melhorada afim de gerar somente os tickets que você quer, mas tá ai a dica!
Vou postar o programa com os algoritmos que fizemos essa semana para quem quiser... Criei a conta no github, mas só posso colocar os arquivos mais tarde, visto que tem um bloqueio besta aqui na faculdade até para portas do git.
0 comentários:
Postar um comentário