Решение задачи коммивояжера методом полного перебора

Министерство образования и науки российской федерации

Федеральное агентство по образованию и науки

Федеральное государственное образовательное учреждение среднего профессионального образования

«Пермский химико-технологический техникум»

Специальность 230105

«Программное обеспечение вычислительной техники и автоматизированных систем»

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

Дисциплина: «Математические методы»

Тема: «Задача коммивояжера»

Выполнил студент гр. П-07-1

_____________ (А.Н. Паньков)

Руководитель проекта

_____________ (Е.В. Задорожная)

2009

Оглавление

• ВВЕДЕНИЕ

ОБЩАЯ ЧАСТЬ

1.1 Цель разработки

1.2 Анализ использования разработки

1.3 Анализ методов решения

1.4 Анализ средств программирования

1.4.1Обзор средств программирования

1.4.2 Характеристика программного обеспечения

1.4.3 Характеристика ПК

1.4.4 Характеристика языка программирования

2. СПЕЦИАЛЬНАЯ ЧАСТЬ

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

2.2. Математическая модель задачи

2.3 Описание метода решения

2.4 Характеристика программы

2.5 Описание процесса отладки и тестирования программы

2.6 Оценка результатов работы программы

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ

ПРИЛОЖЕНИЕ

АНАЛИЗ РАБОТЫ ПРОГРАММЫ

ВВЕДЕНИЕ

Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок” (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование” здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу.

Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”. Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной.

Цель курсовой работы изучить метод полного перебора для решения одной задач линейного программирования - задачи «О коммивояжере» и составить алгоритм и программу для ее решения.

Работа состоит из введения, семи частей, заключения и приложения, в котором приведена программа на языке Borland Delphi, позволяющая находить точное решение задачи.

ОБЩАЯ ЧАСТЬ

1.1 Цель разработки

Данная курсовая работа разрабатывалась с целью повышения уровня образования необходимого выполнения учебного плана задания на курсовую работу по дисциплине «Математические методы» согласно рабочей программы специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем».

1.2 Анализ использования разработки

Сейчас решение данной задачи необходимо во многих областях промышленности и народного хозяйства, связанных с замкнутыми и при этом жестко связанными по времени системами, такими как: конвейерное производство, многооперационные обрабатывающие комплексы, судовые и железнодорожные погрузочные системы, перевозки грузов по замкнутому маршруту, расчет авиационных линий.

1.3 Анализ методов решения

Для решения «Задачи коммивояжера» существует несколько методов решения. Отличаются они прежде всего скоростью решения и точностью.

«Жадный» алгоритм

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

Деревянный алгоритм

Суть метода состоит в построении кратчайшего остовного дерева. Погрешность такого алгоритма равна единице, скорость высокая

Полный перебор

Практически применим только в задачах малого размера. Напомним, что ЗК с n городами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-1)! туров в несимметричной задачи.

Метод ветвей и границ

К идее метода ветвей и границ приходили многие исследователи, но Литтл с соавторами на основе указанного метода разработали удачный алгоритм решения ЗК и тем самым способствовали популяризации подхода. С тех пор метод ветвей и границ был успешно применен ко многим задачам, для решения ЗК было придумано несколько других модификаций метода, но в большинстве учебников излагается пионерская работа Литтла.

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

Алгоритм Дейкстры

Одним из вариантов решения ЗК является вариант нахождения кратчайшей цепи, содержащей все города. Затем полученная цепь дополняется начальным городом - получается искомый тур.

В ориентированной, неориентированной или смешанной (т. е. такой, где часть дорог имеет одностороннее движение) сети найти кратчайший путь между двумя заданными вершинами.

Алгоритм использует три массива из n (= числу вершин сети) чисел каждый. Первый массив a содержит метки с двумя значениями: 0 (вершина ещё не рассмотрена) и 1 (вершина уже рассмотрена); второй массив b содержит расстояния - текущие кратчайшие расстояния от vi до соответствующей вершины; третий массив c содержит номера вершин - k-й элемент ck есть номер предпоследней вершины на текущем кратчайшем пути из vi в vk. Матрица расстояний Dik задаёт длины дуг dik; если такой дуги нет, то dik присваивается большое число Б, равное «машинной бесконечности».

1.4 Анализ средств программирования

1.4.1Обзор средств программирования

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

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

- Трансляторы с языков высокого уровня

