Решение задачи о коммивояжере - Курсовая работа

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

граф моделирование коммивояжер программа

Коммивояжер - не свободно путешествующий турист, а деловой человек, ограниченный временными, денежными или какими-либо другими ресурсами. Эта головоломка в свое время была предложена ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира. Обязательным условием являлось требование: каждую точку за исключением первой можно обойти один раз.

Курс дискретной математики подразумевает изучение студентами технических специальностей теории графов. Графом, простыми словами, называется совокупность непустого множества вершин (узлов) и их взаимосвязей. Узлы графа могут быть связаны ребрами или дугами, их отличие друг от друга тривиально: дуга однонаправленная, а ребро - двунаправленное. В связи с этим графы делятся на три типа: неориентированные графы (узлы соединены только ребрами), ориентированные графы (узлы соединены только дугами) и смешанные графы (связями могут выступать как дуги, так и ребра). Изучение таких структур данных как граф позволяет решать новые задачи, определяемые рядом объектов, связанных друг с другом каким-либо отношением. Начиная от простых моделей, например, переливания различных видов групп крови человеку, заканчивая сложными задачами из NP класса - в том числе и поиска оптимальных путей между пунктами (городами) - задачи Коммивояжера.

1. Описание предприятия

1.1 Структура предприятия

ОАО «Свет шахтера» является одним из старейших машиностроительных предприятий угольной отрасли.

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

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

Свою историю завод ведет со слесарно-механических мастерских Н.Ф. фон-Дитмара, основанных в 1891 году. Название «Свет шахтера» завод носит с 1922 года. В 2004 году заводу исполнилось 113 лет. В 1994 году завод был преобразован в открытое акционерное общество «Свет шахтера» путем приватизации имущества государственного предприятия - завода «Свет шахтера».

Производство горно-шахтного оборудования металлоемко. В год завод производит до 200 конвейеров и множество запчастей к ним. Масса одного конвейера в зависимости от модели и комплектации составляет от 10 до 150 тонн. Следовательно, только на производство конвейеров, не принимая во внимание другой продукции, заводу в год необходимо до 200 тыс. тонн металла (в основном высококачественной стали) и других материалов.

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

Подразделения основного производства представлены следующими цехами: - заготовительный цех (ЗГЦ), включающий механический участок, участок штамповки, слесарный участок и волочильное и заточное отделения;

- литейный цех (Л-1), состоящий из участков чугунного, стального и цветного литья, участка обрубки и лаборатории;

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

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

- цех сварных конструкций (ЦСК), состоящий из заготовительного участка, участка сборки и сварки, участков закалки, участка штамповки и резки металла, участка клепки, участка сверловки, участка наплавки, участка плазменной резки, участка штамповки деталей, участка газовой резки;

- термический цех, включающий участок термообработки на печах СНЦ, участок сборки и сварки звездочек, участок закалки на камерных печах, линию СКЗА по термообработке мелкогабаритных серийных деталей, линию по термообработке боковин, маслоохладительную станцию, участок пескоструйных камер, водонасосную станцию оборотного водоснабжения;

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

- механический цех №2 (М-2), включающий участок средних станков, участок станков с числовым программным управлением, участок обработки гидромуфт и механическую лабораторию;

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

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

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

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

- ремонтно-механический цех (РМЦ), осуществляющий ремонт оборудования и содержащий механический, слесарный и сварочный участки, участок порезки металла, участок наплавки;

- электроучасток, обеспечивающий электропитание;

- теплоцех, обеспечивающий холодную и горячую воду для технологических нужд и отопление;

- участок средств механизации, изготовляющий и внедряющий средства механизации и автоматизации производственных процессов;

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

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

На заводе «Свет шахтера» эксплуатируется 2340 единиц оборудования, в том числе 50 станков с ЧПУ.

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

Рис.1.1 - Производственная структура ОАО «Свет шахтера»

Органами управления общества являются: - общее собрание акционеров;

- наблюдательный совет;

- председатель правления;

- правление.

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

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

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

Остальные должностные лица - это линейный персонал.

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

- производство и сбыт конвейеров: ПДО « Отдел сбыта « ФО « ПЭО;

- обеспечение производства материальными ресурсами: СКБ « ОГТ « ОМТС « ОВКИК.

1.2 Структура автоматизированной системы предприятия

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

