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
