олучить стоимость и соседей этого узла.
Перебрать соседей.
f
Fl
id
m
КЛЮЧИ
ДНКЧЕ-
oe n in hel^hbors.KeusO •
/4 ^ л СОДЕРЖИТ «А» СПИСОК j—-—| ~Г\ УЗЛОб'.САИ У каждого узла имеется стоимость, которая определяет, сколько времени потребуется для достижения этого узла от начала. Здесь мы вычисляем, сколько времени потребуется для достижения узла А по пути Начало > Узел В > Узел А (вместо Начало > Узел А).
h
neui-c-oit - 2 4 5> = S
euj.cost = + neijUwsDO
А ^
СТОИМОСТЬ «в», РАССТОЯНИЕ м. с. I ОТ в ДО А: Ъ С равним эти стоимости.
Мы нашли более короткий путь к узлу А! Обновим стоимость.
C
a
/ .
b
Z
F\H
oo
COSTS
oStsDO pei^-cost
Т t “А” 5 Новый путь проходит через узел В, поэтому В назначается новым родителем.
p
Ч • '
-в;
✓
в
FVP»
—
av-eWtS РУС!' Г / ?
“А” «6н
Parents Мы снова вернулись к началу цикла. Следующим соседом в цикле for является конечный узел.
£ог п. »v\
, Т ' г ^
<5$$?/ А | FimI V Л ““
Сколько времени потребуется для достижения конечного узла, если идти через узел В?
- - costЧ «13Ы««0а >/ V РАССТОЯНИЕ ^ ОТ 6 ЛО КОНЦА 5
П
it-
отребуется 7 минут. Предыдущая стоимость была бесконечной, а 7 минут определенно меньше бесконечности.
Конечному узлу назначается новая стоимость и новый родитель.
А
В
2
f\N
^ ' / *:Ь
costs
.
А
Б
в
STACT
RH
:в- / "
PARENTS
arevt s {V\] - V'ods
J f ‘Vim” "b" П
processed. 3 f pevd (Vodf^
“в/
ОБРАБОТАННЫЕ УЗЛЫ: [В1
орядок, мы обновили стоимости всех соседей узла В. Узел помечается как обработанный.
Н
“/У
ПоДе „lowest_Cost _v\o )
А
5
УЖЕ ОБРАБОТАН
COSTS
айти следующий узел для обработки.
Получить стоимость и соседей узла А.
cost - costs [node)
У узла А всего один сосед: конечный узел.
£от ю ih heicjttcvs. kec|sO:
f“р»м"
Время достижения конечного узла составляет 7 минут. Сколько времени потребуется для достижения конечного узла, если идти через узел А?
p
■ nel^bboys^V)
стоимость от Л ДО КОНЕЧНОГО УЗЛА: \
стоимость ПРИ ПРОХОДЕ ЧЕРЕЗ А: 6
ew-cost * cost
СТОИМОСТЬ ПЕРЕХОДА К в ОТ НКЧКЛК: О '
it с о st s £vn3 > n ew_cost •'
COSTS
J' СТАРАЯ стоимость ПЕРЕХОДА К КОНЕЧНОМУ УЗЛУ: ?
Ч
CO s'
stsfVW Г t
‘W’ £
f T “A”
A
5
В
2.
FiM
Cost 5
A
в
в
sT(4tr
fi4
:A-
Parents
ерез узел А можно добраться быстрее! Обновим стоимость и родителя.
После того как все узлы будут обработаны, алгоритм завершается. Надеюсь, этот пошаговый разбор помог вам чуть лучше понять алгоритм. С функцией find_lowest_cost_node узел с наименьшей стоимостью находится проще простого. Код выглядит так:
def ind_lowest_cost_node(costs): Если это узел lowest_cost = loat("inf") с наименьшей lowest_cost_node = None стоимостью из for node in costs: -< Перебрать все узлы уже виденных cost = costs[node] и он еще не был if cost < lowest_cost and node not in processed: < обработан... lowest_cost = cost < ,..0H назначается новым lowest_cost_node = node узлом с наименьшей return lowest_cost_node стоимостью Упражнения
Каков вес кратчайшего пути от начала до конца в каждом из следующих графов?
Поиск в ширину вычисляет кратчайший путь в невзвешенном графе.
Алгоритм Дейкстры вычисляет кратчайший путь во взвешенном графе.
Алгоритм Дейкстры работает только в том случае, если все веса положительны.
При наличии отрицательных весов используйте алгоритм Веллмана— Форда.
Жадные алгоритмы
В
В этой главе
ы узнаете, как браться за невозможные задачи, не имеющие быстрого алгоритмического решения (NP-полные задачи).
Вы научитесь узнавать такие задачи и не терять время на поиски быстрого алгоритма (которого все равно нет).
Вы познакомитесь с приближенными алгоритмами, которые могут использоваться для быстрого нахождения приближенного решения NP-полных задач.
Вы узнаете о жадной стратегии — очень простой стратегии решения задач.
Задача составления расписания
Д опустим, имеется учебный класс, в котором нужно провести как можно больше уроков. Вы получаете список уроков.
РИС.
3:00
10:00
АНГЛ.
3:30
10:30
МАТ-КА
10:00
11:00
ИНФ-КА
10:30
11:30
МУЗЫКА
11:00
12:00
ПРЕДМЕТ с ДО
Провести в классе все уроки не получится, потому что некоторые из них перекрываются по времени.
Я:ЗС> 10 10*30 И И'ЗО 12
I » » I I )
АНГЛИЙСКИЙ ЯЗЫК
ЯI
РИСОВАНИЕ
Требуется провести в классе как можно больше уроков. Как отобрать уроки, чтобы полученный набор оказался самым большим из возможных?
Вроде бы сложная задача, верно? На самом деле алгоритм оказывается на удивление простым. Вот как он работает:
Выбрать урок, завершающийся раньше всех. Это первый урок, который будет проведен в классе.
Затем выбирается урок, начинающийся после завершения первого урока. И снова следует выбрать урок, который завершается раньше всех остальных. Он становится вторым уроком в расписании.
Продолжайте действовать по тому же принципу — и вы получите ответ! Давайте попробуем. Рисование заканчивается раньше всех уроков (в 10:00), поэтому мы выбираем именно его.
