Задача канадского путешественника

Задача канадского путешественника (ЗКП) (англ. Canadian traveller problem, CTP) — это обобщение задачи о кратчайшем пути на графы, которые частично видимы. Другими словами, граф раскрывается по мере его изучения, а исследованные рёбра дают вклад в стоимость, даже если они не принадлежат конечному пути.

Эту задачу оптимизации предложили в 1989 году Христос Пападимитриу и Михалис Яннакакис и с тех пор было изучено много её вариантов. Название, предположительно, возникло из разговора авторов, обсуждавших проблемы канадских водителей, регулярно попадающих на заблокированные в результате снегопада улицы. Стохастическая версия, где каждое ребро ассоциировано с вероятностью принадлежать графу, получила особое внимание в исследовании операций под именем «Стохастическая задача о кратчайшем пути с рекурсией» (англ. Stochastic Shortest Path Problem with Recourse, SSPPR).

Описание задачи

Для заданного экземпляра имеется некоторое число возможностей или реализаций, как невидимая часть графа может выглядеть. Если экземпляр задан, описание, как получить лучший маршрут, называется политикой. Целью ЗКП является вычислить ожидаемую цену оптимальной политики. Вычисление актуального описания оптимальной политики может оказаться более сложной задачей.

Если дан экземпляр и политика для него, любая реализация даёт свой собственный (детерминированный) проход графа. Заметим, что проход будет не обязательно путём, поскольку лучшей стратегией может оказаться, например, посещение каждой вершины цикла и возврат в начало. Это отличает задачу от задачи о кратчайшем пути (со строго положительными весами), поскольку повторения в проходе означают, что существуют более хорошие решения.

Варианты

Есть пять основных параметров, по которым различаются варианты задачи канадского путешественника. Первый параметр — как формируется цена прохода для данного экземпляра и политики. В стохастической задаче о кратчайшем пути с рекурсией целью является просто минимизация цены прохода (которая определяется как сумма по всем его рёбрам цены ребра на количество использований этого ребра). Для задачи канадского путешественника целью является минимизация конкурентного отношения прохода, то есть минимизация отношения длины полученного прохода к кратчайшему пути.

Второй параметр — как осуществлять политику с учётом различных реализаций, согласующихся с экземпляром. В задаче канадского путешественника хотят изучить худший случай, а в SSPPR — значение в среднем. Для анализа среднего случая следует определить априори распределение для реализации.

Третий параметр ограничен стохастической версией и определяет, какие предположения мы можем сделать о распределении реализаций и как распределение представлено на входе. В стохастической задаче канадского путешественника и рёберно независимой стохастической задаче о кратчайшем пути (англ. Edge-independent Stochastic Shortest Path Problem, i-SSPPR) каждое не известное точно ребро (или цена) имеет ассоциированную вероятность принадлежать реализации и событие, что ребро графу принадлежит, не зависит от других рёбер в реализации. Даже хотя это является существенным упрощением, задача остаётся #P-трудной. Другой вариант не делает никаких предположений о распределении, но требует, чтобы каждая реализация с ненулевой вероятностью была явно указана (например, так: «Вероятность 0,1 на множестве рёбер { {3,4},{1,2} }, вероятность 0,2 на...»). Это называется «дистрибутивной стохастической задачей о кратчайшем пути» (англ. Distribution Stochastic Shortest Path Problem, d-SSPPR или R-SSPPR) и она NP-полна. Второй вариант труднее первого, поскольку первый вариант может представить в логарифмическом пространстве некоторые распределения, в то время как второй вариант представляет их в линейном пространстве.

Четвёртый и конечный параметр — как граф изменяется со временем. В ЗКП и SSPPR реализация фиксирована, но не известна. В стохастической задаче о кратчайшем пути с рекурсией и сбросом (англ. Stochastic Shortest Path Problem with Recourse and Resets) или задаче об ожидаемом кратчайшем пути (англ. Expected Shortest Path problem), новая реализация выбирается из распределения после каждого шага, предпринятого согласно политике. Эта задача может быть решена за полиномиальное время путём его марковского процесса решений с полиномиальным горизонтом. Обобщение процесса Маркова, где реализация графа может влиять на следующую реализацию, как известно, существенно более сложно.

Дополнительный параметр — как новые знания обнаруживаются в реализации. В традиционных вариантах ЗКП агент обнаруживает точный вес (или статус) ребра при достижении принадлежащей ему вершины. Недавно был предложен новый вариант, в котором агент имеет возможность осуществить удалённый сбор информации с любого места в реализации. В этом варианте целью является минимизация цены прохождения плюс цены операций сбора информации.

Формальное определение

Мы определим вариант, который изучался в статье 1989 года. То есть целью является минимизация конкурентного соотношения в худшем случае. Нужно начать с введения некоторых терминов.

