Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Construir soluções computacionais de problemas de diferentes áreas do conhecimento, de forma individual e colaborativa, selecionando as estruturas de dados e técnicas adequadas, aperfeiçoando e articulando saberes escolares.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado não dirigido em que vértices são pontos de coleta de lixo na cidade e arestas têm peso igual ao tempo de deslocamento, produza uma rota aproximada que visite todos os vértices usando uma heurística baseada em lista de vizinhos; descreva também como representar os dados e avalie a complexidade do método.
✍️ Questão dissertativa: veja abaixo a resposta esperada e a explicação.
Resposta esperada
Representação: usar lista de adjacência com, para cada vértice, lista de pares (vizinho, peso). Heurística (vizinho mais próximo): 1) Escolher vértice inicial arbitrário; 2) marcar como visitado; 3) repetir: entre os vizinhos do vértice atual não visitados escolher o de menor peso; se não houver vizinhos não visitados, escolher o vértice não visitado mais próximo pesquisando a lista (ou aplicar busca em largura a partir do atual para encontrar caminho); marcar e avançar até todos visitados; 4) retornar ao início se necessário. Avaliação: heurística é gulosa e não garante otimalidade (problema do caixeiro é NP-difícil), mas é simples e rápida em prática. Complexidade: em lista de adjacência, escolha do vizinho mais próximo local pode ser feita em tempo proporcional ao grau do vértice; processo completo custa aproximadamente O(V^2 + E) no pior caso (implementação simples), ou O(V log V + E) com estruturas auxiliares (heap) para buscas globais. Justificativa prática: solução é aplicável a roteiros urbanos com muitos vértices onde encontrar solução ótima é inviável; representações por lista reduzem memória em grafos esparsos e facilitam iteração sobre vizinhos.
Explicação
A representação em lista de adjacência é eficiente para armazenar grafos esparsos, permitindo acesso rápido aos vizinhos de cada vértice. A heurística do vizinho mais próximo oferece uma abordagem prática para encontrar uma rota, mesmo que não garanta a solução ótima, sendo adequada para situações do mundo real onde a otimização total é inviável. A análise de complexidade apresentada fornece uma visão clara sobre o desempenho do algoritmo em diferentes cenários, destacando sua viabilidade em aplicações urbanas.
Raio-X da questão
algoritmo de roteamento
avaliacao
algoritmos de grafos · heurísticas em algoritmos
Revisar conceitos de grafos e algoritmos de busca.
O aluno pode confundir a representação do grafo e não considerar corretamente os pesos das arestas, resultando em uma rota ineficiente.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Projete um algoritmo em linguagem descritiva que, dado um grafo ponderado dirigido cujas arestas representam tempos de…
- Uma prefeitura quer modelar ruas e rotas de ônibus de um bairro como um grafo direcionado com pesos (tempo de viagem)…
- Dado um grafo ponderado não dirigido onde vértices são cidades e cada aresta armazena distância (km) e limite de…
- Projete um algoritmo (pseudocódigo) que, dado um grafo não direcionado representado por lista de adjacência dos bairros…
- Elabore um algoritmo simples que utilize árvores ou grafos para resolver um problema cotidiano, como o planejamento de…
- Projete um algoritmo descrevendo quais estruturas de dados (registros, listas, matrizes ou grafos) usar para organizar…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog