Відмінності алгоритмів прямої і зворотної прогонок

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

1) Потрібно знайти найкоротшу відстань між двома конкретними вершинами мережі. У цьому випадку вибір може бути довільним, тому що жоден з алгоритмів не має переваги над іншим.

2) Потрібно знайти найкоротшу відстань між вершиною 1 і однією з вершин множини

.

У цьому випадку рекомендується застосовувати АЗП і у пункті 1 алгоритму вважати, що .

3) Потрібно знайти найкоротшу відстань між однією з вершин множини і вершиною . У цьому випадку рекомендується застосовувати АПП і у пункті 1 вважати, що .

4) Потрібно знайти найкоротшу відстань у мережі такого типу (рис. 17):

Рис. 17

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

Для випадків 1 і 4 схеми АПП й АЗП розв’язку ЗЗНШ еквівалентні.

Отже, у загальному випадку, для розв’язку задач ДП можливе застосування чотирьох алгоритмів (зворотньої і прямої прогонки по дугах, що виходять і входять). Для розв’язку задачі ЗНШ обрати можна кожний з них. Однак, при розв’язанні деяких інших задач динамічного програмування можливі ситуації, коли відмінності між цими алгоритмами, пов'язані з ефективністю обчислень, виявляються істотними. Алгоритми по дугах, що виходять можна узагальнити й використати для розв’язання задач, у яких є елемент випадковості. Для алгоритмів по дугах,що входять цього зробити не можна.

Досвід практичного застосування АЗП показує, що процедура зворотньої прогонки більш ефективна.

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