sexta-feira, 20 de fevereiro de 2015

[Python] - Uniform Cost Search (UCS)

Olá pessoal, nesse post irei colocar a implementação do algoritmo Uniform Cost Search (UCS) em Python.

Caso você não lembre como funciona o algoritmo UCS, assista a esse vídeo:


O código está no Github, está todo comentado (comentários em inglês), bem simples de entender.


O grafo utilizado como exemplo para o teste foi esse:



Dentro do módulo "main.py", você poderá configurar algumas variáveis na chamada da função "run" tais como a variável "verbose" que indica se você quer que exiba mensagens, variável "time_sleep" para você ir acompanhando mais lentamente enfim. Veja só o exemplo de execução com a variável "verbose" ativada:

Realmente o menor custo é 10 de "S" para "G". O caminho seria esse: S -> d -> e -> r -> f -> G. Fica como tarefa exibir o caminho do menor custo :)

Quaisquer dúvidas deixem nos comentários, até a próxima.


Nenhum comentário: