X算法

✍ dations ◷ 2025-07-30 00:41:09 #搜寻算法

在计算机科学中,X算法可用来求解精确覆盖问题。此名称最早在高德纳的论文《舞蹈链》中出现,他认为此算法是“试错法中最显而易见”的。 就技术而言,X算法是一个深度优先的不确定性回溯算法。由于X算法是一个解决精确覆盖问题的简洁方法,高德纳希望通过该算法体现舞蹈链数据结构的高效性,他把使用后者的X算法称为DLX。

X算法用由0和1组成的矩阵来表示精确覆盖问题,目标是选出矩阵的若干行,使得其中的1在所有列中出现且仅出现一次。

X算法的步骤如下:

选择的不确定性意味着算法将派生出若干独立的子算法,每个子算法都从其父算法中继承了去除部分行列的矩阵。如果其中有一列全为零,则当前情况无解,子算法返回失败,但不一定意味整个问题无解。

实际上,所有子算法形成了一棵搜索树,其中原问题为根节点,树的第层由子算法在第次所选择的行组成。整个算法即用回溯法对搜索树深度优先遍历。

第二步中,无论用什么方法选择列最终都可以得到解,但有的方法效率明显较高。为减少迭代次数,高德纳建议每次都选取1最少的列。

例如,考虑以下精确覆盖问题:全集 = {1, 2, 3, 4, 5, 6, 7} ,现有U的六个子集 S {\displaystyle {\mathcal {S}}} , , , , , },其中:

此问题可用矩阵表示为:

根据高德纳的建议,每次都选取1最少的列,则X算法的执行步骤如下:

第0层

第一步:矩阵非空,故算法继续执行。

第二步:1最少的列为第一列,含有两个1。所以选择第一列:

第三步:A行和B行第一列均为1,所以依次选择这两行继续搜索。

于是算法开始搜索树的第1层第一个分支:

第0层没有其他可选择的行,算法最终停止。

综上所述,用X算法得出本问题只有一个解: S {\displaystyle {\mathcal {S}}^{*}} , , }。

高德纳主要想通过X算法体现舞蹈链的实用性。他发现了使用舞蹈链的X算法效率极高,并把这一过程称为DLX。DLX用矩阵来表示精确覆盖问题,在内部的存储结构为舞蹈链。舞蹈链是一个双向环形链表,每个矩阵中的1都有一个指针指向其左、右、上、下的1。因为精确覆盖问题中的矩阵一般都是稀疏的,所以舞蹈链中的元素很少,既很省时间,又很省空间。可见使用舞蹈链的DLX算法无论在选择行时还是回溯错误的选择时效率都很高。

相关

  • 衰老人体解剖学 - 人体生理学 组织学 - 胚胎学 人体寄生虫学 - 免疫学 病理学 - 病理生理学 细胞学 - 营养学 流行病学 - 药理学 - 毒理学在生物学及医学上,老化是生理状态随时
  • 氦核作用氦核作用 (或α作用、α反应)是两种核聚变的类型之一,能将恒星的氦转换成重元素,另一种即是3氦过程(3α反应)。 当3氦反应进行时只需要氦的参与,而一旦有一些碳产生,能消耗氦的其他
  • 意大利国家足球队意大利国家足球队(意大利语:Nazionale di calcio dell'Italia)是最成功的国家足球队之一,曾赢得四届世界杯冠军,只比巴西少一次。其传统球衣是蓝衫白裤蓝袜,因此其绰号是“Azzurri
  • 科罗拉多壁虱热病毒科罗拉多壁虱热病毒(Coltivirus),是 呼肠孤病毒科(Reoviruses) 的一个属。 该类病毒会感染如猪等动物,造成如猪流行性腹泻等疾病。代表种:
  • 塞提二世塞提二世 Seti II,古埃及第十九王朝法老(约公元前1200年—约公元前1194年在位)。麦伦普塔赫之子,拉美西斯二世之孙。塞提是他的真名,他的王衔(拉名)是Userkheprure—setpenre,意思是
  • 印地安那波利斯印第安纳波利斯(英语:Indianapolis,发音为/ˌɪndiəˈnæpəlɨs/),简称“Indy”(/ˈɪndi/),是位于美国印地安纳州中部的都市,为该州首府暨最大都市,行政上与其所在的马里昂县合一。
  • span style=color: white;欧盟关税同盟/span本文是 欧洲联盟的政治与政府 系列条目之一欧盟关税同盟(英语:European Union Customs Union (EUCU),法语:Union douanière de l'Union européenne,德语:Europäische Zollunion
  • 1980年美国总统选举吉米·卡特 民主党罗纳德·里根 共和党1980年美国总统选举于1980年11月4日(星期二)举行,是第49次美国总统选举。这次选举主要是现任民主党总统吉米·卡特和共和党候选人,前加
  • 朱姆沃尔特级朱姆沃尔特级驱逐舰(英语:Zumwalt class destroyer,又译为朱沃特级,或常以当初的开发计划名DD(X)称呼之),是服役中的美国海军驱逐舰,设计为多任务功能的濒海战斗舰与宙斯盾防御舰。
  • 魏玛的古典主义魏玛的古典主义在德国文学中指的是1786年约翰·沃尔夫冈·冯·歌德的第一次意大利旅行之后的阶段,魏玛的古典主义大约延续到1810年。有时,魏玛的古典主义也被用来指称有着亲密