1 of 7

Задача Прима-Краскала

2 of 7

Жадные алгоритмы

2

Жадный алгоритм – это многошаговый алгоритм, в котором на каждом шаге принимается решение, лучшее в данный момент.

1

B

2

4

5

9

7

8

1

3

D

E

F

A

C

Задача. Найти кратчайший маршрут из А в F.

Алгоритмизация и программирование. Язык Python, 11 класс

3 of 7

Жадные алгоритмы

3

4

B

2

1

2

9

7

8

1

3

D

E

F

A

C

Задача. Найти кратчайший маршрут из А в F.

Это лучший маршрут?

?

Жадный алгоритм не всегда даёт наилучшее решение!

!

Алгоритмизация и программирование. Язык Python, 11 класс

4 of 7

Задача Прима-Крускала

4

Задача. Между какими городами нужно проложить линии связи, чтобы все города были связаны в одну систему и общая длина линий связи была наименьшей?�(минимальное остовное дерево)

4

B

2

1

2

9

7

8

1

3

D

E

F

A

C

Алгоритм Крускала:

начальное дерево – пустое
на каждом шаге добавляется ребро минимального веса, которое ещё не входит в дерево и не приводит к появлению цикла

Лучшее решение!

!

Алгоритмизация и программирование. Язык Python, 11 класс

5 of 7

Раскраска вершин

5

4

B

2

1

2

9

7

8

1

3

D

E

F

A

C

ищем ребро минимальной длины среди всех рёбер, концы которых окрашены в разные цвета;
найденное ребро (iMin,jMin) добавляется в список выбранных, и все вершины, имеющие цвет col[jMin], перекрашиваются в цвет col[iMin].

Сделать N-1 раз:

col = [i for i in range(N)]

каждой вершине свой цвет

Алгоритмизация и программирование. Язык Python, 11 класс

6 of 7

Раскраска вершин

6

N = 6

W = []

for i in range(N):

W.append ( [0]*N )

# заполнить матрицу

Весовая матрица:

Вывод результата:

for edge in ostov:

print ( "(", edge[0], ",",

edge[1], ")" )

Алгоритмизация и программирование. Язык Python, 11 класс

7 of 7

Раскраска вершин

7

ostov = [] # список выбранных рёбер

for k in range(N-1):

minDist = 1e10 # очень большое число

for i in range(N):

for j in range(N):

if col[i] != col[j] \

and W[i][j] < minDist:

iMin = i

jMin = j

minDist = W[i][j]

ostov.append ( (iMin, jMin) )

c = col[jMin]

for i in range(N):

if col[i] == c:

col[i] = col[iMin]

ищем ребро с минимальным весом

перекраска вершин

добавить новое ребро

Алгоритмизация и программирование. Язык Python, 11 класс