Comments 8
А причем здесь хаб "Расширения для браузеров"?
Решение задачи выглядит как обычный рекурсивный поиск.
Из описания "Prune and search" (копия статьи из вики?) так и не понял как перешли к рекурсивному поиску. Где там отбрасывание работы с постоянным коэффициентом?
Данная статья является переводом статьи из Википедии, целью написания статьи послужило отсутствие известного термина в английском языке на русском языке, чтобы любой, кто столкнется с таким термином, мог загуглить его и посмотреть, что он означает: в переводе математического определения и более простом пояснении (статья уже выдается в поисковиках).
В математическом определении отбрасывание части данных (n(1-p)) происходит на каждом шаге, что приводит к рекурсивной природе алгоритма. Рекурсивный поиск охватывает только те варианты, которые приводят к нужному результату.
И, понимая эту концепцию, мы можем применить ее на данной задаче - на каждом шаге мы отсекаем варианты, которые не приводят нас к желаемому результату.
Мне кажется любое условие IF, подразумевающее какую-то аналитику, всегда работает таким образом, не ясно только зачем для этого термин.
По русски этот метод, кажется, называется метод "ветвей и границ". Но у вас не он. У вас обычный рекурсивный перебор с минимальными отсечениями. Откуда у вас там "отсечение на постоянный коэффициент"?
Большой объем данных- это матрица с буквами
Нет, матрица - это не большой объем данных. Вот количество путей в матрице заданной длины - вот это большой объем данных.
Так-то, по вашему тексту создается ощущение, что у вас линейный алгоритм. Однако на тесте с шахматной доской ("A" и "B" вместо черных и белых клеток) и искомой строки длиной n*m вида "ABAB..ABAC" - ваш код переберет половину всех возможных путей в матрице и займет вечность, даже для матрицы 6x6. Правда, по условию задачи такой тест не впихнуть: там максимум 15 символов для строки. Но все-равно, сложность будет порядка O(n*m*2^L), Где L - длина искомой строки.
Не поймите неправильно, ваше решение - действительно правильное для этой задачи, но это простейший рекурсивный перебор. Натягивать сюда какие-то методы, да еще и ссылки на статьи давать - это сова на глобусе.
Я читал про метод ветвей и границ, когда писал статью, стараясь найти аналогичные определения в русском языке, но, как вы отметили, это не тот же метод.
Вы правы, что в данной реализации отсутствует явное отсечение постоянного коэффициента, но это объясняется особенностями задачи поиска слова в матрице: здесь мы не применяем метод "Отсечение и поиск" в полном объеме, мы используем основную идею - рекурсивный подход, основанный на пошаговом "отсечении" неподходящих вариантов.
Что касается большого объема данных, благодарю за уточнение.
Утверждение о линейности алгоритма дается в математическом определении, которое является переводом оригинальной статьи. Касаемо решаемой задачи оценка сложности не производилась.
"Натягиваю" не я, а англоязычное сообщество, я лишь хочу, чтобы у русскоязычного сообщества было хотя бы базовое понимание того, почему в контексте данной задачи на LeetCode используется этот термин.
Если в статье есть еще какие-то ошибки, то, пожалуйста, дайте знать, я поправлю. Спасибо!
Это ни в коем случае не метод ветвей и границ. Метод ветвей и границ предполагает существование верхней и нижней оценок для ветвей перебора. А этот алгоритм на русском языке называется «перебор с возвращением».
Приведена грамотная реализация алгоритма, в олимпиадных задачах я всегда программирую именно так. Единственно, необходимо убедиться, что i, j и k передаются в функцию search по значению, а board, word и visited – по ссылке.
Впрочем, board, word, visited, m, n и длину слова лучше вообще не передавать, а сделать членами класса. Если же программа пишется на языке без классов, например, на чистом C, то вместо слова, его длины и текущей позиции можно передавать указатель на текущий символ, памятуя, что признаком конца слова в C является ‘\0’-символ.
Отсечение и поиск / Prune and search