ANHANGUERA EDUCACIONAL FACULDADE DE CIÊNCIA DA COMPUTAÇÃO
PAULO RENATO KINJO RA1299102205
[email protected]
ATIVIDADE PRATICA SUPERVISIONADA INTELIGENCIA ARTIFICIAL DIJKSTRA EM ASP.NET MVC 5
Campo Grande 2015
2
PAULO RENATO KINJO RA1299102205
ATIVIDADE PRATICA SUPERVISIONADA INTELIGENCIA ARTIFICIAL DIJKSTRA EM ASP.NET MVC 5
Atividade Pratica Supervisionada da disciplina Inteligência Artificial da Faculdade de Ciência da Computação da Anhanguera Educacional.
Campo Grande 2015
SUMÁRIO
1 2 3 4 5 6 7 8 9
INTRODUÇÃO ...................................................................................................... 4 O ALGORITMO .................................................................................................... 4 PROJETO MVC ..................................................................................................... 4 MODELO ................................................................................................................ 6 CONTROLE ........................................................................................................... 9 VISAO ................................................................................................................... 16 EXECUÇÃO ......................................................................................................... 17 CONCLUSÃO....................................................................................................... 19 REFERÊNCIAS ................................................................................................... 19
4
1 INTRODUÇÃO
Um dos Algoritmos mais utilizado e mais conhecido por toda a comunidade de tecnologia da informação é o algoritmo de Esger Dijkstra (1930-2002), cientista da computação natural de Rotedã na Holanda, que ficou conhecido mundialmente por suas contribuições na área de algoritmos e programas, linguagens de computação, sistemas operacionais e processamento distribuído. Este documento tem como objetivo apresentar um desenvolvimento simples do algoritmo de Dijkstra, para calcular o menor caminho de um ponto ao outro, mas especificamente, de uma cidade a outra. Para fins de demonstração serão utilizadas as tecnologias Asp.Net MVC 5, Entity Framework 6, e a ferramenta Visual Studio 2015 Community. 2
O ALGORITMO Com o objetivo de calcular o caminho mínimo de um vértice (cidade) a outro em um
grafo (mapa) pode-se através de um algoritmo que calcula o menor caminho solucionar tal problema de maneira elegante e eficiente, este algoritmo é conhecido como Dijkstra. Primeiro deve-se escolher um vértice como origem e outro como destino final, este algoritmo testa cada uma das arestas (estradas) que ligam os vértices do grafo, somando os seus pesos (quilômetros de distância), objetivando no final a menor soma entre a origem e o destino. Este algoritmo pode ser utilizado sobre grafos orientados (dígrafos), ou não, e admite que todas as arestas possuam pesos não negativos, sendo esta restrição perfeitamente aceitável, por exemplo, no contexto de um mapa de cidades onde normalmente as estradas (arestas) representam a distância ou tempo médio de percurso.
3
PROJETO MVC Para este projeto, na ferramenta Visual Studio 2015, foi criado um novo projeto com as
configurações apresentadas nas figuras 1 e 2.
5
Figura 1 – Novo Projeto ASP.NET Web Application.
Figura 2 – Escolha do template MVC.
6
É necessário observar que na figura 2, existe a opção de configuração de autenticação (Botão Change Authentication), o Visual Studio 2015, apresenta a possibilidade de configurar diversos mecanismos de segurança voltado para diferentes tipos de projetos. Por padrão a configuração de autenticação selecionada pelo Visual Studio 2015 é a configuração da figura 3.
Figura 3 – Configuração inicial de autenticação do projeto.
Sendo este projeto o calculo do menor caminho em um mapa para o desenvolvimento do algoritmo Dijkstra, não se faz necessária uma configuração de autenticação inicial, sendo assim a opção sem autenticação (No Authentication) será marcada para este projeto. 4 MODELO Seguindo as praticas do padrão arquitetural MVC (Mode, View, Controller), serão criadas as classes de domínio que representam as regras de negócio da aplicação. A classe Cidade, da listagem 1, foi definida de forma sucinta com as propriedades CidadeId (identificador da tabela cidade no banco de dados), Nome, UF, Distância, Visitada, CidadeAnterior e Estradas. As propriedades Nome e UF devem ser armazenadas no banco de dados, para possibilitar uma manutenção adequada de cadastros de cidades e estados. Estas propriedades estão anotadas ([Display] e [Required]) com algumas configurações para ajudar na validação dos campos nas páginas de cadastros, edição e deleção das mesmas. As propriedades, Distancia, Visitada e Cidade anterior recebem uma anotação particular “[NotMapped]” que indica ao Entity Framework, que essas propriedades não devem ser persistidas ou mapeadas para uma tabela no banco de dados, visto que, tais
7
propriedades são consideradas apenas como um auxilio para a implementação do algoritmo de Dijkstra que será apresentado mais adiante. Por fim a propriedade Estradas, que representa uma lista de estradas, foi declarada na classe Cidade, para representar um mapeamento relacional no banco de dados, haja vista que, cada cidade possui uma ou mais estradas que se ligam a elas. Esta definição permite que ao realizar uma consulta de cidade no banco de dados, o Entity seja capaz de trazer todas as estradas que possuem relacionamento com as respectivas cidades. Listagem 1: Cidade Model
A classe Estrada, da listagem 2, foi definida de forma sucinta com as propriedades EstradaId (identificador da tabela estrada no banco de dados), Custo, OrigemId, DestinoId, Origem e Destino. Todas as propriedades desta classe serão persistidas no banco de dados, observando apenas que as propriedades OrigemId e DestinoId, representam atributos chave estrangeira no banco de dados, e as propriedades Origem e Destino, como na classe Cidade, são utilizadas para que, quando for realizada uma consulta no banco de dados o Entity recupere as cidades que estão relacionadas a estas estradas e assim através da orientação a objetos, seja possível acessar as propriedades de cada Cidade. Importante observar que uma estrada possui sempre uma cidade origem, uma cidade destino e um custo para trafegar de uma cidade a outra.
8
Listagem 2: Estrada Model
Definidas as classes Cidade e Estrada, deve se definir outra classe, para representar o mapa, como apresenta a listagem 3, onde por via de regra um mapa possui uma lista de cidades e uma lista de estradas. Listagem 3: PKinMap Model
Neste ponto a classe que representa o mapa apresentada na listagem 3, chama-se PKinMap, um nome fictício para representar o nome da aplicação desenvolvida. Toda essência do problema até este ponto foi modelada, foram criados os modelos de cidades, estradas e o mapa propriamente dito, ou seja, todo o domínio da aplicação já está pronto e todas as regras de uso do sistema estão definidas. A listagem 4, apresenta a classe de configuração do contexto do banco de dados que será gerenciado pelo o Entity Framework (Este framework pode ser baixado e instalado no projeto através do NuGet).
9
Listagem 4: EFContext Model
De forma abstrata, o Entity Framework fará todo o gerenciamento da persistência e do relacionamento das classes Cidade e Estrada, que conforme a listagem 4 serão mapeadas para o banco de dados. Observe que a classe PKinMap, não foi declarada no contexto do banco de dados, isso por que está classe é utilizada apenas para o desenvolvimento do algoritmo de Dijkstra, e logicamente a classe PKinMap pode receber em sua lista de Cidades e Estradas, todas a Cidades e Estradas que estão no banco de dados através de uma consulta via o contexto de banco de dados definido como será apresentado mas adiante. 5 CONTROLE Com o domínio definido e pronto para uso, o próximo passo é criar as classes de controle de cidades e estradas. Por padrão o Visual Studio 2015, cria alguns controles para possibilitar um inicio rápido de desenvolvimento. Neste projeto apenas a classe HomeController foi deixada, outros controles que o Visual Studio criou foram excluídos do projeto. Sendo assim a classe HomeController apresentada na listagem 5 mostra as variáveis que serão utilizadas para manipular esta classe. Listagem 5: HomeController Controle
Foram declaradas, uma variável denominada db (data base), que faz referência ao contexto do banco de dados definido no domínio da aplicação e uma variável _Map que faz referência ao mapa da aplicação definido na camada de modelo. O controle é responsável por realizar a intermediação entre as camadas de visão (view) e de modelo da aplicação, sendo assim no Asp.Net MVC, cada método do controle que retorna
10
um ActionResult, pode representar na camada de visão uma página da aplicação. A listagem 6 apresenta as actions definidas na classe HomeController. Listagem 6: HomeController Controle
Como mostra a listagem 6, a classe HomeController possui duas actions, porem somente a action chamada Index, possui uma página na aplicação, está página representa a página inicial. A action Map, foi criada exclusivamente para realizar a inclusão de uma PartialView, ou seja, uma página parcial que será injetada na página principal, está página parcial possui apenas o trecho de código responsável por apresentar a busca de uma cidade origem a uma cidade destino no Google Maps, como será mostrado mais adiante. Finalmente na classe HomeController são utilizados alguns métodos auxiliares para carregar o mapa (classe PKinMap), calcular o menor caminho, e montar a url que faz a busca no Google Maps, a listagem 7 apresenta esses métodos.
11
Listagem 7: HomeController Controle
12
O método mais importante é o chamado CalcularMenorCaminho, que recebe como parâmetro, uma cidade origem e uma cidade destino. Seguindo o raciocínio para o desenvolvimento do algoritmo de Dijkstra, primeiramente é declarada uma variável que representa a cidade atual, e está recebe a cidade origem para que se inicie o algoritmo tendo como cidade atual a cidade origem e em seguida a distância da mesma recebe o valor zero (notar que o método CarregarMapa() chama o método ResetarCidade() onde este configura todas as cidades com a distância tendo o maior valor inteiro possível). Neste ponto assume-se que todas as cidades possuem uma distância configurada com o maior valor possível, para que o algoritmo possa calcular o caminho menor da cidade origem que possui distância igual a zero até a cidade destino. Observe que a origem é a única cidade com distância igual a zero e todas as demais cidades possuem a mesma distância sendo esta o maior valor inteiro possível da linguagem Csharp. O segundo passo é o laço de repetição while, que é executado enquanto houver na lista de estradas do mapa alguma cidade origem/destino que possua a propriedade Visitada igual a
13
falso, ou seja, enquanto houver qualquer cidade que ainda não foi visitada pelo algoritmo de Dijkstra. Dentro do laço while, ou seja, se ainda existe ao menos uma cidade origem/destino na lista de estradas que ainda não foi visitada, uma variável auxiliar é declarada e chamada estradas. Esta variável recebe uma lista de estradas onde a cidade origem é a cidade atual, e que possua como cidade destino somente as cidades ainda não visitadas. No passo 3 do algoritmo, para cada estrada retornada seguindo a regra anterior, o algoritmo define uma variável para representar a cidade destino que está sendo analisada atualmente dentro do laço de repetição foreach, em seguida é realizada a checagem se a distância desta cidade (aqui a cidade destino conforme algoritmo da listagem 7) é maior que a distância da cidade atual mais o custo da estrada que liga as duas. Caso verdadeiro a distância da cidade sendo analisada recebe o valor da distância da cidade atual mais o custo da estrada que liga as duas, e começa a fazer referência à cidade atual como sendo a sua cidade anterior. Por fim a cidade atual é configurada como visitada, e passa a referenciar a cidade a adjacente a ela onde é escolhida a primeira cidade adjacente que não foi visitada e que tenha o menor custo na estrada. Então todo o processo se repete. Observe a figura 4 como uma ilustração de como seria uma grafo de cidades.
Figura 4 – Grafo de cidades.
Por exemplo, para ir de Ribas do Rio Pardo a Campo Grande, o algoritmo funciona da seguinte forma. O método CalcularMenorCaminho, recebe como parâmetro a cidade Ribas do Rio Pardo como origem, e a cidade Campo Grande como Destino. No primeiro passo a
14
variável cidade atual recebe como referencia a cidade origem (Ribas do Rio Pardo), e configura a sua distância com o valor zero. No passo dois o laço while verifica se na lista de cidades existe alguma cidade que possui o estado “Visitada” como falso, e então se inicia o laço, visto que, a cidade Campo Grande ainda não foi visitada. Em seguida, dentro do laço, a variável estradas é definida e recebe todas as estradas que possuem como cidade origem a cidade Ribas do Rio Pardo, no caso apenas uma estrada será retornada como mostra a figura 4 acima, veja que existe uma seta apenas, partindo de Ribas do Rio Pardo à Campo Grande. No próximo passo o laço de repetição foreach que neste exemplo será executado apenas uma vez, haja vista, a quantidade de estradas retornadas anteriormente foi apenas uma, define uma variável cidade para representar a cidade destino da estrada atual sendo neste exemplo Campo Grande. Então é verificado se a distância da cidade sendo analisada (Campo Grande) é maior que a distância da cidade atual (Ribas do Rio Pardo) mais o custo da estrada. Observe que Campo Grande esta configurada com o maior valor inteiro possível da linguagem CSharp, e a cidade atual que é Ribas do Rio Pardo esta configurada com o valor zero definido no inicio do algoritmo. O custo da estrada como mostra a figura 4 é de 97 km, sendo assim o valor da distância de Campo Grande é maior que 97 (0 + 97) então a cidade sendo analisada (Campo Grande) configura a sua distancia como sendo 97, e diz que ela partiu de Ribas do Rio Pardo (configura a propriedade CidadeAnterior). Por fim a cidade atual (Ribas do Rio Pardo) é marcada como visitada e o algoritmo busca todas as cidades adjacentes a cidade atual que ainda não tenham sido visitadas, neste exemplo a única cidade adjacente e que ainda não tenha sido visitada é Campo Grande, então a variável atual passa a referenciar a cidade Campo Grande e o algoritmo se repete. Para finalizar, as figuras 5 e 6, apresentam como devem ser criados os controladores Cidade e Estado, usando o template fornecido pelo Visual Studio, que automaticamente configura a aplicação para acessar o contexto definido no domínio da aplicação. Observe que a opção selecionada na figura 5 é a opção “MVC 5 Controller with views, using Entity Framework”, este template realiza a configuração de um CRUD (Create, Read, Update, Delete) para as classes de domino, e automaticamente cria todas as páginas necessárias para a utilização do mesmo.
15
Figura 5 – Adicionando Scaffold de controlador usando Entity.
Figura 6 – Configurando a classe de domínio para a criação do controlador
16
6 VISAO Como o Visual Studio criou todas as views referentes aos controles CidadesController e EstradasController, será apresentada apenas a view Index, do HomeController que é responsável por carregar a PartialView que apresenta o mapa do Google Maps. As Listagens 8 e 9 apresentam o código referente a estas views. Listagem 8: Index View(HomeController)
17
É importante observar o script acrescentado na listagem 8 que é responsável por chamar a action da classe HomeController que retorna a PartialView definida na listagem 9 e apresenta no corpo da View da listagem 8 na div MapContent. Listagem 9: Map View(HomeController)
7 EXECUÇÃO Esta aplicação por padrão esta definida para excluir e recriar o banco de dados todas as vezes que a aplicação iniciar. O arquivo Global.asax esta definido na listagem 10. Listagem 10: Global.asax
Em casos em que este comportamento não for desejado, deve se apenas comentar a linha de configuração: Database.SetInitializer(new DropCreateDatabaseAlways());
18
Assim o banco de dados não será mais excluído e recriado. Este comportamento foi configurado para que fosse possível utilizar a action ScriptCidadesCampoGrande da classe HomeController, que executa um script
no banco de dados com uma determinada
configuração, observe a listagem 11. Listagem 11: HomeController Controle
Assim
quando
iniciar
a
aplicação
podemos
acessar
a
url
/Home/ScriptCidadesCampoGrande. O método será então invocado, e ao final a aplicação ira redirecionar para a página inicial, e o banco de dados irá refletir a figura 4. Um exemplo da aplicação final é mostrado na figura 7.
19
Figura 7 – Exemplo da aplicação final.
8 CONCLUSÃO O algoritmo de Dijkstra é simples e poderoso. Com a ajuda das linguagens CSharp e Linq, buscar e manipular as listas de cidades e estradas, mostrou-se algo trivial. Com o entendimento consolidado deste algoritmo, é possível entender mais a fundo, a maioria das aplicações que precisão lidar com o problema de encontrar o menor caminho entre um ponto e outros, ou até mesmo o caminho menos movimentado em uma cidade por exemplo. 9 REFERÊNCIAS [1] https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra : Acessado em 24/09/2015.
