Коммивояжер
Добавлено: Вс, 11 дек 2005, 0:03
Помогите пожалуйста решить задачу методом ветвей и границ
Условия
Студент 4- го курса Уфимского университета после успешной сдачи сессии решил попутешествовать по свету. Он решил посетить несколько городов. Вооружившись справочником по маршрутам воздушного сообщения различных авиакомпаний, он занес в следующую таблицу стоимости полета из одного города в другой. Виза, которую получил студент не позволяет повторно возвращается в уже посещенный город. После составления этой таблицы он понял, что необходимо так выбрать маршрут своего путешествия, чтобы сумма, потраченная на билет была минимальной и чтобы не приходилось посещать один город 2 раза.
Таблица городов здесь http://slil.ru/22478778
Условия
Студент 4- го курса Уфимского университета после успешной сдачи сессии решил попутешествовать по свету. Он решил посетить несколько городов. Вооружившись справочником по маршрутам воздушного сообщения различных авиакомпаний, он занес в следующую таблицу стоимости полета из одного города в другой. Виза, которую получил студент не позволяет повторно возвращается в уже посещенный город. После составления этой таблицы он понял, что необходимо так выбрать маршрут своего путешествия, чтобы сумма, потраченная на билет была минимальной и чтобы не приходилось посещать один город 2 раза.
Таблица городов здесь http://slil.ru/22478778