Path­fin­ding: busca de percursos na in­for­má­tica

Os al­go­rit­mos de busca de percursos estão entre os mais populares e uti­li­za­dos. Mostramos-lhe como funcionam e para que servem.

O que é o path­fin­ding?

O path­fin­ding, também conhecido como busca de percursos, é um problema básico da in­for­má­tica que consiste em encontrar o caminho mais curto ou mais eficiente entre dois pontos. Existe uma grande variedade de al­go­rit­mos de path­fin­ding que são uti­li­za­dos em todo o tipo de cenários de aplicação.

Como funciona o path­fin­ding e para que serve?

Um algoritmo de busca de percursos ge­ral­mente começa por re­pre­sen­tar o problema como um grafo ou uma grelha. Um grafo é um conjunto de nós in­ter­li­ga­dos, como, por exemplo, um diagrama de fluxo. Uma grelha é uma matriz bi­di­men­si­o­nal de células, como um tabuleiro de xadrez. Os nós ou células re­pre­sen­tam posições no espaço do problema, enquanto as arestas ou células ad­ja­cen­tes re­pre­sen­tam as possíveis rotas entre elas.

Depois de re­pre­sen­tar o problema sob a forma de grafo ou grelha, os al­go­rit­mos de busca de percursos utilizam várias técnicas para encontrar o caminho entre dois pontos. Nor­mal­mente, o objetivo dos al­go­rit­mos é encontrar o caminho mais curto ou mais económico e, ao mesmo tempo, ser o mais eficiente possível.

Os al­go­rit­mos de busca de percursos têm muitas apli­ca­ções na in­for­má­tica, entre as quais se destacam as seguintes:

• Robótica: os al­go­rit­mos de path­fin­ding são uti­li­za­dos para ajudar os robôs autónomos a navegar em ambientes complexos. Pense em carros com piloto au­to­má­tico ou robôs as­pi­ra­do­res in­te­li­gen­tes que percorrem a casa de forma autónoma.
• Vi­de­o­jo­gos: os al­go­rit­mos de path­fin­ding são uti­li­za­dos para controlar os mo­vi­men­tos das per­so­na­gens não jogáveis (PNJ) nos vi­de­o­jo­gos. Num jogo de es­tra­té­gia em tempo real, clicar para enviar as suas unidades para a base inimiga também implica a uti­li­za­ção de al­go­rit­mos de path­fin­ding.
• Logística: os al­go­rit­mos de path­fin­ding são uti­li­za­dos na área da logística para encontrar a forma mais eficiente de trans­por­tar mer­ca­do­rias ou pas­sa­gei­ros.
• Regulação do tráfego: os al­go­rit­mos de path­fin­ding são uti­li­za­dos para traçar as melhores rotas no tráfego de uma cidade, evitando en­gar­ra­fa­men­tos.
• Ro­te­a­mento de redes: nas redes in­for­má­ti­cas, os al­go­rit­mos de path­fin­ding são uti­li­za­dos para encontrar o caminho mais rápido para a trans­fe­rên­cia de dados entre di­fe­ren­tes nós da rede.

A seguir, apre­sen­ta­mos em pormenor algumas possíveis apli­ca­ções do path­fin­ding.

Pla­ne­a­mento de percursos na logística

No âmbito da logística, o path­fin­ding consiste em encontrar o melhor percurso para o trans­porte de mer­ca­do­rias. Um percurso ideal minimiza os custos e o tempo de viagem, ga­ran­tindo si­mul­ta­ne­a­mente a segurança dos produtos trans­por­ta­dos. O path­fin­ding na logística é, portanto, uma fer­ra­menta decisiva para otimizar o trans­porte de mer­ca­do­rias e reduzir custos.

A seguir, alguns exemplos para mostrar como o path­fin­ding é utilizado no domínio da logística:

