Завдання для самостійної роботи. 1. За допомогою алгоритма прямої прогонки, знайти найкоротший шлях між вершинами 1 і 9 мережі, зображеної на рис

1. За допомогою алгоритма прямої прогонки, знайти найкоротший шлях між вершинами 1 і 9 мережі, зображеної на рис. 14.

Рис. 14

Відповідь: найкоротший шлях 1—2—6—7—9, довжина шляху 10.

2. За допомогою алгоритма прямої прогонки, знайти найкоротший шлях між вершиною A йоднієї з вершин останнього слою (вершинами G, H або I) наступної мережі (рис. 15).

Рис. 15

Відповідь: найкоротші шляхи: A—B—E—G; A—D—F—G; A—D—F—I, їх довжина 5.

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

1. Покласти ; .

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

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

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

2.2. Для кожного стану виконати наступне:

По кожній дузі (k,s), що входить у вершину знайти

2.3 Вважаємо

3. j=j – 1. Якщо j= 0, то перейти до пункту 4, інакше – перейти до пункту 2.

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

Процес розв’язку ЗЗНШ АЗП по дугах, що входять, проілюстрований на рис. 16.

Рис. 16

У прямокутниках вказані значення, що послідовно принімалися величинами .

Дата добавления: 2014-11-29; Просмотров: 372; Нарушение авторских прав?; Мы поможем в написании вашей работы!