В информатике и теориях графов , то канадский путешественник проблема ( 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 года. То есть цель состоит в том, чтобы минимизировать коэффициент конкуренции в худшем случае. Необходимо начать с введения определенных терминов.
Рассмотрим данный граф и семейство неориентированных графов, которые можно построить, добавив одно или несколько ребер из данного набора. Формально пустьгде мы думаем, что E - это ребра, которые должны быть в графе, а F - как ребра, которые могут быть в графе. Мы говорим чтоявляется реализацией семейства графов. Кроме того, пусть W - связанная матрица затрат, где- стоимость перехода от вершины i к вершине j в предположении, что это ребро находится в реализации.
Для любой вершины v из V назовемего падающий край относительно края множество B на V . Кроме того, для реализации, позволять - стоимость кратчайшего пути в графе от s до t . Это называется автономной проблемой, потому что алгоритм для такой проблемы будет иметь полную информацию о графе.
Мы говорим, что стратегия для навигации по такому графику - это отображение из к , где обозначает Powerset из X . Определяем стоимость стратегии в отношении конкретной реализации следующим образом.
- Позволять а также .
- Для , определять
- ,
- , а также
- .
- Если существует такое T , что, тогда ; в противном случае пусть.
Другими словами, мы оцениваем политику на основе тех ребер, которые, как нам известно, находятся в графе () и известные нам ребра могут быть в графе (). Когда мы делаем шаг в графе, нам становятся известны ребра, инцидентные нашему новому местоположению. Те ребра, которые есть в графе, добавляются к, и независимо от того, находятся ли ребра в графе или нет, они удаляются из множества неизвестных ребер, . Если цель никогда не достигается, мы говорим, что у нас бесконечная цена. Если цель достигнута, мы определяем стоимость обхода как сумму затрат всех пройденных ребер с мощностью.
Наконец, мы определяем проблему канадского путешественника.
- Учитывая экземпляр CTP , решите, существует ли политика так что для каждой реализации , цена политики не более чем в r раз оптимальна в автономном режиме, .
Пападимитриу и Яннакакис отметили, что это определяет игру для двух игроков , в которой игроки соревнуются за стоимость своих путей, а набор ребер выбирается вторым игроком (природой).
Сложность
В исходной статье анализировалась сложность проблемы и сообщалось, что она завершена для PSPACE . Также было показано, что поиск оптимального пути в случае, когда каждое ребро имеет связанную вероятность нахождения в графе (i-SSPPR), является простой для PSPACE, но ♯P- сложной задачей. [1] Устранение этого пробела было открытой проблемой, но с тех пор как направленные, так и неориентированные версии оказались трудными для PSPACE. [2]
Направленная версия стохастической проблемы известна в исследованиях операций как задача стохастического кратчайшего пути с обращением.
Приложения
Сообщается, что эта проблема находит применение в исследованиях операций , планировании перевозок, искусственном интеллекте , машинном обучении , сетях связи и маршрутизации. Исследован вариант задачи для навигации роботов с вероятностным распознаванием ориентиров. [3]
Открытые проблемы
Несмотря на возраст проблемы и ее многочисленные потенциальные приложения, многие естественные вопросы все еще остаются открытыми. Есть ли приближение с постоянным коэффициентом или проблема APX- трудна? I-SSPPR # P-complete? Остался без ответа еще более фундаментальный вопрос: существует ли описание оптимальной политики полиномиального размера , оставляя на мгновение время, необходимое для вычисления описания? [4]
Смотрите также
Заметки
- ^ Papadimitriou и Yannakakis, 1989, стр. 148
- ^ Фрид, Шимони, Бенбассат и Веннер 2013
- ^ Бриггс, Эми Дж .; Детвейлер, Каррик; Шарштейн, Даниэль (2004). «Ожидаемые кратчайшие пути для навигации роботов на основе ориентиров». «Международный журнал исследований робототехники» . 23 (7–8): 717–718. CiteSeerX 10.1.1.648.3358 . DOI : 10.1177 / 0278364904045467 .
- ↑ Каргер и Николова, 2008, с. 1
Рекомендации
- СН Пападимитриу; М. Яннакакис (1989). «Кратчайшие пути без карты». Конспект лекций по информатике . Proc. 16-й ИКАЛП. 372 . Springer-Verlag . С. 610–620.
- Дрор Фрид; Соломон Эяль Шимони; Амит Бенбассат; Кенни Веннер (2013). «Сложность вариантов задач канадского путешественника». Теоретическая информатика . 487 : 1–16. DOI : 10.1016 / j.tcs.2013.03.016 .
- Дэвид Каргер; Евдокия Николова (2008). «Точные алгоритмы решения проблемы канадского путешественника на тропах и деревьях». Цитировать журнал требует
|journal=
( помощь ) - Захи Бная; Ариэль Фельнер; Соломон Эяль Шимони (2009). «Проблема канадского путешественника с дистанционным зондированием». Неизвестный параметр
|conference=
игнорируется ( справка );Цитировать журнал требует|journal=
( помощь )