• Pla­ne­a­mento de percursos: no trans­porte de mer­ca­do­rias, os al­go­rit­mos de path­fin­ding otimizam o percurso dos veículos de dis­tri­bui­ção. O algoritmo tem em conta fatores como a distância, as condições de trânsito e os prazos de entrega para criar o percurso mais eficiente.
• Gestão de in­ven­tá­rios: o path­fin­ding é utilizado na gestão de in­ven­tá­rios ou armazéns para otimizar a dis­po­si­ção das mer­ca­do­rias. Desta forma, garante-se que as mer­ca­do­rias sejam ar­ma­ze­na­das nas posições ideais, o que reduz o esforço e o tempo ne­ces­sá­rios para retirar e entregar as mer­ca­do­rias.
• Gestão da cadeia de abas­te­ci­mento: os al­go­rit­mos de path­fin­ding são uti­li­za­dos para otimizar toda a cadeia de abas­te­ci­mento, desde o início até à entrega, o que garante que os produtos sejam trans­por­ta­dos da forma mais eficiente e económica possível.

Path­fin­ding nos vi­de­o­jo­gos

O path­fin­ding é uma fer­ra­menta im­por­tante nos vi­de­o­jo­gos, per­mi­tindo criar mundos de jogo realistas e im­pres­si­o­nan­tes. O path­fin­ding é uma técnica que permite que as unidades e as per­so­na­gens não jogadoras (NPC) se desloquem pelo mundo do jogo de forma realista e eficaz. Os al­go­rit­mos de path­fin­ding são uti­li­za­dos para de­ter­mi­nar o percurso ideal para o movimento das NPC, evitando obs­tá­cu­los e outros perigos.

Nos vi­de­o­jo­gos, o path­fin­ding é utilizado, entre outras coisas, para realizar as seguintes tarefas:

• PNJs inimigos: o path­fin­ding é utilizado para controlar o com­por­ta­mento dos PNJs inimigos. Desta forma, os PNJs podem seguir o jogador enquanto evitam obs­tá­cu­los e outros perigos.
• Controlo de unidades: o path­fin­ding é utilizado para controlar o movimento das unidades aliadas dentro do mundo do jogo. Isto pode incluir guiar os NPCs até ao seu destino ou seguir a per­so­na­gem do jogador.
• Contornar obs­tá­cu­los: os al­go­rit­mos de path­fin­ding garantem que as unidades contornem obs­tá­cu­los como paredes, penhascos ou outros perigos.
• Gerar mapas e níveis: os al­go­rit­mos de path­fin­ding também são uti­li­za­dos para gerar mapas ou níveis de forma pro­ce­du­ral, o que permite criar mundos de jogo realistas e distintos.

Path­fin­ding no en­ca­mi­nha­mento de redes

O path­fin­ding é utilizado no en­ca­mi­nha­mento de redes para encontrar os percursos ótimos para os pacotes de dados através de uma rede. Os al­go­rit­mos de path­fin­ding oferecem aos ad­mi­nis­tra­do­res de rede a pos­si­bi­li­dade de melhorar o de­sem­pe­nho da rede em função de cir­cuns­tân­cias es­pe­cí­fi­cas. Entre as uti­li­za­ções mais comuns do path­fin­ding no en­ca­mi­nha­mento de redes encontram-se as seguintes:

• En­ge­nha­ria de tráfego: os al­go­rit­mos de path­fin­ding ajudam a otimizar as redes de tráfego e a minimizar o con­ges­ti­o­na­mento. Os al­go­rit­mos de path­fin­ding analisam a topologia da rede e os padrões de tráfego para iden­ti­fi­car as rotas mais efi­ci­en­tes na trans­fe­rên­cia de pacotes de dados através da rede.
• Qualidade de serviço (ou Quality of Service, QoS): os al­go­rit­mos de path­fin­ding podem ser uti­li­za­dos para priorizar o tráfego da rede em função dos re­qui­si­tos de qualidade de serviço. Por exemplo, os dados em que o tempo é um fator crítico, como os fluxos de VoIP ou vídeo, têm pre­fe­rên­cia na hora de serem en­ca­mi­nha­dos. A pri­o­ri­za­ção faz parte da função de custos.
• Equi­lí­brio de carga: existem al­go­rit­mos de path­fin­ding es­pe­ci­al­mente adaptados para dis­tri­buir o tráfego da rede por di­fe­ren­tes rotas. Os al­go­rit­mos de path­fin­ding facilitam o equi­lí­brio de carga para ajudar a melhorar o de­sem­pe­nho da rede e reduzir o risco de con­ges­ti­o­na­mento.
• Re­si­li­ên­cia: os al­go­rit­mos de path­fin­ding são uti­li­za­dos para encontrar rotas al­ter­na­ti­vas para o fluxo de dados quando ocorrem falhas na rede, o que garante que os pacotes de dados sejam entregues de forma fiável quando um com­po­nente da rede falha.

