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 <[email protected]> > 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 <[email protected]> > >> 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 <[email protected]> >> >>> 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 <[email protected]> >>> >>>> 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 <[email protected]> >>>> >>>>> 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 <[email protected]> >>>>> >>>>>> 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 <[email protected]> >>>>>> >>>>>>> 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 <[email protected]> >>>>>>> >>>>>>>> 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 <[email protected]> >>>>>>>> >>>>>>>>> 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 <[email protected]> >>>>>>>>> >>>>>>>>>> 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 <[email protected]> >>>>>>>>>> >>>>>>>>>>> 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 <[email protected]>: >>>>>>>>>>> > Blabos, o que vc quer fazer? >>>>>>>>>>> > >>>>>>>>>>> > 2013/9/19 Blabos de Blebe <[email protected]> >>>>>>>>>>> >> >>>>>>>>>>> >> 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: [email protected] >>>>>>>>>>> >> 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: [email protected] >>>>>>>>>>> > 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: [email protected] >>>>>>>>>>> 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: [email protected] >>>>>>>>>> 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: [email protected] >>>>>>>>> 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: [email protected] >>>>>>>> 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: [email protected] >>>>>>> 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: [email protected] >>>>>> 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: [email protected] >>>>> 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: [email protected] >>>> 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: [email protected] >> 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: [email protected] > 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: [email protected] L<http://mail.pm.org/mailman/listinfo/saopaulo-pm> =end disclaimer
