付冰　胡云　周作建

摘  要： 为了缩短健康体检排队等待时间、预测待检项目整体顺序，以X算法、精确覆盖、广义覆盖、Dancing Links作为理论基础，提出了应用Dancing Links X解决体检时间广义覆盖问题的方法。通过构建以服务时间成本、排队等待时间成本的总成本最小化为目标的Dancing Links X三重约束来搜索可行性解，并摘选最小值。以此模型完成的规划体检顺序，实现了对体检路线的预测，表明基于Dancing Links X三重约束的智能导检路径优化模型可以对待检项目顺序及时间节点预测，为导检的智能化研究提供新思路。

关键词： 智能导检; Dancing Links; X算法; 广义覆盖; 精确覆盖

中图分类号：TP399          文献标识码：A     文章编号：1006-8228（2022）03-61-05

Abstract： In order to shorten the waiting time of physical examination and predict the overall order of the items to be examined， taking X algorithm， precise coverage， generalized coverage and Dancing Links as the theoretical basis， a method of applying Dancing Links X to solve the generalized coverage problem of physical examination time is proposed. By constructing the Dancing Links X triple constraint aiming at minimizing the total cost of service time cost and queuing time cost， the feasible solution is searched and the minimum value is selected. The planned physical examination sequence completed by this model realizes the prediction of physical examination route， which shows that the intelligent physical examination route optimization model based on Dancing Links X triple constraint can predict the order and time nodes of the items to be examined， providing the intelligent research of physical examination guidance with a new idea.

Key words： intelligent physical examination guidance; Dancing Links; X algorithm; generalized coverage; accurate coverage

0 引言

如今人工智能、大數据与健康体检日益紧密结合，就医模式向以预防为主的健康管理转移，全社会均将慢病防控作为重要工作目标和战略任务[1-2]。健康产业的蓬勃发展促使体检人次日趋增长，体检中，排队等候医生检查是人们接受体检服务的开始，而排队等候的时间长、秩序乱、插队多等现象，使得体检客户的满意度降低。为了有效地把控排队效率、维护良好的队列秩序，季克峰[3]等人应用排队论相关理论知识，构建基于排队论的体检导检系统。熊志刚[4]等人引入分时段体检预约模式，设计了分时段体检预约管理系统，通过合理控制人流方式达到人均缩短40min左右的效果。董秀敏[5]学者在大批量体检人员的管理中应用排队论，根据体检项目的空闲概率、体检客户排队等待时间，求出列队长度继而确定诊室的开放数量。何雅庆[6-7]等学者提出在动态规划算法、不完全数独算法、排队论、时间唯一理论的基础上，通过数值计算、逻辑推理、系统构架，进行体检排队系统的设计。王颖纯[8]等学者根据元胞自动机的模拟从而得到了体检人员的体检科目顺序及时间安排。

目前，针对智能导检的研究仍处于薄弱阶段，为体检客户预测待检行程可以使得体检客户提前做好相应检查准备，对体检步骤全面把握。为了能在缩短顾客整体逗留时间的同时为顾客预测待检行程，本文运用Dancing Links实现算法X以解决广义覆盖问题，构建基于Dancing Links三重约束的智能导检路径优化模型，并根据时间成本最低原则摘选体检路线，体检客户可实时知晓体检整体行程及其变更结果。为体检排队的智能化、自动化研究提供新方法。

1 相关知识

1.1 精确覆盖

“精确覆盖”是指在一个全集Y中若干子集的集合为S，求S的子集S*，满足Y的每一个元素在S*中恰好出现一次。在计算机科学中，“精确覆盖”问题是指找出满足要求的一种覆盖，或证明其不存在[9]。由于解决精确覆盖问题已延展至信息科学[10]、自动化系统设计[11]、通信工程[12]及密钥管理[13]等诸多领域，因此国内外学者对于此问题的研究较为深入[14]。李肯立[15]等学者根据精确覆盖问题DNA计算求解过程中的并行计算需求，提出了一种求解精确覆盖问题的DNA计算模型和基于分治方法的DNA计算机算法。

1.2 X算法

