Каково различие между отслеживанием в обратном порядке и поиском в глубину?
Два трюка . В основном, инвертирование HTML-кода ваших желаемых элементов в HTML и использование ~ Оператора следующего сиблинга :
float-right + инвертирует порядок HTML элементы
div{ /* Do with the parent whatever you know just to make the
inner float-right elements appear where desired */
display:inline-block;
}
span{
float:right; /* float-right the elements! */
}
span:hover ~ span{ /* On hover target it's "previous";) elements */
background:red;
} <div>
<!-- Reverse the order of inner elements -->
<span>5</span>
<span>4</span>
<span>3</span>
<span>2</span>
<span>1</span>
</div> Родитель с direction: rtl; + инвертирует порядок внутренних элементов
.inverse{
direction: rtl;
display: inline-block; /* inline-block to keep parent at the left of window */
}
span:hover ~ span{ /* On hover target it's "previous";) elements */
background:gold;
}Hover one span and see the previous elements being targeted!<br>
<div class="inverse">
<!-- Reverse the order of inner elements -->
<span>5</span>
<span>4</span>
<span>3</span>
<span>2</span>
<span>1</span>
</div>5 ответов
Обратное отслеживание - это алгоритм более общего назначения.
Поиск в глубину особая форма возврата, связанная с поиском древовидных структур. Из Википедии:
Один начинается с корня (выбирая какой-то узел в качестве корня в случае графа) и исследует, насколько это возможно, вдоль каждой ветви перед отслеживанием с возвратом.
Он использует отслеживание с возвратом как часть своего средства работы с tree, но ограничивается древовидной структурой.
Обратное отслеживание, тем не менее, может использоваться для любого типа структуры, в которой части домена могут быть удалены - независимо от того, является ли это логическим деревом или нет. В примере Wiki используется шахматная доска и конкретная проблема - вы можете посмотреть на конкретный ход и исключить его, затем вернуться к следующему возможному ходу, исключить его и т. Д.
По моему скромному мнению, большинство ответов любой в основном неточно и/или без любой ссылки для проверки. Таким образом позвольте мне совместно использовать очень четкое объяснение со ссылкой .
Первый, DFS является общим обходом графика (и поиск) алгоритм. Таким образом, это может быть применено к любому графику (или даже лес). Дерево является специальным видом Графика, таким образом, работы DFS для дерева также. В сущности let’s прекращают говорить, что это работает только на дерево или подобные.
На основе [1], Отслеживание в обратном порядке является специальным видом DFS, используемого главным образом для пространства (память) сохранение. Различие, что I’m, собирающийся упоминание, может казаться сбивающим с толку с тех пор в алгоритмах Графика такого вида we’re так привыкший к наличию представлений в виде списка смежности и использованию повторяющегося шаблона для посещения всех ближайших соседей ( для дерева это - непосредственные дети ) узла, мы часто игнорируем, что плохая реализация get_all_immediate_neighbors может вызвать различие в использовании памяти базового алгоритма.
Далее, если узел графика имеет коэффициент ветвления b и диаметр h ( для дерева это - древовидная высота ), если мы храним всех ближайших соседей в каждом шаги посещения узла, требования к памяти будут большие-O (bh) . Однако, если мы берем только единственного (непосредственного) соседа за один раз и разворачиваем его, затем сложность памяти уменьшает до большой-O (h) . , В то время как бывший вид реализации называют как [1 114] DFS, последний вид называют Отслеживание в обратном порядке .
Теперь Вы видите, если you’re, работающий с высокоуровневыми языками, наиболее вероятный you’re на самом деле с помощью Отслеживающий в обратном порядке под маской DFS. Однако это может иметь большое значение, если you’re, работающий с низкоуровневым языком, какие doesn’t поддерживают вид шаблона итератора семантики для get_all_immediate_neighbors.
[1] Stuart Russell и Peter Norvig, Искусственный интеллект: современный Подход, 3-й Ed
Обычно поиск в глубину - это способ повторения фактическая структура графа / дерева ищет значение, тогда как возврат с возвратом - это итерация через проблемное пространство в поисках решения. Отслеживание с возвратом - это более общий алгоритм, который не обязательно относится даже к деревьям.
В поиске в глубину вы начинаете с корня дерева, а затем исследуете его вдоль каждой ветви, затем вы возвращаетесь к каждый последующий родительский узел и обход его потомков
Отслеживание с возвратом - это обобщенный термин, обозначающий начало в конце цели и постепенное движение назад, постепенно выстраивая решение.
Сначала глубина - это алгоритм для обхода или поиска дерево. См. здесь . Отслеживание с возвратом - это гораздо более широкий термин, который используется всякий раз, когда формируется кандидат на решение, а затем отбрасывается путем возврата к предыдущему состоянию. См. здесь . Поиск в глубину использует обратное отслеживание для поиска сначала ветви (кандидата решения), а в случае неудачи - поиска другой ветви (ов).