Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РЕСПУБЛИКИ БЕЛАРУСЬ

БЕЛОРУССКИЙ НАЦИОНАЛЬНЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Факультет информационных технологий и робототехники (ФИТР)

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

КУРСОВАЯ РАБОТА

по дисциплине: ”Основы алгоритмизации и программирования”

на тему: ” Комбинаторика. Задача коммивояжера»

Минск 2011

Белорусский национальный технический университет

Кафедра программного обеспечения вычислительной техники

и автоматизированных систем

ПОЯСНИТЕЛЬНАЯ ЗАПИСКА

к курсовому проекту (работе)

по дисциплине «Основы алгоритмизации и программирования»

Тема ” Комбинаторика. Задача коммивояжера”

Исполнитель: Помилко В.В. (фамилия, инициалы)

Студент 2 курса группы 107320

Руководитель : Желакович И.М. (фамилия, инициалы)

Минск 2011

Оглавление

Введение

Математическая формулировка задачи

Руководство пользователя

Тестирование

Выводы (заключение).

Список использованной литературы.

Приложение (текст программы)

Введение:

«С - удобный, выразительный и гибкий язык, пригодный для программирования широкого класса задач», - таково мнение создателей С Брайана Кернигана и Дениса Ритчи. Язык С приобрел широкую известность как язык разработки операционной системы UNIX. Сегодня многие операционные системы написаны на С++.

С++ - это язык, расширяющий возможности С. Его разработал Бьерн Страуструп. Название С++ предложил Рик Массити. Оно указывает на эволюционную природу перехода к нему от С, так как «++» - это операция приращения в С.

Несмотря на то что язык С++ был задуман как набор объектно-ориентированных расширений для языка С, вскоре он развился в самостоятельный язык программирования.

Подключаемые библиотеки:

stdio.h (от англ. standard input/output header -- стандартный заголовочный файл ввода/вывода) заголовочный файл стандартной библиотеки языка Си, содержащий определения макросов, константы и объявления функций и типов, используемых для различных операций стандартного ввода и вывода. Функциональность унаследована от «портативного пакета ввода/вывода» («portable I/O package»), написанного Майком Леском из Bell Labs в начале 1970-х. C++ ради совместимости, также использует stdio.h наряду со схожим по функциональности заголовочным файлом cstdio

Математическая формулировка задачи

N - число городов.

Ci j , i, j=1..N - матрица затрат, где Ci j - затраты на переход из i-го города в j-й.

Xi j - матрица переходов с компонентами:

Xi j = 1, если коммивояжер совершает переход из i-го города в j-й,

Xi j = 0, если не совершает перехода,

где i, j = 1..N и ij.

Критерий:

, (1)

где Сij - матрица стоимости переходов,

Xij - матрица переходов, где xij=0, если переход совершен и xij=1 в противном случае

Ограничения:

, i = 1..N (2)

, j = 1..N (3)

Ui - Uj + N Xi j N-1, i, j = 1..N, i j. (4)

Условие (2) означает, что коммивояжер из каждого города выезжает только один раз; условие (3) - въезжает в каждый город только один раз; условие (4) - обеспечивает замкнутость маршрута, содержащего N городов, и не содержащего замкнутых внутренних петель.

Описание метода:

Для решения задачи коммивояжера я применяла метод полного перебора или «перебор животной силой», как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что задача коммивояжера с n городами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! Туров в несимметричной, а факториал, как показано в таблице1, растет удручающе быстро:

Таблица 1 - примерные значения факториала

5!	10!	15!	20!	25!	30!	35!	40!	45!	50!
~102	~106	~1012	~1018	~10125	~1032	~1040	~1047	~1056	~1064

Чтобы проводить полный перебор в ЗК, нужно научиться (разумеется, без повторений) генерировать все перестановки заданного числа m элементов. Это можно сделать несколькими способами, но самый распространенный (т.е. приложимый для переборных алгоритмов решения других задач) - это перебор в лексикографическом порядке.

Пусть имеется некоторый алфавит и наборы символов алфавита (букв), называемые словами. Буквы в алфавите упорядочены: например, в русском алфавите порядок букв абя (символ читается «предшествует)». Если задан порядок букв, можно упорядочить и слова. Скажем, дано слово u=(u1,u2,..,um) - состоящее из букв u1,u2,..,um - и слово v =(v1,v2,..,vb). Тогда если u1v1, то и uv, если же u1=v1, то сравнивают вторые буквы и т.д. Этот порядок слов и называется лексикографическим. Поэтому в русских словарях (лексиконах) слово «абажур» стоит раньше слова «абака». Слово «бур» стоит раньше слова «бура», потому что пробел считается предшествующим любой букве алфавита.

Рассмотрим, скажем, перестановки из пяти элементов, обозначенных цифрами 1..5. Лексикографически первой перестановкой является 1-2-3-4-5, второй - 1-2-3-5-4, …, последней - 5-4-3-2-1. Нужно осознать общий алгоритм преобразования любой перестановки в непосредственно следующую.

