Методичні вказівки

Належить до динамічних методів програмування, тобто у процесі рішення для кожної вершини постійна мітка є оптимальним рішенням. Алгоритм дуже просто програмується. Реалізується в табличному вигляді. Перший стовпчик – найменування вершин для дослідування. Другий – має помітки вже досліджених вершин та поточну вершину. Третій – має помітки сусідніх вершин з досліджуваною вершиною. Четвертий – розрахунковий. У розрахунковому стовпчику записують постійні та часові мітки. Постійною вважають часову мітку, якщо всі шляхи до цієї вершини дослідженні та вона є мінімальною з них. Складається з наступним кроків:

1. Присвоюють першій вершині мітку 0, останнім - .

2. Досліджують першу вершину (мітка у другий стовпчик)

3. Досліджують сусідів (мітки супроти сусідніх вершин у третьому стовпчику)

4. Розраховують шляхи від досліджуваної вершини до сусідніх як суму постійної мітки досліджуваної вершини та вагу інцідентного ребра.

5. Якщо всі шляхи до сусідніх вершин вже досліджені, порівнюють всі мітки даного рядка та обирають найменшу (оптимальну) – постійна мітка. У іншому разі переходять до наступного етапу.

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

Контрольні питання:

1. Принцип дії методу метли?

2. Які найкоротші відстані можна визначити по розрахованій таблиці методом метли?

3. Як визначити послідовність вершин за методом метли?

Література [1,7]

Практична робота №4. Найкоротший шлях на транспортній мережі.

Мета: набути практичні навички знаходження найкоротших відстаней методом потенціалів

Задача

Дана транспортна мережа (рис.4.1).

Рис. 4.1 Транспортна мережа

Завдання:

1. Відстані на малюнку розрахувати згідно свого варіанту.

2. Визначити найкоротшу відстань між 1 та 10 вершинами транспортної мережі графічним та аналітичним способом.

Методичні вказівки

Належить до динамічних методів програмування, тобто у процесі рішення для кожної вершини постійна мітка є оптимальним рішенням. Алгоритм дуже просто програмується. Реалізується в графічному або аналітичному вигляді. Складається з наступним кроків:

1. Присвоюють першій вершині мітку 0, останнім - .

2. Досліджують кожну сміжну вершину (мітки сусідніх вершин). Розраховують шляхи від тієї вершини до сміжних як суму постійної мітки сміжної вершини та вагу інцідентного ребра. Зі всіх значень обирають найменше – це є мітка досліджуваної вершини. Таким чином визначають мітки кожної вершини сміжних з першою (приклад див.конспект).

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

4. Після кінцевого перерахунку виписують шлях як послідовність вершин з міток, починаючи з кінця (приклад див.конспект).

Контрольні питання:

1. Принцип дії методу потенціалів?

2. Які найкоротші відстані можна визначити по розрахункам за методом потенціалів?

3. Як визначити послідовність вершин найкоротшого шляху?

Література [1,7]