- Средства редактирования, компоновки и загрузки программ

- Машинно-ориентированные языки

- Отладчики машинных программ

Системы программирования включают в себя:

- Текстовый редактор (Edit)

- Загрузчик программ (Load)

- Запускатель программ (Run)

- Компилятор (Compile)

- Отладчик (Debug)

- Диспетчер файлов (File)

Ядро системы программирования составляет язык. Существующие языки программирования можно разделить на 2 группы: процедурные и непроцедурные (рис.1)

Рис.1 Классификация языков программирования

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

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

Программы на языках высокого уровня близки к естественному (английскому) языку и представляют набор заданных команд.

Перечислим наиболее известные системы программирования:

1. Фортран (FORmula TRANslating system-система трансляции формул) - старейший и по сей день, активно использующийся в решении математической ориентации язык.

2. Бейсик (Beginner's All-purpose Symbolic Instruction Code-универсальный символический код инструкций для начинающих) - несмотря на многие недостатки и изобилие плохо совместимых версии - самый популярный по числу пользователей.

3. Алгол (ALGOrithmic Language-алгоритмический язык) - сыграл большую роль в теории, но для практического программирования сейчас почти не используется.

4. ПЛ/1 (PL/1 Programming Language-язык программирования первый) - многоцелевой язык, сейчас почти не используется.

5. Паскаль (Pascal-назван в честь ученого Блеза Паскаля) - чрезвычайно популярен как при изучении программирования, так и среди профессионалов. На его базе были созданы несколько более мощных языков (Модула, Ада, Дельфи).

6. Кобол (COmmon Business Oriented Language-язык, ориентированный на общественный бизнес) - в значительном мире вышел из употребления.

7. Дельфи (Delphi) - язык объектно-ориентированного “визуального” программирования, в данный момент чрезвычайно популярен.

8. Джава (Java) - платформенно-независимый язык объектно-ориентированного программирования, чрезвычайно эффективен для создания интерактивных web-страниц.

Среди непроцедурных языков наиболее известны:

1. Лисп (Lisp)

2. Пролог (PROgramming in LOGic)

3. Оккам (назван в честь философа У. Оккама)

1.4.2 Характеристика программного обеспечения

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

Основная функция ОС является её способность управлять устройствами памяти на магнитных дисках.

Операционная система MS-DOS состоит из следующих частей: базовой системы ввода/вывода, загрузчика операционной системы, дисковых файлов IO.SYS и MS-DOS.SYS.

В настоящее время существуют более современные ОС, с гораздо большим набором возможностей. Это ОС MS Windows' 95/98/2000/Me, OS/2.

Особенность среды MS Windows

- Стандартизация интерфейса пользователя.

- Оптимальное управление оперативной памятью объёмом в несколько гигабайт.

- Поддержка подключаемых устройств.

- Интеграция функций программ.

- Многозадачность

- Использование графического интерфейса с оконной системой организации.

ОС Windows выполняет следующих основные функции :

- Управление файловой системой носителей информации (отображение, изменение, создание, перемещение, удаление, переименование).

- Запуск и завершение прикладных программ.

- Предоставление сервисов ( всевозможные настройки, оптимизация работы).

- Управление устройствами и BIOS'ом .

Ядро Windows и ее Функции зависят от состава аппаратный средств, работа с которыми осуществляется с помощью драйверов и BIOS'а.

Назначение BIOS - базовой системы ввода / вывода - состоит в выполнении наиболее простых и универсальный услуг ОС, связанный с осуществлением ввода / вывода и прием символов с клавиатуры, анализ принятой информации, выдача символов на принтер и т.д. BIOS содержит также тест функционирования компьютера, проверяющий работу памяти и устройств компьютера при включении его электропитания.

Драйверы устройств предназначены для организации обмена данными между внутренней и внешней памятью. Драйверы включаются в работу в тот момент, когда в него из BDOS поступает команда по поиску нужных данных. Но перед этим BIOS настраивает драйвер на работу по включению соответствующего устройства. Физическая связь организуется через контроллер.

1.4.3 Характеристика ПК

Основными характеристиками персонального компьютера являются:

1. Быстродействие, производительность, тактовая частота. Единицами измерения быстродействия служат:

- МИПС (MIPS - Mega Instruction Per Second) - миллион операций над числами с фиксированной запятой (точкой).

- МФЛОПС (MFLOPS - Mega FLoating Operations Per Second) - миллион операций над числами с плавающей запятой (точкой).

- КОПС (KOPS-Kilo Operations Per Second) для низкопроизводительных электро-вычислительных машин - тысяча неких усредненных операций над числами.

Оценка производительности электро-вычислительной машины всегда приблизительная, ибо при этом ориентируется на некоторые усредненные или, наоборот, на конкретные виды операций. Реально при решении различных задач используются и различные наборы операций. Поэтому для характеристики персонального компьютера вместо производительности обычно указывают тактовую частоту, более объективно определяющую быстродействие машины, так как каждая операция требует для своего выполнения вполне определенного количества тактов. Зная тактовую частоту, можно достаточно точно определить время выполнения любой машинной операции.

2. Разрядность машины и кодовых шин интерфейса.

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

3. Типы системного и локальных интерфейсов.

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

4. Емкость оперативной памяти.

Емкость оперативной памяти измеряется чаще всего в мегабайтах (Мбайт), реже в килобайтах (Кбайт). Напоминаем:

1 Мбайт=1024 Кбайта10242 байт.

Многие современные прикладные программы при оперативной памяти емкостью меньше 128 Мбайт просто не работают либо работают, но очень медленно.

Следует иметь в виду, что увеличение емкости основной памяти в 2 раза, помимо всего прочего, дает повышение эффективной производительности ЭВМ при решении сложных задач примерно в 1,7 раза.

5. Емкость накопителя на жестких магнитных дисках (винчестера). Емкость винчестера измеряется обычно в мегабайтах или гигабайтах (1 Гбайт = 1024 Мбайта).

6. Тип и емкость накопителей на гибких магнитных дисках.

Сейчас применяются в основном накопители на гибких магнитных дисках, использующие дискеты диаметром 3,5 дюйма (1 дюйм=25,4 мм) стандартной емкости 1,44 Мбайта, CD/DVD диски емкостью 700Мбайт и 4,5 Гбайт соответственно .

7. КЭШ - память

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

Следует иметь в виду, что наличие КЭШ-памяти емкостью 256 Кбайт увеличивает производительность ПК примерно на 20%.

8. Тип видеомонитора (дисплея) и видеоадаптера.

9. Тип принтера.

10. Наличие математического сопроцессора.

Математический сопроцессор позволяет в десятки раз ускорить выполнение операций над двоичными числами с плавающей запятой и над двоично-кодированными десятичными числами.

11. Имеющееся программное обеспечение и вид операционной системы.

12. Аппаратная и программная совместимость с другими типами ЭВМ. Аппаратная и программная совместимость с другими типами ЭВМ означает возможность использования на компьютере соответственно тех же технических элементов и программного обеспечения, что и на других типах машин.

13. Возможность работы в вычислительной сети.

14. Возможность работы в многозадачном режиме.

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

15. Надежность.

Надежность - это способность системы выполнять полностью и правильно все заданные ей функции. Надежность ПК измеряется обычно средним временем наработки на отказ.

16. Стоимость.

17. Габариты и масса.

Основные характеристики персональной электронно-вычислительной машины, на которой создавалась программа:

- Процессор Athlon 1000 mHz фирмы AMD

- материнская плата на чипах VIA

- 128 МВ DIMM оперативной памяти

- жёсткий диск 40 Gb (гигабайт)

- интегрированная звуковая карта

- видео карта GeForse2 64МВ

- стандартная клавиатура Microsoft

- мышь

- колонки

- монитор 17''(дюймов)

1.4.4 Характеристика языка программирования

В настоящее время наиболее распространенными алгоритмическими языками является Паскаль, Си, Delphi.

Язык Delphi был разработан как среда программирования для объектно-ориентированного языка Object Pascal.

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

Основные операторы языка являются хорошей иллюстрацией базовый управляющий конструкций структурного программирования.

Большую помощь программистам оказывает библиотека стандартных подпрограмм Delphi. Эта библиотека модернизируется и пополняется уже более десяти лет, В нее входят средства для работы с оперативной и внешней памятью, клавиатурой, дисплеем и другими внешними устройствами ПЭВМ.

Графический пакет системы программирования Delphi - один из самый мощных пакетов такого типа, т.к. позволяет использовать все функции граф. библиотек OpenGL и Direct3D.

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

Среда в системе программирования Delphi многооконная, на экране дисплея одновременно присутствуют несколько окон редактирования, панель компонент, инспектор объектов, редакторы форм и т, д.

2. СПЕЦИАЛЬНАЯ ЧАСТЬ

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

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

Имеется N городов, которые должен обойти коммивояжер с минимальными затратами. При этом на его маршрут накладывается два ограничения:

- маршрут должен быть замкнутым, то есть коммивояжер должен вернуться в тот город, из которого он начал движение;

- в каждом из городов коммивояжер должен побывать точно один раз, то есть надо обязательно обойти все города, при этом не побывав ни в одном городе дважды.

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

2.2. Математическая модель задачи

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

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

X_{i j} - матрица переходов с компонентами:

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

X_{i j} = 0, если не совершает перехода,

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

Критерий:

, (1)

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

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

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

, i = 1..N (2)

, j = 1..N (3)

U_i - U_j + N X_{i j} N-1, i, j = 1..N, i j. (4)

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

2.3 Описание метода решения

Для решения задачи коммивояжера я применял метод полного перебора или «перебор животной силой», как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что задача коммивояжера с 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=(u₁,u₂,..,u_m) - состоящее из букв u₁,u₂,..,u_m - и слово v =(v₁,v₂,..,v_b). Тогда если u₁v_1, то и uv, если же u₁=v_1, то сравнивают вторые буквы и т.д. Этот порядок слов и называется лексикографическим. Поэтому в русских словарях (лексиконах) слово «абажур» стоит раньше слова «абака». Слово «бур» стоит раньше слова «бура», потому что пробел считается предшествующим любой букве алфавита.

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

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

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

2.4 Характеристика программы

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

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

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

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

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

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

Данная программа предназначена для поиска оптимального маршрута перевозки грузов между пунктами назначения. Созданная программа соответствует поставленной задаче. Данная программа весит 458 КБ и занимает 460 КБ памяти на диске, а также 3 МБ оперативной памяти в процессе выполнения.

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

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

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

2.5 Описание процесса отладки и тестирования программы

Отладка программы - это обнаружение и устранение ошибок в программе.

Отладка программы предполагает наличие той или иной ошибки. Одним из критериев профессионального мастерства программиста является обнаруживать собственные ошибки. Отладка программы занимает больше времени, чем первоначальное ее написание. В общее время разработки программы отладка занимает 50-90% времени. Процесс отладки программы зависит от условий функционирования программы, т.е. от используемой ЭВМ, от языка программирования, от операционной системы, от специфики решаемой задачи и от особенностей каждой конкретной программы. Каждый язык программирования связан с определенными типами дефектов программ и ошибок программирования. Существует несколько подходов к отладке программы:

- Исправление ошибок вручную.

- Максимальное использование ЭВМ для выявления ошибок.

- Отладка совмещается с процессом написания программ.

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

Синтаксические ошибки возникают из-за неправильной записи оператора. Логические ошибки возникают из-за неправильного понимания алгоритма задачи.

Отладка имеет место тогда, когда программа работает неправильно. Отладка выявляет причину ошибки.

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

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

В среде Delphi мощный встроенный отладчик, значительно упрощающий отладку программ. Основными инструментами отладки является:

- Пошаговое выполнение программы

Перед выполнением очередного шага соответствующая строка в программе выделяется бирюзовой строкой. Если в строке записаны несколько операторов все они будут выполнятся за один шаг. Для выполнения шага могут использоваться команды Step Over (F8) и Trace Into (F7) из вертикального меню Run. Разница между командами проявляется при попытке вызова процедуры. Первая команда просматривает вызов подпрограммы, как первый оператор. Порядок выполнения тела подпрограммы ее не интересует. Вся подпрограмма будет выполнена за один шаг. По нажатию клавиши F8 указатель следующего выполнения шага переместится на соответствующую строку текста программы. Вторая команда выполняет заход внутрь тела вызываемой подпрограммы и ее пошаговое выполнение. По нажатию F7 на экране будет выдано тело вызванной программы, и указатель следующего выполнения шага переместится на ее первый оператор;

- Выполнение программы до курсора

Курсор ставится на то место программы, где должна произойти приостановка программы. Выполнение программы в этом случаи запускается командой Go to cursor (F4) из вертикального меню Run. Команда позволяет очень просто и быстро указывать системе в каком месте она должна приостановить выполнение программы. Это очень удобно делать при большой программе;

- Установка контрольных точек

Приостановка выполнения программы с возможностью возобновления ее работы реализуется в Delphi с помощью контрольных точек. На экране они изображаются красной полосой. Добавление новой контрольной точки производится с помощью команды Add Breakpoint в вертикальном меню Debug. Воспользоваться ей можно как до начала выполнения программы так и во время выполнения. Просмотр набора описаний контрольных точек их корректировка и удаление выполняются по команде Breakpoint из вертикального меню Debug.

- Наблюдение за значениями переменных

Для просмотра значений переменных и выражений во время выполнения программы предназначено специальное окно Watch, открывающееся по команде Watch из вертикального меню Debug. В простейшем случаи в окне размещаются простые переменные, но могут быть выражения и структуры данных. Для добавления в окно новых объектов предназначена команда Add Watch. Находясь в окне можно использовать для управления за списком наблюдаемых объектов следующие клавиши:

1) Enter-ручное редактирование имени переменной или выражения;