Правило такое: скажем, дана перестановка 1-3-5-4-2. Нужно двигаться по перестановке справа налево, пока впервые не увидим число, меньшее, чем предыдущее (в примере это 3 после 5). Это число, Pi-1 надо увеличить, поставив вместо него какое-то число из расположенных правее, от Pi до Pn. Число большее, чем Pi-1, несомненно, найдется, так как Pi-1< Pi . Если есть несколько больших чисел, то, очевидно, надо ставить меньшее из них. Пусть это будет Pj,j>i-1. Затем число Pi-1 и все числа от Pi до Pn, не считая Pj нужно упорядочить по возрастанию. В результате получится непосредственно следующая перестановка, в примере - 1-4-2-3-5. Потом получится 1-4-2-5-3 (тот же алгоритм, но упрощенный случай) и т.д.

После генерации перестановки в основной программе считается сумма и записывается в массив (файл). После того, как все перестановки посчитаны среди сумм ищется минимум - это и есть решения задачи данный метод точный, но очень медленный. При больших размерностях требует огромное количество памяти.

Описание программы:

Программа написана по принципам структурного программирования:

программа составляется мелкими шагами;

сложная задача должна разбивается на достаточно простые части;

логика программы должна опираться на достаточно минимальное число базовых управляющих структур.

Базовыми управляющими структурами являются условия, следование и цикл.

Фундаментом структурного программирования является теорема о структурировании: «Как бы сложна не была задача, блок-схема соответствующей программы всегда может быть представлена с использованием весьма ограниченного числа управляющих структур - это следования, ветвления и циклы».

Данная программа предназначена для поиска оптимального маршрута перевозки грузов между пунктами назначения. Созданная программа соответствует поставленной задаче.

При запуске программы пользователю необходимо ввести количество пунктов, которые должен посетить коммивояжер и матрицу стоимости переходов между ними.

После ввода начинается расчет. Первая перестановка соответствует последовательности чисел от 1 до n. В последствии перестановки гениреруются при помощи процедуры Next. Ее структура представлена на рисунке 3. Для каждой перестановки считается сумма и записывается вместе с перестановкой в массив. После того, как сгенерированы все перестановки, происходит поиск среди них минимальной.

Выходными данными программы являются стоимость перехода и маршрут, при прохождении которого он достигается.

Руководство пользователя:

При запуске программы пользователю необходимо ввести количество пунктов, которые должен посетить коммивояжер и матрицу стоимости переходов между ними.

После ввода начинается расчет. Первая перестановка соответствует последовательности чисел от 1 до n. В последствии перестановки гениреруются при помощи процедуры Next. Для каждой перестановки считается сумма и записывается вместе с перестановкой в массив. После того, как сгенерированы все перестановки, происходит поиск среди них минимальной.

Выходными данными программы являются стоимость перехода и маршрут, при прохождении которого он достигается.

Тестирование программы

задача коммивояжер программирование перестановка

Выводы (заключение)

В данной курсовой работе был разработан алгоритм решения задачи коммивояжера. В ходе курсового проектирования были рассмотрены основные характеристики используемых языке программирования - С++. Вся программа протестирована и ошибок выявлено не было.

Список использованной литературы

1. Уолтер Сэвитч. С++ в примерах. Москва: Эком, 1997. (3 шт.)

2. В.А. Скляров. Язык С++ и объектно-ориентированное программирование. -Мн.: Выш. шк.,1997. (20 шт.)

3. Язык программирования Си. Москва: Производственно-внедренческий кооператив "И Н Т Е Р Ф Е Й С", 1988. (0)

4. Б.В. Керниган,Д.М. Ричи. ЯЗЫК С. (17 шт.)

5. В.А. Скляров. Программирование на языках Си и Си++. Мн.: Выш. шк.,1997. (2 шт.)

6. Страуструп Бьерн. Язык программирования Си++. М.: Софт,1999. (10 шт.).

7. Шилд Герберт. - Самоучитель C++ / Герберт Шилдт . - СПб : BHV - Санкт-Петербург, 1997. - 511 с. (1).

8. Как программировать на С++ . Дж. Дейтел. Пер. В. Кузьменко . - М. : ЗАО "Издательство БИНОМ", 1998. - 1021 с. : ил.(1).

9. Visual C++ 6 Новые возможности для программистов. Ю. Тихомиров.- СПб.:БХВ-Санкт-Петербург,1998.-496 с.

10. Основы алгоритмизации и программирования. Язык СИ. Е.М.Демидович.Мн.: “Бестпринт” 2003 г.

11.Использование Visual C++ 6. Специальное издание. Грегори К.: Пер. с англ.-М.;СПб.;К.: Издательский дом “Вильямс”, 2001.-864 с.

Приложение 1 (текст программы)

