б зайві гілки в дереві пошуку найкоротшого шляху.
Для пояснення мого варіанту розв'язання задачі слід ввести кілька понять. Проміжну довжину шляху можна визначити наступним чином: уявімо, що торговець вибрав небудь шлях; він вийшов з першого міста і зараз знаходиться в якомусь місті i . Тоді все пройдене відстань з початку в місто i будемо називати проміжна довжина шляху. Якщо виходити з того, що торговець у кожен момент часу буде перебувати в якомусь i -му місті, то завжди можна підрахувати яку відстань він пройшов з початку до цього міста, тобто проміжну довжину шляху.
Мінімальним шляхом будемо називати маршрут, що проходить по всіх містах і має мінімальну довжину.
Мій критерій будується на одному простому твердженні: якщо проміжна довжина шляху більше мінімального шляху, тоді очевидно наступне:
1. проміжна довжина буде рости, коли торговець буде рухатися до кінцевого місту,
2. а значить довжина всього шляху буде більше довжини мінімального маршруту.
отже такий маршрут можна відкинути. p> Пояснення показані на малюнку 1.
У даній програмі використовується наступний критерій: при переході від одного міста до іншого розраховується проміжна довжина шляху, і якщо вона більше поточного мінімального шляху, то обчислення з даної гілки припиняються. Таким чином, відсікаються зайві гілки. p> Рішення даної задачі призводить до перебору можливих варіантів шляху, але критерії такого роду можуть значно скоротити обчислення і зменшити час роботи програми.
В
Мова програмування
Для написання програми була вибрана мова Сі + + з наступних причин:
1. Середа програмування Windows-додатків Microsoft Visual C + + 6.0 дозволяє в моїй завданню наочно відобразити карту міст і схему їх з'єднання.
2. Це одна з мов, в якому я непогано розбираюся. Тому мені зручніше писати програму за допомогою Visual C + +. <В
Опис алгоритму
У програмі міститься рекурсивна функція, яка забезпечує перебір можливих шляхів для пошуку найкоротшого. Саме тут укладено алгоритм рішення задачі В«комівояжераВ». Розглянемо його детальніше:
1. Для кожного міста ( i = від 1 до n ), де ми ще не були. p> 2. Припустимо, що ми прийшли в якесь місто i . Позначаємо його, що ми тут вже були. p> 3. Підраховуємо довжину пройденого шляху.
4. Якщо вона більше ніж довжина мінімального шляху,
4.1. Тоді немає сенсу йти цим шляхом далі.
4.1.1. позначаємо місто як не відвідування, виходимо з міста.
4.2. Інакше, p> 4.2.1. якщо ми в кінці шляху
4.2.1.1. тоді , порівнюємо з мінімальним шляхом, якщо він менше найкоротшого шляху, тоді мінімальний шлях = найкоротший шлях.
4.2.1.2. інакше переходимо до пункту 1.
5. Переходимо до наступного міста, де ми не були.
Слід розглянути оди...