Рассмотрим заданный граф и семейство неориентированных графов, которые могут быть построены путём добавления одного и более рёбер из заданного множества. Формально, пусть ${\mathcal {G}}(V,E,F)=\{(V,E+F')|F'\subseteq F\},E\cap F=\emptyset$, где E — множество рёбер, которые должны быть в графе, а F — множество рёбер, которые могут быть в графе. Мы говорим, что $G\in {\mathcal {G}}(V,E,F)$ является реализацией семейства графов. Далее, пусть W будет ассоциированной матрицей цен, в которой $w_{ij}$ определяет цену прохода из вершины i в вершину j в предположении, что ребро принадлежит реализации.

Для любой вершины v из V мы обозначим через $E_{B}(v,V)$ её инцидентные рёбра из подмножества рёбер B множества V. Для реализации $G\in {\mathcal {G}}(V,E,F)$ пусть $d_{B}(s,t)$ означает цену кратчайшего пути в графе из s в t. Это называется оффлайн-задачей, поскольку алгоритм для выполнения этой задачи должен обладать полной информацией о графе.

Мы говорим, что стратегия $\pi$ навигации по такому графу является отображением из $({\mathcal {P}}(E),{\mathcal {P}}(F),V)$ в $V$, где ${\mathcal {P}}(X)$ обозначает булеан множества X. Мы определяем цену $c(\pi ,B)$ стратегии $\pi$ для конкретной реализации $G=(V,B)$ следующим образом.

• Пусть $v_{0}=s,E_{0}=E$ и $F_{0}=F$.
• Для $i=0,1,2,...$ определяем
  • $E_{i+1}=E_{i}\cup E_{B}(v_{i},V)$,
  • $F_{i+1}=F_{i}-E_{F}(v_{i},V)$,
  • $v_{i+1}=\pi (E_{i+1},F_{i+1},v_{i})$.
• Если существует T, такое, что $v_{T}=t$, то $c(\pi ,B)=\sum _{i=0}^{T-1}w_{v_{i},v_{i+1}}$
• в противном случае пусть $c(\pi ,B)=\infty$.

Другими словами, мы вычисляем политику, основываясь на рёбрах, о которых мы в текущий момент знаем, что они принадлежат графу ($E_{i}$), и на рёбрах, о которых мы знаем, что они могут принадлежать графу ($F_{i}$). Когда мы предпринимаем шаг в графе, рёбра, инцидентные нашему новому положению, становятся нам известными. Рёбра, которые графу принадлежат, включаются в $E_{i}$, и независимо от того, принадлежат они графу или нет, они удаляются из множества неизвестных рёбер, $F_{i}$. Если цель не смогли достичь, мы говорим, что задача имеет бесконечную цену. Если цель достигнута, мы определяем цену прохода как сумму цен всех пройденных рёбер, учитывая кратность.

Наконец, мы определим задачу канадского путешественника.

Если дан экземпляр ЗКП $(V,E,F,s,t,r)$, определяем, существует ли политика $\pi$, такая, что для любой реализации $(V,B)\in {\mathcal {G}}(V,E,F)$ цена $c(\pi ,B)$ политике не более чем в r раз больше оптимального значения $d_{B}(s,t)$.

Пападимитриу и Яннакакис заметили, что это определяет игру двух лиц, где игроки борются за цену пути, а набор рёбер выбирает второй игрок (природа).

Сложность

Оригинальная статья анализировала сложность задачи и указали, что она PSPACE-сложна. Было также показано, что нахождение оптимального пути в случае, когда рёбрам задана вероятность быть в графе (i-SSPPR), является PSPACE-простой задачей, но ♯P-сложной. Была открытой проблема перекинуть мост через эту пропасть, но было доказано, что и ориентированная, и неориентированная версия PSPACE-трудны.

Ориентированная версия стохастической задачи известна в исследовании операций как стохастическая задача о кратчайшем пути с рекурсией (англ. Stochastic Shortest Path Problem with Recourse).

Приложения

Задача имеет приложения в исследовании операций, планировании перевозок, искусственном интеллекте, машинном обучении, сетях коммуникации и маршрутизации. Вариант задачи изучался для навигации роботов с вероятностным распознаванием ориентиров на местности.

Открытые проблемы

Несмотря на возраст проблемы и её большого числа потенциальных приложений, многие естественные вопросы остаются открытыми. Существует ли аппроксимация с постоянным множителем, или задача APX-трудна? Является ли i-SSPPR #P-полной? И даже более фундаментальный вопрос остаётся без ответа: существует ли полиномиального размера описание оптимальной политики, оставляя за скобками время, необходимое для вычисления описания?.

См. также

• Обход графа
• Момент первого попадания
• Задача о кратчайшем пути