Eu tenho um problema com o algoritmo de estrela cadente. É o meu projeto final e preciso de ajuda.
Minha pergunta é como posso calcular o algoritmo heurístico de estrela cadente? Posso usar a estrela cadente pgrouting , mas não entendo como calcular a estrela cadente heurística.
Pesquisei a estrela cadente heurística calculadora no livro da Internet, mas não consigo encontrá-la agora.
Você pode me falar sobre o algoritmo de estrela cadente, não apenas o código-fonte, Sr. Mario?
pgrouting
routing
shooting-star
donni
fonte
fonte
Eu recebo este da lista de discussão. O disparo * é baseado em arestas, por isso vai de uma aresta a outra, enquanto A * e Dijkstra vão de vértice a vértice. Assim, você precisa de uma estrutura de dados que mantenha todas as arestas adjacentes para todas as arestas do seu gráfico. Isso também pode ser feito com um gráfico de linhas (http://en.wikipedia.org/wiki/Line_graph) a partir da sua rede rodoviária original. E, em seguida, você pode atribuir um custo de passagem de borda a borda (como um atributo especial da estrutura de arestas adjacentes ou como um custo do gráfico de linhas) que realmente representa qualquer tipo de limitações ou penalidades para passar de uma borda para outra - como como restrições de curvas em caso de curvas ou qualquer outro tipo de restrição, como semáforos. Com isso, você pode usar A * ou qualquer outro algoritmo de caminho mais curto usando arestas como vértices.
Então, essa é uma ideia por trás do tiroteio *.
E eu recebo este outro de Anton Patrushev: http://download.osgeo.org/pgrouting/forum/pgrouting.postlbs.org/discussion/topic/276.html . Você escreve assim: Em A *, estamos usando algo semelhante à função Manhattan (| Dx | + | Dy |) / 2 http://pgrouting.postlbs.org/browser/trunk/core/src/astar_boost_wrapper.cpp#L75 Lá você verá outras tentativas comentadas. Tentamos função diferente é OK. Provavelmente, era uma razão histórica. função heurística e, por algum motivo (não me lembro agora), decidimos que, para uma rede de estradas comum, isso no Shooting * estamos usando a distância euclidiana. http://pgrouting.postlbs.org/browser/trunk/core/src/shooting_star_boost_wrapper.cpp#L100 .
A outra fórmula: - Distância euclidiana> Sqrt (Dx² + Dy² + Dz²); - Distância de Manhattan> | Dx | + | Dy | + | Dz | ; - Distância máxima> Máx (| Dx |, | Dy |, | Dz |).
Ainda não entendo tudo. Amigo, você pode me dizer brevemente e os detalhes da estrela cadente do algoritmo do processo?
fonte