Наивное решение проблемы N-королев

Вчера была интересная задача и я надеюсь, она многим понравилась! Однако пора приступить к способам ее решения. Начну я с самого простого способа (по факту перебора). Скорее всего вы этим способом и пользовались при выставлении королев(ферзей) на доске.

Итак:

1. Создать цикл с проверкой того, что есть непроверенные конфигурации
2. Внутри цикла генерировать новую конфигурацию и если королевы не атакуют, тогда распечатать эту конфигурацию.


Проблема данного подхода, я думаю, очевидна! Это глупый и наивный перебор абсолютно всех вариантов и он займет недопустимое количество времени.

А вот хорошее решение, я сегодня уже подскажу, но расскажу о нем завтра. Есть такой подход как BackTracking - попробуйте посмотреть в его направлении.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Backtracking алгоритм (Поиск с возвратом)

Один из самых известных алгоритмов по решению специфичных задач поиска - является Backtracking алгоритм. Это по факту даже техника для рекурсивного решения проблем, пытаясь построить решение постепенно, удаляя те решения, которые не удовлетворяют условиям.

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

Обратите внимание на картинку - там представлен способ решения нашей задачи N-Queens. Картинка очень удобна для понимания самого подхода и поможет вам уже воспроизвести алгоритм (рекурсивный) самостоятельно!

Data Science: Алгоритмы и Структуры данных | Чат 💬

Очень простое объяснение сложности алгоритмов

Иногда я нахожу на просторах интернета очень неплохие статьи, которыми могу поделиться. Сегодня одна из таких, которая позволит вам на базовом уровне разобраться что же такое сложность алгоритмов:

https://thatcomputerscientist.com/big-o-notation-explained-as-easily-as-possible

Для более глубокого изучения данного вопроса я порекомендую курс Роберта Седжевика:

https://www.coursera.org/learn/analysis-of-algorithms

Он максимально позволит вам овладеть данной темой.

Data Science: Алгоритмы и Структуры данных | Чат 💬

XOR Linked List

Начнем рассматривать сложные структуры данных. Сегодня начнем одной из таких: XOR связный список.

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

В связанном списке XOR вместо хранения фактических адресов памяти каждый узел хранит XOR адресов предыдущего и следующего узлов.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Продолжение обсуждения про XOR Linked List

Итак, я предлагаю перед тем как продолжать более детально смотреть на определенные примеры и задачи по данной теме. Всё таки немного глубже посмотреть на данную структуру.

Я нашел идеальную статью по этой теме:

https://www.linuxjournal.com/article/6828?page=0,0

Не обращайте внимание на дату создания. Ибо этот топик актуален до сих пор. Ну и плюсом будет в принципе глянуть на Linux Journal: там публиковалось очень много интересных топиков в свое время.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Обход связного XOR списка

Продолжаем тему XOR Linked List и сегодня поговорим про обходы данного листа.

Перемещаться по списку XOR мы можем как в прямом, так и в обратном направлении. Просматривая список, нам нужно запоминать адреса узла, к которому ранее осуществлялся доступ, чтобы вычислить адрес следующего узла.

Например когда мы находимся в узле С, у нас должен быть адрес B. Из XOR мы выщемляем адрес для C, а при помощи C (и функции npx) мы можем узнать адрес следующей ноды.

Завтра посмотрим на SourceCode для полного понимания данного процесса.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Код вставки элемента в XOR Linked List

Data Science: Алгоритмы и Структуры данных | Чат 💬

Структура данных - Префиксное(нагруженное) дерево - Trie

Сегодня (и последующие несколько дней) разберем еще одну продвинутую структуру данных: Trie

Префиксное дерево (Trie) - эффективная структура данных для поиска информации. Используя Trie, сложность поиска у вас сведется к длине ключа, что является оптимальным пределом.

Используя Trie - вы можете икать и вставлять ключ за О(M): где M максимальная длина строки. Однако будет штраф за то как это хранится.

Еще плюсом Trie будет являеться то, что вы легко сможете вывести все слова в алфавитном порядке

А также поможет вам эффективно решать задачи по поиску префикса(суффикса). Задачу подобную я скоро опубликую: она как раз была недавно в leetcode challenge

Data Science: Алгоритмы и Структуры данных | Чат 💬

Описание операции вставки в Trie

Каждый узел в Trie состоит из нескольких ветвей. Каждая ветвь представляет собой возможный символ-ключ. Интересно то, что последний узел каждого поддерева Trit - будет являться концом слова.

Простая структура Node выглядит примерно так:

1. Инициализация детей
2. флаг о конце слова

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

Data Science: Алгоритмы и Структуры данных | Чат 💬

Реализация вставки в Trie (Python)

Data Science: Алгоритмы и Структуры данных | Чат 💬

Расширяющее (косое) дерево - Splay Tree

Основная идея Splay Tree состоит в том, чтобы перенести элемент, к которому недавно осуществлен поиск(или доступ) в корень дерева. Тем самым дать возможность достучаться к нему повторно за O(1).

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

Все операции с Splay Tree выполняются в среднем за O(log N) времени, где N - количество записей в дереве.

В ближайшие дни рассмотрим основные операции над данным деревом.

Data Science: Алгоритмы и Структуры данных | Чат 💬

Операция поиска в Splay Tree

Операция поиска в Splay Tree выполняет стандартный поиск BST, помимо поиска, также происходит и перемещение узла в корень.

Если поиск успешный, то найденный узел перемещается и становится корневым. В противном случае последний узел, к которому было обращение (до достижения NULL) - перемещается в корень.

Доступ к узлу

1. Через корень
2. Узел является дочерним по отношению к корню, либо левым потомком (применим правое вращение), либо правм потомком
3. Другие 2, которые расмотрим в будущем

Data Science: Алгоритмы и Структуры данных | Чат 💬

Jump Search

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

Рассмотрим массив - 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, длина - 16. Размер блока возьмем - 4. Jump Search найдет значение 55 с помощью следующих шагов:

1. Переход от индекса 0 к индексу 4
2. Переход с индекса 4 к индеку 8
3. Перейсти с индекса 8 к индексу 12
4. Поскольку элемент с индексом 12 больше 55, мы вернемся на шаг назад. Переходим на индекс 8
5. Выполняем линейный поиск с индекса 8, чтобы получить элемент 55

Data Science: Алгоритмы и Структуры данных | Чат 💬

Оптимально выбрать блок для пропуска в Jump Search

В худшем случае мы должны делать n/m перехов. Где n - длина массива, а m - длина размера перехода. Если проверенное значение больше, чем искомый элемент, мы выполним m-1 сравнений больше, так как будем использовать линейный поиск.

Общее количество сравнений в наихудшем случае будет ((n / m) + m - 1). Значение функции ((n / m) + m - 1) будет минимальным, когда m = √n. Следовательно, лучший размер шага будет являться m = √n

Data Science: Алгоритмы и Структуры данных | Чат 💬