Поиск на графе... , Поиск на графе...

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

Задача, конечно, NP-полная, коммивояжер - частный случай этой задачи. Когда каждый из n городов имеет одну уникальную достопримечательность, и список состоит из n достопримечательностей.

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

Цитата

т. е. я могу вначале найти города которые нужно посетить

Нет.
Города имеют несколько достопримечательностей, которые могут пересекаться. Если на текущем шаге i выбрали город X[i], то все достопримечательности этого города помечаем как посещённые. На следующем шаге из городов, соединённых с городом X[i], допустимыми будут только те, у которых есть хотя бы одна "новая" достопримечательность.

Сообщение отредактировано: Swetlana - 03.02.12, 05:41

Цитата Swetlana @ 03.02.12, 05:34

На следующем шаге из городов, соединённых с городом X[i], допустимыми будут только те, у которых есть хотя бы одна "новая" достопримечательность.

Вру.
Каждый город может использоваться не один раз. Условие допустимости - просто возможность перехода +
стоимость текущего решения < стоимости текущего оптимума.

Swetlana спасибо!
Буду думать...
я так понимаю что смотреть надо в КОРМЕН, ЛЕЙЗЕРСОН, РИВЕСТ - АЛГОРИТМЫ ПОСТРОЕНИЕ И АНАЛИЗ. Или за последнее время что-то появилось новое?
Я уже давно не занимался этимии вещами.

Nils13, а какого сорта задача - учебная или для дела?
И какова размерность, для скольки городов будете решать?
Если задача учебная, то это, скорее всего, точный переборный алгоритм и n<=20.
Как это решается рекурсивным алгоритмом с возвратом на примере задачи коммивояжера можно посмотреть в FAQ
лекции по структурам данных
FAQ: избранное часть 1 (и не последняя)

Swetlana еще раз спасибо за советы!
Задача ближе к учебной но может перерости и в «для дела». В постановке просится учитывать что программа должна работать в реальном мире. В тестовом варианте есть 13 городов (узлов) и у каждого одна или две достопримечательности (которые могут повторяться). Но программу могут тестить и на большем числе узлов — возможно более 20, у меня нет информации.
Возможен ли такой вариант решения: я стартую с начального узла и дальше рекурсивно использую поиск в глубину до момента когда все достопримечательности будут достижимы — после чего я знаю множество узлов (понятно что это может не являться оптимальным множеством) в которые я должен посетить — и это уже «чистый коммивояжёр».

Nils13, для 13 городов вы просто обязаны найти оптимальный вариант поиском в глубину=алгоритм с возвратом=бэктрекинг.
Для большой размерности как я говорила, нужно разрабатывать приближённый или эвристический алгоритм.
Вы всё пытаетесь свести к коммивояжеру, поймите, это не коммивояжер. У коммивояжера ПОЛНЫЙ ГРАФ, в оптимальном решении каждый город посещается ровно один раз. А вам придётся не по одному разу проходить через вершину.

В разделе где-то прикреплён (мною) исходник для СЕЛЬСКОГО ПОЧТАЛЬОНА, точный алгоритм, задача тоже не такая, но ближе к вашей, т.к. вершина не по одному разу проходится.

ЗЫ. Вообще-то у нас функционирует раздел "Помощь студентам"

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

Что действительно отличает эту задачу - то, что по мере посещения городов, какие-то еще не посещенные города можно уже не посещать. Поле поиска меняется по ходу решения.

Добавлено 04.02.12, 09:14
Это сильно затруднит поиск приближенных алгоритмов

Цитата

и потребовав посетить каждый город хотя бы по одному разу.

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

Добавлено 04.02.12, 12:39

Цитата

Это сильно затруднит поиск приближенных алгоритмов

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

Поэтому и спросила ТС, учебная ли это задача. Для учебной задачи она некорректно поставлена, вот и подумала, что ТС для какой-то реальной задачи сам сделал корявую постановку.

Если всё-таки пытаться разработать приближённый алгоритм, то любая "жадная" стратегия отпадает - не замкнёт цикл. Для неориентированного графа всё было бы по-другому...

Сообщение отредактировано: Swetlana - 04.02.12, 12:41

