ReSQL.ru
     
powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Мобильная версия    Контакт    Правила    FAQ    Помощь
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Доб. в избранное | Игнор. тему | Прикреп. тему | Пометить прочит. / непрочит. | Фильтр
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Динамическое программирование. Поиск оптимального пути с ограничениями.
20 сообщений из 20, страница 1 из 1
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35807994
stopa85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stopa85
Гость
Вобщем смысле - задача коммивояжера. Только выходит он из склада должен пройти по всем клиентам и вернуться на склад так, чтобы попасть к каждому клиенту в определенный интервал времени.
Если торговец приходит к клиенту раньше назначенного интервала - он ждет "начала интервала". Придти позже не допустимо.

Требуется найти кратчайший путь или доказать что такого пути нет.

Как решаю:
Есть список решений (путь, время затраченное на этот путь, длинна пути).

Инициализация:
Список решений содержит пустой элемент: нулевое время и стоимость.

1. ПОКА Выбираем наименьший элемент А (недостроенный путь наименьшей длинны) и списка решений ЦИКЛ
2 Если А содержит всех клиентов Тогда Возврат(А) // - этот путь является решением.
3 ПОКА можно выбрать клиента К, которого нет в А ЦИКЛ // начинаем цикл
4. ЕСЛИ клиента нельзя добавить конец пути А ТОГДА продолжить;
5. Создаем новое недостроенное решение B = A.
6. Добавляем в конец пути B клиета К. Обновляем стоимости и время решения B.
7. Вставить в список решений B.
8. КонецЦикла; // идем пункту 3.
9. Удалить из списка решений A.
10. конецЦикла; // идем к пункту 1.

Алгоритм работает. Вроде бы даже находит оптимальное решение за пару десятков сек для 15 клиентов~)
Беда только одна Список Решений содержит очень большое количество элементов, что ввиду ограниченного объема оперативки не дает использовать его для большей размерности (надо хотя бы для 20-35).

Отсюда вопрос: может у кого есть идеи как не хранить весь этот список в ОЗУ?
...
Рейтинг: 0 / 0
10.02.2009, 13:12:31
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35808008
stopa85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stopa85
Гость
Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
1.  ПОКА Выбираем наименьший элемент А (недостроенный путь наименьшей длинны) и списка решений ЦИКЛ
2        Если А содержит всех клиентов Тогда Возврат(А) // - этот путь является решением.
3        ПОКА можно выбрать клиента К, которого нет в А ЦИКЛ // начинаем цикл
4.            ЕСЛИ клиента нельзя добавить конец пути А ТОГДА продолжить;
5.            Создаем новое недостроенное решение B = A.
6.            Добавляем в конец пути B клиета К. Обновляем стоимости и время решения B.
7.            Вставить в список решений B.
8.       КонецЦикла; // идем пункту 3.
9.   Удалить из списка решений A.
10. КонецЦикла; // идем к пункту 1.

Сорри, забыл офромить)
...
Рейтинг: 0 / 0
10.02.2009, 13:15:39
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35808407
Фотография Aklin J
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Aklin J
Участник
насколько понимаю, все задачи коммивояжера решаются матрицами

4 8 15 16 23 42
...
Рейтинг: 0 / 0
10.02.2009, 15:07:31
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35808599
stopa85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stopa85
Гость
Aklin Jнасколько понимаю, все задачи коммивояжера решаются матрицами
Задача коммивояжера решается методом ветвей и границ, или применительно к коммивояжеру - метод Литтла.
...
Рейтинг: 0 / 0
10.02.2009, 16:07:52
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35808840
Фотография AlexandrPlus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexandrPlus
Участник
здесь вроде тип алгоритма ближайшего соседа
решение неоптимальное, но если конец пути оказывается довольно быстр, то считают (по принц. динам. прогр. Беллм.), что решение довольно оптимально

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

А вообще Прологи под это "заточены" - подгружают, перегружают, ускоряются, "ленятся", ...

А промежуточные пункты-развилки путей допускаются? Насколько разряженная сеть связей между пунктами? ...

Это учебное или практическое (например, Интернет-магазин)?
...
Рейтинг: 0 / 0
10.02.2009, 17:11:01
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35809487
Фотография optimizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
optimizer
Участник
насколько понял здесь не метод динамического программирования, а метод ветвей и границ. Возможно используется обход в ширину, что требовательно к памяти. Попробуйте построить проход в глубину.
...
Рейтинг: 0 / 0
11.02.2009, 00:02:55
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35809657
stopa85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stopa85
Гость
AlexandrPlusА промежуточные пункты-развилки путей допускаются? Насколько разряженная сеть связей между пунктами? ...
В том-то и беда, что что граф "почти" полный. т.е. почти от любого клиента можно приехать к любому другому - это в теории. На практике можно будет пользоваться эвристиками, чтобы значительно сократить этот перебор.

