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
