Aí você que entra na minha área de expertise como se soubesse mais. Sou mestre em computação, li várias versões desses algoritmos.
O nó a que me refiro é o do grafo de roteamento. Não é o nó do mapa (com coordenadas e tal). O nó do grafo de roteamento sequer tem coordenadas, possui apenas propriedades abstratas como o tempo para atravessar uma linha de uma ponta à outra, e a referência a essa linha daí sim no mapa geográfico. On 5 Jul 2015 05:44, "Marcio - Thundercel" <[email protected]> wrote: > Uma coisa é o esperado de acordo com a teoria e outra o observado na > pratica em exaustivos testes. > > 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 algoritmo, dentre outros, trata os nós e é por eles que ele traça a rota. > > Já fizemos inúmeros testes de roteamento e identificamos que o roteamento, > entre duas vias iguais, ele opta pela que tem menos nós. > > Faça o teste chegando em um nó onde se abrem duas vias e que se fecham lá > na frente, como um losango. > Divida um segmento de reta de uma das vias inserindo um nó nela. > Identificará que o roteamento se dá pela via que não tem o nó inserido. > Foi assim que nos testes constatamos a influência de partições de via em > um roteamento. > > -----Mensagem Original----- From: Fernando Trebien > Sent: Sunday, July 5, 2015 4:52 AM > To: OpenStreetMap no Brasil > Subject: Re: [Talk-br] Necessidade de intermediação > > 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 > > _______________________________________________ > Talk-br mailing list > [email protected] > https://lists.openstreetmap.org/listinfo/talk-br >
_______________________________________________ Talk-br mailing list [email protected] https://lists.openstreetmap.org/listinfo/talk-br
