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

Sat Sep 21 07:23:58 PDT 2013

Opa,

No meu caso, os nós não tem peso e o que eu preciso é a quantidade de nós
entre A e B necessariamente no menor path.

É um caso de estudo com expectativa de ter no máximo 1000 nós, uma força
bruta ainda resolve.

Os resultados desse estudo deverão guiar uma abordagem mais eficiente para
ser aplicada em casos 'on-the-wild'. Aí sim eu vou explorar tudo isso que
vocês estão acrescentando.

Meio que chover no molhado, isso, mas essas discussões aqui são bem
melhores que aulas.

[]'s

2013/9/21 Hernan Lopes <hernanlopes em gmail.com>

> A idéia do A* é encontrar o provavel melhor caminho com o menor custo
> computacional.
> Para calcular o melhor caminho vc vai precisar calcular todos e isso vai
> ter um custo bem alto.
> O ideal é misturar A* com djikstra olhando para os vertices proximos do
> inicio
>
> Diz mais ou menos o que eu falei mas em ingles:
>
> The Greedy Best-First-Search algorithm works in a similar way, except that
> it has some estimate (called a *heuristic*) of how far from the goal any
> vertex is. Instead of selecting the vertex closest to the starting point,
> it selects the vertex closest to the goal. Best-First-Search is *not*guaranteed to find a shortest path. However, it runs much quicker than
> Dijkstra’s algorithm because it uses the heuristic function to guide its
> way towards the goal very quickly. For example, if the goal is to the south
> of the starting position, Best-First-Search will tend to focus on paths
> that lead southwards
>
> Referencia/Stanford:
> http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html
>
> Nao sou eu que digo, ta escrito ai...
>
>
>
> 2013/9/21 Hernan Lopes <hernanlopes em gmail.com>
>
>> 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 em 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 em 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 em 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 em 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 em 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 em 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 em 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 em 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 em gmail.com>:
>>>>>>>>>> > Blabos, o que vc quer fazer?
>>>>>>>>>> >
>>>>>>>>>> > 2013/9/19 Blabos de Blebe <blabos em 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 em 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 em 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 em 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 em 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 em 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 em 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 em 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 em 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 em 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 em 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 em pm.org
>  L<http://mail.pm.org/mailman/listinfo/saopaulo-pm>
> =end disclaimer
>
>
-------------- Pr�xima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://mail.pm.org/pipermail/saopaulo-pm/attachments/20130921/93fef522/attachment-0001.html>