|
所在平台: Udemy |
课程主页: https://www.udemy.com/course/dancing-links/
课程评论：没有评论
课程名称：C#实现Dancing Links算法解决五格骨牌填充问题 课程概述： 本课程将带您深入了解唐纳德·克努斯（Donald Knuth）提出的“Dancing Links”算法（也称为X算法）。该算法是一种高效的解决各种组合问题的通用方法，包括五格骨牌（Pentominoes）填充、数独求解、N皇后问题等。 课程分为三个部分： **第一部分：理论** * 深入剖析Dancing Links算法的工作原理。 * 通过详细的“手动”操作示例，循序渐进地讲解算法的每一步。 * 详细解读算法发明者唐纳德·克努斯的原始论文，重点讲解元素的删除与恢复过程。 **第二部分：实践** * 使用C#语言实现双向和四向链表。 * 在此基础上，完整实现Dancing Links（X算法）。 * 利用之前实现的四向链表，添加必要的元素以支持算法的后续操作。 **第三部分：五格骨牌填充** * 将实现的Dancing Links算法应用于一个具体的奥林匹克竞赛题目：将五格骨牌填充到指定的区域。 * 展示Dancing Links算法如何通过快速排除死胡同分支来高效解决此类问题。 * 在最终课程中，将对五格骨牌填充算法进行优化，能将程序运行速度提升十倍。 **总结：** 如果您对算法感兴趣，本课程绝对值得您学习。掌握Dancing Links算法将赋予您高效解决所有可归结为“精确覆盖问题”（Exact Cover Problem）的组合问题的能力。
В этой серии уроков мы познакомимся с гениальным алгоритмом X Дональда Кнута - Dancing Links.Этот алгоритм можно применять для решения самых разных комбинаторных задач, например, заполнение области Пентамимо-фигурами, решение Судоку, размещение ферзей на шахматной доске и так далее. В первой части курса "Теория" мы разберём принцип работы алгоритма, выполним его построчно "ручками" на конкретном примере, чтобы лучше понять, как он устроен и как работает. Мы пошагово рассмотрим статью автора Дональда Кнута, изобретателя этого алгоритма и рассмотрим пошаговое удаление и возвращение элемента.Во второй части курса "Практика" мы реализуем на C# двух- и четырёх-связных списков и дальнейшей реализации "Алгоритма Икс" Дональда Кнута. и напишем весь алгоритм. Используя созданный ранее четырёх-связный список, мы добавим необходимые нам элементы для дальнейшем работы с ними.Во третьей части курса "Пентамимо" мы применим созданный алгоритм к конкретной олимпиадной задаче по размещению пентамимо-фигур в заданной области. Алгоритм Икс решает эту задачу максимально быстро, так как отметает множество тупиковых веток - он их просто пропускает и делает это красиво. На финальном уроке мы оптимизируем наш алгоритм поиска решения Пентамино - ускорим работу программы в десять раз!Если вам нравятся алгоритмы, то обязательно пройдите этот курс, не пожалеете. Знание алгоритма Dancing Links позволит вам эффективно решать любые задачи, решение которых сводятся к задаче о полном покрытии.
