Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Страница 1 из 1 |
[ Сообщений: 7 ] |
|
Автор | Сообщение | |
---|---|---|
Wolffgan |
|
|
|
||
Вернуться к началу | ||
swan |
|
|
Всегда, в силу конечности вариантов.
|
||
Вернуться к началу | ||
Wolffgan |
|
|
Вернуться к началу | ||
ivashenko |
|
|
Получится, но с началом движения не из всякого города!
Ан нет, извиняюсь, не получится. Вроде бы графы для которых это получится называются Эйлеровыми, если не ошибаюсь. Снова соврал |
||
Вернуться к началу | ||
swan |
|
|
В задаче коммивояжера нет условия побывать в каждом городе ровно один раз. В ней надо объехать все города по самому выгодному маршруту, пусть даже при этом какой-то город придется посетить 2 или более раз.
|
||
Вернуться к началу | ||
Wolffgan |
|
|
Насчет последнего не согласен, так как услоие побывать в каждом городе 1 раз четко говорится в условии и обозначается в математической модели (на скрине книга Зайченко Ю.П. "Дослідження операцій").
К тому же при решении методом ветвей и границ при добавлении перехода (i,j) в маршрут, вычеркивается ряд i и столбец j, а значит мы больше не можем выехать из i или вьехать в j с другого города. Так как же определить, что задача не имеет решения ? |
||
Вернуться к началу | ||
swan |
|
|
Можно добавлять и условие ровно 1 раз, если речь идет о метрической задаче коммивояжера. Т.е. наш граф полный, а для любых трех точек выполнено неравенство треугольника. В таком случае, посещать дважды одну точку попросту невыгодно.
|
||
Вернуться к началу | ||
[ Сообщений: 7 ] |
Похожие темы | Автор | Ответы | Просмотры | Последнее сообщение |
---|---|---|---|---|
Задача коммивояжера | 0 |
379 |
05 июн 2014, 20:51 |
|
Задача коммивояжера с использованием алгоритма Флойда | 0 |
393 |
07 ноя 2015, 13:50 |
|
Об одном алгоритме коммивояжера | 5 |
290 |
12 апр 2021, 12:36 |
|
Решение разомкнутой обобщенной задачи коммивояжера | 0 |
436 |
26 июн 2015, 09:41 |
|
Решить задачу коммивояжера с матрицей расстояний | 1 |
210 |
18 янв 2021, 20:33 |
|
Теория вероятности: задача про шары и задача про точку
в форуме Теория вероятностей |
6 |
484 |
02 окт 2021, 01:43 |
|
Задача на построение. Корректна ли задача?
в форуме Геометрия |
9 |
663 |
19 июл 2020, 19:17 |
|
Задача №30 | 4 |
451 |
10 дек 2017, 07:13 |
|
Задача
в форуме Экономика и Финансы |
7 |
624 |
31 мар 2015, 16:45 |
|
Задача №28 | 7 |
838 |
29 ноя 2017, 15:10 |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Кто сейчас на конференции |
Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12 |
Вы не можете начинать темы Вы не можете отвечать на сообщения Вы не можете редактировать свои сообщения Вы не можете удалять свои сообщения Вы не можете добавлять вложения |