![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Вибір того чи іншого напрямку розрахунків (що співпадає з напрямком мережі або є зворотнім до нього) залежить від постановки вихідної задачі ЗНШ. Розглянемо чотири можливі ситуації, що впливають на цей вибір.
1) Потрібно знайти найкоротшу відстань між двома конкретними вершинами мережі. У цьому випадку вибір може бути довільним, тому що жоден з алгоритмів не має переваги над іншим.
2) Потрібно знайти найкоротшу відстань між вершиною 1 і однією з вершин множини
.
У цьому випадку рекомендується застосовувати АЗП і у пункті 1 алгоритму вважати, що .
3) Потрібно знайти найкоротшу відстань між однією з вершин множини і вершиною
. У цьому випадку рекомендується застосовувати АПП і у пункті 1 вважати, що
.
4) Потрібно знайти найкоротшу відстань у мережі такого типу (рис. 17):
|
| ||||||||||||||
![]() | |||||||||||||||
![]() | |||||||||||||||
![]() | |||||||||||||||
![]() | |||||||||||||||
Рис. 17
тобто від однієї (довільної) з вершин із множини до однієї (довільної) з вершин множини
. У цьому випадку вибір напрямку прогонки довільний.
Для випадків 1 і 4 схеми АПП й АЗП розв’язку ЗЗНШ еквівалентні.
Отже, у загальному випадку, для розв’язку задач ДП можливе застосування чотирьох алгоритмів (зворотньої і прямої прогонки по дугах, що виходять і входять). Для розв’язку задачі ЗНШ обрати можна кожний з них. Однак, при розв’язанні деяких інших задач динамічного програмування можливі ситуації, коли відмінності між цими алгоритмами, пов'язані з ефективністю обчислень, виявляються істотними. Алгоритми по дугах, що виходять можна узагальнити й використати для розв’язання задач, у яких є елемент випадковості. Для алгоритмів по дугах,що входять цього зробити не можна.
Досвід практичного застосування АЗП показує, що процедура зворотньої прогонки більш ефективна.
Дата публикования: 2014-11-04; Прочитано: 287 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!