С целью совершенствования процессов управления и учета в конце 1980-х годов на заводе был создан отдел автоматизированных систем управление предприятием (ОАСУП), в дальнейшем переименованный в отдел компьютерных технологий (ОКТ). На первом этапе отдел автоматизировал многие функции по расчету заработной платы, арендовав для этого в других учреждениях машинное время и программное обеспечение. С момента появления на рынке персональных компьютеров по приемлемым ценам была сделана ставка на разработку АСУ собственными силами на основе автоматизированных рабочих мест специалистов различных подразделений завода. С начала 90-х кодов началась разработка таких АРМ по нескольким направлениям: подготовка, планирование и учет производства, бухгалтерский учет, расчет заработной платы. Так, учет материальных ценностей на складах в бухгалтерии был автоматизирован уже в 1992 году. Первоначально все АРМ работали в локальном режиме. Обмен данными осуществлялся посредством переноса копий баз данных на дискетах. Затем в заводоуправлении была создана локальная вычислительная сеть (ЛВС) и доработано программное обеспечение для работы в сетевом режиме. Программное и аппаратное обеспечение АСУ завода все время совершенствовалось.

В настоящее время на предприятии автоматизаций охвачены практически все подразделения предприятия. На Рис. 1.1 представлена структура управления завода и на ее основе цветовая схема оснащенности средствами вычислительной техники и внедрения программного обеспечения в подразделениях завода. Пунктирной линией показаны еще не включенные в локальную вычислительную сеть завода подразделения. Как видно из этого рисунка, автоматизированной системой охвачены практически все подразделения предприятия, однако не все функции управления еще реализованы. В лучшем случае автоматизировано 75% управленческих функций подразделений. Это связано с тем, что технологии, которые использовались до недавнего времени, не позволяют полностью автоматизировать все функции.

Рис. 1.3 - Схема оснащенности средствами вычислительной техники и внедрения программного обеспечения в подразделениях завода

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

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

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

Эти работы включали в себя не только ознакомление с рекламными или презентационными материалами, представляемыми самими фирмами-разработчиками, различными СМИ (Интернет, семинары и т.д.), а и тестирование их в условиях предприятия. Примерами таких работ служат семинары-презентации и «пилотные» проекты ERP-систем: My SAP (R3) (2000г.), Axapta (Microsoft) (май 2004г.), Oracle E-business (Oracle) (октябрь-декабрь 2004г.) и др.

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

- сжатые сроки подготовки производства, отсутствие полной документации и информации о ее готовности;

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

- отсутствие автоматизированного оперативного учета хода производства, при постоянно меняющихся заданиях;

- большая доля устаревшего универсального оборудования;

- большой процент обновления кадров, в том числе квалифицированных;

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

- сложности интеграции готовых систем с работающей АСУ завода;

- необходимость замены до 50% устаревших средств вычислительной техники (СВТ), - создают непреодолимые препятствия для внедрения таких систем или же требуют значительных изменений в работе готовой ERP-системы и изменения принципов работы завода. Это приведет к увеличению стоимости и без того не дешевой (средняя стоимость готовой системы с ее внедрением примерно 1 млн. евро) системы и ее внедрения. Все эти факторы сказываются на возможности успешного применения на предприятии этих систем.

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

- стоимость разработки, внедрения и сопровождения системы собственными силами на порядок ниже, чем покупных систем (Рис. 1.3).

Рис. 1.4 - Оценка вариантов затрат на создание информационной системы.

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

Была разработана новая концепция развития АСУ и создания корпоративной информационной системы (КИС) предприятия. Эта концепция заключается в следующем: - в рамках системы реализуются все функции управления предприятием (планирование, учет, контроль, анализ, отчетность) на всех этапах хозяйственной деятельности (подготовка производства, производство, сбыт, гарантийное обслуживание). Концептуальная схема приведена на рисунке 1.5.

Рис. 1.5 - Функции корпоративной информационной системы ОАО «Свет шахтера»

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

Ядро системы разрабатывается собственными силами на базе технологий фирмы Microsoft. Для разработки используются лицензионные продукты MS SQL Server 2000, Exchange Server, Share Point, Visual Studio.Net 2003.

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

В составе комплексной автоматизированной системы используются ранее разработанные автоматизированные рабочие места.

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

- единое информационное пространство и «сквозное» прохождение информации в системе;

- модульность системы - возможность поэтапного внедрения;

