O problema proposto consiste em determinar o número mínimo de soldados necessários para proteger a capital de um reino contra invasões externas, sendo o mapa do território uma matriz onde:
- Cada posição possui um custo de defesa (soldados) ou é inacessível (montanhas)
- Inimigos só podem se mover horizontal ou verticalmente
- Objetivo: garantir que nenhum caminho externo até a capital exista sem passar por posições defendidas
A solução requer modelagem do mapa como um grafo, permitindo a aplicação de algoritmos eficientes para encontrar o corte mínimo que isole a capital das bordas do mapa. Essa abordagem transforma o problema em um desafio clássico de fluxo em redes, otimizando o uso de recursos militares.
O problema foi modelado através de um grafo ponderado e direcionado G = {V, E} com as seguintes características:
| Componente | Representação |
|---|---|
| Posição (i,j) | Dois vértices: v_in (entradas) e v_out (saídas) |
| Arestas principais | v_in → v_out com peso w_ij (custo de tropas) |
| Arestas de borda | Conexões de v_out para vértice imaginário t com peso w = ∞ |
| Restrições | Apenas uma aresta pode sair de v_in e entrar em v_out |
Justificativa: Esta estrutura permite aplicar algoritmos conhecidos de fluxo em redes.
"O valor máximo de um fluxo s → t é igual à capacidade mínima de um corte s → t"
Isso significa que encontrar o fluxo máximo da capital (s) até a borda (t) equivale a determinar o corte mínimo de vértices necessários para isolar a capital.
- Enquanto existir caminho de s para t com capacidade > 0: 1.1. Execute BFS para encontrar caminho aumentante 1.2. Calcule fluxo mínimo no caminho 1.3. Atualize capacidades das arestas (incluindo reversas)
- Retorne a soma dos fluxos encontrados
Prova de Corretude: Segue diretamente do teorema do fluxo máximo-corte mínimo e das propriedades do algoritmo de Ford-Fulkerson.
- Pior caso: O(|V||E|²)
- Justificativa:
- Cada BFS: O(|V| + |E|)
- Número de iterações: O(|V||E|) (limitado por saturação de arestas)
- Justificativa:
- Estrutura: Lista de adjacências
- Complexidade: O(|V|) (linear no número de vértices)
A abordagem demonstrou:
- Eficácia na solução do problema militar através de teoria de grafos
- Otimização de recursos com algoritmo de fluxo máximo
- Escalabilidade com complexidade viável mesmo para mapas extensos
Principais lições:
- Modelagem adequada é crucial para aplicar algoritmos conhecidos
- Algoritmos de fluxo são versáteis para problemas de corte/isolamento
- Estruturas de dados impactam diretamente no desempenho
- KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Pearson, 2005.
- Ford-Fulkerson Algorithm (GeeksforGeeks): https://www.geeksforgeeks.org/ford-fulkerson-algorithm-for-maximum-flow-problem/
- Teorema Fluxo-Corte (Wikipedia): https://pt.wikipedia.org/wiki/Teorema_do_fluxo_máximo_e_corte_mínimo