Алгоритм X Dancing Links сборки пентамимо на C#

Name: Алгоритм X Dancing Links сборки пентамимо на C#
Rating: 4.6 (12 reviews)

Теоретическое и практическое знакомство с гениальным "Алгоритмом икс" Дональда Кнута с примерами

Created byЕвгений Волосатов

Last updated 11/2018

Russian

What you'll learn

Поймут суть алгоритма X для быстрого поиска решений
Решат задачу расстановки пентамимо с использованием алгоритма Dancing Links

Course content

3 sections • 14 lectures • 4h 7m total length

Что такое Dancing Links8:35
В этой серии уроков мы познакомимся с гениальным "алгоритмом X" Дональда Кнута — Dancing Links.
Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, разложение Пентамимо, решение Судоку, размещение ферзей и так далее. Ссылки на статью Дональда Кнута и обзорная статья на Хабре с описанием данного алгоритма — внизу описания урока.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Подходит ли данный алгоритм для решения задачи Судоку или Парад Ферзей.
Приложить интересную картинку на тему урока.
Работа алгоритма12:43
На этом уроке мы пошагово рассмотрим статью на Хабре (см. ссылки ниже).
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Напишите своё мнение по поводу данного урока.
Самостоятельно рассмотреть варианты поиска решения.
Приложить скриншот проработанного алгоритма.
Двусвязный список с удалением10:46
На этом уроке мы пошагово рассмотрим статью автора данного алгоритма — Дональда Кнута, и рассмотрим пошаговое удаление и возвращение элемента.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Нарисовать циклический список из 4 элементов ABCD.
Проработать весь алгоритм самостоятельно.
Приложить скриншот проработанного алгоритма.
* Продемонстрировать удаление/восстановление всех элементов.

Расширение хоровода24:08
На этом уроке мы наконец приступим к реализации двусвязного списка на языке C#.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Создать новый проект AlgorithmX.
Создать новый класс Cell().
Добавить необходимые переменные и конструктор в классе Cell().
Избавиться от статика в классе Program().
Реализовать функцию test() в классе Program().
Реализовать функцию InsertLeft() в классе Cell().
Доработать конструктор в классе Cell().
Доработать функцию test() в классе Program(), использовав InsertLeft().
Приложить скриншот результата.
Заголовки столбцов12:17
На этом уроке мы реализуем перемещение вверх/вниз для реализации четырёх-связного списка, а также создадим класс Header(), для того чтобы знать, в каком столбце мы находимся.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Добавить новые переменные в классе Cell().
Доработать в конструктор класса Cell() начальные значение новых переменных.
Реализовать функцию InsertUp() в классе Cell().
Создать класс Header() с необходимыми переменными.
Заменить переменную name на header в классе Cell().
Добавить конструктор в классе Header().
Доработать функцию test() в классе Program(), использовав InsertUp() и Header().
Приложить скриншот результата.
Единичная матрица25:01
На этом уроке, используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Создать класс Dance() с необходимыми переменными.
Добавить конструктор в классе Dance().
Модифицировать тип переменной name в классе Header().
Реализовать функцию AddRow() в классе Dance().
Реализовать функцию start() в классе Program(), использовав класс Dance().
Приложить скриншот результата.
* Добавить все 12 строчек по образцу.
Как ссылки пошли впляс21:15
На этом уроке мы реализуем заготовку функции Dance() в классе Dance().
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Добавить все 12 строчек в матрицу.
Реализовать функцию Dance() в классе Dance().
Создать заглушки для функций Cover/Uncover().
Добавить вывод текущего шага в функции Dance().
Приложить скриншот результата.
Открытие/закрытие столбцов32:14
На этом уроке мы доработает функции AddRow() и Dance() в классе Dance(), а также реализуем функции Cover/Uncover().
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Добавить номер строки в классе Cell().
Доработать функцию AddRow() в классе Dance().
Доработать функцию Dance() в классе Dance(), использовав стек для хранения целых чисел.
Реализовать функции Cover/Uncover() в классе Dance().
Перенумеровать ячейки от 0 до 11, чтобы избавиться от пустых столбцов.
Приложить скриншот результата.

