Проектирование вычислительной системы транспортной логистики

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

Оглавление

Введение

Глава 1. Особенности и преимущества языка C#

1.1 Общее описание языка

1.2 Сравнение C# с другими языками программирования

1.3 Использование языка

Глава 2. Проектирование вычислительной системы транспортной логистики

2.1 Логистика

2.2 Транспортные задачи

2.3 Основные понятия и ограничения

2.4 Алгоритмы поиска маршрутов в графе

Глава 3. Разработка вычислительной системы транспортной логистики на языке C#

3.1 Выбор среды разработки

3.2 Визуализация транспортной сети

3.3 Редактирование транспортной сети

3.4 Задание условий поиска

3.5 Пример работы алгоритма

Заключение

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

Введение

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

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

· Анализ

· Проектирование -- разработка комплекса алгоритмов

· Кодирование и компиляцию -- написание исходного текста программы и преобразование его в исполнимый код с помощью компилятора

· Тестирование и отладку -- выявление и устранение ошибок в программах

· Испытания и сдачу программ

· Сопровождение

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

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

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

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

· Паскаль Самоучитель программирования

· Ассемблер Леонтьев

· С++

· BASIC

· Delphi

· С#

Язык программирования С# был создан в конце 1990-х годов и стал частью общей. NET-стратегии Microsoft. Впервые он увидел свет в качестве б-версии в середине 2000 года. Главным архитектором С# был Андерс Хейлсберг (Anders Hejlsberg) -- один из ведущих специалистов в области языков программирования, получивший признание во всем мире.

В рамках данной работы основными задачами будут являться: проектирование и разработка вычислительной системы для решения транспортной задачи, поиска кратчайшего пути в транспортной сети, состоящей из нескольких графов, где каждый граф может представлять собой отдельный вид транспорта. В среде разработки C#, выделение лучших сторон, особенностей данного языка программирования высокого уровня, для наиболее оптимального решения данной задачи.

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

Это связано с несколькими причинами.

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

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

Третья причина состоит в том, что классические постановки задачи, связанные с поиском кратчайшего пути, подробно описанные в ряде трудов (6) (7) (16) (24) (26), решают лишь общую задачу. И, если имеются некоторые априорные данные о предмете исследования или наложены дополнительные ограничения, всегда может быть построена некоторая модификация уже известного алгоритма, обладающая лучшими характеристиками как с точки зрения использования оперативной памяти, так и с точки зрения скорости работы.

Глава 1. Особенности и преимущества языка C#

1.1 Общее описание языка

Последнее время С и С++ являются наиболее используемыми языками для разработки коммерческих и бизнес приложений. Эти языки устраивают многих разработчиков, но в действительности не обеспечивают должной продуктивности разработки. К примеру, процесс написания приложения на С++ зачастую занимает значительно больше времени, чем разработка эквивалентного приложения, скажем, на Visual Basic. Сейчас существуют языки, увеличивающие продуктивность разработки за счет потери в гибкости, которая так привычна и необходима программистам на С/С++. Подобные решения являются весьма неудобными для разработчиков и зачастую предлагают значительно меньшие возможности. Эти языки также не ориентированы на взаимодействие с появляющимися сегодня системами и очень часто они не соответствуют существующей практике программирования для Web. Многие разработчики хотели бы использовать современный язык, который позволял бы писать, читать и сопровождать программы с простотой Visual Basic и в то же время давал мощь и гибкость C++, обеспечивал доступ ко всем функциональным возможностям системы, взаимодействовал бы с существующими программами и легко работал с возникающими Web стандартами.

Учитывая все подобные пожелания, Microsoft разработала новый язык - C#. В него входит много полезных особенностей - простота, объектная ориентированность, типовая защищенность, "сборка мусора", поддержка совместимости версий и многое другое. Данные возможности позволяют быстро и легко разрабатывать приложения, особенно COM+ приложения и Web сервисы. При создании C#, его авторы учитывали достижения многих других языков программирования: C++, C, Java, SmallTalk, Delphi, Visual Basic и т.д. Надо заметить что по причине того, что C# разрабатывался с чистого листа, у его авторов была возможность (которой они явно воспользовались), оставить в прошлом все неудобные и неприятные особенности (существующие, как правило, для обратной совместимости), любого из предшествующих ему языков. В результате получился действительно простой, удобный и современный язык, по мощности не уступающий С++, но существенно повышающий продуктивность разработок.

