четверг, 25 апреля 2013 г.

Алгоритм Бойера - Мура


Алгоритм поиска строки Бойера — Мура считается наиболее быстрым среди алгоритмов общего назначения, предназначенных для поиска подстроки в строке. Был разработан Робертом Бойером и Джеем Муром в 1977 году. Преимущество этого алгоритма в том, что ценой некоторого количества предварительных вычислений над шаблоном (но не над строкой, в которой ведётся поиск) шаблон сравнивается с исходным текстом не во всех позициях — часть проверок пропускаются как заведомо не дающие результата.

Задача о путешествии шахматного коня



Задача о ходе коня — задача о нахождении маршрута шахматного коня, проходящего через все поля доски по одному разу.
Эта задача известна по крайней мере с XVIII века. Леонард Эйлер посвятил ей большую работу «Решение одного любопытного вопроса, который, кажется, не подчиняется никакому исследованию» (датируется 26 апреля 1757 года).


пятница, 19 апреля 2013 г.

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



Алгоритм был разработан Кнутом (Knuth) и Праттом (Pratt) и независимо от них Моррисом (Morris) в 1977 г.

Он относится к "правильным" подходам решения поставленной задачи, в отличии от тривиального подхода, рассмотренного ранее.

Данный подход хоть и считается достаточно тривиальным, описания, которые нашел я, зачастую пестрят математическими основами и доказательствами, которые сбивают с сути. Так в книге, уважаемого Никлауса Вирта, приводится описание, которое я так и не одолел.
Однако я нашел пару статей, которые достаточно информативны, они приведены в ссылках и рекомендуемы для ознакомления.

четверг, 18 апреля 2013 г.

Поиск первого вхождение подстроки. Решение в лоб.




Поиск информации — одно из основных использований компьютера. Одна из простейших задач поиска информации — поиск точно заданной подстроки в строке. Тем не менее, эта задача чрезвычайно важна — она применяется в текстовых редакторах, СУБД, поисковых машинах…

вторник, 12 февраля 2013 г.

Линейный поиск

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

Данный алгоритм приведен здесь, для полноты изложения. Он мало где используется, только если в собственных проектах, которые не накладывают серьезных требований к производительности системы.

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

def linearSearch(li, x):
    i = 0
    length = len(li)
    while i<length and x<> li[i]:
        i+=1
    return i if i<length else None

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


def linearSearchVirt(li, x):
    i = 0
    length = len(li)-1
    while x x<> li[i]:
        i+=1
    return i if i<length else None

Вот и весь линейный поиск!)
Но есть более интересный метод -  двоичный поиск, милости просим к изучению.