Фигуры из пентамимо18:16
На этом уроке мы приступаем к решению олимпиадной задачи "Пентамино", заполнив массив всеми вариантами расположения фигур.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Создать структуру Figure() и Variant().
Создать класс Pentaminos().
Заполнить массив всеми 63 вариантами расположения фигур в классе Pentaminos().
Создать функцию startPent() в классе Program().
Проверить заполнение массива всеми вариантами фигур.
Приложить скриншот результата.
** Доработать функцию startPent() для решения поставленной задачи.
*** Реализовать генератор всевозможных расположений фигур.
Фигуры в консоли14:59
На этом уроке мы решили реализовать возможность отображения фигур в консоли, чтобы в дальнейшем видеть, что происходит в процессе работы алгоритма.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Реализовать функцию Show() в классе Figure().
Добавить в классе Figure() строку символов фигур.
Доработать функцию startPentamino() в классе Program() для отображения фигур.
Реализовать перегрузку функции Show() в классе Figure() для более короткой записи.
Использовать короткую запись в функции startPentamino() класса Program().
Приложить скриншот результата.
* Вывести все 12 фигур в консоли.
Матрица Пентагона15:55
На этом уроке мы завершим реализацию функции поиска решения Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Реализовать алгоритм перебора всех вариантов расположения фигур Пентамино.
Дождаться завершения работы алгоритма и написать время ожидания.
Приложить скриншот результата.
Пентагон в деталях9:40
На этом уроке мы воспользуемся функцией Show() в классе Figure() для визуализации генерации всех вариантов расположения фигур Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Исправить ошибку прошлого урока связанную с nr++.
Использовать отображение генерации расположения вариантов фигур через функцию Show().
Добавить задержку после вывода каждого варианта расположения фигур по нажатию клавиш.
Реализовать функцию Hide() в классе Figure().
Использовать функцию Hide() вместо Console.Clear().
Приложить скриншот результата.
Пентагон ищет решение22:01
На этом уроке мы визуализируем поиск решения Пентамино с использованием yield.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Модифицировать функцию Dance() в классе Dance(), чтобы она возвращала IEnumerable.
Воспользоваться возвращаемым IEnumerable для визуализации текущего состояния поиска решений.
Модифицировать работу рекурсии с использованием yield return.
Создать структуру FigureRow для хранения расположения фигуры на поле.
Использовать динамический список для хранения объектов FigureRow.
Добавить конструктор для удобства добавления информации в список.
Сделать структуру FigureRow глобальной.
Реализовать функции Show/Hide() с параметром FigureRow.
Добавить задержку между отображением/стиранием текущего состояния поиска решения.
Приложить скриншот результата.
* Дождаться окончания поиска решений.
Десятикратная оптимизация19:35
В завершение знакомства с гениальным "алгоритмом X" Дональда Кнута — Dancing Links,
мы оптимизируем наш алгоритм поиска решения Пентамино.
Ссылка на файл с кодом функции инициализации фигур на С# — внизу.
Самостоятельное задание:
Внимательно прослушать и просмотреть видео.
Оптимизировать функцию Dance() в классе Dance().
Реализовать счётчик количество найденных вариантов.
Реализовать счётчик времени потраченного на поиск решений.
Поэкспериментировать с разными размерами поля.
Убрать геттеры/сеттеры в классе Cell() для многократного ускорения работы алгоритма.
Приложить скриншот результата.
*** Реализовать решение Судоку, используя данный алгоритм.
*** Реализовать решение Парад Ферзей, используя данный алгоритм.

Requirements

Логическое мышление
Основы языка программирования C#

Description

В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links.

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

В первой части курса "Теория" мы разберём принцип работы алгоритма, выполним его построчно "ручками" на конкретном примере, чтобы лучше понять, как он устроен и как работает. Мы пошагово рассмотрим статью автора Дональда Кнута, изобретателя этого алгоритма и рассмотрим пошаговое удаление и возвращение элемента.

Во второй части курса "Практика" мы реализуем на C# двух- и четырёх-связных списков и дальнейшей реализации "Алгоритма Икс" Дональда Кнута. и напишем весь алгоритм. Используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними.

Во третьей части курса "Пентамимо" мы применим созданный алгоритм к конкретной олимпиадной задаче по размещению пентамимо-фигур в заданной области. Алгоритм Икс решает эту задачу максимально быстро, так как отметает множество тупиковых веток - он их просто пропускает и делает это красиво. На финальном уроке мы оптимизируем наш алгоритм поиска решения Пентамино - ускорим работу программы в десять раз!

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

Who this course is for:

Для любителей алгоритмов
Для инженеров и программистов
Для студентов с лабораторкой по Dancing Links

Алгоритм X Dancing Links сборки пентамимо на C#

What you'll learn

Explore related topics

Course content

Теория3 lectures • 32min

Практика5 lectures • 1hr 55min

Пентамимо6 lectures • 1hr 40min

Requirements

Description

Who this course is for: