Поиск подстроки в тексте (строке). Алгоритм грубой силы

Метод грубой силы представляет собой прямой подход к решению

задачи, обычно основанный непосредственно на формулировке задачи и определениях используемых ею концепций.

Алгоритм, основанный на методе грубой силы, для решения общей задачи поиска называется последовательным поиском. Этот алгоритм просто по очереди сравнивает элементы заданного списка с ключом поиска до тех пор, пока не будет найден элемент с указанным значением ключа (успешный поиск) или весь список будет проверен, но требуемый элемент не найден (неудачный поиск). Зачастую применяется простой дополнительный прием: если добавить ключ поиска в конец списка, то поиск обязательно будет успешным, следовательно, можно убрать проверку завершения списка в каждой итерации алгоритма. Далее приведен псевдокод такой улучшенной версии; предполагается, что входные данные имеют вид массива.

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

Совершенно очевидно, что время работы этого алгоритма может отличаться в очень широких пределах для одного и того же списка размера п. В наихудшем случае, т.е. когда в списке нет искомого элемента либо когда искомый элемент расположен в списке последним, в алгоритме будет выполнено наибольшее количество операций сравнения ключа со всеми n элементами списка: C(n) = n.

1.2. Алгоритм Рабина.

Алгоритм Рабина представляет собой модификацию линейного алгоритма, он основан на весьма простой идее:

«Представим себе, что в слове A, длина которого равна m, мы ищем образец X длины n. Вырежем "окошечко" размером n и будем двигать его по входному слову. Нас интересует, не совпадает ли слово в "окошечке" с заданным образцом. Сравнивать по буквам долго. Вместо этого фиксируем некоторую числовую функцию на словах длины n, тогда задача сведется к сравнению чисел, что, несомненно, быстрее. Если значения этой функции на слове в "окошечке" и на образце различны, то совпадения нет. Только если значения одинаковы, необходимо проверять последовательно совпадение по буквам.»

Этот алгоритм выполняет линейный проход по строке (n шагов) и линейный проход по всему тексту (m шагов), стало быть, общее время работы есть O(n+m). При этом мы не учитываем временную сложность вычисления хеш-функции, так как, суть алгоритма в том и заключается, чтобы данная функция была настолько легко вычисляемой, что ее работа не влияла на общую работу алгоритма.

Алгоритм Рабина и алгоритм последовательного поиска являются алгоритмами с наименьшими трудозатратами, поэтому они годятся для использования при решении некоторого класса задач. Однако эти алгоритмы не являются наиболее оптимальными.

1.3. Алгоритм Кнута - Морриса - Пратта (кмп).

Метод КМП использует предобработку искомой строки, а именно: на ее основе создается префикс-функция. При этом используется следующая идея: если префикс (он же суффикс) строки длинной i длиннее одного символа, то он одновременно и префикс подстроки длинной i-1. Таким образом, мы проверяем префикс предыдущей подстроки, если же тот не подходит, то префикс ее префикса, и т.д. Действуя так, находим наибольший искомый префикс. Следующий вопрос, на который стоит ответить: почему время работы процедуры линейно, ведь в ней присутствует вложенный цикл? Ну, во-первых, присвоение префикс-функции происходит четко m раз, остальное время меняется переменная k. Стало быть, общее время работы программы есть O(n+m), т. е. линейное время.

Метод Грубой Силы

Полный перебор (или метод «грубой силы» от англ. brute force ) - метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений очень велико, то полный перебор может не дать результатов в течение нескольких лет или даже столетий.

Смотреть что такое "Метод Грубой Силы" в других словарях:

Полный перебор (или метод «грубой силы» от англ. brute force) метод решения задачи путем перебора всех возможных вариантов. Сложность полного перебора зависит от размерности пространства всех возможных решений задачи. Если пространство решений… … Википедия

Сортировка простыми обменами, сортировка пузырьком (англ. bubble sort) простой алгоритм сортировки. Для понимания и реализации этот алгоритм простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: O(n²). Алгоритм… … Википедия

У этого термина существуют и другие значения, см. Перебор. Полный перебор (или метод «грубой силы», англ. brute force) метод решения математических задач. Относится к классу методов поиска решения исчерпыванием всевозможных… … Википедия

