Міністерство освіти і науки РФ
Державне освітня установа вищої професійної освіти
Амурській ДЕРЖАВНИЙ УНІВЕРСИТЕТ
(ГОУВПО В«АмГУВ»)
Факультет математики та інформатики
Кафедра математичного аналізу і моделювання
КУРСОВА РОБОТА
на тему: В« Задача про комівояжера і її узагальнення В»
з дисципліни В«Варіаційне числення та методи оптимізаціїВ»
ЗМІСТ
Введення
1 Постановка завдання
2 Евристичні методи
2.1 Алгоритм Борувкі
2.2 Алгоритм Крускала
2.3 Алгоритм Прима
2.4 Висновок
3 Генетичний алгоритм
4 NP-повна задача
5 Метод гілок і меж
6 Практичне застосування задачі комівояжер
Висновок
Бібліографічний список
ВСТУП
У 1859 р. Сер Вільям Гамільтон, знаменитий математик, що дав світові теорію комплексного числа і кватерниона, запропонував дитячу головоломку, в якій пропонувалося зробити В«Круговий подорожВ» по 20 містах, розташованих в різних частинах земної кулі.
гамільтонових завдання про мандрівнику нерідко перетворюється в задачу про комівояжера. Комівояжер - не вільно мандрівний турист, а ділова людина, обмежений тимчасовими, грошовими або якими-небудь іншими ресурсами. Гамильтонова завдання може стати завданням про комівояжера, якщо кожне з ребер постачити числовою характеристикою. Це може бути кілометраж, час на дорогу, вартість квитка, витрата пального і т.д. Таким чином, умовні характеристики дадуть числовий ряд, елементи якого можуть бути розподілені між ребрами як завгодно.
Задача про комівояжера відноситься до класу NP-важких задач. Методи рішення задачі про комівояжера різні. В даній курсовій коротко розповідається тільки про деяких найбільш відомих.
До евристичним методам вирішення задачі комівояжера слід віднести В«жадібнийВ» алгоритм, на кожному кроці вибирає ребро найменшої вартості з безлічі ребер, не порушують коректності рішення. Ці методи мають велику погрішність. Добре досліджена область генетичних алгоритмів, що показали свою ефективність для даної задачі, але вони досить громіздкі. Метод перебору простий, але тільки лише при невеликій кількості ітерацій.
І найбільш зручним мені здається метод гілок і меж. Його можна застосовувати і при великому кількості міст.
1. ПОСТАНОВКА ЗАВДАННЯ
Рис.1
Припустимо, що бродячий торговець повинен, покинувши місто, якому привласнимо номер 1, об'їхати ще N - 1 міст і повернуться знову в місто номер 1. У його розпорядженні є дороги, з'єднують ці міста. Він повинен вибрати свій маршрут - порядок відвідування міст так, щоб шлях, який йому доведеться пройти, був якомога коротшим. Основна умова цієї задачі полягає в тому, що комівояжер не має права повертатися знову в це місто, в якому він одного разу вже побував. Це умова будемо називати умовою (О±). Ми вважаємо, що відстань між двома містами - функція f ( x i , x j ) - визначено. Зрозуміло, функція f ( x i , x j ) може означати не тільки відстань, але, наприклад, час або витрати в дорозі і т.д. тому в загальному випадку
f ( x i , x j ) в‰ f ( x j , x i ),
а функції f ( x i , x i ) природно приписати значення в€ћ. Довжина l шляхи S визначається формулою
(1.1)
Сума у ​​виразі (1) поширена по всіх індексах i і j , задовольняючим умові (О‘), тобто умові, що кожен з індексів i і j входить у вираз (1) один і тільки один раз. Функція l = l ( x 1 , ..., x N ) є, таким чином, адитивної - вона представима у вигляді суми доданків, проте сама задача - задача відшукання мінімуму l - В силу обмеження (О±) не є адитивною і не задовольняє принципом оптимальності.
Розглянемо знову площину t , x , де t - дискретний аргумент, приймає значення 0,1, 2, ..., N , відповідні етапам подорожі торговця. Значить t = 0 відповідає його початкового стану в місті номер 1, t = 1 - переходу з міста номер 1 в місто, який він вибрав першим для відвідування, і т.д., t = N означає останній етап його подорожі - повернення в місто номер 1. Аргумент x тепер також приймає дискретні значення 1,2, ..., N (Малюнок 1.1). З'єднаємо точку (0, 1) з точками (1,1), (1, 2), ... (1, N ) і довжинам відрізків, що з'єднують ці точки, припишемо значення f ( x 1 < i>, x j ) . Далі точки (1, s) - вузли, лежачі на першій вертикалі, ми з'єднаємо з усіма уздамі другий вертикалі, довжинам відрізків ми припишемо значення f ( x s , x k ) і т.д. точки ( N -1, s ) з'єднаємо з точкою ( N , 1).
У результаті ми побудували деякий граф, кожна ламана якого, з'єднує точку (0,1) сточки (N, 1), описує шлях комівояжера. Наше завдання ми можемо тепер сформулювати таким чином. Серед всіх ламаних, що належать цьому графу і з'єднують точки (0,1) і ( N , 1) і задовольняють умові (О±), знайти ломанную найкоротшою довжини. Умова (О‘) полягає тепер у тому, що шукана ламана перетинає (у вузлі) кожну з прямих x = i один і тільки один раз. Таким чином, задача про комівояжера формулюється більш звичним для нас мовою.
Розглянемо вузол P , лежачий на третій вертикалі (Малюнок 1.2). Якби умова (О±) відсутнє, то вибір траєкторії, яка з'єднує точку P з крапкою ( N , 1), не залежав би від того шляху, який привів нас в точку P . У даному випадку ситуація інша, і якщо два комівояжера знаходяться в точці P , але один з них прийшов у цей стан, рухаючись вздовж траєкторії, що проходить через точку Q , а другий через точку R , то їх стану істотно відрізняються один від одного.
Комівояжер, який рухався по другій траєкторії, вже побував в містах номер 2 і номер 5 і в майбутньому він вже не має права знову заїжджати в ці міста. Що стосується комівояжера, який рухався вздовж першої траєкторії, то він побував у містах номер 3 і номер 6; він не має права повертатися в ці міста, але зате він ще зобов'язаний відвідати міста номер 2 і номер 5 і т. Д.
Оскільки функція f ( x i , x < sub> j ) визначена на кінцевому множині точок, то і функція l (х 1 , ..., x N ) також визначена на кінцевому множині точок.
Отже, завдання визначення мінімуму функції l зводиться до перебору деякого кінцевого безлічі значень цієї функції, і проблема носить чисто обчислювальний характер. Однак саме обчислювальні труднощі тут величезні.
Легко підрахувати, що кількість можливих варіантів (число значень функції l ) одно ( N - 1 )! . Таким чином, безпосередньо перебрати і порівняти між собою усі можливі шляхи, по яких може слідувати бродячий торговець, для досить великої кількості міст практично неможливо.
Виникає проблема побудови такого методу послідовного аналізу варіантів, який виділя...