2) Insert-добавление в окно наблюдения нового объекта;

3) Delete-удаление нового объекта из окна;

- Вычисление выражений и изменение значений переменных во время остановки работы программы

Значение переменных можно не только наблюдать, но и изменять. Для этого служит команда Evaluate/Modify из вертикального меню Debug. В поле Expression вводится выражение, по нажатию кнопки Evaluate оно вычисляется и его значение помещается в поле With out. Если в поле Expression стоит переменная можно ввести ее новое значение с помощью поля New Value. В случаи нажатия кнопки Modify это значение будет присвоено переменной. После этого выполнения программы можно будет продолжить уже с измененной переменной.

В данной программе имеется ряд ограничений на значения переменных:

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

- цена переходов между городами не должна быть отрицательной.

2.6 Оценка результатов работы программы

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

Ручной вариант решения.

Расчет контрольного примера производился для матриц размером 3х3

Исходная матрица

Решение

стоимость	Порядок посещения городов
32	1	3	2
32	2	1	3
32	3	2	1
39	1	2	3
39	2	3	1
39	3	1	2

Минимальное значение 32 достигается при перестановке 1-3-2, что совпадает с результатом работы программы, представленном на рис. 5 приложения 2.

ЗАКЛЮЧЕНИЕ

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

СПИСОК ЛИТЕРАТУРЫ

