Inteligência Artificial - a problemática de encontrar o melhor percurso

Tema: Inteligência Artificial – Tecnologia

A Inteligência Artificial, objeta fazer com que os computadores realizem tarefas que até então seriam feitas somente por humanos. Tarefas estas que exijam processamento cognitivo e paralelo, do tipo de tomada de decisão. Entretanto enseja-se também que computadores dotados de capacidade cognitiva, por meio de ferramentas que empreguem a Inteligência Artificial, realizem tarefas melhores que seres humanos, uma vez que especula-se que as máquinas não cometam erros humanos, por motivos de cansaço, desatenção ou fadiga.

Dentro do contexto da Inteligência Artificial, um campo da Ciência da Computação vasto e multifacetado, temos um procedimento que objetiva encontrar o melhor percurso para um destino final, isto é, traçar seguramente a melhor rota dentre várias possíveis, aqui entendida como a mais curta.

Objetivamente e de forma pragmática, um procedimento para encontrar a rota mais curta através de uma rede é achar todas as vias possíveis e selecionar a melhor delas.

Este procedimento dá-se por meio das assim intituladas: busca por profundidade e busca por amplitude. Na busca por profundidade percorre-se todos os destinos finais e computa-os, após finalizados todos os destinos, deduz-se matematicamente o de menor valor (percurso); na busca por amplitude, percorre-se em níveis, ao final da varredura, são computadas às distâncias e então chega-se ao resultado do menor percurso. Entretanto é pertinaz destacar que, a busca não é concluída quando é achado o menor percurso, ela prossegue todos os destinos possíveis, pois necessita-se de percorrê-los todos, para balizar os dados e então concluir o menor percurso. Ao sistema de busca dá-se o nome de árvore. Em se tratando de uma amplitude de busca, isto é, árvore pequena, não há problema, entretanto para muitos destinos possíveis, há uma complexidade maior.

Admitindo-se que as ramificações da árvore, isto é, os destinos são uniformes, o número de ramos alternativos em cada nó de decisão é B. Desta forma no primeiro nível, horizontalmente haverá B nós. E para cada um dos B nós, terá mais B nós no nível seguinte; o segundo, no caso, então será B². A conclusão leva a um número expressivo de B no expoente "d", isso para amplitudes e profundidades modestas. Mesmo nestes casos pode-se ter B = 10 e d = 10, traduzindo 10 na potência 10, ou seja, o numeral dez, seguido de dez zeros - 10 bilhões de percursos a serem testados. Isto torna-se uma tarefa computacional extenuante, demandando grande capacidade de processamento de dados.

Uma solução possível para este problema é um sistema denominado “ramificar-e-ligar”. A sua funcionalidade é basicamente a seguinte: durante a busca, tem-se muitos caminhos (rotas) incompletos, que competem para ser o escolhido na forma lógico/inferencial/dedutiva. Neste caso a mais curta é estendida à um nível adiante, criando novas vias incompletas para os ramos. Há então uma nova análise e repete-se à sistemática, onde a mais curta é estendida. Isso repete-se até chegar ao destino, ramificando-se e estendendo o nível mais curto. Como a via mais curta é sempre a escolhida e consequentemente estendida, a que primeiro alcançar o destino é certamente a melhor (menor distância).

Há porém duas questões que deve-se atentar:

1 - Entretanto não há como asseverar com certeza absoluta, pois nada garante que sempre pegue-se o menor caminho (rota), mas certamente é um dos “menores caminhos”.

2 - Outro aspecto a ser frisado, é o seguinte; como o alongamento dos caminhos escolhidos, não garantem que seja o menor, há sempre a possibilidade de grandes números de alongamentos para descobrir o destino, acarretando mais dados e sequências para processar. Pode-se muito bem chegar a resolução na primeira tentativa, mas não há garantia disso.

(Fonte: Artificial Intelligence – Patrick Henry Winston)