мотивация
На днях я путешествовал по городу на общественном транспорте и составил интересную графическую задачу, моделирующую проблему поиска кратчайшей связи между двумя местами.
Нам всем известна классическая «задача кратчайшего пути»: ориентированный граф с длинами и двумя вершинами , найдите кратчайший путь между и (т. е. путь, минимизирующий общую длину ребра). Предполагая неотрицательные длины ребер, существуют различные алгоритмы, и проблема проста.w e ∈ R + 0 ,s , t ∈ V s t
Это хорошая модель для случая, когда мы идем, например. Вершины являются перекрестком в нашей сети дорог, и каждый край имеет фиксированную длину - например, в метрах. Другая возможная интерпретация весов - это время, которое требуется нам, чтобы перейти от одной из его вершин к другой. Это интерпретация, которая меня интересует сейчас.
проблема
Теперь я хочу смоделировать следующую ситуацию. Я хочу путешествовать из пункта А в пункт Б в городе на общественном транспорте и минимизировать время . Сеть общественного транспорта может быть легко смоделирована как ориентированный граф, как и следовало ожидать. Интересной частью являются граничные веса (это время модели) - общественный транспорт (например, автобусы) отправляется только через определенные интервалы, которые различны для каждой остановки (вершина на графике). Другими словами - веса ребер не постоянны, они меняются в зависимости от времени, когда мы хотим использовать ребро.
Как смоделировать эту ситуацию: у нас есть ориентированный граф и функция веса ребер которая принимает время в качестве аргумента и возвращает время , необходимое для использования ребра на нашем пути. Например, если шина от вершины до вершины уходит в момент времени и это занимает раз, а мы достигаем вершины в момент времени , то - это вес ребра. Ясно, что .w : E × R + 0 → R + 0 u t = 10 5 v t = 8 w ( v u , 8 ) = 7 w ( v u , 10 ) = 5
Определить общий вес пути немного сложно, но мы можем сделать это рекурсивно. Пусть - направленный путь. Если то . В противном случае , где - без . Это естественное определение, соответствующее реальной ситуации. k = 1 w ( P ) =w ( P ) = w ( P ′ ) + w ( v k - 1 v k , w ( P ′ ) ) P ′ P v k
Теперь мы можем изучить эту проблему при различных предположениях о функции . Естественным предположением является которое моделирует «ожидание time».w ( e , t ) ≤ w ( e , t + Δ ) + Δ для всех e ∈ E , Δ ≥ 0 , Δ
Если функция «ведет себя хорошо», возможно, можно свести эту проблему к классической проблеме кратчайшего пути. Но мы могли бы спросить, что происходит, когда весовые функции становятся дикими. А что если мы отбросим предположение об ожидании?
Вопросов
Мои вопросы следующие.
- Обсуждалась ли эта проблема раньше? Это кажется естественным.
- Есть ли какие-либо исследования по этому поводу? Мне кажется, что существуют различные подзадачи, которые необходимо задать и изучить - в основном, в отношении свойств весовой функции.
- Можем ли мы свести эту проблему (возможно, при некоторых предположениях) к классической проблеме кратчайшего пути?
Ответы:
Это известно как проблема «кратчайшего пути, зависящего от времени». Действительно исследование было сделано для этой проблемы; см., например, классическую статью Орды и Рома, а также недавнюю статью SODA, в которой доказывается, что когда весовая функция каждого ребра кусочно-линейная, полиномиального размера, то кратчайший путь между двумя фиксированными точками изменяется раз.nΘ(logn)
Алгоритм Дейкстры действительно может быть использован для этой проблемы, когда применяется политика ожидания, то есть ожидание в узле, если это уменьшает конечное время прибытия. Без политики ожидания ситуация намного хуже: кратчайший путь может быть непростым, подпуть кратчайшего пути не может быть кратчайшим между двумя конечными точками подпути, пути, проходящие через бесконечное число ребер, могут иметь конечное время прибытия и т. Д. Снова посмотрите статью Орды и Рома для дальнейшего обсуждения.
источник
Вам известна проблема «кратчайших неубывающих путей»? Он был определен для моделирования таких ситуаций, как эти. Хотя это немного менее выразительно по сравнению с вашей формулировкой, есть быстрые подсказки для этого.
источник
Если вы предполагаете, что времена являются интегральными (что имеет смысл в случае общественного транспорта), вы можете создать сеть с расширенным временем, аналогичную той, которая была предложена Ford-Fulkerson для максимального потока во времени (или самого быстрого потока) и вместо этого найдите кратчайший путь в этом графе.
источник