🌍 Do JSON ao Mapa: Busca Inteligente em Grafos Geográficos com Interface Interativa

✨ Resumo

Este artigo apresenta a evolução de um projeto de problem solving utilizando algoritmos de busca inteligente aplicados a grafos geográficos. O trabalho teve início com uma implementação clássica dos algoritmos A* e Busca Gulosa, estruturada em Python, e evoluiu para uma plataforma interativa utilizando a biblioteca Gradio. A proposta oferece ao usuário uma experiência acessível e visual para explorar caminhos entre cidades com base em suas coordenadas geográficas reais. Toda a solução é executável no Google Colab, com visualizações de rotas e mapas gerados automaticamente.

📊 Introdução

A busca por soluções otimizadas é um dos principais desafios em Inteligência Artificial. Este projeto nasceu com a proposta de aplicar algoritmos de busca inteligente em um grafo geográfico, conectando cidades e encontrando rotas ideais com base na distância real entre elas. A ideia foi alçada a um novo patamar com a criação de uma interface interativa, democratizando o acesso à tecnologia e tornando a experiência muito mais intuitiva.

📂 Dataset e Construção do Grafo

Estrutura dos Dados

O arquivo cities.json utilizado neste projeto é composto por uma lista de cidades norte-americanas com as seguintes informações:

{
"city": "New York",
"state": "New York",
"latitude": 40.7127837,
"longitude": -74.0059413,
"population": "8405837",
"rank": "1",
"growth_from_2000_to_2013": "4.8%"
}

Geração Dinâmica das Arestas

Como o arquivo não continha dados de estradas, foi implementada uma lógica para conectar automaticamente cidades que estão a uma distância máxima de 500 km, utilizando a biblioteca geopy. Isso permitiu criar um grafo coerente e funcional.

Visualização

Foi utilizada a biblioteca NetworkX para criar os grafos e o matplotlib para gerar as visualizações das rotas encontradas pelos algoritmos.

🤖 Algoritmos Implementados

A* (A-Star)

O algoritmo A* combina a busca em profundidade com uma heurística (neste caso, a distância geográfica entre os pontos). Ele garante a menor rota quando a heurística é admissível.

Busca Gulosa

Este algoritmo prioriza o nó mais "promissor" com base apenas na heurística, o que nem sempre garante a melhor rota, mas pode ser mais rápido.

💻 Interface Interativa com Gradio

A grande inovação desta versão é a interface criada com Gradio. A aplicação permite ao usuário:

• Selecionar origem e destino a partir de listas suspensas
• Escolher entre os algoritmos A* e Busca Gulosa
• Visualizar a rota traçada diretamente no gráfico

A interface foi pensada para funcionar no Google Colab, com todas as bibliotecas sendo instaladas automaticamente. O usuário não precisa editar nenhum trecho de código, apenas interagir com os menus e observar os resultados visualmente.

🔍 Comparativo das Versões

Link do Problem Solving projeto inicial: https://github.com/FabianaAlbuquerque97/Busca-Inteligente-em-Grafos-Geograficos/blob/main/Problem_solving.ipynb

Link do projeto Busca Inteligente em Grafos Geográficos – Versão Interativa: https://github.com/FabianaAlbuquerque97/Busca-Inteligente-em-Grafos-Geograficos/blob/main/Busca_Inteligente_em_Grafos_Geográficos_–_Versão_Interativa.ipynb

🔗 Link do Repositório e Execução

• 🔍 Código completo no GitHub: https://github.com/FabianaAlbuquerque97/Busca-Inteligente-em-Grafos-Geograficos/tree/main
• 🚀 Compatível com Google Colab: basta abrir o .ipynb, instalar as dependências, importar o arquivo cities.json para o ambiente do Colab e executar.

📸 Exemplos Visuais

Rota gerada pelo algoritmo A*:

🔍 Análise da Busca A*

• Caminho encontrado:
• ['Dallas', 'Lancaster', 'Palmdale', 'Pasadena', 'Houston']
• O algoritmo levou em conta critérios além da menor distância — como informado, houve um critério de desempate pela população.
• Distância total: 0.91
• Visualização:
• Nós azuis: representam as cidades no grafo.
• Arestas cinza claro: conexões possíveis entre cidades.
• Caminho mais curto (em vermelho): rota final encontrada pelo A*, destacando as cidades percorridas.
• Isso indica que, entre rotas com custo similar, o algoritmo optou por cidades com maior população — uma heurística útil em problemas urbanos ou de logística.

🧠 Busca Inteligente em Grafos Geográficos com interface interativa

🎯 Entradas do Usuário

No painel à esquerda, o usuário define:

• Cidade de Origem: Los Angeles
• Cidade de Destino: Philadelphia
• Algoritmo de Busca Selecionado: DFS (Busca em Profundidade)

📍 Resultado da Busca

O painel à direita exibe o caminho encontrado pelo algoritmo DFS:

Los Angeles → San Diego → Phoenix → Las Vegas → Fresno → San Jose → ...
→ New York → Philadelphia

Esse caminho é longo e não otimizado, o que é esperado da DFS, pois ela explora o grafo em profundidade, sem considerar distância ou custo. Ela pode:

• Ser muito ineficiente em mapas reais.
• Chegar à solução apenas após explorar muitos caminhos.

🧭 Algoritmos disponíveis

