My Profile Photo

Jociel Souza

PHP Clojure Javascript Mongodb ZendFramework


Desenvolvedor Web - Backend - PHP


Estudante de Ciência da Computação, desenvolvedor de software apaixonado por tecnologia e entusiasta de empreendedorismo,


Estudante de Ciência da Computação procurando sempre aprender algo novo, desenvolvedor web com conhecimento em PHP7^, Zend Framework, Doctrine ORM, Doctrine ODM, MongoDB, Javascript, HTML, GIT entre outros, atualmente estudando também Clojure, Elm e o paradigma funcional e tentando compartilhar o conhecimento adquirido.


Clojure - Algoritmo A* | Jociel Souza

Clojure - Algoritmo A*

Trabalho faculdade



Atualmente estou estudando Clojure e agora quase finalizando o sementre da universidade estão surgindo os trabalhos de implementação e resolvi fazê-los usando Clojure, por que não uma boa nota e a aprovação na disciplina para dar uma motivada não é não? 8D, e pretendo descrever alguns por aqui até para deixar meio documentado também, então vamos lá.


Search A*

O algoritmo A* (A estrela), é um algoritmo de busca, de caminho em grafo, heurística, algoritmos de busca heurística utilizam informações extras sobre o domínio problema para guiar o processo de busca.

http://maratonapuc.wikidot.com/apostilas:a-star
http://www.dainf.ct.utfpr.edu.br/~fabro/IA_I/busca/IA_Estrategias_Busca_Inf.pdf
http://www.cos.ufrj.br/~ines/courses/cos740/leila/cos740/apres_ia.pdf
https://pt.wikipedia.org/wiki/Algoritmo_A*


Função Heurística (h(n))

Utilizando uma função estima-se o custo de um determinado nó(estado) até o objetivo final para ver o quanto esse estado é bom o suficiente para atingir o objetivo em relação aos outros estados, essa função é conhecida como função heurística (h). Essa função é específica para cada problema e deve ser analisada e criada de acordo com o mesmo.

Função de custo (g(n))

Usando outra função (g), avalia-se o custo total para chagar do estado inicial até o estado que esta sendo avaliado.

Função de avaliação (f(n))

A função global de avaliação (f(n)) dá-se pela soma da função heurística h(n) e a função de custo g(n), f(n) = g(n) + h(n).


Para esse exercício utilizei um grafo como na imagem a seguir, o objetivo é ir do estado A até o estado G pelo menor caminho.


Criando o projeto


Caso não saiba como criar um projeto em clojure, tem um artigo com uma introdução para criação projetos e dependências em Clojure:


Vou criar um projeto chamado astar-algorithm-clojure utilizando o Liningen:

lein new astar-algorithm-clojure

Após isso, teremos a estrutura de dirétório do projeto, irei criar todas as funções no arquivo padrão core.clj no diretório src.


Usando Map criei a estrutura que irá representar o grafo da imagem, onde temos os estados pais e os estados filhos com o valor de custo para ir do estado pai até o respectivo estado filho.

Onde :A é o estado pai e :C e :B são seus estado filhos, 14 e 12 são os custos para ir de :A até os estados filhos respectivos e assim é com os outros estados também.

Utilizarei valores já processados para a função heurística de cada estado, também usando Map para representar essa função.

Nesse exemplo, aplicando a função heurística para o estado :A retorna o valor 30, para :B retorna 26. Esse é o valor heurístico dos estados, que será somado ao custo do estado para calcular o custo total do caminho por esse estado.
Pode-se usar diversas formas para essa função heurística, como por exemplo Manhattan Distance, e Euclidean Distance.


Vamos criar duas funções, state-children e children-values onde state-children recebe um estado e retorna seus estados filhos em uma lista e children-values recebe um estado e retorna o custo associado aos estados filhos.

Passando o estado :A para a função state-children retorna o seus estado filhos (:C :B) e para a função children-values retorna o custo associado aos seus filhos (14 12).

Agora criaremos nossas funções de custo (g) e heurística (h), a função h recebe um estado e retorna seu valor heurístico, e a função g recebe o custo total atual e o custo de um estado filho o qual se esta avaliando, e retorna o somatório de ambos.

Para nosso exemplo com o estado :A passando para a função h retornará o valor 30 e a função g, pegando como exemplo o estado :B para avaliar e passando o custo total atual como 0 teremos (0 + 12).

A nossa função de avaliação recebera o custo do estado que esta sendo avaliado, o estado que esta sendo avaliado, e o custo total atual e irá aplica a soma da função g e h.


A proxíma função get-costs é responsável por calcular o custo, usando a função de avaliação, para ir a cada estado filho do estado atual, retornando todos os custos em uma lista. Tomando como custo total atual 10 e o estado atual :A, a função retornará (54 52).


A função get-next-state recebe o estado atual e os custos de seus estados filhos, e retorna o estado filho que teve o menor custo calculado pela função get-costs, como teve o menor custo, esse estado será o próximo do caminho.


A função get-real-cost soma o custo atual do caminho com o custo do próximo estado retornado pela get-next-state, para ir guardando o custo total do caminho.


E agora a função goal-test recebe um estado e apenas verifica se o estado é o objetivo.


A função principal do algoritmo, search-A*, recebendo apenas um estado como parâmetro, que será o estado inicial :A, irá realizar uma chamada recursiva passando o estado, o custo total atual como 0, e um vetor vazio onde irá guardar os estado que farão parte do caminho (linha 2).

Primeiro testa se o estado atual é o ojetivo (linha 4), se não for, verifica se o estado possui estados filhos (linha 8), caso possui, irá pegar o custo para ir para cada um dos estado filhos em uma lista costs (linha 9), após isso, irá pegar o estado filho com menor custo get-nest-state (linha 10).

Depois de descobrir o estado de menor custo, faz uma chamada recursiva passando o estado retornado de menor custo, next-state, como estado atual, o calculo do custo como custo total atual, e o vetor com o estado inserido, para o próximo processamento (linha 11).
Executando essas ações recursivamente até encontrar o estado objetivo (linha 4), ao encontrar o estado objetivo apenas vai inseri-lo no vetor onde estão os estados do caminho, imprimir o caminho encontrado e o custo total do caminho.

E a função inicial do algoritmo que vai chamar a search-A*

Se rodarmos o algoritmo com o exemplo feito, teremos a seguinte saida:

[:A :C :E :D :G]
43

Que é o caminho mais curto encontrado pelo algoritmo e o custo total do caminho.

Uma questão que ficou em aberto nesse exemplo é quando o algoritmo encontrar um estado sem filhos, simplesmente irá parar, uma solução pode ser implmentar uma forma de retroceder até um estado que tenha estados filhos para continuar o processo.


Conclusão

O objetivo é só demostrar uma alternativa de implementação e como resolvi os trabalhos em Clojure, além de praticar o desenvolvimento nessa tecnologia que estou estudando. Não entrei em detalhes sobre a linguagem, espero escrever mais sobre futuramente, também como irá surgir novos trabalhos do curso tentarei resolvê-los utilizando Clojure e se possível escrever algo sobre também como forma de estudar.

O código completo podem ver aqui

Dúvidas, sugestões… podem deixar comentários, e compartilhar caso gostou :D.

comments powered by Disqus