Програмний код описаного алгоритму у вигляді уривку лістингу.
Лабораторна робота Тема: Задача про прокладання найвигіднішого шляху між двома пунктам. Мета: Ознайомитися з алгоритмами реалізації розв’язування задачі динамічного програмування. Обладнання: Інструкційна карта, роздатковий матеріал. Теоретичні відомості Задача: Залізнична колія, що прокладається між двома населеними пунктами А і В, має пройти через пересічену місцевість: ліси, болота, річку, пагорби тощо. Відома вартість прокладання дороги через окремі зони, на які можна розбити місцевість між цими населеними пунктами. Необхідно так прокласти дорогу, рухаючись від пункту А до пункту В, щоб сумарні витрати на її спорудження були мінімальними. Приклад алгоритму розв’язування: Нехай маємо прямокутну область між двома пунктами А і В, розбита на зони 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 Все права принадлежат авторам размещенных материалов.
|