Skip to content

Latest commit

 

History

History

practice_2.2

Folders and files

NameName
Last commit message
Last commit date

parent directory

..
README.md
README.md
 
 
test_maze.py
test_maze.py
 
 

README.md

Практическая работа №7 "Лабиринты"

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

Предусмотреть:

  1. Интерфейс командной строки (CLI) или графический интерфейс
  2. Возможность указывать размеры лабиринта (изображения)
  3. Генерацию лабиринта и сохранение его в виде изображения jpg, png (выходной файл указывает пользователь)
  4. Сохранение лабиринта в виде любого текстового формата
  5. Загрузку лабиринта из текстового файла
  6. Загрузку лабиринта из изображения
  7. Решение лабиринта
  8. Вывод пути от начальной до конечной точек
  9. Покрыть тестами генерацию и решение лабиринта
  10. *Генерация гифки построения и решения лабиринта

Алгоритмы:

Генерация

  1. Алгоритм Эйлера
  2. Алгоритм Краскала
  3. Алгоритм двоичного дерева
  4. Алгоритм Прима
  5. Алгоритм «Sidewinder»
  6. Рекурсивный алгоритм сегментации

Решение

  1. А*
  2. Best-first search
  3. Jump Point Search
  4. Поиск в глубину (DFS, Depth-first search)
  5. Алгоритм Дейкстры
  6. Алгоритм Левита
  7. Поиск в ширину (BFS, Breadth-first search)
  8. Алгоритм Ли (Волновой алгоритм)

Требования к реализации

Реализуйте модуль maze.py с функциями генерации и решения лабиринта.

Функция генерации должна принимать размеры лабиринта, а также дополнительные параметры алгоритма (по необходимости) и возвращать лабиринт в любом удобном представлении, например в виде двумерного массива или графа.

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

Остальной функционал (чтение, запись в файл, генерация изображения и другие) должен располагаться в соответствующих функциях.

Методика оценивания

Оценка выставляется в соответствии со следующими требованиями:

  1. Общие требования:
    • код работы проходит проверку утилитой pylint с конфигурационным файлом .pylintrc.
    • код работы успешно проходит тесты, если таковые имеются.
    • наличие документации к функциям, методам, классам и модулям.
  2. На оценку 3 балла реализовать:
    • все вышеперечисленное;
    • пункты 1, 2, 3, 7 и 8.
  3. На оценку 4 балла дополнительно реализовать:
    • все вышеперечисленное;
    • пункты 4 и 5;
  4. На оценку 5 балла:
    • реализовать все требования, указанные в описании к работе, кроме 10.
  5. Плюс в карму:
    • все вышеперечисленное;
    • пункт 10;

Полезные материалы