Специальная часть
Описание метода решения
Для того, чтобы начать решать задачу необходимы условия задачи, в данном случае они представлены в виде таблицы. В таблице даны расстояния между городов.
В условии сказано, что коммивояжер начинает свой маршрут из города 1.
1)По таблице находим город 1 и по строке начинаем искать тот город, который будет давать наименьшее приращение к длине пути или город, ближайший к городу 1.
2) Так как путь только начался то расстояние, пройденное коммивояжером, будет равно нулю, значит к нему прибавляем найденное расстояние.
3) После этого записываем получившуюся сумму, и продолжаем искать город , подходящий к маршруту, после того как следующий город найден, расстояния снова складываются.
4) После того как все города использованы в маршруте, наша задача вернуться в город 1, откуда начинался маршрут, по строке последнего города смотрим расстояние до города 1 и прибавляем его к получившейся сумме расстояний между городов.
5) В результате этих действий находят оптимальный маршрут, с самым коротким расстоянием между городов.
Решение задачи теста для написания и отладки программы
В
данной таблице приведены все условия
для решения задачи, а именно длинны
путей между городами. Q
– расстояние, L
- шаг
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
1 |
|
5 |
11 |
6 |
3 |
15 |
8 |
2 |
5 |
|
7 |
12 |
6 |
7 |
2 |
3 |
11 |
7 |
|
3 |
6 |
3 |
7 |
4 |
6 |
12 |
3 |
|
2 |
4 |
13 |
5 |
3 |
6 |
6 |
2 |
|
2 |
5 |
6 |
15 |
7 |
3 |
4 |
1 |
|
4 |
7 |
8 |
2 |
7 |
13 |
5 |
4 |
|
Q =
L = 1
=
L = 1->5
Q = Q
L = 1->5->4
Q = Q +
Q
+
= 5 + 3 = 8
L = 1->5->4->3
Q = Q +
L = 1->5->4->3->6
Q = Q +
L = 1->5->4->3->6->7
Q = Q +
L = 1->5->4->3->6->7->2
Q = Q +
L = 1->5->4->3->6->7->2->1
Анализ полученных результатов
В результате решения задачи самым оптимальным маршрутом между данными городами был выявлен маршрут, состоящий из семи шагов, а именно:
1->5->4->3->6->7->2->1.
Длинна пройденного пути для этого маршрута оказалась самой наименьшей:
Q = 22
Разработка алгоритма
После того как пользователь запустил исполняемый файл, на рабочем столе появится пустое окно (рис В1), в котором пользователь должен ввести цифру количества столбцов и строк таблицы. Число строк соответствует числу городов. Так как созданная таблица будет квадратная , то пользователю достаточно ввести одну цифру. Данная форма создаст число переменных в соответствии с количеством ячеек таблицы.
Далее открывается окно с созданной таблицей (рис. В2), в которую следует ввести цифры из таблицы, данной в качестве условия пользователю. Цифры соответствуют расстояниям между городами. В данном окне так же возможен выбор города, с которого коммивояжер начнет маршрут. Программа будет проверять минимальный элемент по строке, и суммировать его с количеством уже пройденного пути.
После того, как все поля таблицы заполнены, следует нажать кнопку «Продолжить» будет произведен подсчет согласно формулам подсчета задач коммивояжера.
В третьем окне появится результат подсчетов программы, а именно оптимальный маршрут между данными городами и расстояние, потраченное на прохождение этого маршрута.(рис.В3) ответ будет выведен с помощью цифры с количеством пройденного пути и маршрута в виде цифр и стрелок
После выполнения всех этих действий пользователь может закрыть окно с программой, после чего она завершает работу.