TCC · Otimização combinatória · Concluído

Como defender um império inteiro com metade das tropas?

Constantino enfrentou isso no século IV. Virou um problema de matemática que nenhum computador resolve rápido até hoje. Meu TCC atacou com algoritmos inspirados em formigas e em evolução — e corrigiu um modelo publicado errado.

Ver a estratégia Ver a estrutura técnica Repositório

C++
Algoritmo Genético
Colônia de Formigas
Programação Linear Inteira
2024–2025

Resumo

O essencial em cinco pontos.

O problema: proteger todas as regiões de um grafo pelo menor custo, com quem está desguarnecido dependendo dos vizinhos. É NP-completo.
Minha contribuição: as duas primeiras meta-heurísticas da literatura para o problema — colônia de formigas e algoritmo genético, em C++.
A correção: a formulação exata publicada antes aceita soluções inválidas. Mostro o contraexemplo e proponho a primeira correta.
Evidências: 362 grafos sob três métricas declaradas antes dos experimentos. Só 6 ficaram a mais de 50% da referência.
Formato: TCC em Ciência da Computação na UFC Quixadá, defendido em fevereiro de 2025.

Busto em mármore do imperador Constantino, o Grande, visto de frente. — Constantino, o Grande, que reorganizou a defesa do império no século IV. Busto do Museo Chiaramonti, Vaticano. Foto de Marie-Lan Nguyen, domínio público.

A estratégia de Constantino

Metade das legiões, o mesmo território.

Oito regiões, cinquenta legiões. Quando sobraram vinte e cinco, guarnecer tudo virou impossível — e o imperador mudou a pergunta.

01 Oito regiões vizinhas
Gália, Roma, Constantinopla, Ibéria, Ásia Menor, Egito, África do Norte e Britânia, ligadas por fronteiras.
02 Metade da força
De cinquenta para cerca de vinte e cinco legiões: não dá para ocupar todas as regiões.
03 Defesa em profundidade
Uma região pode ficar sem tropas, desde que os vizinhos consigam socorrê-la sem se desguarnecer.

A regra do jogo

Três legiões de defesa para cada região.

A regra inteira, em uma frase

Cada região precisa somar três legiões de defesa: as que já estão lá mais as que os vizinhos podem enviar — e todo vizinho que envia precisa deixar uma legião para trás.

tropas na região + (tropas de cada vizinho − 1) ≥ 3

Cada região recebe 0, 2, 3 ou 4 legiões. O custo é a soma de todas elas. O problema é encontrar a distribuição válida mais barata.

Uma região com 4 legiões salva qualquer vizinho sozinha: manda 3, fica com 1. Uma com 2 só consegue mandar 1 — precisa de companhia.

Experimente

Distribua as legiões do império.

Clique numa região para mudar as tropas: 0 → 2 → 3 → 4. O mapa avisa na hora quem ficou desprotegido.

Império protegido.

Custo: 8 legiões
Melhor possível: 8 legiões

Começa em uma das cinco soluções ótimas: oito legiões, ninguém desprotegido. Não existe arranjo válido mais barato.

sem tropas, depende dos vizinhos
com tropas, envia uma a menos do que tem
desprotegida: não chega a três legiões de defesa

Mapa do Império Romano representado como um grafo, com os rótulos de uma solução ótima de Dominação Romana Tripla nos vértices. — A mesma solução sobre o mapa original: duas regiões com quatro legiões cobrem as outras seis. Figura do TCC, elaborada pelo autor com base em Gray (2015).

Por que três?

A terceira versão de um problema clássico.

A ideia de Constantino virou problema matemático em 2004 e ganhou versões cada vez mais exigentes. Muda uma coisa só: quantas legiões de socorro cada região precisa reunir.

2004

Dominação romana

Uma legião de socorro por região. Basta um vizinho forte.

2016

Dominação romana dupla

Duas legiões. Um único vizinho comum já não basta.

2021 · este trabalho

Dominação romana tripla

Três legiões. A mais exigente das três e a que tolera mais falhas simultâneas.

O trade-off

Mais robusta, não mais barata

Exigir três em vez de uma custa mais legiões. O ganho não é economia: é margem para absorver quedas simultâneas.

Por que é difícil

Fácil de conferir, difícil de achar.

Conferir se uma distribuição funciona leva um instante. Achar a mais barata entre todas é outra história.

Com oito regiões existem 65.536 distribuições. Com cem, o número tem 61 dígitos — bilhões de vezes o total de átomos da Terra. Um computador testando um bilhão por segundo desde o Big Bang teria coberto uma fração desprezível. E o problema é NP-completo: não se conhece método exato e rápido.

65.536 distribuições possíveis em um mapa de apenas oito regiões

4¹⁰⁰ distribuições em uma rede de cem pontos: bilhões de vezes o total de átomos da Terra

NP-completo nenhum algoritmo exato e rápido é conhecido para o problema

O que eu fiz

Três formas de atacar, e uma correção.

Meta-heurística

Colônia de formigas

Formigas artificiais montam distribuições e deixam rastro nas escolhas que deram certo. Foi o método que se saiu melhor.

Meta-heurística

Algoritmo genético

Uma população de soluções que se cruzam, sofrem mutações e competem. As mais baratas sobrevivem.

Método exato

Programação linear inteira

O problema como sistema de restrições, resolvido por solver enquanto o grafo é pequeno. É a régua para medir os outros dois.

Correção

Um modelo publicado que falhava

A formulação exata da literatura aceitava distribuições inválidas. Mostrei um contraexemplo e propus a primeira correta.

Resultados

362 grafos, medidos contra o ótimo.

Bases clássicas, redes reais e grafos gerados para o trabalho. Onde o solver exato respondeu, a comparação é contra o ótimo.

362 grafos avaliados, entre bases clássicas, redes reais e instâncias geradas

ACO a colônia de formigas venceu na maioria dos casos, em tempo e em qualidade

6 grafos, entre todos os avaliados, ficaram a mais de 50% do ótimo

O algoritmo genético não foi descartado: seguiu competitivo em grafos menores e estruturados, e às vezes chegou ao ótimo onde a colônia de formigas não chegou.

Onde isso aparece hoje

O mesmo problema, sem legiões.

Troque regiões por bairros e legiões por depósitos: quantos depósitos abastecem a cidade inteira, sabendo que quem socorre o vizinho não pode ficar sem estoque? É a mesma conta.

Lojas e depósitos: cobrir todos os bairros, inclusive os sem loja própria, sem desabastecer quem socorre.
Servidores e antenas: onde instalar para a rede seguir atendida quando um ponto cai — e quando dois caem juntos.
Equipes e plantões: distribuir ambulâncias ou brigadas entre regiões que se cobrem sem ficarem descobertas.

A literatura cita defesa militar, servidores e cobertura de redes; loja e plantão são analogias. O trabalho é sobre o problema matemático, não sobre um caso aplicado.

Aprofundamento

A partir daqui, o detalhe.

A página técnica traz a definição formal, o contraexemplo que derruba a formulação anterior, os dois algoritmos passo a passo e as tabelas medidas.

Ver a estrutura técnica →

Código e experimentos

Veja a implementação e o TCC completo.

Abrir repositório Abrir TCC Estrutura técnica