Очень часто можно проследить такую связь - чем более язык защищен и устойчив к ошибкам, тем меньше производительность программ, написанных на нем. К примеру рассмотрим две крайности - очевидно это Assembler и Java. В первом случае вы можете добиться фантастической быстроты своей программы, но вам придется очень долго заставлять ее работать правильно не на вашем компьютере. В случае же с Java - вы получаете защищенность, независимость от платформы, но, к сожалению, скорость вашей программы вряд ли совместима со сложившимся представлением о скорости, например, какого-либо отдельного клиентского приложения (конечно существуют оговорки - JIT компиляция и прочее). Рассмотрим C++ с этой точки зрения - на мой взгляд соотношение в скорости и защищенности близко к желаемому результату, но на основе собственного опыта программирования я могу с уверенностью сказать, что практически всегда лучше понести незначительную потерю в производительности программы и приобрести такую удобную особенность, как "сборка мусора", которая не только освобождает вас от утомительной обязанности управлять памятью вручную, но и помогает избежать вам многих потенциальных ошибок в вашем приложении. В действительности скоро "сборка мусора", да и любые другие шаги к устранению потенциальных ошибок стану отличительными чертами современного языка. В C#, как в несомненно современном языке, также существуют характерные особенности для обхода возможных ошибок. Например, помимо упомянутой выше "сборки мусора", там все переменные автоматически инициализируются средой и обладают типовой защищенностью, что позволяет избежать неопределенных ситуаций в случае, если программист забудет инициализировать переменную в объекте или попытается произвести недопустимое преобразование типов. Также в C# были предприняты меры для исключения ошибок при обновлении программного обеспечения. Изменение кода, в такой ситуации, может непредсказуемо изменить суть самой программы. Чтобы помочь разработчикам бороться с этой проблемой C# включает в себя поддержку совместимости версий (vesioning). В частности, в отличии от C++ и Java, если метод класса был изменен, это должно быть специально оговорено. Это позволяет обойти ошибки в коде и обеспечить гибкую совместимость версий. Также новой особенностью является native поддержка интерфейсов и наследования интерфейсов. Данные возможности позволяют разрабатывать сложные системы и развивать их со временем.

В C# была унифицирована система типов, теперь вы можете рассматривать каждый тип как объект. Несмотря на то, используете вы класс, структуру, массив или встроенный тип, вы можете обращаться к нему как к объекту. Объекты собраны в пространства имен (namespaces), которые позволяют программно обращаться к чему-либо. Это значит что вместо списка включаемых файлов заголовков в своей программе вы должны написать какие пространства имен, для доступа к объектам и классам внутри них, вы хотите использовать. В C# выражение using позволяет вам не писать каждый раз название пространства имен, когда вы используете класс из него. Например, пространство имен System содержит несколько классов, в том числе и Console. И вы можете писать либо название пространства имен перед каждым обращением к классу, либо использовать using как это было показано в примере выше.

Важной и отличительной от С++ особенностью C# является его простота. К примеру, всегда ли вы помните, когда пишите на С++, где нужно использовать "->", где "::", а где "."? Даже если нет, то компилятор всегда поправляет вас в случае ошибки. Это говорит лишь о том, что в действительности можно обойтись только одним оператором, а компилятор сам будет распознавать его значение. Так в C#, оператор"->" используется очень ограничено (в unsafe блоках, о которых речь пойдет ниже), оператор "::" вообще не существует. Практически всегда вы используете только оператор "." и вам больше не нужно стоять перед выбором.

Еще один пример. При написании программ на C/С++ вам приходилось думать не только о типах данных, но и о их размере в конкретной реализации. В C# все упрощено - теперь символ Unicode называется просто char (а не wchar_t, как в С++) и 64-битное целое теперь - long (а не __int64). Также в C# нет знаковых и беззнаковых символьных типов.

