Проекты: Основные структуры данных и алгоритмы
Не забывайте использовать Git для фиксации изменений в ваших проектах!
Проект 1: Поиск в деревьях
Вы узнали о Двоичных деревьях поиска -- где берется группа данных и выстраивается дерево с узлами, в котором каждый левый узел "ниже" каждого правого. Дерево начинается с "корневого узла", а любой узел без потомков называется "листовым узлом".
Вы также узнали о таких алгоритмах поиска, как поиск-в-ширину (breadth-first-search, или BFS) и поиск-в-глубину (depth-first-search, или DFS). Первый из них больше подходит для поиска лучшего решения, но работает дольше (слишком долго для больших наборов данных), а второй часто выполняет поиск быстрее, но выдает ПЕРВОЕ решение, не обязательно лучшее. Здесь вам предстоит реализовать оба варианта.
Задания
Вы создадите простую структуру двоичного дерева из произвольных данных и функцию поиска данных внутри него.
- Создайте класс
Node
. Он должен содержатьvalue
, которое он хранит, а также ссылки на родителей и потомков (при их наличии). Для них должны быть геттеры и сеттеры (напримерparent node
,child node
(s)). - Создайте метод
build_tree
, который принимает массив (например [1, 7, 4, 23, 8, 9, 4, 3, 5, 7, 9, 67, 6345, 324]) и создает из него двоичное дерево с соответственно расположенными узламиNode
. Для начала, начните с отсортированного массива. - Проведите рефакторинг метода
build_tree
, чтобы обработать сложно сортируемые данные перед постройкой дерева. Необходимо будет выяснить, как добавить узел для каждого случая (например, если лист где-то посередине). - Чтобы протестировать правильность построения дерева, напишите простой скрипт, выполняющий
build_tree
. - Создайте метод
breadth_first_search
, который принимает искомое значение и возвращает содержащий его узел, используя принцип BFS. Подсказка: Используйте массив в виде очереди (queue) для отслеживания дочерних узлов, которые еще надо посетить и для добавления в него новых (как в этом видео). Если узел в итоге не найден, возвращаетсяnil
. - Создайте метод
depth_first_search
, который возвращает содержащий искомое значение узел, используя алгоритм DFS. Здесь используйте массив, работающий как stack. - Дополнительно, реализуйте метод
dfs_rec
, используя DFS, но вместо применения стека, сделайте его рекурсивным. Подсказки:
- Представляйте метод
dfs_rec
как маленького робота, идущего вниз по дереву и проверяющего, та ли эта ветка, который запускает других роботов для поиска по дереву. Ни один робот не должен быть запущен, пока предыдущие не закончили поиск. - Метод должен принимать два параметра - искомое значение и текущий узел.
- Представляйте метод
Решения студентов
Проект 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]]
- Сделайте скрипт, создающий игровое поле и коня.
- Возможные ходы коня можно представить как дочерние узлы дерева. Не позволяйте коню выйти за пределы доски.
- Решите, какой алгоритм поиска необходимо использовать для этой задачи. Подсказка: один из них может привести к бесконечным ходам.
- Используйте выбранный алгоритм для поиска кратчайшего пути между стартовой клеткой (узлом) и финишной. Вывод на экран должен быть примерно таким:
> knight_moves([3,3],[4,3])
You made it in 3 moves! Here is your path:
[3,3]
[4,5]
[2,4]
[4,3]
Решения студентов
Дополнительные ресурсы
Этот раздел содержит полезные ссылки на дополнительные материалы. Они не обязательны, так что расценивайте их как нечто полезное, если вы хотите поглубже погрузиться в тему
- Обзор методик поиска от Coursera с уклоном в техническую сторону вопроса.