Page 201 - Bkhargava_-_Grokaem_algoritmy

200 Глава 8. Жадные алгоритмы

ЕСЛИ IПОРО~ roPo.a. - САН-ФРАНЦИСКО:

~МАРИН
~

ФРЕМОНТ
ФРЕМОНТ

Мы знаем, что во Фремонте начинаются шесть возможных маршрутов. Ого!
Да они очень похожи на шесть маршрутов, которые вы вычислили ранее,
когда городов было всего три! Только теперь во всех маршрутах появился
дополнительный город, Фремонт! Начинает проявляться закономерность.
Предположим, из четырех городов выбирается начальный город Фремонт.
Остается еще три города. И вы знаете, что для перемещения между тремя
городами есть шесть разных маршрутов. Итак, если начать с Фремонта,
существуют шесть возможных маршрутов. Также возможно начать с одного
из других городов.

IНЧИНАЕМ НАЧИНАЕМ
& МАРИНЕ: & САН-ФРАНЦИСКО:

б &0.3MOil'HЫX =
МАРШРПО&
б &0.3MOil'HЫX ::::
МАРШРПО&

НАЧИНАЕМ
& БЕРКЛИ:

б &О.3МОЯ.НЬIХ ::::
мНШРУТо&

Четыре возможных начальных города, шесть возможных маршрутов для
каждого начального города = 4 х 6 = 24 возможных маршрута.

www.trk.kg