algoritmo Dijkstra para iPhone

StackOverflow https://stackoverflow.com/questions/876623

  •  22-08-2019
  •  | 
  •  

Pergunta

É possível facilmente usar a funcionalidade de GPS no iPhone desde SDK 3.0, mas é explicitamente proibido o uso de mapas do Google. Isso tem duas implicações, eu penso:

  1. Você terá que fornecer mapas-se
  2. Você terá que calcular as rotas mais curtas si mesmo.

Eu sei que calcular a rota mais curta tem intrigado os matemáticos para as idades, mas ambos Tom Tom e Google estão fazendo um grande trabalho, então essa questão parece ter sido resolvida. Pesquisando na 'net, não sendo um matemático mim, me deparei com a Algoritmo de Dijkstra . Existe alguém de vocês que tem utilizado com sucesso este algoritmo em um Mapa-como aplicativo no iPhone? Você estaria disposto a compartilhá-lo comigo / comunidade? Será que isso é a abordagem certa, ou são as outras opções? Muito obrigado pela sua consideração.

Foi útil?

Solução

algoritmo de Dijkstra é para encontrar o caminho mais curto para todos os nós (de um nó de partida única). programadores de jogos usar uma pesquisa dirigida, tais como A *. Onde Dijkstra processa o nó que está mais próximo da posição inicial em primeiro lugar, A * processa o que é estimada em mais próximo para a posição final

A forma como isto funciona é que você fornecer uma função barato "estimativa" de qualquer posição para o ponto final. Um bom exemplo é o quão longe um pássaro voaria para chegar lá. A * adiciona isso para a distância atual desde o início para cada nó e, em seguida, escolhe o nó que parece estar no caminho mais curto.

A sua melhor estimativa, menor é o tempo que vai demorar para encontrar um bom caminho. Se esse tempo ainda é muito longo, você pode fazer um achado caminho em um mapa simples e depois outro em um mapa mais complexo para encontrar a rota entre os lugares que você encontrou no mapa simples.

Atualização Depois de muito procurar, eu encontrei um href="http://www.gamasutra.com/features/19990212/sm_04.htm" artigo em A * para você para leia

Outras dicas

Eu não acredito que o algoritmo de Dijkstra seria útil para o mapeamento do mundo real, porque, como disse Tom Leys (I gostaria de comentar sobre o seu post, mas falta o representante para fazê-lo), que exige um único ponto de partida. Se os começando alterações pontuais, tudo deve ser recalculado, e gostaria de imaginar isso seria bastante lenta em um dispositivo como o iPhone para um significativamente grande conjunto de dados.

algoritmo Dijkstra é O (m log n) para n nós em arestas (para um único caminho) e é bastante eficaz para ser usado para o encaminhamento da rede. Isso significa que ele é o bastante eficiente para ser usado por um one-off computação.

Resumidamente, o algoritmo de Dijkstra trabalha como: 

Take the start node
Assign it a depth of zero
Insert it into a priority queue at its depth key

Repeat:
    Pop the node with the lowest depth from the priority queue
    Record the node that you came from so you can track the path back
    Mark the node as having been visited
    If this node is the destination:
        Break
    For each neighbour:
        If the node has not previously been visited:
            Calculate depth as depth of current node + distance to neighbour
            Insert neighbour into the priority queue at the calculated depth.

Return the destination node and list of the nodes through which it was reached.

Ao contrário da crença popular, o algoritmo de Dijkstra não é necessariamente um todos os pares mais curto calculadora caminho, embora possa ser adaptado para fazer isso.

Você teria que obter um gráfico das ruas e os cruzamentos com as distâncias entre os cruzamentos. Se você tivesse esses dados você pode usar o algoritmo de Dijkstra para calcular a rota mais curta.

Se você olhar para a tecnologia TomTom chamadas 'IQ Routes', eles medem o tempo velocidade e curso real por roadstretch por hora do dia. Isso faz com que o tempo de chegada mais precisos. Portanto, a hora prevista de chegada é mais baseada em fatos http://www.tomtom.com/page/iq -routes

Calcular percurso usando o algoritmo A * é rápido o suficiente abundância em um iPhone com dados de mapas off-line. Tenho experiência de fazer isso comercialmente. Eu uso o algoritmo A * como documentado na Wikipedia, e eu continuo a rede rodoviária na memória e re uso-lo; uma vez que é carregado, roteamento, mesmo sobre uma área grande como a Espanha ou a metade ocidental do Canadá é praticamente instantânea.

Eu tomo dados do OpenStreetMap ou elswhere e convertê-lo em um grafo direcionado, assumindo (que é o caminho certo para fazê-lo de acordo com aqueles que sabem) que quaisquer duas estradas que compartilham de um ponto com o mesmo ID são unidas. I atribuir pesos para diferentes tipos de estradas com base nas velocidades esperadas, e se uma parte de uma estrada é one-way I criar apenas um único arco; Bidirecionais estradas obter dois arcos, um em cada sentido. Isso é muito bonito a coisa toda para além de algum código ad-hoc para evitar voltas perigosas, e implementação de restrições de roteamento.

Tenha um olhar em CloudMade . Eles oferecem um serviço gratuito para iPhone e iPad que permite a navegação com base em sua localização atual. Ele é construído sobre mapas de ruas abertas e tem algumas características interessantes como fazer o seu próprio mapstyle. É um pouco lento ao longo do tempo, mas o seu totalmente gratuito.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top