X算法

✍ dations ◷ 2025-06-16 10:07:53 #搜寻算法

在计算机科学中,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算法无论在选择行时还是回溯错误的选择时效率都很高。

相关

  • 按章工作按章工作是工业行动的一种,指员工以不多于其雇员合约所规定的职责范围,并完全依从安全指引之类的守则而不作任何变通的条件下工作,以达到减慢工作进度、降低生产率等令雇主有所
  • 利基市场产品 · 定价 · 分销 服务 · 零售 · 宣传 品牌管理 · 大客户营销 营销道德 · 营销效果 营销调查 · 市场调查 市场划分 · 营销战略 市场优势 · 操
  • 哈图西里三世哈图西里三世(英语:Hattusili III),新王国的赫梯国王,篡夺乌尔希泰舒普之位,著有自传,叙述其掌权经过,改朝换代未对赫梯政治结构造成重大变化,在位时期除对安纳托利亚南部用兵之外,一
  • 蔓越莓蔓越橘(英语:Cranberry),又称蔓越莓、小红莓,是杜鹃花科越橘属红莓苔子亚属(学名:拉丁语:Oxycoccus),又名毛蒿豆亚属的俗称,此亚属的物种均为常绿灌木,主要生长在北半球气候较清凉的温带
  • Nasub2/subPo钋化钠是一种无机化合物,由2种金属化合而成:钋和钠,化学式为:Na2Po。钋化钠的晶体结构为反萤石型结构,和其他氧族元素化碱金属类似(氧化钠、硫化钠、硒化钠、碲化钠)。要制备钋
  • 暗网黑暗网站(英语:Dark web)多简称为暗网,是存在于黑暗网络、覆盖网络上的万维网内容,只能用特殊软件、特殊授权、或对电脑做特殊设置才能访问。暗网是由深网的一小部分所构成的。而
  • 马来西亚国家银行马来西亚国家银行(马来语:Bank Negara Malaysia,英语:Central Bank of Malaysia;缩写:BNM;简称国行)是马来西亚的中央银行。成立于1959年1月24日,总部设在马来西亚首都吉隆坡,并在槟城
  • Bacteria放线菌门 Actinobacteria(高G+C) 厚壁菌门 Firmicutes(低G+C) 无壁菌门 (无细胞壁)产水菌门 Aquificae 异常球菌-栖热菌门 Deinococcus-Thermus 纤维杆菌门-绿菌门/拟杆菌门 Fibro
  • 特拉华殖民地特拉华殖民地(英语:Delaware Colony)是北美洲中部殖民地(英语:Middle Colonies)包括特拉华河湾西岸土地。17世纪早期此地由莱纳佩人及美国原住民的阿萨提格人(英语:Assateague tribe
  • 美国副总统美国副总统(英语:Vice President of the United States,非正式简称:VP / veep)是美国联邦政府行政分支中位阶第二高的官员,仅次于美国总统;同时在美国总统继任顺序中排列第一。同