- трехуровневая архитектура системы на базе технологии ASP.Net;

- широкое использование собственных инструментальных средств разработки;

- единый подход к разработке и стандартизация программного обеспечения;

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

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

КИС ЗСШ базируется на ERP-стандартах и отвечает рекомендациям методик ERP (Enterprise Requirements Planning - Планирование ресурсов предприятия) и CSRP (Customer Synchronized Resource Planning -Планирование ресурсов в зависимости от потребностей клиента).

КИС ЗСШ функционирует в архитектуре клиент-сервер платформе Microsoft SQL Server 2000.

Особое место в планах развития системы КИС ЗСШ занимают новые перспективные технологии Microsoft.Net и ASP.Net, предназначенные для разработки трехуровневых Internet и Intranet приложений. Технология .Net используется для разработки отдельных модулей, формирования оперативных отчетов по базе данных и предназначена для обеспечения работы удаленных пользователей в реальном масштабе времени с базой данных системы.

В системе используются следующие технические решения и технологии: - ориентация на использование широких возможностей служб Windows XP и Windows 2003;

- использование Microsoft Exchange Server и Microsoft Share Point Server для организации документооборота, архива документов и электронной почты;

- тесная интеграция с продуктами Microsoft Office (Word, Excel, Outlook, INFOPATH) и стандартными средствами разработки (Seagate Crystal Reports);

- использование интернет-решений класса B2E, В2В на базе технологий ASP.Net;

- использование стандартных технологий OLE, ACTIVEX, COM, ODBC, XML, ADO.Net и т.д.

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

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

Рис. 1.6. - Локальная вычислительная сеть ОАО «Свет шахтера»

2. Обзор методов решения индивидуального задания

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

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

Рис. 2.1 - Узкий ромб

Посмотрим, как поведет себя при решении ЗК жадный алгоритм. Здесь он превратится в стратегию “иди в ближайший (в который еще не входил) город”. Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рис. 2, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм “иди вы ближайший город” выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур.

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

Как видим, жадный алгоритм ошибается. Можно ли доказать, что он ошибается умеренно, что полученный им тур хуже минимального, положим, в 1000 раз? Мы докажем, что этого доказать нельзя, причем не только для жадного логарифма, а для алгоритмов гораздо более мощных. Но сначала нужно договориться, как оценивать погрешность неточных алгоритмов, для определенности, в задаче минимизации. Пусть FB - настоящий минимум, а FA - тот квазиминимум, который получен по алгоритму. Ясно, что FA/ FB?1, но это - тривиальное утверждение, что может быть погрешность. Чтобы оценить ее, нужно зажать отношение оценкой сверху: FA/FB ?1 ne,(5) где, как обычно в высшей математике, е?0, но, против обычая, может быть очень большим. Величина е и будет служить мерой погрешности. Если алгоритм минимизации будет удовлетворять неравенству (5), мы будем говорить, что он имеет погрешность е.

