Eu já fiz muitos testes sobre relacionados a esse tema, e o A* sempre se saiu melhor para calcular a provavel melhor distancia... que não é necessariamente a menor mas está próxima de.
2013/9/21 Bruno Buss <[email protected]> > Oi Hernan, > > Mesmo no caso de grafos com arestas com peso (como no caso onde se modela > cidades como vértices e arestas como distância entre as duas cidades), > existem algoritmos ótimos e polinomiais para encontrar o menor caminho > entre dois vértices, não sendo *necessário/preciso* a utilização de > A*/heurísticas para encontrar o menor caminho no caso geral do problema. > > [ ]'s > > > 2013/9/21 Hernan Lopes <[email protected]> > >> Bruno, >> >> Como ele estava falando em ruas e mapas, e agora em grafos, e melhor >> caminho, me pareceu que os vertices seriam locais e haveria uma distância >> entre eles. Por isso a minha sugestão. >> Se não for isso, ignore >> >> >> 2013/9/21 Bruno Buss <[email protected]> >> >>> 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 >>> >>> >> >> =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
