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

Hernan Lopes hernanlopes at gmail.com
Sat Sep 21 00:06:00 PDT 2013


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

> 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 <hernanlopes at gmail.com>
>
>> 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 <bruno.buss at gmail.com>
>>
>>> 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
>>>
>>> =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
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130921/7cbcd52c/attachment-0001.html>


More information about the SaoPaulo-pm mailing list