Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Даны множество вершин и множество дуг . Здесь вершины представляют города, а дуги ‑ упорядоченные пары и городов, между которыми возможна непосредственная поездка, время которой . Цель ‑ нахождение маршрута, начиная с города 1, с минимальным временем, и проходящего через каждый город только один раз.
Введем бинарную решающую переменную :
Задача коммивояжера может быть сформулирована в виде следующей задачи ДО:
при ограничениях
(в каждый город въезжают только один раз),
(из каждого города выезжают только один раз),
Дата публикования: 2015-01-23; Прочитано: 168 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!