Сайт підготовки до олімпіади з інформатики

програмування в С++

Динамічне прогамування на графах PDF Печать E-mail
Добавил(а) Administrator   
11.03.11 13:40

 (динамічне програмування)

 

Найкоротші шляхи

Нехай є n міст, пронумерованих числами від 1 до n. Для кожної пари міст із номерами і, j у таблиці a[і][j] зберігається ціле число - ціна прямого авіаквитка з міста i у місто j. Вважається, що рейси існують між будь-якими містами, a[і,і] = 0 при всіх і, a[і][j] може відрізнятися від a[j,і]. Найменшою вартістю проїзду з і в j вважається мінімально можлива сума цін квитків для маршрутів (у тому числі з пересадженнями), що ведуть з і в j. (Вона не перевершує a[і][j], але може бути менше).

У пропонованих нижче задачах потрібно знайти найменшу вартість проїзду для деяких пар міст при тих чи інших обмеженнях на масив a і на час роботи алгоритму.

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

 

1) Знайти найменшу вартість проїзду з 1-го міста в усі інші .

Позначимо через Мінвар(1,s,к) найменшу вартість проїзду з 1 у s менш чим з k пересадженнями. Тоді виконується таке співвідношення:

Мінвар (1,s,k+1) = найменшому з чисел Мінвар(1,s,k) і

Мінвар(1,і,k) + a[і][s] (і=1..n)

Як відзначалося вище, шуканою відповіддю є Мінвар (1,і,n) для всіх і=1..n.

((0,20,3,4,5,6),

                                 (20,0,5,6,7,8),

                                 (3,5,0,6,7,8),

                                 (4,6,6,0,8,8),

                                 (5,7,7,8,0,9),

                                 (6,8,8,8,9,0));

1 2 -----20

1-3 ---- 3 , 3-2---- 5= 8

min(20,8)=8

 

 

 

флойд

 

for k:=1 to n do

for i:=1 to n do

for j:=1 to n do

if a[i,k]+a[k,j]  a[i,j]:=a[i,k]+a[k,j];

Практична робота:  «Визначення найкоротшого шляху в графі методом динамічного програмування»

Прізвище ______________________________

 

Завдання

Результат

1.                    

Намалювати граф з кількістю вершин N=6

(навантажений, неорієнтований)

 

 

 

 

 

2.                    

Написати матрицю суміжності

Зауваження, якщо немає зв’язку, то записати велике число, наприклад 1000

 

 

 

 

 

1

2

3

4

5

6

1

 

 

 

 

 

 

2

 

 

 

 

 

 

3

 

 

 

 

 

 

4

 

 

 

 

 

 

5

 

 

 

 

 

 

6

 

 

 

 

 

 

 

3.                    

Намалювати каркас мінімальної  ваги (остове дерево)

 

 

 

 

 

 

 

 

4.                    

Скопіювати папку «!Лабораторна 10 динамічне» в свою папку

Занести матрицю в файл graph.dat

 

5.                    

За допомогою програми  ford.dpr відшукати всі мінімальні  шляхи та занести в таблицю

 

1

2

3

4

5

6

1

 

 

 

 

 

 

2

 

 

 

 

 

 

3

 

 

 

 

 

 

4

 

 

 

 

 

 

5

 

 

 

 

 

 

6

 

 

 

 

 

 

6.                    

За допомогою програми  floid.dpr відшукати всі мінімальні  шляхи та занести в таблицю

 

1

2

3

4

5

6

1

 

 

 

 

 

 

2

 

 

 

 

 

 

3

 

 

 

 

 

 

4

 

 

 

 

 

 

5

 

 

 

 

 

 

6

 

 

 

 

 

 

7.                    

За допомогою програми  deikstr.dpr відшукати всі мінімальні  шляхи з вершини start в вершину finish та занести в таблицю

Start

Finish

Шлях

Довжина

1

 

 

 

 

2

 

 

 

 

3

 

 

 

 

4

 

 

 

 

5

 

 

 

 

6

 

 

 

 

8.                    

Порівняти результати таблиць в завданнях 5,6,7

 

 

 

 

 

Статистика

Пользователей : 261
Статей : 225
Просмотрено статей : 108154

Вход/Регистрация

Нет