Задача про найкоротший шлях

Кожен багатокроковий процес прийняття рішень може бути зведений до задачі знаходження найкоротшого шляху (ЗЗНШ) у спрямованій ациклічній слоїстій мережі (САСМ). Саме з такої точки зору і будемо розглядати ЗЗНШ.

Розглянемо ряд визначень.

Спрямована мережа - це трійка , де - непорожня кінцева множина вершин (), - множина дуг: .

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

Кожній дузі поставлено у відповідність деяке дійсне число - довжина дуги, що з'єднує вершини і , , .

Шляхом називається кінцева послідовність вершин, таких, що . Довжина шляху – сума довжин дуг, що входять у нього.

Шлях, у якого , називається циклом.

Мережа називається ациклічною, якщо вона не містить жодного циклу.

В спрямованій ациклічній мережі завжди можна позначити вершини цілими числами від 1 до , таким чином, що для кожної дуги буде справедлива нерівність . Далі будемо вважати, що така нумерація проведена.

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

Відзначимо, що в загальному випадку й , і має сенс розв’язувати задачі при кількості слоїв (рис. 7).

Рис. 7

Кожна спрямована ациклічна мережа може бути зведена до слоїстої мережі шляхом введення фіктивних вершин і дуг. Наступний приклад ілюструє цей процес. Нехай маємо спрямовану ациклічну мережу (рис. 8). Ця мережа не є слоїстою.

Рис. 8

Після додавання фіктивних вершин 4', 5', 6', 7' і 8', а також дуг з нульовими вагами, що входять у ці вершини, одержали слоїсту мережу (рис 9).

Рис. 9

Розглянемо задачу знаходження найкоротшого шляху в САСМ з погляду ідей і прийомів ДП.

Нехай . Мета задачі – знайти найкоротший шлях між вершинами 1 і .

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

На початку кроку система може перебувати в одній з вершин . У цьому випадку кажуть, що система перебуває в одному з можливих станів . Для кожної вершини відомі дуги, що з'єднують її з однією з вершин множини . Інакше кажучи, для кожного стану відомі варіанти розв’язків (управлінь), що переводять систему в один із станів наступного кроку. Таким чином, варіантами розв’язків для стану : є всі дуги (s,k), що починаються в вершині .

Нехай - довжина найкоротшого шляху на кроках від до включно, за умови, що на початку кроку система перебуває в стані . Якщо на кроці , перебуваючи у вершині , ми приймаємо рішення піти по дузі , то мінімальна довжина шляху з вершини в цьому випадку становитиме

де – довжина найкоротшого шляху від вершини до вершини , що складається з кроків . Перебравши всі можливі варіанти розв’язків і знайшовши мінімум, отримаємо:

(1)

Цей вираз справедливий і при , якщо прийняти .

З урахуванням позначень, мета нашої задачі – знайти .