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
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.b...@gmail.com
Oi Hernan,
Mesmo no caso de grafos com arestas com peso (como no
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
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
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
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.
Não use cpan pra um problema simples
Não resolva problemas simples que já foram resolvidos.
=begin disclaimer
Sao Paulo Perl Mongers: http://sao-paulo.pm.org/
SaoPaulo-pm mailing list: SaoPaulo-pm@pm.org
Lhttp://mail.pm.org/mailman/listinfo/saopaulo-pm
=end disclaimer
2013/9/21 Bruno Buss bruno.b...@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
Fora que tem um código de a* muito bem feito em C. Depois vou procurar ele
é postar. Ele era extremamente rápido (usei pra procurar 500 caminhos numa
grande de 1000*1500 recalculado a cada batida de um NPC com outro)
On Sep 21, 2013 3:16 PM, Eden Cardim e...@insoli.de wrote:
2013/9/21 Bruno
Eu pessoalmente discordo na consideração do A* ser a solução padrão para
esse tipo de problema ou no geral mesmo, mas acredito que isso vai desde
gosto, experiência de problemas anteriores e modo de cada um abordar
determinado tipos de problema.
Enfim, meu ponto original era apenas sobre o
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ó
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
Oi Blabos,
Não use cpan pra um problema simples, grafos são facilmente representados
como Adjacency Lists ( http://en.wikipedia.org/wiki/Adjacency_list ) em
Perl: basicamente uma hash table onde cada vertex aponta para uma lista de
vertices adjacentes.
Aqui tem uma explicação bem elegante (e
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
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
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
Blabos, o que vc quer fazer?
2013/9/19 Blabos de Blebe bla...@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:
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
18 matches
Mail list logo