Обложка первого издания брошюры «Документы Бейла…» Криптограммы Бейла три зашифрованных сообщения, как то полагается, несущих в себе информацию о местонахождении клада из золота, серебра и драгоценных камней, зарытого якобы на терр … Википедия

Snefru это криптографическая однонаправленная хеш функция, предложенная Ральфом Мерклом. (Само название Snefru, продолжая традиции блочных шифров Khufu и Khafre, также разработанных Ральфом Мерклом, представляет собой имя египетского… … Википедия

Попытка взлома (дешифрования) данных, зашифрованных блочным шифром. К блочным шифрам применимы все основные типы атак, однако существуют некоторые, специфичные лишь для блочных шифров, атаки. Содержание 1 Типы атак 1.1 Общие … Википедия

Нейрокриптография раздел криптографии, изучающий применение стохастических алгоритмов, в частности, нейронных сетей, для шифрования и криптоанализа. Содержание 1 Определение 2 Применение … Википедия

Оптимальный маршрут коммивояжёра через 15 крупнейших городов Германии. Указанный маршрут является самым коротким из всех возможных 43 589 145 600. Задача коммивояжёра (англ. Travelling salesman problem, TSP) (коммивояжёр … Википедия

Криптографическая хеш функция Название N Hash Создан 1990 Опубликован 1990 Размер хеша 128 бит Число раундов 12 или 15 Тип хеш функция N Hash криптографическая … Википедия

Задача коммивояжёра (коммивояжёр бродячий торговец) является одной из самых известных задач комбинаторной оптимизации. Задача заключается в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с… … Википедия

и следующую функцию: function show(pos, path, w, h) { var canvas = document.getElementById("canID"); // получаем объект канваса var ctx = canvas.getContext("2d"); // у него есть свойство - контекст рисования var x0 = 10, y0 = 10; // положение левого верхнего угла карты canvas.width = w+2*x0; canvas.height = h+2*y0; // меняем размеры канваса (чуть больше, чем w x h) ctx.beginPath(); // начало рисования ломаной линии ctx.moveTo(x0+pos.x,y0+pos.y)// переходим на 0-й город for(var i=1; i Пример результата вызова функции приведен справа. Смысл команд рисования должен быть ясен из их названия и комментариев в коде. Сначала рисуется замкнутая ломаная линия (путь коммивояжёра). Затем - окружности городов и поверх них - номера городов. Работа с канавасом в JavaScript несколько громоздка и в дальнейшем мы будем использовать класс draw , который эту работу упрощает и одновременно позволяет получать картинки в svg-формате.

Перебор в таймере

Реализация переборного алгоритма поиска кратчайшего пути в таймере не представляет труда. Для сохранения лучшего пути в массиве minWay , напишем функцию копирования значений элементов массива src в массив des :

Function copy(des, src) { if(des.length !== src.length) des = new Array(src.length); for(var i=0; i

У меня есть математическая проблема, которую я решаю методом проб и ошибок (я думаю, это называется грубой силой), и программа отлично работает, когда есть несколько параметров, но по мере добавления дополнительных переменных/данных требуется больше времени и дольше для запуска.

Моя проблема заключается в том, что, хотя прототип работает, он полезен для тысяч переменных и больших наборов данных; поэтому, мне интересно, можно ли масштабировать алгоритмы грубой силы. Как я могу подойти к его масштабированию?

3 ответа

Как правило, вы можете количественно оценить, насколько хорошо алгоритм будет масштабироваться, используя нотацию большого вывода для анализа ее темпа роста. Когда вы говорите, что ваш алгоритм работает под "грубой силой", он неясно, в какой степени он будет масштабироваться. Если ваше решение "грубой силы" работает, перечисляя все возможные подмножества или комбинации набора данных, то оно почти наверняка не будет масштабироваться (оно будет иметь асимптотическую сложность O (2 n) или O (n!), соответственно). Если ваше решение для грубой силы работает, найдя все пары элементов и проверив их, оно может масштабироваться достаточно хорошо (O (n 2)). Однако, без дополнительной информации о том, как работает ваш алгоритм, это трудно сказать.

По определению алгоритмы грубой силы глупы. Вам будет намного лучше с более умным алгоритмом (если он у вас есть). Лучший алгоритм уменьшит работу, которая должна быть выполнена, надеюсь, в той степени, в которой вы можете это сделать, не требуя "масштабирования" на нескольких машинах.

Независимо от алгоритма, наступает момент, когда требуемое количество данных или вычислительная мощность настолько велики, что вам нужно использовать что-то вроде Hadoop. Но, как правило, мы действительно говорим о больших данных здесь. В наши дни вы уже можете много сделать с одним ПК.

Алгоритм решения этой проблемы закрыт для процесса, который мы изучаем для ручного математического деления, а также для преобразования из десятичной в другую базу, например восьмеричную или шестнадцатеричную, за исключением того, что в двух примерах рассматривается только одно каноническое решение.

Чтобы убедиться, что рекурсия завершена, важно заказать массив данных. Чтобы быть эффективными и ограничивать количество рекурсий, важно также начать с более высоких значений данных.

Конкретно, здесь рекурсивная реализация Java для этой проблемы - с копией вектора результата coeff для каждой рекурсии, как ожидалось в теории.

Import java.util.Arrays; public class Solver { public static void main(String args) { int target_sum = 100; // pre-requisite: sorted values !! int data = new int { 5, 10, 20, 25, 40, 50 }; // result vector, init to 0 int coeff = new int; Arrays.fill(coeff, 0); partialSum(data.length - 1, target_sum, coeff, data); } private static void printResult(int coeff, int data) { for (int i = coeff.length - 1; i >= 0; i--) { if (coeff[i] > 0) { System.out.print(data[i] + " * " + coeff[i] + " "); } } System.out.println(); } private static void partialSum(int k, int sum, int coeff, int data) { int x_k = data[k]; for (int c = sum / x_k; c >= 0; c--) { coeff[k] = c; if (c * x_k == sum) { printResult(coeff, data); continue; } else if (k > 0) { // contextual result in parameters, local to method scope int newcoeff = Arrays.copyOf(coeff, coeff.length); partialSum(k - 1, sum - c * x_k, newcoeff, data); // for loop on "c" goes on with previous coeff content } } } }

Но теперь этот код находится в специальном случае: последний тест значения для каждого коэффициента равен 0, поэтому копия не нужна.

В качестве оценки сложности мы можем использовать максимальную глубину рекурсивных вызовов как data.length * min({ data }) . Конечно, он не будет хорошо масштабироваться, а ограниченным фактором будет память трассировки стека (опция -Xss JVM). Код может выйти из строя с ошибкой для большого набора data .

Чтобы избежать этих недостатков, процесс "прекращения" полезен. Он заключается в замене стека вызовов метода на программный стек для хранения контекста выполнения для последующей обработки. Вот код для этого:

Import java.util.Arrays; import java.util.ArrayDeque; import java.util.Queue; public class NonRecursive { // pre-requisite: sorted values !! private static final int data = new int { 5, 10, 20, 25, 40, 50 }; // Context to store intermediate computation or a solution static class Context { int k; int sum; int coeff; Context(int k, int sum, int coeff) { this.k = k; this.sum = sum; this.coeff = coeff; } } private static void printResult(int coeff) { for (int i = coeff.length - 1; i >= 0; i--) { if (coeff[i] > 0) { System.out.print(data[i] + " * " + coeff[i] + " "); } } System.out.println(); } public static void main(String args) { int target_sum = 100; // result vector, init to 0 int coeff = new int; Arrays.fill(coeff, 0); // queue with contexts to process Queue contexts = new ArrayDeque(); // initial context contexts.add(new Context(data.length - 1, target_sum, coeff)); while(!contexts.isEmpty()) { Context current = contexts.poll(); int x_k = data; for (int c = current.sum / x_k; c >= 0; c--) { current.coeff = c; int newcoeff = Arrays.copyOf(current.coeff, current.coeff.length); if (c * x_k == current.sum) { printResult(newcoeff); continue; } else if (current.k > 0) { contexts.add(new Context(current.k - 1, current.sum - c * x_k, newcoeff)); } } } } }

С моей точки зрения, трудно быть более эффективным в одном выполнении потока - механизм стека теперь требует копий массива coeff.