Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

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



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

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

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

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

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

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

2.3 Вважаємо

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

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

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

Рис. 16

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





Дата публикования: 2014-11-04; Прочитано: 295 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2025 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...