Dancing Links X在智能導檢中的應用研究

付冰　胡云　周作建

摘? 要： 為了縮短健康體檢排隊等待時間、預測待檢項目整體順序，以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