Проблема канадского путешественника

В информатике и теории графов проблема канадского путешественника ( CTP ) представляет собой обобщение задачи о кратчайшем пути на графы, которые частично наблюдаемы . Другими словами, «путешественник» в данной точке графа не может видеть весь граф, а только соседние узлы или определенное «ограничение реализации».

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

Описание проблемы

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

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

Варианты

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

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

Третий параметр ограничен стохастическими версиями и касается того, какие предположения мы можем сделать о распределении реализаций и о том, как это распределение представлено на входе. В стохастической задаче канадского путешественника и в независимой от ребра стохастической задаче о кратчайшем пути (i-SSPPR) каждое неопределенное ребро (или стоимость) имеет связанную с ним вероятность нахождения в реализации, и событие, когда ребро находится в графе, является независимым. из которых остальные ребра находятся в реализации. Несмотря на значительное упрощение, проблема по-прежнему остается #P -сложной. Другой вариант — не делать никаких предположений о распределении, но требовать, чтобы каждая реализация с ненулевой вероятностью была явно указана (например, «Вероятность 0,1 набора ребер { {3,4},{1,2} }, вероятность 0,2 из. .."). Это называется стохастической задачей кратчайшего пути распределения (d-SSPPR или R-SSPPR) и является NP-полной . Первый вариант сложнее второго, поскольку первый может представлять в логарифмическом пространстве некоторые распределения, которые второй представляет в линейном пространстве.

Четвертый и последний параметр — это то, как график меняется со временем. В CTP и SSPPR реализация фиксирована, но неизвестна. В стохастической задаче кратчайшего пути с обращением и сбросами или задаче ожидаемого кратчайшего пути новая реализация выбирается из распределения после каждого шага, предпринятого политикой. Эту проблему можно решить за полиномиальное время, сведя ее к марковскому процессу решения с полиномиальным горизонтом. Известно, что марковское обобщение, при котором реализация графа может влиять на следующую реализацию, гораздо сложнее.

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

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

Мы определяем вариант, изучаемый в статье 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}$. Если цель никогда не достигается, мы говорим, что у нас бесконечная стоимость. Если цель достигнута, мы определяем стоимость прогулки как сумму стоимостей всех пройденных ребер с учетом мощности.

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

Учитывая экземпляр CTP $(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.

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

Приложения

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

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

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

См. также

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

Ссылки

• CH Пападимитриу; М. Яннакакис (1989). «Кратчайшие пути без карты». Конспекты лекций по информатике . Учеб. 16-й ИКАЛП. Том. 372. Шпрингер-Верлаг . стр. 610–620.
• Дрор Фрид; Соломон Эял Шимони; Амит Бенбассат; Сенни Веннер (2013). «Сложность вариантов задачи канадского путешественника» . Теоретическая информатика . 487 : 1–16. arXiv : 1207.4710 . дои : 10.1016/j.tcs.2013.03.016 . S2CID   17810202 .
• Дэвид Каргер; Евдокия Николова (28 января 2008 г.). Точные алгоритмы решения задачи канадского путешественника о путях и деревьях (PDF) (Отчет). Массачусетский технологический институт.
• Захи Бная; Ариэль Фельнер; Соломон Эял Шимони (2009). Канадский путешественник Проблема с дистанционным зондированием . Международная совместная конференция по искусственному интеллекту (IJCAI).