Завдання для самостійної роботи. 1. Перетворити ациклічну мережу (рис

1. Перетворити ациклічну мережу (рис. 11) до слоїстої. Розв’язати задачу, застосувавши алгоритм зворотної прогонки.

Рис. 11

Відповідь: найкоротший шлях 1-4-7-8, довжина 5

2. Застосувавши алгоритм зворотньої прогонки, знайти найкоротший шлях між вершинами 1 і 10 наступної мережі (рис. 12).

Рис. 12

Відповідь: найкоротші шляхи 1–2–3–6–8–9–10; 1–2–6–8–9–10, їх довжина дорівнює 10.

3. Застосувавши алгоритм зворотньої прогонки, знайти найкоротший шлях між однією з вершин першого слою (вершинами A, B або C) і вершиною K мережі, представленої на рис. 13.

Рис. 13

Відповідь: найкоротший шлях C–E–F–K; довжина шляху 4.

У розглянутих алгоритмах обчислення починалися з кінця мережі і рухалися в напрямку її початку, тобто в напрямку, зворотньому напрямку дуг. Звідси й термін “ зворотня прогонка ” у назві алгоритму.

Задача може бути розв’язана і в іншому напрямку, тобто при русі від початку мережі до її кінця. У цьому випадку говорять про “ пряму прогонку ”.

У випадку прямої прогонки під величиною розуміємо мінімальну довжину шляху на кроках включно за умови, що наприкінці кроку прийшли у вершину . Нехай до стану ми прийшли по дузі (). У цьому випадку мінімальна довжина шляху становить величину . Знайшовши мінімум по всім вхідним у вершину дугам, отримаємо:

(2)

Співвідношення (2) справедливо і для , якщо прийняти, що . З урахуванням позначень наша мета – знайти .

Співвідношення (1) і (2) називаються (основними) рекурентними співвідношеннями.

3.4 Схема алгоритму прямої прогонки (АПП) по дугах, що входять

1. Вважаємо .

2. Планування кроку

2.1. Виділити всі можливі стани, які можуть мати місце наприкінці кроку , тобто визначити множину .

2.2. Для кожного знайти найкоротший шлях з вершини 1 у вершину

Запам'ятати , для якого досягається мінімум цього виразу (умовний оптимальний розв’язок).

3. , якщо , те перейти до п. 4. Інакше - перейти до п. 2.

4. Формування оптимального розв’язку.

Дата добавления: 2014-11-29