Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Завдання для самостійної роботи. 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; Просмотров: 353; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.008 сек.