Дискуссионный математический форумМатематический форум
Математический форум Math Help Planet

Обсуждение и решение задач по математике, физике, химии, экономике

Теоретический раздел
Часовой пояс: UTC + 3 часа [ Летнее время ]
новый онлайн-сервис
число, сумма и дата прописью

Часовой пояс: UTC + 3 часа [ Летнее время ]




Начать новую тему Ответить на тему  [ Сообщений: 7 ] 
Автор Сообщение
 Заголовок сообщения: Задача коммивояжера
СообщениеДобавлено: 06 май 2016, 22:39 
Не в сети
Начинающий
Зарегистрирован:
06 май 2016, 22:35
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Такой вопрос, всегда ли задача киммивояжера (метод ветвей и границ) имеет решение, и если нет, как выявить его отсутствие ?

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача коммивояжера
СообщениеДобавлено: 07 май 2016, 10:19 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
Всегда, в силу конечности вариантов.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача коммивояжера
СообщениеДобавлено: 07 май 2016, 23:35 
Не в сети
Начинающий
Зарегистрирован:
06 май 2016, 22:35
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
А если будет задан например такой граф ?
Тогда уже не получиться составить такой замкнутый маршрут, при котором комивояжер побывает в каждом городе 1 раз и вернется в исходный.
Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача коммивояжера
СообщениеДобавлено: 07 май 2016, 23:47 
Не в сети
Light & Truth
Зарегистрирован:
28 мар 2014, 23:59
Сообщений: 6312
Cпасибо сказано: 633
Спасибо получено:
509 раз в 477 сообщениях
Очков репутации: 47

Добавить очки репутацииУменьшить очки репутации
Получится, но с началом движения не из всякого города!

Ан нет, извиняюсь, не получится.

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

Снова соврал :)

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача коммивояжера
СообщениеДобавлено: 08 май 2016, 07:05 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

Добавить очки репутацииУменьшить очки репутации
В задаче коммивояжера нет условия побывать в каждом городе ровно один раз. В ней надо объехать все города по самому выгодному маршруту, пусть даже при этом какой-то город придется посетить 2 или более раз.

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача коммивояжера
СообщениеДобавлено: 08 май 2016, 12:35 
Не в сети
Начинающий
Зарегистрирован:
06 май 2016, 22:35
Сообщений: 3
Cпасибо сказано: 0
Спасибо получено:
0 раз в 0 сообщении
Очков репутации: 1

Добавить очки репутацииУменьшить очки репутации
Насчет последнего не согласен, так как услоие побывать в каждом городе 1 раз четко говорится в условии и обозначается в математической модели (на скрине книга Зайченко Ю.П. "Дослідження операцій").
К тому же при решении методом ветвей и границ при добавлении перехода (i,j) в маршрут, вычеркивается ряд i и столбец j, а значит мы больше не можем выехать из i или вьехать в j с другого города.
Так как же определить, что задача не имеет решения ?
Изображение

Вернуться к началу
 Профиль  
Cпасибо сказано 
 Заголовок сообщения: Re: Задача коммивояжера
СообщениеДобавлено: 08 май 2016, 12:57 
Не в сети
Последняя инстанция
Зарегистрирован:
06 дек 2014, 09:11
Сообщений: 7070
Cпасибо сказано: 115
Спасибо получено:
1662 раз в 1508 сообщениях
Очков репутации: 283

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

Вернуться к началу
 Профиль  
Cпасибо сказано 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему      Страница 1 из 1 [ Сообщений: 7 ]

 Похожие темы   Автор   Ответы   Просмотры   Последнее сообщение 
Задача коммивояжера

в форуме Исследование операций и Задачи оптимизации

befree666

0

379

05 июн 2014, 20:51

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

в форуме Дискретная математика, Теория множеств и Логика

rny

0

393

07 ноя 2015, 13:50

Об одном алгоритме коммивояжера

в форуме Дискуссионные математические проблемы

Individ1

5

290

12 апр 2021, 12:36

Решение разомкнутой обобщенной задачи коммивояжера

в форуме Исследование операций и Задачи оптимизации

lgalimova

0

436

26 июн 2015, 09:41

Решить задачу коммивояжера с матрицей расстояний

в форуме Дискретная математика, Теория множеств и Логика

Roman_152

1

210

18 янв 2021, 20:33

Теория вероятности: задача про шары и задача про точку

в форуме Теория вероятностей

AdmiralAnanas

6

484

02 окт 2021, 01:43

Задача на построение. Корректна ли задача?

в форуме Геометрия

Student Studentovich

9

663

19 июл 2020, 19:17

Задача №30

в форуме Интересные задачи участников форума MHP

andrei

4

451

10 дек 2017, 07:13

Задача

в форуме Экономика и Финансы

denisi-svetlana

7

624

31 мар 2015, 16:45

Задача №28

в форуме Интересные задачи участников форума MHP

andrei

7

838

29 ноя 2017, 15:10


Часовой пояс: UTC + 3 часа [ Летнее время ]



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 12


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Перейти:  

Яндекс.Метрика

Copyright © 2010-2023 MathHelpPlanet.com. All rights reserved