[Talk-br] Necessidade de intermediação

[Fernando Trebien]

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" <thundercel em gpsinfo.com.br>
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 <thundercel em gpsinfo.com.br>:
>
>> 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
> Talk-br em openstreetmap.org
> https://lists.openstreetmap.org/listinfo/talk-br
>
> _______________________________________________
> Talk-br mailing list
> Talk-br em openstreetmap.org
> https://lists.openstreetmap.org/listinfo/talk-br
>
-------------- Próxima Parte ----------
Um anexo em HTML foi limpo...
URL: <http://lists.openstreetmap.org/pipermail/talk-br/attachments/20150705/e0e797b0/attachment.html>