| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Задача коммивояжера с переменными весами |
| Автор: GooG2e 17.2.2016, 12:40 |
| Всем привет! Сразу скажу, что задача сложная и я надеюсь хоть на какую-то помощь и совет. Любые мысли и идеи приветствуются и предлагаю их обсуждать. Позже постараюсь с примерами картинок оформить. Чем отличается задача от традиционного коммивояжёра: 1)У перехода две стоимости - время и расстояние 2)Переход от точки к точки допустимо совершать только в определённое время и от перехода зависит время перехода (грубо говоря мы переходим из A в B и допустим в 13:00 это стоит 1 час времени, а в 15:00 - 2 часа времени, стоимость в расстоянии не меняется). Соответственно у нас есть время отправления и прибытия из точки в точку. По каждому необходимо пройтись ОДИН раз. Если где-то осталась непройденное направление, то допускается пройтись ещё один раз по направлению (учитывая времена). 3)В каждой точке коммивояжёр должен отдохнуть определённое время(зависит от точки и только после этого он может ехать дальше) 4)При набеге определённой стоимости в часах, либо в километрах коммивояжёр обязан оказаться в определённом городе (поспать допустим). Можно прийти заранее, но позже нельзя. 5)Город начала и время отправления можно выбрать самостоятельно - в приоритете города, в которых коммивояжёр может поспать (4). Соответственно жду подсказок, вопросов и обсуждения Какие есть мысли на данный момент, возможно они кого-то натолкнут на более интересные: 1)Город следует выбирать по принципу различия входов и выходов - допусти приехать можно 8 способами, а уехать 9 способами (опять же предположение) 2)Следующее направление движение следует выбирать на основе стоимостных функций. Одна стоимостная функция зависит от приближения времени сна т.е. она увеличивается при приближении данного времени и если данное направление приводит в город, в котором можно отдохнуть. Вторая функция зависит от среднего количества неиспользованных направлений движения т.е. она увеличивается в направлении где много неотработанных направлений. Это нужно для того чтобы не использовать возможность повторного проезда по направлению (она нежелательна). Пока больше мыслей нет.. |
| Автор: ksnk 17.2.2016, 12:59 |
| GooG2e, На первый взгляд - задача для полного перебора. Условия достаточно сложны для интуитивного поиска инвариантов, в то же время достаточно жесткие условия, которые эффективно сокращают возможные "ходы". |
| Автор: GooG2e 17.2.2016, 14:38 |
| Ну мы вот сейчас ходим и в ТЗ проверяем условия, по которым можно что-то отрезать при волновом поиске. |
| Автор: Akina 17.2.2016, 16:15 | ||||||
Жаль, что Вы не ответили на мой вопрос на http://forum.sources.ru/index.php?showtopic=408076:
|
| Автор: GooG2e 17.2.2016, 16:21 | ||
да необходимо пройтись именно по каждому направлению, а не узлу. Грубо говоря есть расписание автобусов и нужно на всех автобусах хоть раз прокатиться. На одном атвобусе нельзя кататься больше двух раз |
| Автор: Akina 17.2.2016, 16:36 | ||
И (поскольку речь однозначно идёт о направленном графе) имеется в виду, что должно быть пройдено каждое ребро. Ну, как я уже сказал, это не задача коммивояжёра, а задача обхода ориентированного графа. Стандартные методы решения - это использование конечных автоматов, обычно основанных на построении остова графа с поиском в глубину или в ширину по нему. Из оптимизаций тут можно применить разве что откаты по остову, но особых результатов от такой оптимизации я бы не ждал, особенно если количество рёбер невелико. |
| Автор: GooG2e 19.2.2016, 15:30 | ||
Пока есть вариант с поиском в глубину, чтобы при нахождении одного варианта мы могли начать отбрасывать другие, если они хуже по определённому критерию. |
| Автор: GooG2e 20.2.2016, 18:15 |
| Сегодня возник ещё один вариант - строить дерево вширь, но на каждом этапе искать вариант с минимльной стоимостью и все элементы, которые имеют стоимость в n раз больше отсекать. При необходимости n можно повышать т.е. в цикле увеличивать значение, если при прошлом обходе не получился ответ. |