В C#, также как и в Visual Basic после каждого выражения case в блоке switch подразумевается break. И более не будет происходить странных вещей если вы забыли поставить этот break. Однако если вы действительно хотите чтобы после одного выражения case программа перешла к следующему вы можете переписать свою программу с использованием, например, оператора goto.

Многим программистам (на тот момент, наверное, будущим программистам) было не так легко во время изучения C++ полностью освоиться с механизмом ссылок и указателей. В C# (кто-то сейчас вспомнит о Java) нет указателей. В действительности нетривиальность указателей соответствовала их полезности. Например, порой, трудно себе представить программирование без указателей на функции. В соответствии с этим в C# присутствуют Delegates - как прямой аналог указателя на функцию, но их отличает типовая защищенность, безопасность и полное соответствие концепциям объектно-ориентированного программирования.

Хотелось бы подчеркнуть современное удобство C#. Когда вы начнете работу с C#, а, надеюсь, это произойдет как можно скорее, вы увидите, что довольно большое значение в нем имеют пространства имен. Уже сейчас, на основе первого примера, вы можете судить об этом - ведь все файлы заголовков заменены именно пространством имен. Так в C#, помимо просто выражения using, предоставляется еще одна очень удобная возможность - использование дополнительного имени (alias) пространства имен или класса.

Современность C# проявляется и в новых шагах к облегчению процесса отладки программы. Традиционным средством для отладки программ на стадии разработки в C++ является маркировка обширных частей кода директивами #ifdef и т.д. В C#, используя атрибуты, ориентированные на условные слова, вы можете куда быстрее писать отлаживаемый код.

В наше время, когда усиливается связь между миром коммерции и миром разработки программного обеспечения, и корпорации тратят много усилий на планирование бизнеса, ощущается необходимость в соответствии абстрактных бизнес процессов их программным реализациям. К сожалению, большинство языков реально не имеют прямого пути для связи бизнес логики и кода. Например, сегодня многие программисты комментируют свои программы для объяснения того, какие классы реализуют какой-либо абстрактный бизнес объект. C# позволяет использовать типизированные, расширяемые метаданные, которые могут быть прикреплены к объекту. Архитектурой проекта могут определяться локальные атрибуты, которые будут связанны с любыми элементами языка - классами, интерфейсами и т.д. Разработчик может программно проверить атрибуты какого-либо элемента. Это существенно упрощает работу, к примеру, вместо того чтобы писать автоматизированный инструмент, который будет проверять каждый класс или интерфейс, на то, является ли он действительно частью абстрактного бизнес объекта, можно просто воспользоваться сообщениями основанными на определенных в объекте локальных атрибутах.

1.2 Сравнение C# с другими языками программирования

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

Свой синтаксис C# во многом унаследовал от C++ и Java. Разработчики, имеющие опыт написания приложений на этих языках, найдут в C# много знакомых черт. Но вместе с тем он является во многом новаторским - аттрибуты, делегаты и события, прекрасно вписанные в общую идеологию языка, прочно заняли место в сердцах.NET - разработчиков. Их введение позволило применять принципиально новые приемы программирования.

Конечно, излюбленным объектом для сравнения с C# у мировой коммьюнити является Java. Также разработанный для работы в виртуальной среде выполнения, имеющей объектно-ориентированную архитектуру и сборщик мусора, осноыванный на механизме ссылок. При сравнении с этим языком сразу выделаются такие особенности, как возможность объявлять несколько классов в одном файле, из чего следует синтаксическая поддержка иерархической системы пространств имен. Из реализации ООП-концепций сходство в механизме наследования и реализации (и в Java и в C# возможно единичное наследование, но множественная реализация интерфейсов, в отличие от C++). Но в Java отсутствуют свойства и индексаторы (а также делегаты и события, но они отсутствуют еще много где). Также есть возможность перечисления контейнеров.

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

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

1.3 Использование языка

В этой части будут рассмотрены более практические аспекты использования C#. Компиляция, отладка и тому подобные вопросы. Начнем с компиляции:

Переходя к более подробному знакомству с C#, традиционно рассмотрим программу "Hello, world": using System;

