Page 162 - Bkhargava_-_Grokaem_algoritmy

История одного обмена 161

за $15. Как Раме вычислить путь от книги до пианино, при котором он
потратит наименьшую сумму? На помощь приходит алгоритм Дейкстры!
Вспомните, что алгоритм Дейкстры состоит из четырех шагов. В этом при­
мере мы выполним все четыре шага, а в конце будет вычислен итоговый
путь .

У.3ЕЛ С.ТОИМОС.ТЬ
ПЛАСТИНКА 5
ПОСТЕР ~
ГИТАРА О<) МЫ ЩЕ
НЕ JlOXOJlИЛИ
БАРАБАН Оо j
JlO ЭТКХ У.3ЛО6
()С)
j ПКАНКНО от НАЧАЛЬНОrо
1

Прежде чем начинать, необходимо немного подготовиться. Постройте та­
блицу со стоимостями всех узлов. (Стоимость узла определяет затраты на
его достижение.)
Таблица будет обновляться по мере работы алгоритма. Для вычисления
итогового пути в таблицу также необходимо добавить столбец «родителм.

У.3 Е.Л РОJlИТЕ.ЛЬ
ПЛАСТИНКА KHllrA
ПОС.ТЕ.Р KHllrA
-
ГИТАРА
БАРАБАН -
-
ПИАНИНО

Вскоре я покажу, как работает этот столбец. А пока просто запустим алго­
ритм.

Шаг 1: найти узел с наименьшей стоимостью. В данном случае самый де­
шевый вариант обмена с доплатой $0 - это постер. Возможно ли получить
постер с меньшими затратами? Это очень важный момент, хорошенько по­
думайте над ним. Удастся ли вам найти серию обменов, при которой Рама

www.trk.kg