Encontrar o caminho mais curto — Informática, 7–10
Os computadores podem comparar caminhos possíveis por ruas, salas ou mapas de jogos. A ideia importante é que um bom caminho precisa de uma medida clara, como distância ou tempo.
Um caminho é uma escolha
Para chegares de um lugar a outro, pode haver vários caminhos possíveis. Um computador pode representar cada caminho como passos ligados e somar os seus custos. O custo pode ser o número de quadrados, quilómetros, minutos ou moedas. Depois procura um caminho cujo custo total seja menor do que o dos outros.
Porque comparar caminhos?
As pessoas precisaram de encontrar caminhos para mapas, entregas e viagens, mas verificar todos os caminhos demora demasiado num lugar grande. Os computadores são bons a repetir comparações cuidadosas sem se cansarem. O problema não é apenas encontrar um caminho; é poupar distância, tempo, combustível ou dinheiro.
Três caminhos num mapa
Precisas de ir de A para B. O caminho 1 tem 4 quadrados, o caminho 2 tem 3 e o caminho 3 tem 5. Se cada quadrado custar um ponto, os totais são 4, 3 e 5. O computador escolhe o caminho 2 porque 3 é o menor total. Se a lama fizesse um quadrado custar 3 pontos, teria de somar esses novos custos.
O mais curto nem sempre é o mais rápido
Parece natural escolher o caminho com menos passos, por isso muitas pessoas lhe chamam o melhor. Mas uma estrada curta pode estar cheia, ser íngreme ou estar fechada, enquanto uma mais longa pode ser rápida. O computador não adivinha o que significa melhor: tens de indicar se deve contar distância, tempo, perigo, preço ou outra coisa.
Caminhos na vida real
As aplicações de mapas usam a procura de caminhos para sugerir viagens, e os sistemas de entregas usam-na para planear várias paragens. Os jogos usam ideias parecidas para mover uma personagem à volta de obstáculos. O resultado depende do mapa e dos custos recebidos, por isso um caminho pode ser o melhor matematicamente e ainda assim não servir uma pessoa.
Continua a explorar
Outras línguas
A carregar o MyLeoNes™…