Объединение прямой и обратной формулировок

Итак, у нас имеются симметричные алгоритмы для построения значений функ- ций f и g. Идея заключается в том, чтобы использовать эти два алгоритма совместно для поиска оптимального выравнивания. Прежде всего стоит выделить два основ- ных факта, характеризующих отношения между функциями f и g.

(6.19) Длина кратчайшего пути из угла в угол в GXY, проходящего через (i, j), равна f( U j) + g(k j).

Доказательство. Пусть СЕ. — длина кратчайшего пути из угла в угол, проходя- щего через (i, j). Очевидно, что любой такой путь должен перейти от (0,0) к (i, j), а затем от (i, j) к (m, n). Следовательно, его длина равна как минимум f(i, j) + g(U Л а значит, СЕ. > f(i, j) + g(i, j). С другой стороны, рассмотрим путь из угла в угол, со- стоящий из пути минимальной длины из (0, 0) в (i, j), за которым следует путь минимальной длины из (i, j) в (m, n). Длина этого пути равна f (i, j) + g(i, j), поэтому t}

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

Еще по теме Объединение прямой и обратной формулировок:

  1. Прямой результат
  2. Глава третья Первый прямой ченнелинг
  3. Прямой доступ к информации и предузнавание
  4. Репортаж ПРЯМОЙ
  5. АНАЛИЗ ПРЯМОЙ
  6. Первый прямой ченнелинг
  7. Прямой доступ к информации (на основе книг Барбары Энн Бреннан).
  8. 8. Общественные объединения
  9. 6. Объединение работодателей
  10. 1. Понятие и виды объединений работодателей
  11. Право ребенка на объединение