class Hello{

static void Main() {

Console.WriteLine("hello, world");

}

Поместите эту программу в файл hello.cs и скомпилируйте ее командой csc hello.cs

Так выглядит вызов компилятора в простейшем случае. Далее мы приведем полный список параметров компилятора. При вызове компилятора убедитесь, что у вас прописан путь csc.exe - C Sharp Compiler

В результате вы получите файл hello.exe, запустив который, вы увидите надпись "hello, world".

Метод Main - это точка входа в программу. С него начинается выполнение (те, кто знаком с C++ или Java) понимают, о чем идет речь. Этот метод обязательно должен быть статическим. Далее в нашем примере используется метод WriteLine из класса System.Console. Этот метод отправляет строку на стандартный вывод.

Вы можете также создавать библиотеки классов - dll-сборки, которые могут использоваться другими приложениями. Для этого нужно указать /target:library в опциях компилятора

Если компилятор обнаружит ошибки в программе, он выдаст соответствующее сообщение и остановит процесс компиляции. Также он может выдать предупреждения - если он обнаружит код, который, строго говоря, правильный, но имеет подозрения на ошибку. К таким предупреждениям стоит прислушиваться.

Вообще, компилятор C# имеет множество возможностей, узнать о которых можно из следующей таблицы. В ней описаны все опции командной строки компилятора CSC:

Выходные файлы/out:<file> Имя выходного файла (если не указано - производное от имени первого исходного файла)

/target:exe Скомпилировать консольный запускаемый файл (по умолчанию) (Краткая форма: /t:exe)

/target:winexe Скомпилировать запускаемый файл Windows (Краткая форма: /t:winexe)

/target:library Скомпилировать в библиотеку DLL (Краткая форма: /t:library)

/target:module Скомпилировать модуль, который может быть добавлен в другую конструкцию (Краткая форма: /t:module)

Примечание: Модуль и библиотека имеют одинаковые расширения (DLL), но несмотря на это, они представляют из себя разные вещи. Библиотека - это классическая библиотека DLL. Модуль - это файл откомпилированный без создания конструкции (assembly). В дальнейшем вы можете добавить модуль в любую другую конструкцию при компиляции (с помощью опции /addmodule). /nooutput[+|-] Только проверять ошибки в коде; не создавать запускаемый файл

define: <список символов> Определяет директивы препроцессора (Краткая форма: /d)

Написание csc /define:mark1 MyApp.cs равносильно наличию в файле строки

#define mark1

/doc:<file> Создать XML файл документации

Входные файлы/recurse:<маска>

Включить все файлы, удовлетворяющие маске.

/main:<тип> Обозначить класс, содержащий точку входа в программу (все остальные будут игнорироваться) (Краткая форма: /m)

/reference:<список файлов> Включить метаданные из указанных файлов конструкций (Краткая форма: /r)

Примечание: все данные, помеченные как public, из указаных файлов конструкций будут включены в данную конструкцию. Если файл не содержит объявления конструкции, то метаданные из него могут быть включены с помощью /addmodule./addmodule:<список файлов> Включить указанные модули в сборку

Ресурсы/win32res:<file> Добавляет файл ресурсов Win32(.res) в выходной файл

/win32icon:<file> Добавляет иконку в выходной файл

/resource:<resinfo> Включает.NET ресурс (Краткая форма: /res)

* Примечание: resinfo являет собой следующую последовательность: filename[,identifier[,mimetype]], где filename - имя файла ресурса, identifier - логическое имя ресурса (используется для его загрузки), mimetype - медиа тип ресурса (обычно отсутствует). /linkresource:<resinfo> Создает ссылку на ресурсный файл в данной сборке (не включая его в выходной файл)(Краткая форма: /linkres)

Создание кода/debug[+|-] Создавать информацию отладки.

/debug:{full|pdbonly} Указание типа отладки ('full' - по умолчанию, позволяет прикреплять отладчик к запускаемой программе)

/optimize[+|-] Запускать оптимизацию (Краткая форма: /o)

/incremental[+|-] Запускать компиляцию только измененных частей кода(Краткая форма: /incr)

Ошибки и предупреждения /warnaserror[+|-] Относиться к предупреждениям, как к ошибкам

/warn:<n> Установить уровень предупреждений (0-4) (Краткая форма: /w)

/nowarn:<список предупреждений> Исключить указанные предупреждения

Примечание: список предупреждений - последовательность их номеров num1[,num2[...]]

Язык/checked[+|-] Выполнять проверки на переполнения и опустошения

/unsafe[+|-] Допускать unsafe код (unsafe код - небезопасный код, он будет обсужден в дополнительных главах)

Разное@<file> Прочтение команд и опций компилятора из файла

/help Показывает информацию о использовании (Краткая форма: /?)

/nologo Не показывать копирайт при компиляции

Дополнительно/baseaddress:<address> Базовый адрес для создаваемой библиотеки

/bugreport:<file> Создавать файл отчета об ошибках

/codepage:<n> Указать таблицу символов, для использования во время открытия исходного текста

/fullpaths Компилятор будет указывать полные имена файлов

/nostdlib[+|-] Не допускать включения стандартной библиотеки (mscorlib.dll). В этой библиотеке хранятся все основные классы.NET Framework.

Глава 2. Проектирование вычислительной системы транспортной логистики

2.1 Логистика

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

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

Понятие логистики включает в себя множество поддисциплин: закупочная, транспортная, складская, производственная, информационная логистика и другие [19].

В рамках данной работы будет рассматриваться транспортная логистика.

Транспортная логистика

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

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

Вредом для объекта доставки считается негативное воздействие на логистический объект как со стороны внешних факторов (условия перевозки), так и со стороны временного фактора при доставке объектов, подпадающих под данную категорию.

Перечислим основные задачи, которые стоят перед транспортной логистикой [20]:

1. Выбор типа транспортного средства.

2. Выбор вида транспортного средства.

3. Совместное планирование транспортных процессов со складскими и производственными операциями.

4. Совместное планирование транспортных процессов на различных видах транспорта.

5. Обеспечение технологического единства транспортно-складского процесса.

6. Определение рациональных маршрутов поставки.

Все они (кроме подзадач связанных со складскими операциями) будут затронуты в данном исследовании.

Подходы к решению задачи

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

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

Характерная особенность исследования операций -- системный подход к поставленной проблеме и анализ. Системный подход является главным методологическим принципом исследования операций. Он заключается в следующем. Любая задача, которая решается, должна рассматриваться с точки зрения влияния на критерии функционирования системы в целом. Для исследования операций характерно то, что при решении каждой проблемы могут возникать новые задачи. Важной особенностью исследования операций есть стремление найти оптимальное решение поставленной задачи (принцип «оптимальности»). Однако на практике такое решение найти невозможно по таким причинам [2] [23]:

1. отсутствие методов, дающих возможность найти глобально оптимальное решение задачи

2. ограниченность существующих ресурсов (к примеру, ограниченность машинного времени ЭВМ), что делает невозможным реализацию точных методов оптимизации.

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

2.2 Транспортные задачи

Задача коммивояжёра

Одной из самых известных задач транспортной логистики является задача коммивояжёра.

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

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

Общая постановка задачи, впрочем, как и большинство её частных случаев, относится к классу NP-сложных задач [11] [13].

Перечислим основные методы решения этой задачи: полный лексический перебор

- случайный перебор жадные алгоритмы

- метод ближайшего соседа

- метод включения ближайшего города o метод самого дешёвого включения

- метод минимального основного дерева

Все эффективные (сокращающие полный перебор) методы решения задачи коммивояжёра -- методы эвристические. В большинстве эвристических методов находится не самый эффективный маршрут, а приближённое решение. Зачастую востребованы так называемые any-time алгоритмы, то есть постепенно улучшающие некоторое текущее приближенное решение.

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

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

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

NP-сложные задачи

В теории алгоритмов классом NP1 называют множество алгоритмов, время работы которых существенно зависит от размера входных данных. В то же время, если предоставить алгоритму некоторые дополнительные сведения (так называемых свидетелей решения), то он сможет достаточно быстро (за время, не превосходящее многочлена от размера данных) решить задачу. Многие задачи на графах относят к классу NP-полных задач [7].

Транспортная задача

Транспортная задача (Задача Монжа-Канторовича) -- задача об оптимальном плане перевозок продукта из пунктов отправления в пункты потребления. Разработка и применение оптимальных схем грузовых потоков позволяют снизить затраты на перевозки. Транспортная задача является по теории сложности вычислений NP-сложной.

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

2.3 Основные понятия и ограничения

В математической теории графов и информатике граф -- это совокупность объектов со связями между ними.

Объекты представляются как вершины, или узлы графа, а связи -- как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах [16].

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

Граф не должен содержать петель, т.к. петля не имеет смысла с точки зрения транспортной сети.

Граф не должен содержать изолированных вершин, т.к. из вершины всегда должно выходить хотя бы одно ребро.

Граф не обязательно должен быть связным, т.к. поиск может осуществляться только внутри обособленной области связности.

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

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

2.4 Алгоритмы поиска маршрутов в графе

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

поиск в ширину (breadth-first search -- BFS); поиск в глубину (depth-first search -- DFS).

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

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

Поиск в ширину следует использовать в том случае, если

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

2. нам нужно найти кратчайший путь в невзвешенном графе.

Поиск в ширину выполняется в следующем порядке: началу обхода приписывается метка 0, смежным с ней вершинам -- метка 1. Затем

поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т.д.

Легко увидеть, что с помощью поиска в ширину можно также занумеровать вершины, нумеруя вначале вершины с меткой 1, затем с меткой 2 и т.д.

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

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

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

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

Если бы транспортная сеть ограничивалась одним графом, то алгоритм Дейкстры являлся бы одним из лучших выборов для поиска оптимального пути. Но, сама идея алгоритма при учёте количества пересадок может привести к тому, что некоторые потенциально достижимые вершины никогда не будут достигнуты, т.к. алгоритм «израсходует» все допустимые пересадки, стремясь сделать путь максимально дешёвым. В первую очередь это связано с тем, что поиск осуществляется не только для целевой вершины, но и для всех вершин входящих в транспортную сеть.

Алгоритм Беллмана-Форда -- алгоритм поиска кратчайшего пути во взвешенном графе. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает рёбра с отрицательным весом. Предложен независимо Ричардом Беллманом и Лестером Фордом.

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

Но он не позволяет формализовать и алгоритмизировать ограничения на количество пересадок, т.к. в нём, как и в алгоритме Дейкстры путь ищется не только до заданной вершины, но и для всех остальных.

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

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

Глава 3. Разработка вычислительной системы транспортной логистики на языке C#

3.1 Выбор среды разработки

Для реализации программного комплекса использовался язык высокого уровня C# и среда разработки MS Visual Studio 2008. Этот выбор обусловлен исходя из следующих критериев [5] [9] [15] [17] [22]:

1. Среда разработки и язык позволяют быстро и качественно создавать пользовательский интерфейс высокого уровня, используя дизайнер форм, сводя к минимуму труд программиста. В качестве альтернативы могла быть рассмотрена среда разработки Code Gear 2009, но MS Visual Studio 2008 явно обладает рядом преимуществ т.к. является естественной платформой для разработки под Windows.

2. Язык C# так же обладает рядом преимуществ по сравнению с Object Pascal, т.к. является более новым и более развитым языком.

3. В нём на очень высоком уровне реализованы механизмы безопасности кода.

4. Ещё одним несомненным плюсом является наличие русскоязычной развитой справочной системы, что значительно упрощает процесс программирования.

5. Ещё одной альтернативным языком могла бы быть JAVA, но для её работы требуется устанавливать собственный Framework, в то время как Framework необходимый для работы программ написанных с использованием C# уже присутствует на уровне операционной системы.

6. Ещё одним преимуществом является возможность использовать как управляемый, так и неуправляемый код, как ручное, так и автоматизированное управление памятью. Основные конкуренты

JAVA и Object Pascal не позволяют одновременно использовать обе эти модели.

7. Ещё одним преимуществом может рассматриваться использование байт-кода, что обеспечивает высокую скорость работы и более полное использование аппаратных возможностей ПК.

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

3.2 Визуализация транспортной сети

Рассмотрим алгоритм визуализации транспортной сети.

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

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

Для текста, антиалайзинг был отключен, т.к. использовался шрифт небольшого размера, а сглаживание снижало лёгкость его чтения.

Текущие объекты (вершины и рёбра) обрисовываются с использованием полужирного начертания линий и шрифтов.

Перейдём непосредственно к алгоритму.

Сначала обрисовывались рёбра, т.к. вершины их перекрывают и визуально находятся на один уровень выше.

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

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

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

Предусмотрена система обозначений в виде суффиксов веса: Ч -- ребро недоступно; ° -- ребро помечено как невидимое; † -- ребро помечено для удаления.

После того, как обрисованы рёбра, начинается визуализация вершин.

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

3.3 Редактирование транспортной сети

Добавление элементов

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

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

Удаление элементов

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

если граф помечен на удаление, все рёбра и вершины в него входящие так же помечаются на удаление;

если вершина помечена на удаление, все рёбра ей инцидентные также помечаются на удаление;

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

Редактирование элементов

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

А все элементы управления на форме имеют соответствующие обработчики событий, которые при изменении значений сразу фиксируют их.

Для хранения данных использовался формат XML. Этот открытый формат имеет явные преимущества, т.к. является стандартом. Таким образом, транспортная сеть в этом формате потенциально может использоваться и в других приложениях.

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

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

3.4 Задание условий поиска

Условия поиска задаются при помощи компонента numericUpDown.

Поиск маршрутов

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

Листинг предложенных алгоритмов представлены в приложении.

Все представленные алгоритмы обладают похожей секцией инициализации:

Перед осуществлением непосредственного поиска выполняются следующие действия.

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

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

3. Все вершины, которые ранее были помечены как часть пути, должны потерять эту отметку.

4. Все рёбра, которые ранее были помечены как часть пути, должны потерять эту отметку.

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

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

7. Создаётся стек для хранения вершин, входящих в текущий путь. Создаётся стек для хранения рёбер, входящих в текущий путь.

8. Вес текущего пути принимается за ноль.

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

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

11. Из стека извлекаются все рёбра вошедшие в оптимальный маршрут.

a. Каждое ребро, извлечённое из стека, помечается как часть оптимального маршрута

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

с. Осуществляется обрисовка транспортной сети с отмеченным на ней маршрутом.

Поиск в глубину (рекурсивная версия)

Перейдём к самому алгоритму поиска. Данная версия алгоритма поиска в глубину была реализована с использованием рекурсии, т.к. рекурсия является очень естественным приёмом при работе с графами. Учитывая тот факт, что использование рекурсии может приводить к замедлению работы алгоритма в следующем параграфе будет рассмотрена версия алгоритма поиска вглубину без использования рекурсии. Основная идея алгоритма состоит в следующем.

В функцию передаётся 4 параметра:

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

2. Вершина, в которую мы хотим пойти.

3. Ребро, по которому мы хотим пойти.

4. Вершина, в которую мы хотим попасть.

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

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

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

Перейдём к штатному режиму работы алгоритма.

В-первую очередь проверяется «А можно ли идти в эту вершину?». Идти нельзя если:

мы уже были в этой вершине (если пренебречь этим условием, то возможно образование циклов, а т.к. веса рёбер у нас всегда положительные, то путь, в котором есть цикл, никогда не сможет стать оптимальным);

вершина заблокирована; ребро заблокировано.

Если нельзя, то функция досрочно прекращает свою работу. Во-вторых, проверяется «А нужно ли идти в эту вершину?». Идти не нужно если:

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

Затем пересчитываются показатели,

увеличивается вес текущего пути (соответственно на вес ребра по которому был сделан очередной шаг алгоритма поиска в глубину); при необходимости увеличивается количество пересадок. Делается проверка «А не достигли ли мы заданной вершины?». Если вершина достигнута, то делается проверка на то, а не является ли текущий путь более оптимальным (в смысле суммарного веса), по сравнению с текущим кандидатом на оптимальность. Если текущий путь лучше, то он записывается на место оптимального.

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

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

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

Поиск в глубину (нерекурсивная версия)

Нерекурсивная версия этого алгоритма может иметь выигрыш по скорости работы в связи с тем что:

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

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

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

Рассмотрим сам алгоритм.

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

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

3. В стек складывается текущая вершина, с которой начинается поиск.

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

5. Верхняя вершина стека является текущей. Осуществляется проверка того, а не дошли ли мы до финальной вершины.

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