мості (так званих свідків рішення), то він зможе досить швидко (За час, що не перевершує многочлена від розміру даних) вирішити завдання. Проблема в тому, що знайти таких свідків буває складно, тому багато алгоритми з класу NP вважаються довгими. Класичним прикладом NP-завдання є завдання комівояжера.
Задача комівояжера (комівояжер - бродячий торговець) полягає у знаходженні самого вигідного маршруту, що проходить через зазначені міста хоча б по одному разу. В умовах задачі вказуються критерій вигідності маршруту (найкоротший, самий дешевий, сукупний критерій тощо) і відповідні матриці відстаней, вартості і т. п. Як правило, вказується, що маршрут повинен проходити через кожне місто тільки один раз, в такому випадку вибір здійснюється серед гамільтонових циклів [1] . p> Існує маса різновидів узагальненої постановки завдання, зокрема геометрична задача комівояжера (коли матриця відстаней відображає відстані між точками на площині), трикутна задача комівояжера (коли на матриці вартостей виконується нерівність трикутника), симетрична і асиметрична завдання комівояжера.
Найпростіші методи розв'язання задачі комівояжера: повний лексичний перебір, жадібні алгоритми (метод найближчого сусіда, метод включення найближчого міста, метод найдешевшого включення), метод мінімального кістяка. На практиці застосовуються різні модифікації ефективніших методів: метод гілок і меж і метод генетичних алгоритмів.
Задача комівояжера є NP-повна задача [2] . Часто на ній проводять обкатку нових підходів до евристичному скорочення повного перебору.
У основі методу гілок і меж лежить просте спостереження, що якщо нижня межа для підобласті A дерева пошуку більше, ніж верхня межа якої-небудь раніше переглянутої підобласті B, то A може бути виключена з подальшого розгляду. Це зазвичай виконується за допомогою глобальної змінної m, в якій запам'ятовується мінімальна верхня межа, отримана для всіх переглянутих до теперішнього часу варіантах; будь-яка вершина дерева пошуку, нижня межа якої більше m, може бути виключена з подальшого розгляду.
У наступному розділі ми перейдемо до розгляду генетичних алгоритмів.
Генетичні алгоритми. Загальний опис. Математичний апарат. p> Генетичні алгоритми призначені для вирішення завдань оптимізації. Прикладом такого завдання може служити навчання нейромережі, тобто підбору таких значень ваг, при яких досягається мінімальна помилка. При цьому в основі генетичного алгоритму лежить метод випадкового пошуку. Основним недоліком випадкового пошуку є те, що нам невідомо, скільки знадобиться часу для вирішення завдання. Для того щоб уникнути таких витрат часу при вирішенні завдання, застосовуються методи, що проявилися в біології. При цьому використовуються методи відкриті при вивченні еволюції і походження видів. Як відомо, в процесі еволюції виживають найбільш пристосовані особини. Це призводить до того, що пристосованість популяції зростає, дозволяючи їй краще виживати в що з...