X算法[16]是一个递归、非确定性、深度优先的回溯算法。它是由Donald Knuth创建的并可用于查找精确覆盖问题的所有解决方案的算法。公式1为二进制矩阵。X算法步骤为：①如果矩阵A为空矩阵，则当前记录的解为可行解;算法终止，成功返回。②否则选择矩阵A中“1”的个数最少的列c。③a.如果存在A[r][c]=1的行r，将行r放入可行解列表，进入步骤④;b.如果不存在A[r][c]=1的行r，则剩下的矩阵不可能完成精确覆盖，说明选择有错或者无解，需要回溯，并且恢复此次删除的行和列，然后跳到步骤③a。④对于所有的满足A[r][j]=1的列j，对于所有满足A[i][j]=1的行i，将行i从矩阵A中删除;最后将列j从矩阵A中删除。⑤在不断减少的矩阵A上递归重复调用上述算法;回溯的实质是在问题的解空间进行深度优先搜索，X算法在回溯中的用法具有重要意义。

[ABCDEFG001011010010010110010100100001000010001101]  ⑴

1.3 广义覆盖

基本的精确覆盖问题可以进一步将约束分为primary及secondary，可称其为主要约束及次要约束。广义覆盖问题要求一组行刚好覆盖每个主要约束列一次，并且每个次要约束列最多被覆盖一次[17]。广义覆盖问题与精确覆盖问题解决方法几乎相同，唯一区别为通过仅对主要约束列创建一个列标头的循环列表来初始化数据结构，每个次要约束列的头应具有指向其自身的L和R字段，算法的其余部分与精确覆盖完全一样，所以我们仍将其称为算法Dancing Links X（缩写：DLX）[16]。

1.4 Dancing Links

Dancing Links是Donald Knuth建議的有效实现X算法的技术。Knuth假设x为双向链的一个结点，L[x]是指向x的左元素，R[x]是指向x的右元素。下面描述了对x的两个操作，公式⑵代表从双向链表中删除x，公式⑶代表将x插入双向链表中。

[LRx←Lx， RLx←Rx]  ⑵

[LRx←x，      RLx←x]  ⑶

如公式⑴给定一个二进制矩阵，Dancing Links将1表示为数据对象。每个数据对象x具有字段L[x]，R[x]，U[x]，D[x]和C[x]，这些字段用于链接到左，右，上和下分别占1的任何其他单元。在合适的单元格中没有对应的1的任何链接将改为链接到其自身[16]。如图1为依据给定的二进制矩阵构建的交叉十字循环双向链。DLX在缓存和回溯的过程中拥有着高效、高速、空间耗用低等特性。

2 基于Dancing Links X的智能导检模型

2.1 问题描述

首先是队列问题，科室、项目、体检客户均存在差异性，体检客户检查套餐及项目可进行个性化选择，并且不同项目服务时间具有各异性。其次是科室诊室数量设置问题，体检中心为平均检查时间较长的科室分配多个诊室，此时要把科室数量不同的因素考虑到体检客户排队算法当中。最后是待检路径预测问题，为方便顾客提前知晓待检项目的顺序及检测时间点，以便顾客提前做好相应准备。目前体检排队问题均属于多诊室串联排队性质，项目服务时间大致恒定。体检中心需要为体检客户分配合理的检查顺序，以使得体检客户逗留时间最短。

2.2 智能导检模型构建

通过对体检中心的调查，本文确定了每个项目的大致时间，并预先设定每个时间块均为1分钟。本文为科室及检查项目设定编号并标识对应诊室数量，如表1为体检项目时间及项目编码标识表。根据体检特性分析可知：①每位体检客户要完成个人体检单中全部确定待检项目;②每位体检客户在同一时间里只能进行一个项目检查;③每位体检客户同一检查项目做一次;④体检项目均有其固定科室;⑤不同项目服务时间具有各异性;⑥不同科室的诊室数量不同。根据以上特性并依据表2，本文将项目、诊室、科室及项目起止时间点构建为三重约束。Constraint 1：一般情况每位体检客户同一科室只能进入一次，不得进行二次检查。列元素代表科室编号，行元素代表诊室编号。

根据所有列元素不得重复原则可知同一科室不得重复进入，如图2 Constraint 1所示。Constraint 2：科室与项目所属关系为固定状态。列元素代表项目编号，行元素代表诊室编号，科室包含固定项目，科室下的诊室均可对固定项目进行检测。根据所有列元素不得重复原则可知所有检查项目不得重复，并且同一科室所有检查项目一次检测完成，如图2 Constraint 2所示。Constraint 3：项目检查时间不得冲突。列元素代表时间轴，行元素代表诊室编号，根据所有列元素不得重复原则可知同一时间不得在不同科室检查，如图2 Constraint 3所示。根据以上三重约束，本文考虑依据广义覆盖问题构建智能导检模型，通过Dancing Links列举所有可行性解，并根据生成的满足给定约束条件的方案列表摘选路径。