Os botões mostram:

• DFS: já selecionado.
• Greedy: disponível, mas não selecionado.
• Isso indica que o sistema permite comparar o desempenho de algoritmos não informados (como DFS e Greedy) sobre o mesmo grafo.

🗺️ Visualização do Caminho

Abaixo da seção “Resultado”, há um gráfico que mostra visualmente o caminho encontrado. Embora ele não esteja totalmente visível na imagem, o botão de “expandir tela cheia” (⤢) e “download” indicam que o usuário pode:

• Visualizar as cidades percorridas no mapa.
• Fazer o download da imagem da rota.

💻 Comparação clara e direta entre os Algoritmos DFS (Busca em Profundidade) e Greedy (Busca Gulosa)

🔍 1. Definição dos Algoritmos

• DFS (Depth-First Search):
• 🔸 Tipo de busca: Cega (não informada)
• 🔸 Critério de decisão: Vai fundo no grafo o máximo possível
• 🔸 Objetivo: Explorar profundamente um caminho antes de voltar
• Greedy Best-First Search:
• 🔸 Tipo de busca: Heurística (informada)
• 🔸 Critério de decisão: Escolhe o próximo nó com menor custo heurístico (ex: distância até o destino)
• 🔸 Objetivo: Chegar rápido ao destino com base em uma estimativa (não garante o melhor caminho)

⚙️ 2. Funcionamento

• DFS:
• 🔹 Usa pilha (stack), geralmente com recursão
• 🔹 Explora um caminho até o fim antes de voltar
• 🔹 Não considera o custo acumulado
• 🔹 ❌ Não é completo (pode não encontrar solução em grafos grandes)
• 🔹 ❌ Não garante o caminho mais curto
• Greedy:
• 🔹 Usa fila de prioridade baseada na heurística (ex: distância Euclidiana)
• 🔹 Explora nós que "parecem" mais promissores primeiro
• 🔹 Considera apenas a heurística (não o caminho já percorrido)
• 🔹 ✅ É completo (se a heurística for admissível)
• 🔹 ❌ Não garante o caminho ótimo

🧭 3. Exemplo no Grafo Geográfico

• DFS:
• 🔸 No exemplo da imagem (Los Angeles → Philadelphia), o algoritmo encontrou um caminho muito longo, passando por diversas cidades aleatórias.
• 🔸 Ineficiente para rotas reais.
• Greedy:
• 🔸 Teria escolhido cidades mais próximas do destino desde o início.
• 🔸 Mais rápido e direto.

📌 4. Quando Usar Cada Um

• DFS é indicado quando:
• ✅ Há muitos caminhos e recursos limitados
• ✅ A solução ótima não é necessária
• ❌ Não é bom para grafos grandes ou com muitos ciclos
• Greedy é indicado quando:
• ✅ Existe uma boa heurística (ex: distância real entre cidades)
• ✅ Precisamos de uma solução rápida e razoável
• ❌ Não é garantido que encontrará o melhor caminho possível

✅ Resumo Final

• DFS:
• 🔹 Tipo de busca: Cega
• 🔹 Eficiência: Baixa em grafos grandes
• 🔹 Caminho ótimo: Não garante
• 🔹 Ideal para: Exploração completa ou testes simples
• Greedy:
• 🔹 Tipo de busca: Heurística
• 🔹 Eficiência: Alta (com heurística boa)
• 🔹 Caminho ótimo: Não garante
• 🔹 Ideal para: Navegação rápida e problemas de caminho com boa heurística

🚀 Conclusão

Esse projeto demonstra como é possível transformar um problema clássico de algoritmos de busca em grafos em uma experiência envolvente e acessível com Python. A integração com bibliotecas modernas como Gradio não só melhora a usabilidade, mas também aumenta o impacto visual e educacional da solução.

Se você quer aprender mais sobre grafos, heurísticas e construir projetos interativos, recomendo clonar o repositório, testar as rotas e quem sabe até criar sua própria versão com mapas reais da sua cidade!

A evolução deste projeto representa um salto em direção à democratização da Inteligência Artificial. Ao tornar acessível uma ferramenta antes restrita a desenvolvedores experientes, é mostrado que é possível criar soluções poderosas, visuais e educativas ao mesmo tempo.

📊 Referências

• Documentação oficial NetworkX
• Biblioteca Gradio
• Dataset adaptado de Simple Maps US Cities
• Geopy: para cálculo de distâncias geográficas

🚀 Se você gostou desse projeto, não esqueça de curtir, comentar e compartilhar! Vamos juntos construir uma comunidade cada vez mais colaborativa. 😊

👩‍💻 Sobre a autora

📌 Conecte-se comigo e me siga para mais conteúdos como este! 🚀 :

• GitHub: github.com/FabianaAlbuquerque97
• LinkedIn: linkedin.com/in/fabiana-albuquerque-tecnologa

Artigo elaborado por Fabiana de Albuquerque Silva, com base no repositório de projeto público disponível no GitHub.

#Python #IAComPython #InteligenciaArtificial #CienciaDeDados  

#Grafos #GraphTheory #AlgoritmosDeBusca #BuscaInteligente  

#Geolocalizacao #VisualizacaoDeDados #DesenvolvimentoPython  

#MachineLearning #AStar #DFS #Greedy #PythonNaPratica  

#DesafioIA27 #CompartilheConhecimento