close

Вход

Забыли?

вход по аккаунту

?

Постановка задачи

код для вставкиСкачать
 Постановка задачи.
Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:
* маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;
* в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.
Для расчета затрат существует матрица условий, содержащая затраты на переход из каждого города в каждый, при этом считается, что можно перейти из любого города в любой, кроме того же самого (в матрице как бы вычеркивается диагональ). Целью решения является нахождения маршрута, удовлетворяющего всем условиям и при этом имеющего минимальную сумму затрат.
Состав выполняемых функций.
Нахождение кратчайшего пути от одного населённого пункта к другому возможен следующий состав выполняемых функций:
* Ввод данных пользователем с клавиатуры - вводится число населённого пункта и вес, соединяющие их;
* Вывод результата - пользователь задаёт начальный и конечный населённый пункт, между которыми необходимо продолжить путь, на экран появляется маршрут.
Требование к входным и выходным данным.
Для рассматриваемой задачи " Нахождение кратчайшего пути от одного населенного пункта к другому" необходимо при реализации задачи предусмотреть следующие условия: при вводе необходимо указать, пункт назначение и пункт источник, а так же вес каждого пути указать неотрицательными числами, названия самих городов недопустимы.
Относительно задачи коммивояжера уместно сделать два замечания.
Во-первых, в постановке Сij означали расстояния, поэтому они должны быть неотрицательными, т.е. для всех jТ: Сij0; Cjj=∞ (1) (последнее равенство означает запрет на петли в туре), симметричными, т.е. для всех i,j: Сij= Сji. (2)и удовлетворять неравенству треугольника, т.е. для всех:
Сij+ СjkCik(3) Второе замечание касается числа всех возможных туров. В несимметричной задаче коммивояжёре все туры t=(j1,j2,..,jn,j1) и t'=(j1,jn,..,j2,j1) имеют разную длину и должны учитываться оба. Разных туров очевидно (n-1)!.
Необходимо разработать программу с использованием модульного программирования осуществляющую нахождение кратчайшего пути между городами, задаваемым пользователем в процессе работы. 
Документ
Категория
Рефераты
Просмотров
26
Размер файла
69 Кб
Теги
задачи, постановка
1/--страниц
Пожаловаться на содержимое документа