Более эффективный по затратам пространства способ построения путей
Ключевая роль в этом алгоритме отводится процедуре, которую мы назовем Ра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.
Еще по теме Более эффективный по затратам пространства способ построения путей:
- Как использовать тип для более эффективного консультирования
- Понятие коммуникации как методологический принцип построения гносеологической конструкции социокультурного пространства города
- СПОСОБЫ ПОСТРОЕНИЯ НАТАЛЬНОЙ КАРТЫ
- АВРАЛ КАК ЭФФЕКТИВНЫЙ СПОСОБ ОРГАНИЗАЦИИ РАБОТЫ
- ПСИХОЛОГИЧЕСКИЕ СПОСОБЫ ВОЗДЕЙСТВИЯ В ПРОЦЕССЕ ОБЩЕНИЯ. ПРИЕМЫ ПОВЫШЕНИЯ ЭФФЕКТИВНОСТИ ОБЩЕНИЯ
- Сейчас наша популяция сократилась до такого уровня, что нам всё труднее обеспечивать защиту Западного Побережья, которую мы до сих пор предоставляли, в то время как в самом близком будущем вам потребуется гораздо более эффективная защита.
- Статья 947. Возмещение затрат на сохранение
- Статья 277. Повреждение путей сообщения и транспортных средств
- поиск путей утверждения в обществе правозаконности.
- Статья 801. Затраты, связанные с использованием транспортного средства
- 2. Договоры об эксплуатации подъездных путей и о подаче и уборке вагонов
- Способ мышления определяет способ взаимоотношений с окружающим миром.
- Статья 904. Возмещение исполнителю фактических затрат по договору о безвозмездном предоставлении услуг
- Статья 342. Возмещение затрат на содержание безнадзорного домашнего животного и выплата вознаграждения
- Статья 1024. Право комиссионера на возмещение затрат, сделанных им в связи с выполнением договора комиссии
- МОЧЕВЫВОДЯЩИХ ПУТЕЙ ИНФЕКЦИЯ См. статью УРЕТРИТ. МУРАШКИ ПО ТЕЛУ См. статью ОНЕМЕНИЕ.
- Статья 1232. Обязанность наследников возместить затраты на содержание, уход, лечение и погребение наследодателя