<<
>>

Снижение затрат памяти

Всего одно небольшое изменение реализации позволит значительно снизить затра- ты памяти. Типичным недостатком многих алгоритмов динамического программи- рования являются высокие требования к памяти, обусловленные необходимостью хранения массива M.
В алгоритме Беллмана-Форда в том виде, в каком он записан, этот массив имеет размер n2; тем не менее сейчас мы покажем, как сократить его до O(n). Вместо того чтобы сохранять M[i, v] для каждого значения i, мы будем использовать и обновлять одно значение M[v] для каждого узла v — длину крат- чайшего пути из v в t, найденного на данный момент. Алгоритм, как и прежде, выполняется для итераций i = 1, 2, ..., n-1, но i теперь используется как простой счетчик; при каждой итерации и для каждого узла v выполняется обновление

А теперь отметим следующий факт.

(6.26) На протяжении работы алгоритма M[v] содержит длину некоторого пути из v в t и после i циклов обновлений значение M[v] не превышает длину кратчай- шего пути из v в t, использующего не более i ребер.

С учетом (6.26) мы теперь снова можем использовать (6.22), чтобы показать, что работа завершена после n - 1 итераций. Так как сохраняется только массив M, индексируемый по узлам, для его хранения достаточно памяти O(n).

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Снижение затрат памяти:

  1. Кнуты и снижение веса
  2. Снижение обязательств
  3. 2. Метод снижения обязательств
  4. Статья 947. Возмещение затрат на сохранение
  5. Статья 394. Возмещение вреда, причиненного собственнику земельного участка, жилого дома, других зданий в связи со снижением их ценности
  6. Статья 801. Затраты, связанные с использованием транспортного средства
  7. Статья 904. Возмещение исполнителю фактических затрат по договору о безвозмездном предоставлении услуг
  8. Статья 342. Возмещение затрат на содержание безнадзорного домашнего животного и выплата вознаграждения
  9. Статья 1024. Право комиссионера на возмещение затрат, сделанных им в связи с выполнением договора комиссии
  10. ПРЕДСТАВЛЕНИЕ ПАМЯТИ
  11. Гигиена памяти.
  12. укрепление памяти