[SP-pm] Distância entre nós em um grafo

Fri Sep 20 14:39:13 PDT 2013

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 <blabos at gmail.com>

> 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 <bruno.buss at gmail.com>
>
>> 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 <blabos at gmail.com>
>>
>>> 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 <arbex at arbex.pro.br>
>>>
>>>> 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 <hernanlopes at gmail.com>:
>>>> > Blabos, o que vc quer fazer?
>>>> >
>>>> > 2013/9/19 Blabos de Blebe <blabos at gmail.com>
>>>> >>
>>>> >> 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: SaoPaulo-pm at pm.org
>>>> >>  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: SaoPaulo-pm at pm.org
>>>> >  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: SaoPaulo-pm at pm.org
>>>>  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: SaoPaulo-pm at pm.org
>>>  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: SaoPaulo-pm at pm.org
>>  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: SaoPaulo-pm at pm.org
>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
> =end disclaimer
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130920/ea324276/attachment-0001.html>