<div dir="ltr">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. <br></div><div class="gmail_extra">
<br><br><div class="gmail_quote">2013/9/21 Bruno Buss <span dir="ltr"><<a href="mailto:bruno.buss@gmail.com" target="_blank">bruno.buss@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Oi Hernan,<div><br></div><div>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.</div>
<div><br></div><div>[ ]'s</div></div><div class="HOEnZb"><div class="h5"><div class="gmail_extra"><br><br><div class="gmail_quote">2013/9/21 Hernan Lopes <span dir="ltr"><<a href="mailto:hernanlopes@gmail.com" target="_blank">hernanlopes@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div><div></div>Bruno,<br><br>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.<br>
Se não for isso, ignore <br>
</div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/9/21 Bruno Buss <span dir="ltr"><<a href="mailto:bruno.buss@gmail.com" target="_blank">bruno.buss@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Olá Hernan,<div><br></div><div>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.</div>
<div>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 ;)</div>
<div><br></div><div>[ ]'s</div><div><br></div></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/9/20 Hernan Lopes <span dir="ltr"><<a href="mailto:hernanlopes@gmail.com" target="_blank">hernanlopes@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr"><div>Blabos,<br><br>Se quiser encontrar o menor caminho vc precisa do algoritmo A* pra isso, A (estrela) para calcular<br>
<br><a href="http://en.wikipedia.org/wiki/A*_search_algorithm" target="_blank">http://en.wikipedia.org/wiki/A*_search_algorithm</a><br>
<br>Video:<br><br><a href="http://www.youtube.com/watch?v=J-ilgA_XNI0" target="_blank">http://www.youtube.com/watch?v=J-ilgA_XNI0</a><br><a href="http://www.youtube.com/watch?v=19h1g22hby8" target="_blank">http://www.youtube.com/watch?v=19h1g22hby8</a><br>
<br>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. <br>
</div></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/9/20 Blabos de Blebe <span dir="ltr"><<a href="mailto:blabos@gmail.com" target="_blank">blabos@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Opa,<div><br></div><div>@Buss @Carlos, correto e correto.</div><div><br></div><div>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.</div>
<div><br></div><div>Não é a melhor solução, mas é uma solução suficientemente boa dentro dos parâmetros que eu preciso neste momento.</div><div><br></div><div>Eu to usando SQLite por enquanto, mas o Postgres não tem algo assim embutido não?</div>
<div><br></div><div>Fico grato por estar numa lista onde sempre encontro várias dicas cada uma melhor que a outra.</div><div><br></div><div>[]'s</div></div><div><div><div class="gmail_extra">
<br><br><div class="gmail_quote">
2013/9/20 Bruno Buss <span dir="ltr"><<a href="mailto:bruno.buss@gmail.com" target="_blank">bruno.buss@gmail.com</a>></span><br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div dir="ltr">Oi Blabos,<div><br></div><div>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.</div>
<div><div><br></div><div>[ ]'s<br><div class="gmail_extra"><div><div><br><br><div class="gmail_quote">2013/9/20 Blabos de Blebe <span dir="ltr"><<a href="mailto:blabos@gmail.com" target="_blank">blabos@gmail.com</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">Opa,<div><br></div><div>Nos capítulos anteriores...</div><div><br></div><div>Eu procurei ajuda sobre como fazer uma conta e como executar essa conta de forma assíncrona em relação à aplicação web.</div>
<div><br></div><div>Os donos dos resultados dessa conta relacionam-se entre si de forma que eu modelei esse relacionamento através de um grafo direcionado.</div><div><br></div><div>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.</div>
<div><br></div><div>É a partir dessa informação que eu *começo* o meu trabalho.</div><div><br></div><div>Obrigado a todos que contribuíram com sugestões que eu já usei, e com sugestões que ainda vou usar.</div>
<div><br></div><div>[]'s</div></div><div><div><div class="gmail_extra"><br><br><div class="gmail_quote">2013/9/19 Wagner Arbex <span dir="ltr"><<a href="mailto:arbex@arbex.pro.br" target="_blank">arbex@arbex.pro.br</a>></span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Opa, tb fiquei curioso sobre a sua aplicação, Blabos.<br>
<br>
Fiz uma aplicação, na mão, em que precisava achar os componentes<br>
conexos e os ciclos e, depois, fiz uma outra versão usando as rotinas<br>
do módulo Graph-0.96 (<a href="http://search.cpan.org/perldoc?Graph" target="_blank">http://search.cpan.org/perldoc?Graph</a>), que vc tb<br>
citou. Ainda não gostei do que fiz e estou trabalhando em uma versão<br>
mais "sofisticada", tentando aplicar aprendizado de máquina, fazendo<br>
com que a rotina "adquira conhecimento" sobre os dados que recolhe ao<br>
longo de cada componente conexo que percorre.<br>
<br>
Posso estar enganado, mas não me lembro de ter visto ninguém falando<br>
sobre grafos a lista, por isso estou fiquei curioso qto à sua<br>
aplicação.<br>
<br>
Acho que existem outras questões que vc pode querer considerar no<br>
caminho entre dois vértices em um grafo. P. ex., só existe um caminho<br>
entre qq dois nós? Interessa saber se existe outro caminho? O que está<br>
sendo procurado é qq caminho ou um caminho específico, p. ex., o<br>
caminho mais curto ou caminho mais rápido? Existem "pesos" nas arestas<br>
entre os dois nós? Lembrando que uma árvore é um caso particular de<br>
grafo, o grafo é realmente um grafo ou uma árvore?<br>
<br>
Gostei da conversa e se eu achar que posso ajudar, vou tentar<br>
contribuir com alguns centavos.<br>
<br>
[]s, W.<br>
<br>
2013/9/19 Hernan Lopes <<a href="mailto:hernanlopes@gmail.com" target="_blank">hernanlopes@gmail.com</a>>:<br>
<div><div>> Blabos, o que vc quer fazer?<br>
><br>
> 2013/9/19 Blabos de Blebe <<a href="mailto:blabos@gmail.com" target="_blank">blabos@gmail.com</a>><br>
>><br>
>> E aí pessoal,<br>
>><br>
>> Estou precisando calcular a distância entre nós em um grafo direcionado.<br>
>><br>
>> É aquele algoritmo clássico que tem no Cormen ou qualquer livro decente do<br>
>> ramo.<br>
>><br>
>> No cpan eu achei de interessante:<br>
>><br>
>> <a href="https://metacpan.org/module/JHI/Graph-0.96/lib/Graph.pod" target="_blank">https://metacpan.org/module/JHI/Graph-0.96/lib/Graph.pod</a><br>
>> <a href="https://metacpan.org/module/Paths::Graph" target="_blank">https://metacpan.org/module/Paths::Graph</a><br>
>> <a href="https://metacpan.org/module/Boost::Graph" target="_blank">https://metacpan.org/module/Boost::Graph</a><br>
>> <a href="https://metacpan.org/module/DBIx::Path" target="_blank">https://metacpan.org/module/DBIx::Path</a><br>
>><br>
>> Gostaria de ouvir a opinião de vcs a respeito, e se tiverem outras<br>
>> sugestões, sou todo ouvidos.<br>
>><br>
>> []'s<br>
>><br>
>><br>
>><br>
>> =begin disclaimer<br>
>> Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
>> SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
>> L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
>> =end disclaimer<br>
>><br>
><br>
><br>
> =begin disclaimer<br>
> Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
> SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
> L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
> =end disclaimer<br>
><br>
<br>
<br>
<br>
</div></div><span><font color="#888888">--<br>
Wagner Arbex, DSc<br>
Bioinformática e modelagem matemática e computacional de biossistemas<br>
<br>
<a href="http://www.arbex.pro.br/" target="_blank">http://www.arbex.pro.br/</a><br>
</font></span><div><div>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
</div></div></blockquote></div><br></div>
</div></div><br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br></div></div>Bruno C. Buss<br><a href="http://www.brunobuss.net" target="_blank">http://www.brunobuss.net</a>
</div></div></div></div>
<br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br></div>
</div></div><br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br></div>
</div></div><br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>Bruno C. Buss<br><a href="http://www.brunobuss.net" target="_blank">http://www.brunobuss.net</a>
</div>
</div></div><br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br></div></div></div></div>
<br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org" target="_blank">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br><br clear="all"><div><br></div>-- <br>Bruno C. Buss<br><a href="http://www.brunobuss.net" target="_blank">http://www.brunobuss.net</a>
</div>
</div></div><br>=begin disclaimer<br>
Sao Paulo Perl Mongers: <a href="http://sao-paulo.pm.org/" target="_blank">http://sao-paulo.pm.org/</a><br>
SaoPaulo-pm mailing list: <a href="mailto:SaoPaulo-pm@pm.org">SaoPaulo-pm@pm.org</a><br>
L<<a href="http://mail.pm.org/mailman/listinfo/saopaulo-pm" target="_blank">http://mail.pm.org/mailman/listinfo/saopaulo-pm</a>><br>
=end disclaimer<br>
<br></blockquote></div><br></div>