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

Bruno Buss bruno.buss at gmail.com
Fri Sep 20 23:34:42 PDT 2013 

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

> 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
>>
>>
>
> =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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130921/f0888887/attachment.html>

More information about the SaoPaulo-pm mailing list