Olá Hernan, Encontrar caminho mínimo em um grafo, seja direcionado ou não, seja com arestas com peso ou não, é um problema já bem resolvido e não necessita de A* e/ou heurística nenhuma. Talvez a utilização do A* e/ou heurísticas especificas sejam necessárias dependendo do tamanho do grafo, qual a configuração exata do seu problema e suas restrições de tempo e espaço, mas na forma geral do problema não é necessário nenhuma heurística ;)
[ ]'s 2013/9/20 Hernan Lopes <[email protected]> > Blabos, > > Se quiser encontrar o menor caminho vc precisa do algoritmo A* pra isso, A > (estrela) para calcular > > http://en.wikipedia.org/wiki/A*_search_algorithm > > Video: > > http://www.youtube.com/watch?v=J-ilgA_XNI0 > http://www.youtube.com/watch?v=19h1g22hby8 > > A partir de um nó tem que verificar quais os proximos nós e somar a > distancia e usar uma heuristica que indique qual a melhor opcao entre eles > pra chegar ate o final, por ex veriricar a distancia de N nós filhos dos > nós diretos do ponto inicial e comparar qual posicao estaria segundo esse > caminho e qual a distancia até o final (seguindo esse caminho qual está > mais proximo do final?) dai vc pode tentar seguir esse caminho, mas se nao > der pra chegar la vc vai ter que olhar pra tras voltar e tentar uma outra > opcao. > > > 2013/9/20 Blabos de Blebe <[email protected]> > >> Opa, >> >> @Buss @Carlos, correto e correto. >> >> Nesse caso específico eu conscientemente abri mão da eficiência em prol >> do "já esta implementado". Foram 4 linhas usando o DBIx::Class + Graph, >> desde buscar todos os dados até encontrar o menor path. >> >> Não é a melhor solução, mas é uma solução suficientemente boa dentro dos >> parâmetros que eu preciso neste momento. >> >> Eu to usando SQLite por enquanto, mas o Postgres não tem algo assim >> embutido não? >> >> Fico grato por estar numa lista onde sempre encontro várias dicas cada >> uma melhor que a outra. >> >> []'s >> >> >> 2013/9/20 Bruno Buss <[email protected]> >> >>> Oi Blabos, >>> >>> Pelo o que você disse, no seu grafo as arestas não tem peso (ou todas >>> tem o mesmo peso, e.g. 1) e o que você quer fazer é contar a distância >>> entre 2 nós do grafo, então você pode utilizar um algoritmo mais simples >>> como uma busca em largura para calcular a distância entre dois nós. Se sua >>> representação do grafo for através de lista de adjacências, a BFS roda em >>> tempo linear no tamanho do grafo - O(n + m) - enquanto a melhor >>> implementação conhecida para o Dijkstra, com heap de fibonacci, fica em >>> (n*logn + m) apesar de ser bem mais complexa de implementar. >>> >>> [ ]'s >>> >>> >>> 2013/9/20 Blabos de Blebe <[email protected]> >>> >>>> Opa, >>>> >>>> Nos capítulos anteriores... >>>> >>>> Eu procurei ajuda sobre como fazer uma conta e como executar essa conta >>>> de forma assíncrona em relação à aplicação web. >>>> >>>> Os donos dos resultados dessa conta relacionam-se entre si de forma que >>>> eu modelei esse relacionamento através de um grafo direcionado. >>>> >>>> Eu só precisava saber a quantos nós cada um deles está um do outro, eu >>>> nem preciso do path em si. Um simples scalar( Graph::SP_Dijkstra( a, b ) ) >>>> - 1 já me dá isso. >>>> >>>> É a partir dessa informação que eu *começo* o meu trabalho. >>>> >>>> Obrigado a todos que contribuíram com sugestões que eu já usei, e com >>>> sugestões que ainda vou usar. >>>> >>>> []'s >>>> >>>> >>>> 2013/9/19 Wagner Arbex <[email protected]> >>>> >>>>> Opa, tb fiquei curioso sobre a sua aplicação, Blabos. >>>>> >>>>> Fiz uma aplicação, na mão, em que precisava achar os componentes >>>>> conexos e os ciclos e, depois, fiz uma outra versão usando as rotinas >>>>> do módulo Graph-0.96 (http://search.cpan.org/perldoc?Graph), que vc tb >>>>> citou. Ainda não gostei do que fiz e estou trabalhando em uma versão >>>>> mais "sofisticada", tentando aplicar aprendizado de máquina, fazendo >>>>> com que a rotina "adquira conhecimento" sobre os dados que recolhe ao >>>>> longo de cada componente conexo que percorre. >>>>> >>>>> Posso estar enganado, mas não me lembro de ter visto ninguém falando >>>>> sobre grafos a lista, por isso estou fiquei curioso qto à sua >>>>> aplicação. >>>>> >>>>> Acho que existem outras questões que vc pode querer considerar no >>>>> caminho entre dois vértices em um grafo. P. ex., só existe um caminho >>>>> entre qq dois nós? Interessa saber se existe outro caminho? O que está >>>>> sendo procurado é qq caminho ou um caminho específico, p. ex., o >>>>> caminho mais curto ou caminho mais rápido? Existem "pesos" nas arestas >>>>> entre os dois nós? Lembrando que uma árvore é um caso particular de >>>>> grafo, o grafo é realmente um grafo ou uma árvore? >>>>> >>>>> Gostei da conversa e se eu achar que posso ajudar, vou tentar >>>>> contribuir com alguns centavos. >>>>> >>>>> []s, W. >>>>> >>>>> 2013/9/19 Hernan Lopes <[email protected]>: >>>>> > Blabos, o que vc quer fazer? >>>>> > >>>>> > 2013/9/19 Blabos de Blebe <[email protected]> >>>>> >> >>>>> >> E aí pessoal, >>>>> >> >>>>> >> Estou precisando calcular a distância entre nós em um grafo >>>>> direcionado. >>>>> >> >>>>> >> É aquele algoritmo clássico que tem no Cormen ou qualquer livro >>>>> decente do >>>>> >> ramo. >>>>> >> >>>>> >> No cpan eu achei de interessante: >>>>> >> >>>>> >> https://metacpan.org/module/JHI/Graph-0.96/lib/Graph.pod >>>>> >> https://metacpan.org/module/Paths::Graph >>>>> >> https://metacpan.org/module/Boost::Graph >>>>> >> https://metacpan.org/module/DBIx::Path >>>>> >> >>>>> >> Gostaria de ouvir a opinião de vcs a respeito, e se tiverem outras >>>>> >> sugestões, sou todo ouvidos. >>>>> >> >>>>> >> []'s >>>>> >> >>>>> >> >>>>> >> >>>>> >> =begin disclaimer >>>>> >> Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >>>>> >> SaoPaulo-pm mailing list: [email protected] >>>>> >> L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >>>>> >> =end disclaimer >>>>> >> >>>>> > >>>>> > >>>>> > =begin disclaimer >>>>> > Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >>>>> > SaoPaulo-pm mailing list: [email protected] >>>>> > L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >>>>> > =end disclaimer >>>>> > >>>>> >>>>> >>>>> >>>>> -- >>>>> Wagner Arbex, DSc >>>>> Bioinformática e modelagem matemática e computacional de >>>>> biossistemas >>>>> >>>>> http://www.arbex.pro.br/ >>>>> =begin disclaimer >>>>> Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >>>>> SaoPaulo-pm mailing list: [email protected] >>>>> L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >>>>> =end disclaimer >>>>> >>>> >>>> >>>> =begin disclaimer >>>> Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >>>> SaoPaulo-pm mailing list: [email protected] >>>> L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >>>> =end disclaimer >>>> >>>> >>> >>> >>> -- >>> Bruno C. Buss >>> http://www.brunobuss.net >>> >>> =begin disclaimer >>> Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >>> SaoPaulo-pm mailing list: [email protected] >>> L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >>> =end disclaimer >>> >>> >> >> =begin disclaimer >> Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ >> SaoPaulo-pm mailing list: [email protected] >> L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> >> =end disclaimer >> >> > > =begin disclaimer > Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ > SaoPaulo-pm mailing list: [email protected] > L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> > =end disclaimer > > -- Bruno C. Buss http://www.brunobuss.net
=begin disclaimer Sao Paulo Perl Mongers: http://sao-paulo.pm.org/ SaoPaulo-pm mailing list: [email protected] L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> =end disclaimer
