1. Aleatório
Como o aluno_1.py da monitoria: sorteia um vértice livre. Serve de base de comparação.
função ALEATÓRIO(grafo)
livres ← { v : time(v) = 0 }
devolva um vértice de livres sorteadoProjeto da disciplina · demonstração
Jogo de Voronoi em grafos
Esta página serve para treinar para a competição do projeto. Você escolhe um grafo e duas estratégias, ou joga você mesmo, e acompanha cada lance com a explicação de quem ficou com cada vértice e por quê.
- Cada equipe escolhe 3 centros
As duas equipes, a vermelha e a preta, se alternam. Em cada lance, a equipe da vez escolhe um vértice livre, que vira um centro seu.
- O centro mais próximo leva o vértice
A distância é o número de arestas do menor caminho. Se as duas equipes têm centros à mesma distância, o peso do vértice se divide ao meio.
- Ganha quem somar mais peso
Depois do 6º lance, cada equipe soma os pesos dos seus vértices. O confronto tem duas partidas, e cada equipe começa uma delas.
Estas são as regras da documentação do projeto, escrita pela monitoria. Se houver diferença, vale a documentação.
Jogar
Escolha o grafo
Deslize para o lado para ver os 13 grafos.
Escolha quem joga
Para jogar, escolha “Você” numa equipe; escolha nas duas para disputar com um colega no mesmo computador.
Assista ou jogue
Equipe vermelha0
Equipe preta0
Passe o mouse ou toque num vértice para ver a que distância ele está do centro mais próximo de cada equipe.
- Da equipe vermelha
- Da equipe preta
- Empate: o peso se divide
- Ainda sem dono
- Centro (anel)
- Peso
Quer comparar todas as estratégias no grafo escolhido de uma vez?
Todos contra todos
Torneio
Cinco estratégias
Como cada estratégia escolhe
São as estratégias que você escolhe no passo 2. Leia o pseudocódigo, aperte “Testar no tabuleiro” e acompanhe, lance a lance, por que ela escolheu cada vértice. Em todas, time(v) vale 0 para vértice livre, 1 para centro próprio e 2 para centro do adversário, como na documentação, e d(u, v) é o número de arestas do menor caminho; empates ficam com o vértice de maior peso e, persistindo, com o primeiro em ordem alfabética.
2. Maior peso
Como o aluno_2.py: pega o vértice livre mais pesado e ignora onde ele está no grafo.
função MAIOR_PESO(grafo)
livres ← { v : time(v) = 0 }
devolva o v de livres com maior peso(v)3. Ganho imediato
Testa cada vértice livre e fica com o que dá mais pontos logo depois do lance, contando a posição dos centros já colocados.
função GANHO_IMEDIATO(grafo)
meus ← { c : time(c) = 1 }
deles ← { c : time(c) = 2 }
para cada v com time(v) = 0
ganho(v) ← PONTOS(meus ∪ {v}, deles)
devolva o v de maior ganho(v)
função PONTOS(meus, deles)
total ← 0
para cada vértice u
a ← min { d(c, u) : c ∈ meus }
b ← min { d(c, u) : c ∈ deles }
se a < b então total ← total + peso(u)
senão se a = b < ∞ então
total ← total + peso(u)/2
devolva total
▹ o mínimo de um conjunto vazio é ∞4. Mediana ponderada
Procura o vértice livre mais perto, em média, de todo o peso do grafo: a mediana do grafo. Não olha o adversário.
função MEDIANA(grafo)
para cada v com time(v) = 0
custo(v) ← Σ peso(u) · d(v, u)
▹ soma sobre todos os vértices u
devolva o v de menor custo(v)5. Antecipação
Supõe que o adversário vai responder com o seu melhor ganho imediato e escolhe o lance com o melhor saldo depois dessa resposta: um minimax de profundidade 2.
função ANTECIPAÇÃO(grafo)
meus ← { c : time(c) = 1 }
deles ← { c : time(c) = 2 }
para cada v com time(v) = 0
M ← meus ∪ {v}; D ← deles
se |deles| < 3 então
r ← o w livre, w ≠ v, que maximiza
PONTOS(deles ∪ {w}, M)
D ← deles ∪ {r}
saldo(v) ← PONTOS(M, D) − PONTOS(D, M)
devolva o v de maior saldo(v)Para o seu grupo
Estas estratégias são exemplos para estudo e comparação. O código entregue no projeto precisa ser de autoria do grupo, sem código gerado por IA nem copiado de outras fontes, como manda a documentação.
Use a demonstração para testar ideias: o que acontece na estrela, no haltere ou quando a sua equipe começa a segunda partida? Uma sugestão de exercício: rode o torneio em vários grafos e explique por que a mediana ponderada vai bem em uns e mal em outros.
A competição da turma
Os grupos
Dez grupos se inscreveram no aviso da monitoria no Classroom até 15/10. O prazo de inscrição já passou: quem não se inscreveu só pode pedir a liberação diretamente ao monitor bolsista, Gabriel Nobrega da Silva Barros (gnsb@cin.ufpe.br). A entrega do resposta.py é até 30/11, no Classroom, e a apresentação, em 03/12. As entradas oficiais da competição e os seus SHA-256 saem em novembro.
Grupo 1
- Caio Manoel
- Lucas de Oliveira
- Lucas Matheus
- Vinicius Fonseca
- Thiago Ramalho
- Natália Bourbon
Grupo 2
- Benjamim Bahia
- Eduardo Aguiar
- Rafael Gomes
- João Vitor Godoy
- Carlos Henrique
- Wellington Barbosa
Grupo 3
- Gabriel Francisco
- Rennan Eloi
- Cristiano Pinzon
- Vinícius Athayde
- Jeferson Barbosa
- Matheus Enrico
Grupo 4
- Beatriz Novo
- Beatriz Holanda
- Clara Galamba
- João Marcelo Casado
- Luiza Severo
- Maria Lúcia Fragoso
Grupo 5
- Camila de Menezes
- Isabel Emily
- Lays Vitória
- Mariana Vitória
- Marília Luz
- Tayná Rafaelly
Grupo 6
- Leandro Leite
- Marcelo Duque
- Heitor Samuel
- Leonardo Gonçalves
- Daniel França
- Everton Junior
Grupo 7
- Marcus Didier
- José Vinícius
- João Gabriel Gomes
- Miguel Remides
- Vitor Didier
- Yuãn Rivke
Grupo 8
- Felipe Mateus
- Glucia Fleurie
- Helloisa Helena
- Joyce de Oliveira
- Thales Vinícius
Grupo 9
- Claudemir Araújo
- Davi Ariel
- Kauê Pinheiro
- Luís Filipe
- Lívia Clarissa
- Matheus Alves
Grupo 10
- Andrew Bispo
- Davi Tavares
- Felipe Alves
- Caio Leonardo
- Leonardo Alves
- Silvio Oliveira
Os grupos estão numerados pela ordem de inscrição, e os nomes, como cada grupo os escreveu no Classroom. Correções vão para a monitoria.