Pla­ne­a­mento de percursos no pla­ne­a­mento dos trans­por­tes

O path­fin­ding é utilizado no sistema de trans­por­tes para otimizar o fluxo de tráfego e reduzir o con­ges­ti­o­na­mento. Os al­go­rit­mos de path­fin­ding ajudam os en­ge­nhei­ros de tráfego a conceber redes de tráfego efi­ci­en­tes e a de­sen­vol­ver es­tra­té­gias para melhorar a cir­cu­la­ção. Seguem-se algumas das prin­ci­pais apli­ca­ções do path­fin­ding no sistema de trans­por­tes:

• Pla­ne­a­mento de percursos: os al­go­rit­mos de path­fin­ding são uti­li­za­dos para planear os percursos ótimos dos veículos, evitando zonas con­ges­ti­o­na­das. Isto melhora a fluidez do tráfego e reduz os atrasos.
• Oti­mi­za­ção dos semáforos: os al­go­rit­mos de path­fin­ding permitem otimizar a sin­cro­ni­za­ção dos semáforos em função do tráfego e da sua in­ten­si­dade. Sin­cro­ni­zar os semáforos e ajustar os horários pode melhorar a cir­cu­la­ção.
• Gestão de in­ci­den­tes: os al­go­rit­mos de path­fin­ding são uti­li­za­dos para iden­ti­fi­car percursos al­ter­na­ti­vos para os veículos em caso de acidentes ou cortes nas estradas. Desta forma, o path­fin­ding ajuda a reduzir o con­ges­ti­o­na­mento e a melhorar a fluidez do tráfego nas zonas afetadas.
• Trans­porte público: os al­go­rit­mos de path­fin­ding podem ser uti­li­za­dos para otimizar os percursos e horários do trans­porte público. Isto ajuda a melhorar a efi­ci­ên­cia dos sistemas de trans­porte público e a reduzir a congestão do tráfego.

Que al­go­rit­mos de busca de percursos existem?

Os desafios do path­fin­ding decorrem das res­tri­ções de espaço de cada projeto. É ne­ces­sá­rio ter em conta os obs­tá­cu­los que bloqueiam o caminho direto, bem como os custos de des­lo­ca­mento pelo espaço. Os custos podem ser de vários tipos; por exemplo, um percurso pode ser mais económico do ponto de vista ener­gé­tico, mas exigir um tempo de des­lo­ca­mento mais longo.

Por vezes, é ne­ces­sá­rio incluir de­ter­mi­na­dos pontos fixos no percurso; assim, o algoritmo de busca de percursos garante que o des­lo­ca­mento pelo espaço não se faça em círculos. Em geral, deve encontrar-se um percurso ótimo da forma mais rápida e eficiente, sobretudo se for realizado em tempo real.

Alguns dos al­go­rit­mos de busca de percursos mais comuns são os seguintes:

• Pesquisa em Largura (BFS): conhecida como pesquisa em largura, explora todos os nós vizinhos do ponto de partida antes de passar para o nível seguinte de nós e faz-o de forma iterativa até atingir o objetivo.
• Algoritmo de Dijkstra: explora o grafo, per­cor­rendo primeiro o nó inex­plo­rado mais próximo do ponto de partida e atu­a­li­zando ite­ra­ti­va­mente a distância de todos os nós a partir do ponto de partida até atingir o objetivo.
• Pesquisa A*: combina as ideias da BFS e do algoritmo de Dijkstra, uti­li­zando uma função heu­rís­tica para orientar a pesquisa até ao nó alvo.
• Pesquisa voraz «primeiro o melhor»: seleciona o próximo nó a explorar, com base numa es­ti­ma­tiva heu­rís­tica da distância até ao nó alvo.
• Pesquisa bi­di­re­ci­o­nal: pesquisa si­mul­ta­ne­a­mente a partir dos nós de partida e de destino até ao centro do grafo para encontrar o caminho mais curto.