Всем спасибо за обсуждение.
Задача не есть «классическая учебная» - студентом я был примерно 12 лет назад :-)
Задача скорее тренировочная. В постановке я ничего не менял. Мне прежде всего интересен подход к таким задачам. И в какие книги можно глянуть. Поскольку я сам пришел из физики а не из прикладной математики — то могу не знать элементарных вещей в этой области — потому и спрашиваю.
Еже раз спасибо!

Nils13, пока нет корректной математической постановки задачи, нечего обсуждать.

Некорректные постановки появляются в разделе по двум причинам.
1. Студенты-двоечники не знают своего задания.
2. Человек, который учился понемногу когда-нибудь чему-нибудь, думает, что сделать постановку реальной задачи - раз плюнуть, это он сделает сам. А вот алгоритм пусть ему подскажут. Это не так. Сделать постановку задачи означает выбрать определённую модель для её решения, и такой человек называется "математик-постановщик".

ЗЫ. С удовольствием и совершенно бесплатно делаю постановки реальных задач дискретной оптимизации, с подбором/разработкой алгоритма. Потому что потом даю эти задания в качестве курсовых и дипломов. Как появится реальная задача - бобро пожаловать

Уважаемая Swetlana,
Постановка этой задачи не относится ни к одному из указанных вами типов (Студенты-двоечник и Человек, который учился понемногу когда-нибудь чему-нибудь ). Я понимаю что существуют некорректно поставленные задачи а также задачи имеющие много решений и т. д. Вероятно вы правы в смысле математической постановки задачи (я тут действительно не профессионал).
Но я занимаюсь совершенно реальными проектами из жизни. Представьте, что есть «реальная туристическая фирма» у которой есть карта городов с достопримечательностями и клиент который хочет посетить некое множество из этих достопримечательностей. Вопрос — как предложить наиболее оптимальный маршрут клиенту. Ограничение следующее — необходимо посетить все указанные клиентом достопримечательности и вернуться в начальную точку (каждый город можно посетить много раз). Все, больше никаких ограничений нет. Конечно интересует минимальная стоимость путешествия.

Nils13, наконец-то.

Вы пишите "направленный граф". Для вашей задачи это означает, что из Праги в Дрезден мы можем доехать на автобусе за x крон, а вот стоимость путешествия из Дрездена в Прагу равна + бесконечности.

Граф у вас неориентированный, взвешенный, метрика - эвклидова. А эвклидова метрика сильно облегчает жизнь.
И вот уже предложение amk дополнить до полного графа приобретает смысл реальной эвристики. Если от города a до города b нет прямого ребра, то несуществующее ребро можно заменить кратчайшим путём от a до b.

Обсуждение продолжается

Добавлено 04.02.12, 16:36
Я вот хочу спросить. Если посещаем город с целью осмотра достопримечательностей, то к стоимости проезда, наверно, нужно добавлять стоимость проживания в гостинице + стоимость экскурсии? И наверно надо учитывать, сколько дней находимся в городе (например, один день на каждую достопримечательность.)
А если мы просто осуществляем возврат через этот город (как при поиске в глубину), то либо пренебрегать стоимостью проживания, либо считать фиксированной

В данной задачи действительно проезд из города А в город B не равен проезду из B в А, т.е. граф направленный. Например есть рейс из А в В а обратно нет и клиент должен возвращаться через другой город. Это только один пример. Но естественно известно что весь граф связанный — т. е. клиент всегда может попасть из любого города в любой — но не всегда напрямую

Добавлено 04.02.12, 16:42

Цитата Swetlana @ 04.02.12, 16:16

Я вот хочу спросить. Если посещаем город с целью осмотра достопримечательностей, то к стоимости проезда, наверно, нужно добавлять стоимость проживания в гостинице + стоимость экскурсии? И наверно надо учитывать, сколько дней находимся в городе (например, один день на каждую достопримечательность.)
А если мы просто осуществляем возврат через этот город (как при поиске в глубину), то либо пренебрегать стоимостью проживания, либо считать фиксированной

На данном этапе пренебрегаем этими вещами.

То есть для любой пары вершин существует ориентированный путь.

Цитата

На данном этапе пренебрегаем этими вещами.

перебор (алгоритм с возвратом для n<=20) эту задачу решает.