Помогите решить теорию алгоритмов 6 вариант. Created by gerasimyuk2011. matematika-ru

Составим матрицу смежности .Где означает отстутствие пути (ребра) между вершинами.Составим по ней матрицу кратчайших путей .Пусть , а - длина пути из в .Пусть - множество вершин.Рассмотрим вершины . Если кратчайший путь между и проходит через вершину , то , иначе, . Тогда .Составим алгоритм на псевдокоде:.Вообще, сложность алгоритма и при , количество операций . Делать 125 сравнений - несколько много. Приведу лишь итоговую матрицу:

Помогите решить теорию алгоритмов 6 вариант...

gerasimyuk2011 @gerasimyuk2011

July 2022 1 2 Report

Помогите решить теорию алгоритмов 6 вариант

Answers & Comments

Indentuum

Verified answer

Составим матрицу смежности $M$ .

$M = \begin{pmatrix} 0 & 4 & 4 & \infty & 3 \\ 2 & 0 & 8 & \infty& \infty \\ \infty & \infty & 0 & 5 & 5 \\ \infty & \infty & 8 & 0 & \infty \\ \infty & \infty & 4 & 4 & 0\end{pmatrix}$

Где $\infty$ означает отстутствие пути (ребра) между вершинами.

Составим по ней матрицу кратчайших путей $D$ .

Пусть $D = M$ , а $D_{uv}$ - длина пути из $u$ в $v$ .

Пусть $V = \{ A, B, C, D, E\}$ - множество вершин.

Рассмотрим вершины $k,u,v \in V$ . Если кратчайший путь между $u$ и $v$ проходит через вершину $k$ , то $M_{uk} + M_{kv} \leq M_{uv}$ , иначе, $M_{uk} + M_{kv} > M_{uv}$ . Тогда $D_{uv} = \min(D_{uv}, D_{uk} + D_{kv})$ .

Составим алгоритм на псевдокоде:

$\textrm{for } k \in V \textrm{ do}\\\textrm{\quad for } u \in V \textrm{ do}\\\textrm{\qquad for } v \in V \textrm{ do}\\\textrm{\qquad\quad} D_{uv} = \min(D_{uv}, D_{uk} + D_{kv})$ .

Вообще, сложность алгоритма $O(n^3)$ и при $n = 5$ , количество операций $\approx 5^3 = 125$ . Делать 125 сравнений - несколько много. Приведу лишь итоговую матрицу:

$D = \begin{pmatrix} 0 & 4 & 4 & 7 & 3 \\ 2 & 0 & 6 & 9 & 5 \\ \infty & \infty & 0 & 5 & 5 \\ \infty & \infty & 8 & 0 & 13 \\ \infty & \infty & 4 & 4 & 0\end{pmatrix}$

0 votes Thanks 0

nekotoryj algoritm iz odnoj cepochki simvolov poluchaet novuyu cepochku sleduyushim obfa81e5d58b77f7bc168a871e4be38e73 4757

Answer

gerasimyuk2011 July 2022 | 0 Ответы

Answers & Comments

Verified answer

nekotoryj algoritm iz odnoj cepochki simvolov poluchaet novuyu cepochku sleduyushim obfa81e5d58b77f7bc168a871e4be38e73 4757

u ispolnitelya delitel dve komandy kotorym prisvoeny nomera 1 razdeli na 2 23bbd7c38f06e4c05b788325e07b00af4 71399

obyasnite vyskazyvanie nastoyashie svojstva cheloveka obnaruzhivayutsya lish togda k

1 v kakom variante otveta slova ne yavlyayutsya paronimami a zhelannyj zhelateln

pomogite reshit zadachi po fizike93b16fa8eedcf296f9acf17e17073f85 77658

рекомендуемые вопросы

Helpful Links

Helpful Social