н з основних моментів алгоритму, пов'язаних з перебором маршрутів. З малюнка № 2 можна простежити порядок формування шляхів і розглянути на конкретному прикладі, як працює алгоритм. Тут наведено приклад для 4 міст. Зупинимося на малюнку по докладніше. p>
А) Ми починаємо шлях з пункту 1. У нашому маршруті записаний перший місто. Розглядаємо ті міста, де ми не були: це 2, 3 і 4. Спочатку переходимо у другій. p>
Б) Додаємо до маршрутом 2 місто. Дивимося, чи можна кудись перейти з другого міста. Можна відвідати третій і четвертий. Ми вибираємо третє місто.
В) Ставимо на третє місце в нашому маршруті місто 3. Далі ми дивимося, куди можна відправитися - до пункту 4. p> Г) На четверте місце в маршруті ставимо місто 4. Тут ми бачимо, що в нашому маршруті заповнені всі чотири місця і значить наш шлях закінчений. Порівнюємо довжину нашого шляху з мінімальним. Потім ми виходимо тому з пункту 4 до пункту 3 і в маршруті переміщаємося на третє місце. Дивимося, що в місті 3 ми були, тоді беремо наступний не відвідування місто - четвертий.
Д) Ставимо на третє місце маршруту четверте місто. З четвертого пункту можна відвідати тільки третій. p> Е) Прийшли в третій пункт. Ставимо на четверте місце маршруту місто 3. Бачимо, що всі чотири місця в нашому шляху заповнені і значить шлях закінчений. Порівнюємо довжину нашого шляху з мінімальним. Виходимо тому - з пункту 3 до пункту 4 і в маршруті переміщаємося на третє місце. Бачимо що тут теж немає НЕ відвіданих міст. Знову переходимо на рівень вгору: з пункту 4 в пункт2 і у маршруті переміщаємося на друге місце. У пункті 2 ми були, але залишилися не Відвідування міста 3 і 4. Переходимо в третій. На друге місце в маршруті записуємо третє місто.
Ж) Звідси можна потрапити в другий і четвертий. Переходимо у другій. На третє місце у маршруті ставимо друге місто. І так далі.
З наведеного прикладу вже можна виділити, як алгоритм перебирає шляху. Він діє за такою схемою:
0. Початкове значення j = 1 (перше місце в маршруті). p> 1. Ми знаходимося в місті k. p> 2. Для кожного міста (i = Від 1 до n)
3. Розглядаємо місто i. p> 4. Якщо цей місто ще не відвідано,
4.1. тоді переходимо в місто i; j збільшуємо на одиницю. Додаємо номер міста в маршрут на місце j. Позначаємо місто як відвіданий. Переходимо до пункту 1 (k = i).
4.2. інакше йти нікуди, тобто усі міста ми відвідали. p> 4.2.1. якщо j = Кількості міст (n), т.е ми дісталися до останнього пункту в маршруті і наш шлях сформований, тоді порівнюємо довжину шляху з довжиною мінімального маршруту. p> 4.2.2. Позначаємо місто як не відвідування і виходимо з нього. Зменшуємо j на одиницю. p> 5. Беремо наступний місто (i = i +1). br/>
В Опис основних структур даних
Тепер розглянемо структуру програми, опишемо класи та процедури, які були змінені і наповнені кодом.
Програм...