AlexandrPlusЭто учебное или практическое (например, Интернет-магазин)?
Учебно-практическое. Это маленькая часть дипломной работы. Мне надо пользоваться этой подзадачей, что бы решить VRPwTW(от Vehicle routing problem with time window. Задача маршрутизации транспортных средств с учетом ограничений на грузоподъемность, и временные окна клиентов ). Мои преподы желают видеть "точное решение".
Если кому-то интересно - поделюсь материалом с которым пытаюсь разобраться (на английском)

optimizer ... метод ветвей и границ
Да, но... тут нужны оценки с низу и с верху... в этом вся проблема...
...
Рейтинг: 0 / 0
11.02.2009, 08:36:07
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35810336
Фотография optimizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
optimizer
Участник
так каким методом решает приведенный алгоритм? все таки динамическим программированием? не узнаю
...
Рейтинг: 0 / 0
11.02.2009, 12:26:33
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35811239
Фотография AlexandrPlus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexandrPlus
Участник
stopa85AlexandrPlusА промежуточные пункты-развилки путей допускаются? Насколько разряженная сеть связей между пунктами? ...
В том-то и беда, что что граф "почти" полный. т.е. почти от любого клиента можно приехать к любому другому - это в теории. На практике можно будет пользоваться эвристиками, чтобы значительно сократить этот перебор.


Такое на практике едва ли будет. В смысле - реальные пути-дороги.

stopa85
AlexandrPlusЭто учебное или практическое (например, Интернет-магазин)?
Учебно-практическое. Это маленькая часть дипломной работы. Мне надо пользоваться этой подзадачей, что бы решить VRPwTW(от Vehicle routing problem with time window. Задача маршрутизации транспортных средств с учетом ограничений на грузоподъемность, и временные окна клиентов ). Мои преподы желают видеть "точное решение".
Если кому-то интересно - поделюсь материалом с которым пытаюсь разобраться (на английском)

optimizer ... метод ветвей и границ
Да, но... тут нужны оценки с низу и с верху... в этом вся проблема...

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

и там же распределить грузы по грузовикам и назначить им пути - то есть не один, а несколько коммивояжеров, да еще грузы разложить - грузовики разные
и временнЫе окна, чтобы грузы были приняты

дальше заполнения транспортных листов из ИС с довводом с листов же в ИС после, не прошли, так как переключились на другие задачи

А диплом для реального предприятия?

Вообще любопытно.
Решающий такие задачи софт коммерческий такой тоже уже есть.
...
Рейтинг: 0 / 0
11.02.2009, 15:38:49
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35811321
Фотография AlexandrPlus
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
AlexandrPlus
Участник
и здесь 1С
простая маршрутизация

и водилы с КПК, где электронные маршрутные (путевые) листы
...
Рейтинг: 0 / 0
11.02.2009, 15:58:40
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35812425
stopa85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stopa85
Гость
optimizerтак каким методом решает приведенный алгоритм? все таки динамическим программированием? не узнаю
Да Вы правы. Это не метод динамического программирования и это не метод ветвей и границ. Это тупой поиск в ширину - он обречен на задачах большой размерности (25 клиентов это слишком много)
...
Рейтинг: 0 / 0
12.02.2009, 08:41:58
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35813387
Фотография optimizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
optimizer
Участник
на задачах большой размерности все обречены :)

Попробуйте, все таки, МВГ с проходом в глубину, с памятью точно проблем не будет. Проблемы будут со временем полного обхода дерева, т.е гарантированного нахождения оптимума. Для определения границы, если ничего оригинального не придумаете, то, в принципе, можно взять оценку текущего лучшего решения. Очень важную роль будет играть порядок сортировки ветвей при ветвлении (какие элементы решения в первую очередь рассматривать) - здесь надо применять эвристики для сортировки.
...
Рейтинг: 0 / 0
12.02.2009, 13:05:15
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35814067
stopa85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stopa85
Гость
optimizer,

