2015-07-05 1:40 GMT-03:00 Marcio - Thundercel <[email protected]>: > Por outro lado lembro que classificação de vias e de velocidades interferem > no roteamento e, infelizmente, não dominamos ainda o algoritmo garmin. O que > sabemos sobre ele advém de exaustivos testes realizados. > Não estamos debatendo tempo e sim roteamento e tudo que interfere nele. > Como bem deve saber você o roteamento leva em consideração, além de outros, > a quantidade de nós empregados para unir os segmentos de reta na retratação > da via. > Ao se reduzir a velocidade de um trecho de via o editor é obrigado a dividir > a via de forma a poder no trecho dividido estabelecer a velocidade. Isso por > si só já afeta o calculo de rota por aquele trecho.
Afeta, mas muito pouco, pelo menos na minha compreensão de algoritmos de roteamento. O que acontece é que ele cria um novo nó no grafo de roteamento para representar o trecho. O nó contem o tempo total para percorrer o trecho, calculado dividindo distância por velocidade. (há variações em que o nó contem ambas velocidade e distância e o cálculo do tempo é feito durante o processamento, mas elas são matematicamente equivalentes) A criação do nó em si não interfere, a princípio, com o algoritmo. Será um nó a mais a ser visitado enquanto o grafo é explorado pelo algoritmo de roteamento. O que acontece é que algoritmos diferentes usam heurísticas diferentes. Algumas dessas heurísticas decidem "descartar" alguns nós que eles "acham" que têm pouca chance de conduzir à melhor rota. "Heurística" é um método matematicamente impreciso para chegar a uma solução sub-ótima mais rapidamente. Se é impreciso, há heurísticas melhores e piores. Uma heurística comum é visitar primeiro os nós relativos às vias de maior classificação. Nesse caso, como a classificação não foi alterada, o nó seria visitado mesmo tendo uma velocidade mais baixa. Mas o Garmin pode usar alguma outra heurística que eu desconheço. Outro insight: explorar o gráfico requer somar esses tempos, trecho por trecho. São milhares de operação de soma. Se o programa não for bem construído, ele pode acumular erros numéricos ao somar milhares de números. O OSRM me parece particularmente sensível a esses erros. O Garmin geralmente opera num hardware limitado e talvez também seja sensível (tratar desses erros numéricos requer usar mais memória). Mais um insight: classificação interfere com esses algoritmos "mais simples" que usam "heurísticas". A classificação das vias não interfere em nada com o algoritmo A* (a-estrela) puro, nem com o algoritmo do OSRM. Por isso, classificações não devem ser alteradas com vistas ao roteamento. No entanto, um bom método de classificação serve bem a praticamente qualquer algoritmo de roteamento, não por ser o objetivo da classificação, mas por ser efeito colateral dela. Se, numa rota com vários quilômetros, a escolha de uma alternativa ou outra depender de um trecho tão curto quanto o mencionado, é bem provável que alguma dessas características esteja inteferindo no resultado. Mas os mapeadores do OSM não podem fazer nada, e talvez nem os desenvolvedores da aplicação sem ter que reescrevê-la por completo para resolver algum problema mais profundo. O que os roteadores prometem não é encontrar a melhor rota, mas uma rota sub-ótima. Quanto mais longa a distância, maior o efeito desses dois fatores (erro numérico e qualidade da heurística). Até mesmo o Waze às vezes faz bobagem na tentativa de encontrar a melhor rota. -- Fernando Trebien +55 (51) 9962-5409 "Nullius in verba." _______________________________________________ Talk-br mailing list [email protected] https://lists.openstreetmap.org/listinfo/talk-br
