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

Bruno Buss bruno.buss at gmail.com
Sat Sep 21 07:34:55 PDT 2013


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


More information about the SaoPaulo-pm mailing list