1. Мамиконов А.Г. Основы построения АСУ. - М.: Высшая школа - 1981.

2. Схрейвер А. Теория линейного и целочисленного программирования. - М., Мир - 1981.

3. Таха Х. Введение в исследование операций. - М.: Мир - 1985.

4. Волчков Б.А., Лифшиц И.И. Автоматизированные системы в планировании. - М., Экономика - 1980.

5. Касаткин А.И. Управление ресурсами. - Минск, Высшая школа -1992.

6. Журнал "PC Magazine" (№3 - 1994)

7. О. Оре Графы и их применение. Пер. с англ. под ред. И.М. Яглома. - М., Мир - 1965

8. В. П. Сигорский. Математический аппарат инженера. - Киев, Техніка - 1975

9. Ю. Н. Кузнецов, В. И. Кузубов, А. Б. Волощенко. Математическое программирование: учебное пособие. 2-е изд. перераб. и доп. - М.; Высшая школа - 1980.

10. Е. В. Маркова, А. Н. Лисенков. Комбинаторные планы в задачах многофакторного эксперимента. - М., Наука - 1979

11. Е. П. Липатов. Теория графов и её применения. - М., Знание - 1986

12. В. М. Бондарев, В. И. Рублинецкий, Е. Г. Качко. Основы программирования. - Харьков, Фолио - 1998.

13. Ф. А. Новиков Дискретная математика для программистов. - СПб, Питер - 2001

ПРИЛОЖЕНИЕ

АНАЛИЗ РАБОТЫ ПРОГРАММЫ

После запуска программы перед пользователем раскрывается окно, изображенная на рис. 4. В нем предоставляется возможность выбора варианта заполнения матрицы (в ручную, из файла, случайными числами). После этого нажимается кнопка «заполнить» и матрица заполняется. Когда матрица заполнена, нажимается кнопка «рассчитать» и программа производит расчет. На рис. 5 представлен вариант, когда программа заполнила матрицу случайными числами.