O AHP combina critérios e produz a superfície de aptidão. A etapa seguinte é um problema de caminho de menor custo em uma grade.
Cada célula se conecta a até oito vizinhas. Para uma passagem de i a j, o custo é:
d(i,j) × [custo da linha + peso do terreno × (1 − (scoreᵢ + scoreⱼ)/2)]
A distância considera o tamanho X/Y da célula e os passos diagonais. Células com zero ou NoData são proibidas; diagonais não cortam cantos de barreiras. O custo da linha deve ser positivo para evitar trajetos gratuitos em áreas verdes.
A sequência A → B → C → … é obrigatória. Cada trecho é calculado separadamente e os custos são somados. Como o modelo é aditivo e não cobra curvas, trechos ótimos formam um ótimo para a ordem fixada. A rota pode repetir células. Isso não resolve a melhor ordem de visita (problema do caixeiro-viajante) nem uma rede ramificada de transmissão.
A* usa uma estimativa admissível: distância em linha reta multiplicada pelo menor custo por unidade. Encontra o ótimo na grade.
Dijkstra (SciPy) calcula custos acumulados a partir de A. Encontra o mesmo custo ótimo, embora possa escolher outra rota em caso de empate.
Dijkstra bidirecional expande a busca a partir de A e B, com condição de parada que preserva o ótimo.
A* ponderado (2×) usa g + 2h para privilegiar a direção do destino. Pode encontrar uma rota mais cara; nesta implementação com reabertura, o custo é limitado a até 2× o ótimo. O fator da heurística não altera os pesos físicos do problema.
Busca gulosa prioriza a proximidade estimada do destino, sem considerar o custo já acumulado na prioridade. Não garante menor custo.
Pareto aproximado executa sete cenários de peso da linha (0,01× a 20× do valor escolhido e um cenário sem penalidade do terreno), remove duplicatas e rotas dominadas nas dimensões comprimento e impacto integrado. Não é BOA* nem EMOA*: não garante a fronteira completa, e a soma ponderada pode perder soluções não convexas. Todos os custos exibidos usam os pesos originais.
Penalização sucessiva aumenta temporariamente o custo perto das rotas já encontradas para explorar outros corredores. Apenas a primeira rota tem garantia de ótimo do custo original. Não são os k menores caminhos de Yen. Todos os resultados são avaliados pela mesma função de custo original.
Nos demos, verde = 1, amarelo = 0,5, vermelho/laranja = 0,15, azul/ciano = 0,01. Letras magenta foram detectadas e preenchidas pela cor vizinha. O centro de cada letra define o ponto do exemplo. O exterior cinza e preto da primeira imagem fica como NoData.
As imagens não possuem escala geográfica. O padrão mede pixels; inserir a dimensão real da célula permite trabalhar em metros. GeoTIFF projetado mantém a escala em metros. Os cálculos usam a resolução integral do raster, sem redução automática.
Uma linha construída também depende de torres, ângulos, declividade, vãos, faixa de servidão e restrições legais. Este laboratório otimiza apenas a superfície fornecida e o comprimento; o ótimo é da grade de oito vizinhos, não de todas as curvas possíveis.
Theta* busca segmentos com ângulos livres; em terreno heterogêneo precisa integrar o custo de todas as células atravessadas. BOA*/EMOA* buscam alternativas multiobjetivo de Pareto. D* Lite reaproveita buscas quando o mapa é alterado. Esses três métodos não estão implementados neste laboratório.
Yen encontra k caminhos simples de menor custo, frequentemente muito parecidos entre si. Análise de Pareto e varredura de pesos ajudam a comparar extensão e impacto. Custos de mudança de direção exigem incluir a direção no estado da busca; corredores de custo acumulado ajudam a identificar faixas de alternativas.
Documentação SciPy / Dijkstra ↗ · Referência de A* ↗