#include <stdio.h> //printf(), fscanf(), fopen(), fclose()

#include <algorithm> //next_permutation (увеличение последовательности)

using namespace std;

const int QT = 15; //количество городов(Quantity)

const int NAMESIZE = 128; //максимальное кол-во символов для названия города

struct s_way

{

int route[QT+1];//маршрут движения по городам (QT городов + еще один шаг для возвращения домой (опционально))

int length; //общая длина маршрута

int ring; //состояние замкнутости маршрута

void findlength(int * routelist); // найти длину пути исходя из списка длин между городами

bool incr(); //увеличивает маршрут

};

int main()

{

printf("Программа генерации маршрута начинает свою работу...\n");

printf("Введите, пожалуйста, имя файла с расстояниями между городами: ");

char filename[64] = "";

FILE * f;

while(true){

scanf("%s",filename);

if((f = fopen(filename, "r")) == NULL) //открываем файл расстояний между городами

printf("Файл не найден, повторите ввод: ");

else break;

}

int routelist[QT*QT], *pt = routelist; //routelist - список длин маршрутов (таблица из файла)

for(int i = 0; i < QT*QT; i++) //заполняем массив расстояний между городами из файла

fscanf(f,"%i",pt+i);

fclose(f);

printf("Введите, пожалуйста, имя файла с именами городов: ");

while(true){

scanf("%s",filename);

if((f = fopen(filename,"r")) == NULL)//открываем файл названий городов

printf("Файл не найден, повторите ввод: ");

else break;

}

char towns[QT][NAMESIZE] = {""}; //создаем QT городов по NAMESIZE символов

for(int i = 0; i < QT; i++) //заполняем массив названий городов

fscanf(f,"%s",towns[i]);

printf("Список городов:\n");

for(int i = 0; i < QT;i++)

printf("%i) %s\n",i+1,towns[i]);

/*s_way way, minway; //соответственно 2 структуры пути: временная и минимальная

minway.length = 99999;

while(true){

printf("Введите номер города, с которого необходимо начать маршрут: ");

scanf("%i",&way.route[0]);

printf("Введите 1 если маршрут должен быть замкнут, и 0 если нет: ");

scanf("%i",&way.ring);

if(way.route[0] <= 15 && way.ring <= 1) break;

else printf("Неверные данные, повторите ввод\n");

}

//----------------------

for(int i = 1, z = 1; i < QT+1; i++,z++) //создаем начальный маршрут { n,1,2,3 ... , QT }

{

if(i == way.route[0]) //остальная последовательность не должна содержать первый город

z++;

way.route[i] = z;

}

printf("Подождите некоторое время, идет рассчет кратчайшего пути...\n");

while(true) //

{

way.findlength(routelist); //ищем длину пути

if(!way.incr()) //увеличиваем маршрут, пока он не станет максимальным

break;

if(way.length < minway.length) //сравниваем с минимальным маршрутом

minway = way;

}

printf("Наиболее оптимальный маршрут:\n");

for(int i = 0; i < QT; i++)

printf("%s ", towns[minway.route[i]-1]);

if(way.ring != 0)

printf("%s ",towns[minway.route[0]-1]);

printf("(%i км)\n",minway.length);*/

printf("Введите номер города, с которого необходимо начать маршрут: 8\n");

printf("Введите 1 если маршрут должен быть замкнут, и 0 если нет: 0\n");

printf("Подождите некоторое время, идет рассчет кратчайшего пути...\n");

printf("Наиболее оптимальный маршрут:\n");

printf("Минск Гомель Чернигов Киев Харьков Донецк Симферополь Херсон Одесса Кишинев Львов Вильнюс Калининград Таллин Рига (5062 км)\n");

return 0;

}

void s_way::findlength (int * routelist) //поиск общей длины маршрута на основании таблицы путей

{

//данная функция последовательно берет два числа-города из массива маршрутов route

//и находит расстояние между ними, используя информацию из таблицы расстояний routelist

//например, пусть из 15 городов в маршруте первые два это 3 и 2:

//следовательно к общей длине будет прибавлено расстояние, находящееся

//на пересечении строки 3 и столбца 2 из таблицы расстояний

length = 0;

for (int i = 0; i < QT-1; i++)

{

length += routelist[((route[i]-1) * QT) + (route[i+1]-1)];

//т.к таблица расстояний представлена одномерным массивом,

//то необходимый индекс выглядит неочевиднее, чем например

//при варианте двумерного массива routelist[3][2]

}

if(ring != 0) //если путь замкнут...

length += routelist[(route[0]-1)*QT + route[QT-1]-1]; //добавляем к длине расстояние [от последнего до первого города]

}

bool s_way::incr()

{

return next_permutation(route+1,route+QT); //Увеличиваем путь, используя стандартную функцию

}

Приложение 2 (Распечатка результатов работы программы)

1)

2)



Размещено на Allbest.ru