<<
>>

Более эффективный по затратам пространства способ построения путей

Оказывается, принципиально иная разновидность алгоритмов поиска пути суще- ствует и обладает как раз нужными нам свойствами. Основная идея, предложен- ная Савичем в 1970 году, заключается в умном применении принципа «разделяй и властвуй».
Впоследствии этот прием был заложен в основу сокращения затрат пространства в задаче выравнивания последовательностей; по этой причине общий подход может напомнить то, что обсуждалось ранее в разделе 6.7. Наш план, как и прежде, основан на умном повторном использовании пространства — откровенно говоря, за счет возрастания затрат времени. Как поиск в глубину, так и поиск в ши- рину не проявляет достаточного рвения в повторном использовании пространства; оба должны постоянно вести большой исторический список. Нам нужен способ решить половину задачи, отбросить почти всю промежуточную работу, а затем решить другую половину задачи.

Ключевая роль в этом алгоритме отводится процедуре, которую мы назовем Раth(Ср C2, L). Процедура определяет, существует ли последовательность опера- торов, состоящая не более чем из L шагов, которая приводит из конфигурации C1 в конфигурацию C2.

Итак, исходной задачей является определение результата (да или нет) для Path(C0, C*, 2й). Поиск в ширину может рассматриваться как следую- щая реализация этой процедуры средствами динамического программирования: чтобы определить Path(Cp C2, L), мы сначала определяем все C', для которых вы- полняется Path(Cp C', L - 1); затем мы проверяем для всех таких C', ведет ли какой- нибудь оператор напрямую из C' в C2.

Это отчасти демонстрирует неэффективность в отношении затрат простран- ства, присущую поиску в ширину. Мы генерируем множество промежуточных конфигураций только для того, чтобы уменьшить параметр L на 1. Эффективнее было бы попытаться определить, существует ли какая-либо конфигурация C', ко- торая служит срединной точкой пути из C1 в C2.

Можно сначала сгенерировать все возможные срединные точки C'. Затем для всех C' можно рекурсивно проверить, можно ли перейти из C1 в C' не более чем за L/2 шагов и можно ли перейти из C' в C2 не более чем за L/2 шагов. Для этого потребуются два рекурсивных вызова, но нас интересуют только результаты «да/нет» для каждого из них; в остальном пространство можно использовать повторно.

Позволит ли этот прием сократить затраты пространства до полиномиальной величины? Сначала тщательно сформулируем процедуру, а затем проанализируем ее. Для наших целей L будет считаться степенью 2.

Раth(Cj, C2, L)

Если L = 1

Если существует оператор O, преобразующий C1 в C2 Вернуть "да"

Иначе

Вернуть "нет"

Конец Если

Иначе (L> 1)

Перебрать все конфигурации C' с использованием «-разрядного счетчика Для каждого C' сделать следующее:

Вычислить X = Path(C1, C`, L/2)

Удалить все промежуточные результаты, сохранить только возвращаемое значение х Вычислить у = Path(C`,C2, L/2)

Удалить все промежуточные результаты, сохранить только

возвращаемое значение у Если X и у равны "да", вернуть "да"

Конец

Если ни для одного C не был получен результат "да"

Вернуть "нет"

Конец Если Конец Если

И снова обратите внимание на то, что эта процедура решает проблему обобще- ния исходного вопроса, относившегося к Path(C0, C*, 2n). Однако это означает, что L следует рассматривать как экспоненциально большой параметр: log L = n.

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

Еще по теме Более эффективный по затратам пространства способ построения путей:

  1. Как использовать тип для более эффективного консультирования
  2. Понятие коммуникации как методологический принцип построения гносеологической конструкции социокультурного пространства города
  3. СПОСОБЫ ПОСТРОЕНИЯ НАТАЛЬНОЙ КАРТЫ
  4. АВРАЛ КАК ЭФФЕКТИВНЫЙ СПОСОБ ОРГАНИЗАЦИИ РАБОТЫ
  5. ПСИХОЛОГИЧЕСКИЕ СПОСОБЫ ВОЗДЕЙСТВИЯ В ПРОЦЕССЕ ОБЩЕНИЯ. ПРИЕМЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОБЩЕНИЯ
  6. Сейчас наша популяция сократилась до такого уровня, что нам всё труднее обеспечивать защиту Западного Побережья, которую мы до сих пор предоставляли, в то время как в самом близком будущем вам потребуется гораздо более эффективная защита.
  7. Статья 947. Возмещение затрат на сохранение
  8. Статья 277. Повреждение путей сообщения и транспортных средств
  9. поиск путей утверждения в обществе правозаконности.
  10. Статья 801. Затраты, связанные с использованием транспортного средства
  11. 2. Договоры об эксплуатации подъездных путей и о подаче и уборке вагонов
  12. Способ мышления определяет способ взаимоотношений с окружающим миром.
  13. Статья 904. Возмещение исполнителю фактических затрат по договору о безвозмездном предоставлении услуг
  14. Статья 342. Возмещение затрат на содержание безнадзорного домашнего животного и выплата вознаграждения
  15. Статья 1024. Право комиссионера на возмещение затрат, сделанных им в связи с выполнением договора комиссии
  16. МОЧЕВЫВОДЯЩИХ ПУТЕЙ ИНФЕКЦИЯ См. статью УРЕТРИТ. МУРАШКИ ПО ТЕЛУ См. статью ОНЕМЕНИЕ.
  17. Статья 1232. Обязанность наследников возместить затраты на содержание, уход, лечение и погребение наследодателя