Зразок оформлення розділу „Аналізу завдання”

Данна задача є класичною задачею теорії графів і відома як задача пошуку найкоротших шляхів в мережі.

Подібні задачі виникають при виборі маршрутів в обчислювальних мережах і транспортних системах. У обчислювальних мережах рішення подібних задач визначає склад і структуру мережевих протоколів для обслуговування руху пакетів інформації. За даними про завантаження каналів обчислюється найбільш оптимальний маршрут проходження пакету інформації. При знаходженні такого шляху до пакету додається заголовок, в якому указують перелік вузлів для переходу від вершини х_i до вершини х_j або чергову вершину переходу. У транспортних системах рішення подібних задач визначає найекономніший по вартості або за часом маршрут руху транспортної одиниці.

Кожна вершина в такому графі використовується тільки один раз, а довжина найкоротшого шляху визначиться сумою вартостей ребер для переходу _i,j=(х_i;...х_k;...х_j):

L_i,j=_m,n l_m,n, где im, nj, mn.

Для пошуку найкоротших шляхів є декілька алгоритмів. Алгоритми Форда-Беллмана і Дейкстри дозволяють знайти найкоротші шляхи від заданої вершини графа до будь-якої іншою. В результаті цих обчислень формується граф типу “дерево” з коренем в заданій вершині. Алгоритми Флойда і Данцига дозволяють шукати найкоротші шляхи між будь-якою парою вершин графа типу мережа.

У основі всіх алгоритмів лежить операція порівняння двох простих маршрутів. На мал. 30 показані два прості маршрути, що сполучають вершини хi і хj. Вибір найкоротшого шляху між вершинами хi і хj є результат порівняння довжин двох маршрутів, тобто L_i,j=min{l_i,j; (l_i,p + l_p,j)}. Якщо існує декілька вершин, суміжних з вершинами х_i і х_j слід виконувати процедуру послідовно, порівнюючи довжини двох (див.Мал.)

Алгоритм Флойда. Для того, щоб вибирати найкоротші шлях і переходи між вершинами x_i і x_j, необхідно використовувати дві матриці: матрицю найкоротших шляхів ||l(n;n)|| і матрицю найкоротших переходів ||(n;n)||, які дозволяють обчислювати і порівнювати різні маршрути через базову вершину графа.

lp	x0	..	xi	xp	xj	..	xn
x0	0	..	l0i	∞	l0j	..	l0n
..	..	0	..	..	..	..	..
xi	li0	..	0	lip	lij	..	lin
xp	∞	..	lpi	0	lpj	..	lpn
xj	lj0	..	lji	ljp	0	..	ljn
..	..	..	..	..	..	0	..
xn	ln0	..	lni	lnp	lnj	..	0nn

Вершина х_p в матриці найкоротших шляхів називається базовою, а рядок і стовпець матриці ||l^p|| - базовими (виділені в матриці заливкою), якщо вона дозволяє порівнювати найкоротші шляхи між будь-якою парою вершин x_i і x_j, суміжних з вершиною х_p. Базова вершина дозволяє знайти шлях з вершини x_i у вершину x_j через вершину x_p по формулі l_ij=(l_ip+ l_pj), представити цей результат для порівняння з наявним значенням l_ij і вибрати найкоротший шлях. Якщо як базова, використовувати послідовно всі вершини, починаючи з вершини х₀, то за p=(n-1) кроків ітерації можна знайти найкоротші шляхи між будь-якою парою вершин. Для p=0 матриця ||l⁰|| є матриця вартостей графа.

p	x0	..	xi	xp	xj	..	xn
x0	x0	..	xi	xp	xj	..	xn
..	x0	..	xi	xp	xj	..	xn
xi	x0	..	xi	xp	xj	..	xn
xp	x0	..	xi	xp	xj	..	xn
xj	x0	..	xi	xp	xj	..	xn
..	x0	..	xi	xp	xj	..	xn
xn	x0	..	xi	xp	xj	..	xn

Матриця переходів ^p є похідною матриці найкоротших шляхів. Для p=0 елементи матриці ⁰ є кінцеві вершини переходу з х_i в х_j. Тому в кожному стовпці х_j матриці ⁰ вказана вершина х_j. На p-му кроці ітерації відбувається заміна вершини переходу вершиною найкоротшого переходу по формулах:

а) якщо (l_i,p+ l_p,j)^pl_i,j^p, то _i,j ^(p+1)= _i,j ^p=х_j;

б) якщо (l_i,p+ l_p,j)^p<l_i,j^p, то _i,j ^(p+1)=х_p.

Отже, для аналізу n-вершинного графа необхідно послідовно побудувати n матриць найкоротших шляхів і найкоротших переходів.

Додаток Є