Проекты: Основные структуры данных и алгоритмы

Не забывайте использовать Git для фиксации изменений в ваших проектах!

Проект 1: Поиск в деревьях

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

Вы также узнали о таких алгоритмах поиска, как поиск-в-ширину (breadth-first-search, или BFS) и поиск-в-глубину (depth-first-search, или DFS). Первый из них больше подходит для поиска лучшего решения, но работает дольше (слишком долго для больших наборов данных), а второй часто выполняет поиск быстрее, но выдает ПЕРВОЕ решение, не обязательно лучшее. Здесь вам предстоит реализовать оба варианта.

Задания

Вы создадите простую структуру двоичного дерева из произвольных данных и функцию поиска данных внутри него.

1. Создайте класс Node. Он должен содержать value, которое он хранит, а также ссылки на родителей и потомков (при их наличии). Для них должны быть геттеры и сеттеры (например parent node, child node(s)).
2. Создайте метод build_tree, который принимает массив (например [1, 7, 4, 23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]) и создает из него двоичное дерево с соответственно расположенными узлами Node. Для начала, начните с отсортированного массива.
3. Проведите рефакторинг метода build_tree, чтобы обработать сложно сортируемые данные перед постройкой дерева. Необходимо будет выяснить, как добавить узел для каждого случая (например, если лист где-то посередине).
4. Чтобы протестировать правильность построения дерева, напишите простой скрипт, выполняющий build_tree.
5. Создайте метод breadth_first_search, который принимает искомое значение и возвращает содержащий его узел, используя принцип BFS. Подсказка: Используйте массив в виде очереди (queue) для отслеживания дочерних узлов, которые еще надо посетить и для добавления в него новых (как в этом видео). Если узел в итоге не найден, возвращается nil.
6. Создайте метод depth_first_search, который возвращает содержащий искомое значение узел, используя алгоритм DFS. Здесь используйте массив, работающий как stack.
7. Дополнительно, реализуйте метод dfs_rec, используя DFS, но вместо применения стека, сделайте его рекурсивным.

8. Подсказки:

   1. Представляйте метод dfs_rec как маленького робота, идущего вниз по дереву и проверяющего, та ли эта ветка, который запускает других роботов для поиска по дереву. Ни один робот не должен быть запущен, пока предыдущие не закончили поиск.
   2. Метод должен принимать два параметра - искомое значение и текущий узел.

Решения студентов

• Решение 1
• Решение 2
• Решение 3
• Решение 4
• Решение 5

Проект 2: Ход конем

Вы освоили DFS и BFS, давайте используем эти алгоритмы на реальной задаче.

Шахматный конь может попасть на любую клетку стандартной шахматной доски, стартовав с любой другой клетки, если ему дать достаточно ходов (не верите? Посмотрите). Фигура ходит на две клетки вперед и одну в сторону. Ход может быть в любом направлении.

Задания

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

Доску можно представить как поле, имеющее 2 измерения. Тогда функция может выглядеть так:

• knight_moves([0,0],[1,2]) # => [[0,0],[1,2]]
• knight_moves([0,0],[3,3]) # => [[0,0],[1,2],[3,3]]
• knight_moves([3,3],[0,0]) # => [[3,3],[1,2],[0,0]]

1. Сделайте скрипт, создающий игровое поле и коня.
2. Возможные ходы коня можно представить как дочерние узлы дерева. Не позволяйте коню выйти за пределы доски.
3. Решите, какой алгоритм поиска необходимо использовать для этой задачи. Подсказка: один из них может привести к бесконечным ходам.
4. Используйте выбранный алгоритм для поиска кратчайшего пути между стартовой клеткой (узлом) и финишной. Вывод на экран должен быть примерно таким:

    > knight_moves([3,3],[4,3])
    You made it in 3 moves! Here is your path:
    [3,3]
    [4,5]
    [2,4]
    [4,3]

Решения студентов

• Решение 1
• Решение 2
• Решение 3
• Решение 4
• Решение 5

Дополнительные ресурсы

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

• Обзор методик поиска от Coursera с уклоном в техническую сторону вопроса.