Здавалка
Главная | Обратная связь

Програмний код описаного алгоритму у вигляді уривку лістингу.

Лабораторна робота

Тема: Задача про прокладання найвигіднішого шляху між двома пунктам.

Мета: Ознайомитися з алгоритмами реалізації розв’язування задачі динамічного програмування.

Обладнання: Інструкційна карта, роздатковий матеріал.

Теоретичні відомості

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

Приклад алгоритму розв’язування:

Нехай маємо прямокутну область між двома пунктами А і В, розбита на зони 5-ма рядками і 4-ма стовпцями, у кожній з яких зазначена вартість прокладання колії. Будемо рухатись від лівої нижньої зони до правої верхньої лише вгору і направо. Отже, задана таблиця аij, розмірністю n*m (n=5, m=4).

Стартовим буде елемент а51: його значення не змінюється (мал. а). Розглянемо сусідні з ним елементи: а41 і а52. Зміна значення елемента а41 за­лежить лише від значення а51, і вартість такого переходу станови­тиме 3 + 10 = 13. Зміна значення елемента а52 залежить також ли­ше від значення а51, і його значення при переході від а51 вправо становитиме 3 + 4 = 7 (б). Для зручності оброблені елементи таблиці виділено сірим кольором. Наступним для розгляду елементом може бути а42. До цього елемента можна перейти вже двома шляхами: або від лівого елемента а41, або від нижнього а52. Вартість першого переходу становитиме 13+1=14, а другого -7+1= 8. Зрозуміло, що кращим є другий перехід. Запишемо це нове перераховане значення а42 у таблицю (в). Продов­жуючи за аналогією перерахунок значень елементів таблиці, бу­демо розглядати ті її елементи, для яких існує перерахований лівий і нижній елементи, а для крайніх елементів - відповідно лівий або нижній. На кожному етапі новим значенням елемента аіj буде менше з двох можливих варіантів. Таким чином дійдемо до останнього елемента а14 (и). Отримане значення для нього і буде найменшою вартістю прокладання залізничної колії від населеного пункту А до населеного пункту В. Для нашого прикладу вона становитиме 28.

 

А) Б) В) Г) Д)

 

Е) Є) Ж) З) И)

Програмний код описаного алгоритму у вигляді уривку лістингу.


Хід роботи:

1. Ознайомитись з теоретичним матеріалом.

2. Використовуючи описаний вище алгоритм розв’язування задачі, розв’язати задачу знаходження найвигіднішого шляху між двома пунктами для таких початкових даних:

Вар 1 Вар2

 

3. ** Реалізувати розв’язок даної задачі за допомогою мови програмування.

4. Оформити звіт. Зробити висновки до роботи.





©2015 arhivinfo.ru Все права принадлежат авторам размещенных материалов.