Ок, попробую, правда результаты будут не скоро. Для оценки можно использовать решение Задачи линейного программирования (см рисунок), ну или с немного "расслабленными" ограничениями.
...
Рейтинг: 0 / 0
12.02.2009, 16:19:21
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35814927
Фотография optimizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
optimizer
Участник
хорошо, если можно представить задачу в ЛП, оценка границы результатом решения ЛП даст хороший отсев.
ЗЫ динамическое программирование, имхо, имеет хорошую эффективность, но в любом случае она подвержена проклятию размерности и ее минус в том, что нельзя остановить на половине работы и довольствоваться тем что получилось, в отличие от МВГ
...
Рейтинг: 0 / 0
13.02.2009, 03:07:35
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35815155
stopa85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stopa85
Гость
optimizer,
А что вы думаете по этому поводу?
Количество преременных в задаче порядка o(x^2), (не считая переменных, которые мы будем вводить для того чтобы задачу к каноническому виду... найти допустимый базис...)

Итого исходя из постановки для 30 клиентов будем иметь порядка 900 столбцов и 900 строк.
Не многовато ли? Ведь решать ее придется много-много раз? Или это как раз не проблема?
...
Рейтинг: 0 / 0
13.02.2009, 09:45:22
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35821270
борщ
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
борщ
Гость
stopa85optimizer,
А что вы думаете по этому поводу?
Количество преременных в задаче порядка o(x^2), (не считая переменных, которые мы будем вводить для того чтобы задачу к каноническому виду... найти допустимый базис...)

Итого исходя из постановки для 30 клиентов будем иметь порядка 900 столбцов и 900 строк.
Не многовато ли? Ведь решать ее придется много-много раз? Или это как раз не проблема?
Чё то непонимаю :граф с 30 вершинами?-почему тупо перебором нельзя решить?
...
Рейтинг: 0 / 0
17.02.2009, 09:25:02
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35821823
30!
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
30!
Гость
борщЧё то непонимаю :граф с 30 вершинами?-почему тупо перебором нельзя решить?
А сколько, по-вашему, вариантов надо перебрать?
Перестановки, что ли, да? Не напомните формулку?
...
Рейтинг: 0 / 0
17.02.2009, 12:13:49
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35823659
daunito
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
daunito
Участник
только недавно решал такую задачу. Метод ветвей и границ. Решается через матрицу путей, если первоначально есть стоимости, время или длина каждого. Для решения нужна матрица х*х. По идее работать должно быстро ибо на каждую матрицу для расчетов требуется доля секунды. Матриц будет х штук. Каждая следующая на единицу меньше предыдущей
...
Рейтинг: 0 / 0
18.02.2009, 03:29:26
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35824392
stopa85
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
stopa85
Гость
daunito,

Если честно я Вас не совсем понял.

Вы имеете ввиду алгоритм Литтла? (или что-то другое)

Если В процессе нахождения Гамельтонова цикла - проверять может ли текущее разбиение (та часть что уже построена) представлять собой часть решения, если нет - отбрасывать ветвь.

stopa85
Если торговец приходит к клиенту раньше назначенного интервала - он ждет "начала интервала". Придти позже не допустимо.
...
Рейтинг: 0 / 0
18.02.2009, 12:42:46
| Ответить | Цитировать | Написать  
Динамическое программирование. Поиск оптимального пути с ограничениями.
    #35832043
Фотография optimizer
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
optimizer
Участник
stopa85optimizer,
А что вы думаете по этому поводу?
Количество преременных в задаче порядка o(x^2), (не считая переменных, которые мы будем вводить для того чтобы задачу к каноническому виду... найти допустимый базис...)

Итого исходя из постановки для 30 клиентов будем иметь порядка 900 столбцов и 900 строк.
Не многовато ли? Ведь решать ее придется много-много раз? Или это как раз не проблема?

сложно сказать, тем более не понимаю как будете делать ветвление, лучше попробовать, тем более существуют готовые реализации для решения задач ЛП
...
Рейтинг: 0 / 0
22.02.2009, 22:58:01
| Ответить | Цитировать | Написать  
20 сообщений из 20, страница 1 из 1
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Динамическое программирование. Поиск оптимального пути с ограничениями.
Найденые пользователи ...
Разблокировать пользователей ...
Читали тему (0):
Читали форум (0):
Пользователи онлайн (0):
Польз. соглашение   Полит. конфиден.  
NoSQL.ru       Кролег: Проекты, Новости, Чат       РЕД ФОРУМ       Фотоальбом: Участники, Встречи
Закрыть
start [/forum/topic.php?fid=16&msg=35808840&tid=1344652]:
 0ms
get settings:
 9ms
get forum list:
 13ms
check forum access:
 2ms
check topic access:
 2ms
track hit:
 175ms
get topic data:
 10ms
get forum data:
 2ms
get page messages:
 52ms
get tp. blocked users:
 1ms
others: 239ms
total:  505ms
созд. / загр.: 505ms
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]