Menor problema de distância com o comprimento em função do tempo

10

Motivação

Outro dia, eu estava viajando pela cidade com transporte público e criei um problema gráfico interessante, modelando o problema de encontrar a conexão de menor tempo entre dois lugares.

Todos conhecemos o clássico "Problema do caminho mais curto": Dado um gráfico direcionado com comprimentos de e dois vértices , encontre o caminho mais curto entre e (ou seja, o caminho que minimiza o comprimento total da aresta). Assumindo comprimentos de borda não negativos, existem vários algoritmos e o problema é fácil.w eR + 0 ,G=(V,E)s , t V s tweR0+,eEs,tVst

Este é um bom modelo para o caso em que estamos caminhando, por exemplo. Os vértices são encruzilhadas em nossa rede de estradas e cada aresta tem comprimento fixo - em metros, por exemplo. Outra possível interpretação dos pesos das é o tempo que leva para irmos de um de seus vértices para o outro. Essa é a interpretação que me interessa agora.we

Problema

Agora quero modelar a seguinte situação. Quero viajar do ponto A ao ponto B em uma cidade através de transporte público e minimizar o tempo . A rede de transporte público pode ser facilmente modelada como um gráfico direcionado, como seria de esperar. A parte interessante são os pesos das arestas (o tempo do modelo) - o transporte público (ônibus, por exemplo) sai apenas em determinados intervalos, que são diferentes para cada parada (vértice no gráfico). Em outras palavras - os pesos das arestas não são constantes, eles mudam dependendo do tempo em que queremos usar a aresta.

Como modelar esta situação: Temos um gráfico direcionado e uma função de peso da aresta w : E × R + 0R + 0 que leva o tempo como argumento e retorna o tempo necessário para usar o método vantagem em nosso caminho. Por exemplo, se o barramento do vértice v para o vértice u sai em t = 10 e leva 5 vezes, chegamos ao vértice v em t = 8G=(V,E) w:E×R0+R0+vut=105vt=8, então é o peso da borda. Claramente, w ( v u , 10 ) = 5 .w(vu,8)=7w(vu,10)=5

É um pouco complicado definir o peso total do caminho, mas podemos fazê-lo recursivamente. Seja um caminho direcionado. Se k = 1 então w ( P ) = 0 . Caso contrário, w ( P ) = w ( P ) + w ( v k - 1 v k , w ( P ) )P=v1v2vk1vkk=1w(P)=0W(P)=W(P)+W(vk-1 1vk,W(P)), onde é o subcaminho de P sem v k . Esta é uma definição natural correspondente à situação do mundo real.PPvk

Agora podemos estudar o problema sob várias suposições sobre a função . A suposição natural é w ( e , t ) w ( e , t + Δ ) + Δ  para todos  e E , Δ 0 , que modela "aguardando o tempo Δ ".W

W(e,t)W(e,t+Δ)+Δ para todos eE,Δ0 0,
Δ

Se a função "se comportar bem", pode ser possível reduzir esse problema ao problema clássico de caminho mais curto. Mas poderíamos perguntar o que acontece quando as funções de peso ficam selvagens. E se deixarmos de lado a suposição de espera?

Questões

Minhas perguntas são as seguintes.

  • Esse problema já foi perguntado antes? Parece meio natural.
  • Existe alguma pesquisa sobre isso? Parece-me que existem vários subproblemas a serem solicitados e estudados - principalmente em relação às propriedades da função peso.
  • Podemos reduzir esse problema (possivelmente sob algumas suposições) ao problema clássico de caminho mais curto?
JS_
fonte
TV=T×V(t0 0,v0 0)(t1 1,v1 1)t1 1=W((v0 0,v1 1),t0 0)TWT
Uma variante simples desse problema (onde os pesos das arestas dependem linearmente do tempo) é chamada " caminho mais curto paramétrico ".
Neal Young

Respostas:

8

nΘ(registron)

O algoritmo de Dijkstra pode realmente ser usado para esse problema, quando a política de espera é imposta, ou seja, espera em um nó se isso reduzir o tempo final de chegada. Sem a política de espera, a situação é muito mais complicada: o caminho mais curto pode não ser simples, o subcaminho de um caminho mais curto pode não ser o mais curto entre os dois pontos finais do subcaminho, os caminhos que atravessam um número infinito de arestas podem ter um horário finito de chegada etc. Veja novamente o artigo de Orda e Rom para mais discussões.

Hsien-Chih Chang 張顯 之
fonte
3

Você está ciente do problema dos "caminhos mais curtos e não decrescentes"? Foi definido para modelar situações como essas. Embora seja um pouco menos expressivo em comparação com a sua formulação, existem algs rápidos para isso.

Ryan Williams
fonte
1

Se você presumir que os tempos são integrais (o que faz sentido no caso de transporte público), você pode criar uma rede de tempo expandido, semelhante à sugerida por Ford-Fulkerson para o fluxo máximo ao longo do tempo (ou fluxo mais rápido) e encontre o caminho mais curto neste gráfico.

Hélio
fonte