Предположим теперь, что имеется алгоритм А решения ЗК, погрешность которого нужно оценить. Возьмем произвольный граф G (V,E) и по нему составим входную матрицу ЗК: С[i,j]={ 1,если ребро (i,j) принадлежит Е

1 ne в противном случае

Если в графе G есть гамильтонов цикл, то минимальный тур проходит по этому циклу и FB = n. Если алгоритм А тоже всегда будет находить этот путь, то по результатам алгоритма можно судить, есть ли гамильтонов цикл в произвольном графе. Однако, непереборного алгоритма, который мог бы ответить, есть ли гамильтонов цикл в произвольном графе, до сих пор никому не известно. Таким образом, наш алгоритм А должен иногда ошибаться и включать в тур хотя бы одно ребро длины 1 ne. Но тогда FA?(n-1) (1 ne) так что FA/FB=1 ne т.е. превосходит погрешность е на заданную неравенством (5). О величине е в нашем рассуждении мы не договаривались, так что е может быть произвольно велик.

Таким образом, доказана следующая теорема.

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

Это соображение было впервые опубликовано Сани и Гонзалесом в 1980 г. Теорема Сани-Гонзалеса основана на том, что нет никаких ограничений на длину ребер. Теорема не проходит, если расстояния подчиняются неравенству треугольника (4).

Рис. 2.2 - Закрытый конверт Рис. 2.3

Если оно соблюдается, можно предложить несколько алгоритмов с погрешностью 12. Прежде, чем описать такой алгоритм, следует вспомнить старинную головоломку. Можно ли начертить одной линией открытый конверт? Рис.2 показывает, что можно (цифры на отрезках показывают порядок их проведения). Закрытый конверт (Рис. 2.2.) одной линией нарисовать нельзя и вот почему. Будем называть линии ребрами, а их перекрестья - вершинами.

Когда через точку проводится линия, то используется два ребра - одно для входа в вершину, одно - для выхода. Если степень вершины нечетна - то в ней линия должна начаться или кончиться. На Рис. 2.2 вершин нечетной степени две: в одной линия начинается, в другой - кончается. Однако на Рис. 2.3 имеется четыре вершины степени три, но у одной линии не может быть четыре конца. Если же нужно прочертить фигуру одной замкнутой линией, то все ее вершины должны иметь четную степень.

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

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

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

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

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

Вначале обсудим свойство спрямления. Рассмотрим какую-нибудь цепь, например, на Рис. 2.4. Если справедливо неравенство треугольника, то d[1,3]?d[1,2] d[2,3] и d[3,5]?d[3,4] d[4,5] Сложив эти два неравенства, получим d[1,3] d[3,5]?d[1,2] d[2,3] d[3,4] d[4,5]. По неравенству треугольника получим. d[1,5]?d[1,3] d[3,5]. Окончательно d[1,5]? d[1,2] d[2,3] d[3,4] d[4,5]

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

Вернемся к ЗК и опишем решающий ее деревянный алгоритм.

1. Построим на входной сети ЗК кратчайшее остовное дерево и удвоим все его ребра. Получим граф G - связный и с вершинами, имеющими только четные степени.

2. Построим эйлеров цикл G, начиная с вершины 1, цикл задается перечнем вершин.

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

Пример 1. Дана полная сеть, показанная на Рис. 2.4. Найти тур жадных и деревянных алгоритмов.

Табл. 2.1

- 1 2 3 4 5 6

1 - 6 4 8 7 14

2 6 - 7 11 7 10

3 4 7 - 4 3 10

4 8 11 4 - 5 11

5 7 7 3 5 - 7

6 14 10 10 11 7 -

Рис. 2.5

Решение. Жадный алгоритм (иди в ближайший город из города 1) дает тур 1-(4)-3-(3)-5(5)-4-(11)-6-(10)-2-(6)-1, где без скобок показаны номера вершин, а в скобках - длины ребер. Длина тура равна 39, тур показана на Рис. 2.4.

2. Деревянный алгоритм вначале строит остовное дерево, показанное на Рис. 2.5 штриховой линией, затем эйлеров цикл 1-2-1-3-4-3-5-6-5-3-1, затем тур 1-2-3-4-5-6-1 длиной 43, который показан сплошной линией на Рис. 2.5.

Теорема. Погрешность деревянного алгоритма равна 1.

Доказательство. Возьмем минимальный тур длины FB и удалим из него максимальное ребро. Длина получившейся гамильтоновой цепи LHC меньше FB. Но эту же цепь можно рассматривать как остовное дерево, т. к. эта цепь достигает все вершины и не имеет циклов. Длина кратчайшего остовного дерева LMT меньше или равна LHC. Имеем цепочку неравенств

FB>LHC?LMT (6)

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

2LMT>FA (7)

Умножая (6) на два и соединяя с (7), получаем цепочку неравенств

2FB>2LHC?2LMT?FA (8)

Т.е. 2FB>FA, т.е. FA/FB>1 e; e=1.

Теорема доказана.

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

Известно еще несколько простых алгоритмов, гарантирующих в худшем случае e=1. Для того, чтобы найти среди них алгоритм поточнее, зайдем с другого конца и для начала опишем “brute-force enumeration” - “перебор животной силой”, как его называют в англоязычной литературе. Понятно, что полный перебор практически применим только в задачах малого размера. Напомним, что ЗК с n городами требует при полном переборе рассмотрения (n-1)!/2 туров в симметричной задаче и (n-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). Тогда если u1?v1, то и u?v, если же 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 (тот же алгоритм, но упрощенный случай) и т.д. Нужно понимать, что в ЗК с n городами не нужны все перестановки из n элементов. Потому что перестановки, скажем, 1-3-5-4-2 и 3-5-4-2-1 (последний элемент соединен с первым) задают один и тот же тур, считанный сперва с города 1, а потом с города 3. Поэтому нужно зафиксировать начальный город 1 и присоединять к нему все перестановки из остальных элементов. Этот перебор даст (n-1)! разных туров, т.е. полный перебор в несимметричной ЗК (мы по-прежнему будем различать туры 1-3-5-4-2 и 1-2-4-5-3).

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

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

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

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

Изложим алгоритм Литтла на примере 1 предыдущего раздела.. Повторно запишем матрицу:

Нам будет удобнее трактовать Cij как стоимость проезда из города i в город j. Допустим, что добрый мэр города j издал указ выплачивать каждому въехавшему в город коммивояжеру 5 долларов. Это означает, что любой тур подешевеет на 5 долларов, поскольку в любом туре нужно въехать в город j. Но поскольку все туры равномерно подешевели, то прежний минимальный тур будет и теперь стоить меньше всех. Добрый же поступок мэра можно представить как уменьшение всех чисел j-го столбца матрицы С на 5. Если бы мэр хотел спровадить коммивояжеров из j-го города и установил награду за выезд в размере 10 долларов, это можно было бы выразить вычитанием 10 из всех элементов j-й той строки. Это снова бы изменило стоимость каждого тура, но минимальный тур остался бы минимальным. Итак, доказана следующая лемма.

Вычитая любую константу из всех элементов любой строки или столбца матрицы С, мы оставляем минимальный тур минимальным.

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

Прочерки по диагонали означают, что из города i в город i ходить нельзя. Заметим, что сумма констант приведения по строкам равна 27, сумма по столбцам 7, сумма сумм равна 34.

Тур можно задать системой из шести подчеркнутых (выделенных другим цветом) элементов матрицы С, например, такой, как показано на Табл. 2.2. Подчеркивание элемента означает, что в туре из i-го элемента идут именно в j-тый. Для тура из шести городов подчеркнутых элементов должно быть шесть, так как в туре из шести городов есть шесть ребер. Каждый столбец должен содержать ровно один подчеркнутый элемент (в каждый город коммивояжер въехал один раз), в каждой строке должен быть ровно один подчеркнутый элемент (из каждого города коммивояжер выехал один раз); кроме того, подчеркнутые элементы должны описывать один тур, а не несколько меньших циклов. Сумма чисел подчеркнутых элементов есть стоимость тура. На Табл. 2.2 стоимость равна 36, это тот минимальный тур, который получен лексикографическим перебором.

Теперь будем рассуждать от приведенной матрицы на Табл. 2.2. Если в ней удастся построить правильную систему подчеркнутых элементов, т.е. систему, удовлетворяющую трем вышеописанным требованиям, и этими подчеркнутыми элементами будут только нули, то ясно, что для этой матрицы мы получим минимальный тур. Но он же будет минимальным и для исходной матрицы С, только для того, чтобы получить правильную стоимость тура, нужно будет обратно прибавить все константы приведения, и стоимость тура изменится с 0 до 34. Таким образом, минимальный тур не может быть меньше 34. Мы получили оценку снизу для всех туров.

Теперь приступим к ветвлению. Для этого проделаем шаг оценки нулей. Рассмотрим нуль в клетке (1,2) приведенной матрицы. Он означает, что цена перехода из города 1 в город 2 равна 0. А если мы не пойдем из города 1 в город 2? Тогда все равно нужно въехать в город 2 за цены, указанные во втором столбце; дешевле всего за 1 (из города 6). Далее, все равно надо будет выехать из города 1 за цену, указанную в первой строке; дешевле всего в город 3 за 0. Суммируя эти два минимума, имеем 1 0=1: если не ехать “по нулю” из города 1 в город 2, то надо заплатить не меньше 1. Это и есть оценка нуля. Оценки всех нулей поставлены на Табл. 2.5 правее и выше нуля (оценки нуля, равные нулю, не ставились).

Выберем максимальную из этих оценок (в примере есть несколько оценок, равных единице, выберем первую из них, в клетке (1,2)).

Итак, выбрано нулевое ребро (1,2). Разобьем все туры на два к

граф моделирование коммивояжер программа

В ходе прохождения производственной практики был рассмотрен один из видов задач теории графов и сетевого моделирования «Задачу о коммивояжере».

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

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

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

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

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

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

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

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