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

Sat Sep 21 10:32:46 PDT 2013

O A* é uma das maneiras de resolver o problema. Pode ser bastante eficiente
dependendo da heurística.
Mas a eficiência pode variar de caso a caso dependendo de muitos fatores.
Com certeza tem um algoritmo melhor para cada caso. Não tem um unico
algoritmo que é bom em todas as situacões.

2013/9/21 Bruno Buss <bruno.buss at gmail.com>

> Oi Hernan,
>
> Você está correto quando você diz que é possível que ao utilizar o A* ou
> alguma heurística, você consiga calcular o menor caminho entre um par de
> vértices ou quase este menor caminho e geralmente tem uma complexidade de
> tempo menor que os algoritmos ótimos. Isso eu não discordo.
>
> O que eu não concordei foi quando no seu e-mail, você afirmou que era
> *necessário/preciso* utilizar A*/heurística para resolver esse problema.
> Essa informação é que, para os meus conceitos, não está correta.
>
>
> Antes de continuar, só para esclarecer alguns pontos sobre algoritmos e
> heurísticas:
>
> * Algoritmos ótimos:
> Algoritmos desenvolvidos com uma prova matemática, que garantem que
> independente do caso de entrada o algoritmo retornará o resultado ótimo
> para aquela instância.
>
> Vem também com uma complexidade de tempo bem definida, mesmo que nem
> sempre polinomial. (No caso no qual estamos discutindo, SSSP e ASPS, ambos
> tem algoritmos ótimos polinomiais).
>
>
> * Algoritmos aproximativos:
> Algoritmos desenvolvidos com uma prova matemática, que garantem uma
> resposta que esteja a uma distância \alpha do valor ótimo onde \alpha pode
> ser tanto aditivo (Resposta do Algoritmo <= OPT + \alpha) ou multiplicativo
> (Resposta do Algoritmo <= OPT * \alpha). É *importante ressaltar* que as
> garantias são do tipo "<=" ou seja, na instância (aka entrada) com a
> estrutura mais escrota possível (para o seu algoritmo) ele vai errar no
> máximo de um valor pré-determinado, porém em boa parte dos casos ele
> encontrara o valor ótimo ou algo muito mais próximo do que a folga
> estabelecida pelo \alpha.
>
> Vem também com uma complexidade de tempo bem definida, mesmo que nem
> sempre polinomial.
>
>
> * Heurísticas:
> Algoritmos desenvolvidos sem uma prova matemática para garantia de tempo e
> resultado. Apesar disso não querer dizer que eles não são eficientes ou
> encontram bons resultados, continuemos por favor.
> Heurísticas são altamente experimentais, já que não contem uma prova de
> corretude/completude matemática por trás e utilizam de bateria de testes -
> onde se conhece o resultado ótimo, ou melhor conhecido - para avaliar se
> uma heurística está boa ou não. Mas no fim das contas, a heurística pode
> retornar o resultado ótimo, algo perto, ou algo lá na tonga da mironga...
> não se tem nenhuma garantia, além da experimental de fato.
>
> Como as heurísticas "não se comprometem" a retornar o melhor resultado ou
> alguma garantia de distância do melhor resultado (como no caso dos alg.
> aproximativos), pode-se dar ao luxo de fazer um corte por tempo ou número
> de iterações. O que os torna computacionalmente viável para, por exemplo,
> instâncias *muito grandes* onde os algoritmos ótimos iriam demorar
> demais... e alguma resposta é melhor do que nenhuma.
>
>
>
>
> Agora veja bem, eu não sou contra heurísticas e nem desgosto delas. Elas
> são aplicáveis em diversos lugares (como o exemplo que citei em relação a
> instâncias muito grandes para os algoritmos ótimos) e devem estar sempre na
> sua "toolbox de solucionar problemas". Só discordo completamente em afirmar
> de cara que a melhor abordagem é um heurística, quando existem algoritmos
> ótimos e algoritmos aproximativos para o caso geral, existem diversos
> outros dentro dessas duas categorias com complexidades bem melhores ao se
> restringir a estrutura matemática da entrada (e.g. estou pra ver cidades
> que quando modeladas em grafos, de fato fiquem parecidas com um K_n), etc
> principalmente quando não se conhece dados básicos do problema como tamanho
> ou características estruturais.
>
> [ ]'s
>
> 2013/9/21 Hernan Lopes <hernanlopes at 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 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
>>>>
>>>>
>>>
>>
>> =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/1c787c1e/attachment-0001.html>