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

Цитата amk @ 04.02.12, 09:12

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

Это для задачи коммивояжера (когда граф не полный), не для описанной.

Думаю, для описанной задачи, на практике годится и перебор. Сильно сомневаюсь, что человеку по силам марафон длиной даже в 20 городов.

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

Цитата Swetlana @ 04.02.12, 17:22

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

Спасибо!
а при больших n (n>20)?

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

amk, не согласна с тобой.
Почему нецелесообразно сводить задачу к коммивояжеру.

Вот для каждой достопримечательности написали список городов. Если выбирать минимальное количество городов, которое покроет все достопримечательности, это уже NP-полная задача. Ладно, пусть мы её решили. Выбрали k городов, которые хз какой стоимости соответствуют.

Теперь строим из этих k городов полный ориентированный граф. Алгоритмом Флойда посчитали длины кратчайших путей A[u,v] для каждой направленной пары вершин (u,v) НА ИСХОДНОМ ГРАФЕ. Строим фиктивную дугу u->v с весом A[u,v], получили полный орграф. Свели задачу к коммивояжеру. Решили.
Теперь заменяем дугу u->v на настоящий путь. А он уже содержит вершины из исходного графа, например, те, которые не содержатся среди этих k вершин. И достопримечательности в этих вершинах могут отменить посещение каких-то вершин из этих k.
Даже если две NP-полных задачи решим оптимально, решение уже заведомо дважды неоптимальное

Добавлено 04.02.12, 20:53

Цитата Nils13 @ 04.02.12, 17:28

Спасибо!
а при больших n (n>20)?

Разрабатывать самому, вряд ли есть готовый приближённый алгоритм.
Могу предложить простой "жадный" алгоритм.

Предварительная обработка данных.
Алгоритмом Флойда рассчитываем длины кратчайших путей для любой пары вершин. Восстанавливаем эти пути как последовательность вершин, составляем список достопримечательностей по всему этому пути.
Имеем три массива nXn, где n - количество городов. A[u,v] - длина кратчайшего пути от u до v;
L[u,v] - множество "покрытых" достопримечательностей; C[u,v] - их количество.

Также заводим логический массив Dop[1..m], где m - количество достопримечательностей. Для посещённой достопримечательности Dop[i] ложь. Вначале заполняем весь массив true.
Шаг 0. Проверяем, содержит ли исходный пункт s все достопримечательности. Если да - конец
Шаг 1. Решение (маршрут) храним в массиве X. Заносим в X[1] исходный пункт s. Перебираем все оставшиеся вершины и выбираем u, для которой C[s,u] максимально. Если таких несколько, то из них выбираем ту, у которой A[s,u] минимально. Заносим u в решение X[2]:=u. Помечаем все достопримечательности из списка L[s,u] как просмотренные.
Шаг 2. Проверка на полное решение. Берём список L[u,s]. Если просмотр этих достопримечательностей делает весь Dop просмотренным, то возвращаемся в исходный пункт, конец.
Иначе вызываем рекурсию rec(3) для заполнения 3-й позиции в массиве X.

Добавлено
После посещения каких-то достопримечательностей, переписываем массив C[u,v], там должно быть количество только непосещённых.

Сообщение отредактировано: Swetlana - 05.02.12, 06:20

Swetlana, я и не предлагаю сводить описанную задачу к коммивояжеру. Я просто напомнил, что задачу коммивояжера можно переформулировать для неполного графа.

Более того, я не уверен, что для данной задачи будут сколько-нибудь разумно работать приближенные методы, применимые к задаче коммивояжера (точнее их аналоги).

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

Цитата

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

кто-то предлагал наверно, топикстартёр

Цитата

Более того, я не уверен, что для данной задачи будут сколько-нибудь разумно работать приближенные методы, применимые к задаче коммивояжера (точнее их аналоги).

Генетические алгоритмы точно не будут. Возможно, Ant Colony, т.к. внутри них локальный поиск, а он вообще хорошо работает.

Цитата Nils13 @ 04.02.12, 17:28

а при больших n (n>20)?

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

Ant Colony в просторечии муравьиные алгоритмы

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

Еще раз всем спасибо за обсуждение!
С большими размерностями вроде ситуация для меня прояснилась.
А если вернуться к малым n (условно n<20): Swetlana советовала "перебор (алгоритм с возвратом)" — тут я имею вопрос.
Если речь идет например о классической задаче о расстановке ферзей, то все понятно — строим дерево и обрубаем ветки которые не приводят к решению. Но в нашем случае что является признаком мертвой ветки? В любом случае я дойду до конца и переберу все достопримечательности. Можно ли здесь сократить простой перебор?

Цитата

Но в нашем случае что является признаком мертвой ветки?

Только стоимость. Посмотрите всё-таки лекции по структурам данных из FAQ'а раздел называется "Модификация общей схемы алгоритма с возвратом для решения задач на минимум".

Первое решение находите отдельно, приближённым алгоритмом. Заносите его стоимость в OptCost, сам маршрут - в OptX. Можно, конечно, положить OptCost=+бесконечность, тогда первое найденное решение туда запишется.
Всякий раз, когда собираетесь удлинить маршрут ещё на один город, сравнивайте
Cost (текущая стоимость) + стоимость нового ребра < OptCost
В противном случае это тупиковая ветвь и город отбрасывается как недопустимый.

Цитата

к малым n (условно n<20)

пожалуй n<=25 для современных компов

Сообщение отредактировано: Swetlana - 05.02.12, 16:35

Ок!
Пойду думать и реализовывать...
Всем спасибо!