ЗМІСТ
Метод гілок і меж
Метод першого порядку
Метод другого порядку
Оптимальний пошук
Пасивний пошук
метод дихотомії
Метод золотого перерізу
Динамічне програмування
Лінійне програмування. Метод Жордана-Гаусса. p> Список літератури
Метод гілок і меж
Як приклад методу гілок і меж розглянемо завдання комівояжера.
Постановка завдання.
Є N пунктів, відстань між якими відомі. Необхідно, почавши руху з п.1. послідовно обійти всі інші по самому короткому шляху і повернутися в п.1. Умова a полягає в наступному: у кожен пункт треба увійти тільки один раз і один раз з нього вийти. На рис.1. наведено приклад завдання для N = 5. На ребрах, що з'єднують вершини графа (пункти), вказані відстані.
В
Рис. 1. br/>
Умова a унеможливлює вибір на деякому кроці обчислень оптимального із шляхів, що приводять у деяку точку. Рішення завдання методом прямого перебору всіх можливих (N-1)! можливо лише для малих N, Необхідний метод, який дозволяє зменшувати число розглянутих варіантів. Таким методом є метод гілок і меж (МВТ). p> Основний зміст методу полягає в тому, що будуються нижні оцінки функції мети (ФЦ), що дозволяють відбракувати безліч варіантів, для яких значення ФЦ свідомо гірше. У міру розгляду нових варіантів межа переміщується вниз (в задачі мінімізації) до тих пір, поки число різних варіантів не зменшується настільки, що вибір кращого з них буде зроблений безпосереднім порівнянням. p> Рішення завдання.
Запишемо вихідні дані у вигляді таблиці C0 = (Cij). У ній i і j - номери пунктів, рух на кожному кроці відбувається з i в j, довжина цього кроку шляху Cij, хрестиками відзначені заборонені переходи. Нехай Сi = min Cij. Знайдемо Сi для кожного i (в таблиці ці значення підкреслені), після чого зробимо приведення матриці С0 до C01 по рядках, де Cij1 обчислюються за формулами Cij1 = Cij - Ci. Позначимо d01 = ГҐCi. і Cj1 = min Cij. Знайдемо Cj для всіх j і виконаємо приведення C01 за стовпцями. У наведеному прикладі всі Сj = 0, тому C02 = C01, константа приведення за стовпцями d02 = 0, d0 = d01 + d02 = 23. br/>В
Можна стверджувати, що задачах з матрицями C0 і C01 відповідає один і той же оптимальний маршрут. Довжина будь-якого шляху LS (C0) і LS (C02) пов'язані формулою LS (C0) = LS (C02) + d0. що випливає з умови a. Тоді будь-який шлях по матриці представляє рух по клітках таблиці, причому в кожному рядку і кожному стовпці можна побувати тільки один раз. p> Величину d0 можна використовувати в якості нижньої межі при оцінці всіх можливих шляхів.
Розглянемо шлях, який включає перехід з i в j. Для нього LS Ві gij = d0 + Cij. Такий перехід завжди є, тому що в наведеній матриці хоча б один елемент у рядку - нульовий....