3 实验分析

DLX选择主列中1最少的行元素E1，并将其置于可行解中，同时将时间冲突行元素摘除，接下来在主列中选择1最少的行元素D1与D2并执行D1，时间、科室、项目冲突行元素有A3、B1、B2、D2，将其摘除之后违反约束1及约束2，输出错误分支并回溯及选择D2。以此遍历所有分支，搜索所有可行解，如图2结论得出三种时间路线图，时间路线均满足三重约束，均为可行性解，如图3所示。根据DLX将三种结果对照表1进行实例化分析，整理可行性解及其时间成本，时间成本=离开时间-进入时间，本文应用DLX筛选所有可行方案，最终以时间成本最低为最优解输出体检时间路线。如图4所示，最终摘选方案二作为当前方案。

4 总结

本文将排队问题转化为广义覆盖问题，继而应用Dancing Links X算法解决广义覆盖问题。通过构建Dancing Links X三重约束与体检排队模式相结合的方式筛查可行性解，并得到较为满意的可行方案以及最优解，完成体检行程预判及时间成本最小化输出。本文使用了X算法、广义覆盖及Dancing Links对体检排队进行顺序规划，并取得了较好结果，最终实现为体检客户智能预测整体待检行程。表明通过Dancing Links X实现智能导检是可行的，为智能导检排队问题提供新方法，为实施健康中国战略提供新思路。

参考文献（References）：

[1] 中共中央国务院印发《“健康中国2030”规划纲要》[J].中华人民共和国国务院公报，2016（32）：5-20

[2] 国务院办公厅关于印发中国防治慢性病中长期规划（2017—2025年）的通知[J].中华人民共和国国务院公报，2017（7）：17-24

[3] 季克峰，赵凯，李慧杰，等.排队论在体检导检中的应用研究[J].中国数字医学，2021，16（1）：60-62

[4] 熊志刚，周旖旎.分時段体检预约管理系统研究与设计[J].中国数字医学，2020，15（12）：27-29，97

[5] 董秀敏.排队论与人性化服务结合用于大批体检人员的管理[J].中国误诊学杂志，2010，10（14）：3377

[6] 何雅庆，谢应朗，宋勤，等.体检排队系统的理论基础[J].中国医学创新，2013，10（19）：139-142

[7] 何雅庆，谢应朗，宋勤，等.体检排队系统数学模型的制作[J].中国医药科学，2013，3（6）：152-154

[8] 王颖纯，岳磊，刑蕊，等.现代体检管理信息系统的析与设计[J].天津理工大学学报，2011，27（4）：56-57

[9] 姜华林.基于精确覆盖的应用算法研究[J].电脑知识与技术，2018，14（35）：61-62

[10] 林浩.信息需求网络上最优连接问题[J].系统工程学报，2004，19（4）：427-430，440

[11] Lehmann M，Mai T L，Wollschlaeger B.Design approach for component-based automation systems using exact cover[A].Emerging Technology&Factory[C] Automation.IEEE，2014：1-8

[12] 林宇.基于FFTx下一代通信网精确覆盖系统的设计与实现[J].移动通信，2014，38（10）：19-23

[13] Fu Xiong，Xu Shou-zhi.Minimum exact cover problem of group key distribution[J].Wuhan University Journal of Natural Sciences，2009，14（2）：137-142

[14] 胡沁，宁爱兵，苟海雯，等.精确覆盖问题的加权分治算法[J].运筹与管理，2020，29（4）：179-186

[15] 李肯立，刘杰，杨磊，等.精确覆盖问题的O（1.414^n）链数DNA计算机算法[J].计算机研究与发展，2008（10）：1782-1788

[16] Donald Knuth. Dancing links[J]. Millenial Perspectives in Computer Science，2000：187-214

[17] Nguyen Vivian，Moran Bill，Novak Ana，MakHau Vicky，Caelli Terry，Hill Brendan，Kirszenblat David. Dancing Links for Optimal Timetabling[J].Military Operations Research，2018，23（2）

3215501908264