Алгоритм X Dancing Links сборки пентамимо на C#
Теоретическое и практическое знакомство с гениальным "Алгоритмом икс" Дональда Кнута с примерами
Description
В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links.
Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, заполнение области Пентамимо-фигурами, решение Судоку, размещение ферзей на шахматной доске и так далее.
В первой части курса "Теория" мы разберём принцип работы алгоритма, выполним его построчно "ручками" на конкретном примере, чтобы лучше понять, как он устроен и как работает. Мы пошагово рассмотрим статью автора Дональда Кнута, изобретателя этого алгоритма и рассмотрим пошаговое удаление и возвращение элемента.
Во второй части курса "Практика" мы реализуем на C# двух- и четырёх-связных списков и дальнейшей реализации "Алгоритма Икс" Дональда Кнута. и напишем весь алгоритм. Используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними.
Во третьей части курса "Пентамимо" мы применим созданный алгоритм к конкретной олимпиадной задаче по размещению пентамимо-фигур в заданной области. Алгоритм Икс решает эту задачу максимально быстро, так как отметает множество тупиковых веток - он их просто пропускает и делает это красиво. На финальном уроке мы оптимизируем наш алгоритм поиска решения Пентамино - ускорим работу программы в десять раз!
Если вам нравятся алгоритмы, то обязательно пройдите этот курс, не пожалеете. Знание алгоритма Dancing Links позволит вам эффективно решать любые задачи, решение которых сводятся к задаче о полном покрытии.
What You Will Learn!
- Поймут суть алгоритма X для быстрого поиска решений
- Решат задачу расстановки пентамимо с использованием алгоритма Dancing Links
Who Should Attend!
- Для любителей алгоритмов
- Для инженеров и программистов
- Для студентов с лабораторкой по Dancing Links