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

Sat Sep 21 00:19:41 PDT 2013

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 at 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 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/795845d8/attachment-0001.html>