{"id":987,"date":"2020-08-26T09:26:20","date_gmt":"2020-08-26T12:26:20","guid":{"rendered":"http:\/\/www.galirows.com.br\/meublog\/?p=987"},"modified":"2020-09-29T14:54:34","modified_gmt":"2020-09-29T17:54:34","slug":"proposta-de-trabalho-metodos-de-busca-para-resolver-um-labirinto","status":"publish","type":"post","link":"http:\/\/www.galirows.com.br\/meublog\/blog\/proposta-de-trabalho-metodos-de-busca-para-resolver-um-labirinto\/","title":{"rendered":"Proposta de trabalho &#8211; M\u00e9todos de busca para resolver um labirinto"},"content":{"rendered":"\n<p>A ideia desse trabalho \u00e9 implementar algoritmos para resolver um labirinto. M\u00e9todos de busca em largura e busca em profundidade s\u00e3o os mais simples para experimentar, mas tamb\u00e9m pode ser implementado o algoritmo de busca A*.<\/p>\n\n\n\n<p>\u00c9 normal aprender sobre a busca em largura e profundidade em disciplina de estrutura de dados, onde e dada uma \u00e1rvore e o algoritmo percorre a \u00e1rvore at\u00e9 uma n\u00f3 folha com o que se quer encontrar. <\/p>\n\n\n\n<p>O trabalho aqui proposto visa aprender a usar efetivamente esses m\u00e9todos de busca, onde n\u00e3o se tem uma \u00e1rvore para ser percorrida, sendo necess\u00e1rio construir a \u00e1rvore passo-a-passo, enquanto se &#8220;caminha&#8221; pelo labirinto.<\/p>\n\n\n\n<p>\u00c9 recomendado que a implementa\u00e7\u00e3o leve em considera\u00e7\u00e3o os passos para formula\u00e7\u00e3o de um problema, que consistem em:<\/p>\n\n\n\n<ul class=\"wp-block-list\"><li>Estado inicial: onde o agente come\u00e7a;<\/li><li>A\u00e7\u00f5es (fun\u00e7\u00e3o sucessor): poss\u00edveis a\u00e7\u00f5es que o agente pode executar <\/li><li>Resultado (modelo de transi\u00e7\u00e3o): dado um estado e uma a\u00e7\u00e3o, especifica um novo estado<ul><li>Result(S,a) = S\u2019<\/li><\/ul><\/li><li>Teste de Objetivo: determina se o estado \u00e9 objetivo ou n\u00e3o;<\/li><li>Custo de Caminho: dado um caminho (sequencia de transi\u00e7\u00f5es estado\/a\u00e7\u00e3o) determina um n\u00famero que \u00e9 o custo daquele caminho<ul><li>Na maioria dos problemas, a custo ser\u00e1 aditivo, sendo assim, o custo de um caminho \u00e9 a soma dos passos individuais<\/li><\/ul><\/li><li>Custo de Passo: a implementa\u00e7\u00e3o do custo de caminho envolve o custo de passo. Este recebe um estado, uma a\u00e7\u00e3o e um resultado e retorna um n\u00famero que \u00e9 o custo da a\u00e7\u00e3o<ul><li>StepCost(S,a,S\u2019) = n<\/li><\/ul><\/li><\/ul>\n\n\n\n<p>Existem diversos geradores de labirinto com c\u00f3digo fonte dispon\u00edvel na internet e uma possibilidade \u00e9 fazer uso desses geradores (o objetivo do trabalho e implementar os m\u00e9todos de busca para solucionar o labirinto). Essas solu\u00e7\u00f5es j\u00e1 prontas de gera\u00e7\u00e3o de labirinto s\u00e3o interessantes para aproveitar e estudar recursos de programa\u00e7\u00e3o. <\/p>\n\n\n\n<p>Para aqueles que preferem fazer algo mais simples, segue uma recomenda\u00e7\u00e3o sobre o ambiente do labirinto: o m\u00e9todo deve executar em um ambiente composto por uma matriz quadrada de ordem <em>n (at\u00e9 10)<\/em> e nula. C\u00e9lulas com valor 1 s\u00e3o por onde \u00e9 poss\u00edvel se mover, c\u00e9lulas com valor 0 (zero) representar\u00e3o lugares que o agente n\u00e3o poder\u00e1 percorrer (paredes). A c\u00e9lula com valor 2 representa o local de onde o agente iniciar\u00e1 e a c\u00e9lula de valor 3 o lugar onde ele precisa chegar. Se as paredes forem adicionadas aleatoriamente, um cuidado que precisa ser tomado \u00e9 que exista uma solu\u00e7\u00e3o para o problema e isso n\u00e3o \u00e9 f\u00e1cil, por isso recomendo criar labirintos est\u00e1ticos.<\/p>\n\n\n\n<p>No caso de utilizar mapas est\u00e1ticos, elabore alguns labirintos para avaliar. A figura abaixo ilustra um labirinto. Veja que existem v\u00e1rias formas de alcan\u00e7ar o objetivo. Coloquei tamb\u00e9m um caminho circular para dificultar (o algoritmo pode ficar preso no ciclo, dependendo da implementa\u00e7\u00e3o).<\/p>\n\n\n\n<p class=\"has-text-align-center\"><img loading=\"lazy\" decoding=\"async\" width=\"416\" height=\"218\" class=\"wp-image-989\" style=\"width: 416px;\" src=\"http:\/\/www.galirows.com.br\/meublog\/wp-content\/uploads\/2020\/08\/mapaBusca.png\" alt=\"\" srcset=\"http:\/\/www.galirows.com.br\/meublog\/wp-content\/uploads\/2020\/08\/mapaBusca.png 416w, http:\/\/www.galirows.com.br\/meublog\/wp-content\/uploads\/2020\/08\/mapaBusca-300x157.png 300w, http:\/\/www.galirows.com.br\/meublog\/wp-content\/uploads\/2020\/08\/mapaBusca-150x79.png 150w\" sizes=\"auto, (max-width: 416px) 100vw, 416px\" \/><\/p>\n\n\n\n<p>Para implementa\u00e7\u00e3o do m\u00e9todo de busca, considere o custo de passo com valor igual para qualquer movimenta\u00e7\u00e3o e que ser\u00e1 permitida a movimenta\u00e7\u00e3o em quadro dire\u00e7\u00f5es (cima, baixo, esquerda e direita). A implementa\u00e7\u00e3o deve ter uma fun\u00e7\u00e3o sucessor e uma fun\u00e7\u00e3o de teste de objetivo.<\/p>\n\n\n\n<p>O v\u00eddeo a seguir \u00e9 uma explica\u00e7\u00e3o de como aplicar a elabora\u00e7\u00e3o da \u00e1rvore de busca para esse trabalho.<\/p>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Exemplifica\u00e7\u00e3o dos m\u00e9todos de busca para um labirinto\" width=\"685\" height=\"514\" src=\"https:\/\/www.youtube.com\/embed\/C8otuQJB60c?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n","protected":false},"excerpt":{"rendered":"<p>A ideia desse trabalho \u00e9 implementar algoritmos para resolver um labirinto. M\u00e9todos de busca em largura e busca em profundidade s\u00e3o os mais simples para experimentar, mas tamb\u00e9m pode ser implementado o algoritmo de busca A*. \u00c9 normal aprender sobre a busca em largura e profundidade em disciplina de estrutura de dados, onde e dada [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"_monsterinsights_skip_tracking":false,"_monsterinsights_sitenote_active":false,"_monsterinsights_sitenote_note":"","_monsterinsights_sitenote_category":0,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-987","post","type-post","status-publish","format-standard","hentry","category-offtopic"],"aioseo_notices":[],"amp_enabled":true,"_links":{"self":[{"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/posts\/987","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/comments?post=987"}],"version-history":[{"count":5,"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/posts\/987\/revisions"}],"predecessor-version":[{"id":1014,"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/posts\/987\/revisions\/1014"}],"wp:attachment":[{"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/media?parent=987"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/categories?post=987"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.galirows.com.br\/meublog\/wp-json\/wp\/v2\/tags?post=987"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}