Dancing Links X在智能導(dǎo)檢中的應(yīng)用研究

付冰　胡云　周作建

摘? 要： 為了縮短健康體檢排隊(duì)等待時(shí)間、預(yù)測(cè)待檢項(xiàng)目整體順序，以X算法、精確覆蓋、廣義覆蓋、Dancing Links作為理論基礎(chǔ)，提出了應(yīng)用Dancing Links X解決體檢時(shí)間廣義覆蓋問(wèn)題的方法。通過(guò)構(gòu)建以服務(wù)時(shí)間成本、排隊(duì)等待時(shí)間成本的總成本最小化為目標(biāo)的Dancing Links X三重約束來(lái)搜索可行性解，并摘選最小值。以此模型完成的規(guī)劃體檢順序，實(shí)現(xiàn)了對(duì)體檢路線的預(yù)測(cè)，表明基于Dancing Links X三重約束的智能導(dǎo)檢路徑優(yōu)化模型可以對(duì)待檢項(xiàng)目順序及時(shí)間節(jié)點(diǎn)預(yù)測(cè)，為導(dǎo)檢的智能化研究提供新思路。

關(guān)鍵詞： 智能導(dǎo)檢; Dancing Links; X算法; 廣義覆蓋; 精確覆蓋

中圖分類號(hào)：TP399? ? ? ? ? 文獻(xiàn)標(biāo)識(shí)碼：A? ? ?文章編號(hào)：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 引言

如今人工智能、大數(shù)據(jù)與健康體檢日益緊密結(jié)合，就醫(yī)模式向以預(yù)防為主的健康管理轉(zhuǎn)移，全社會(huì)均將慢病防控作為重要工作目標(biāo)和戰(zhàn)略任務(wù)[1-2]。健康產(chǎn)業(yè)的蓬勃發(fā)展促使體檢人次日趨增長(zhǎng)，體檢中，排隊(duì)等候醫(yī)生檢查是人們接受體檢服務(wù)的開(kāi)始，而排隊(duì)等候的時(shí)間長(zhǎng)、秩序亂、插隊(duì)多等現(xiàn)象，使得體檢客戶的滿意度降低。為了有效地把控排隊(duì)效率、維護(hù)良好的隊(duì)列秩序，季克峰[3]等人應(yīng)用排隊(duì)論相關(guān)理論知識(shí)，構(gòu)建基于排隊(duì)論的體檢導(dǎo)檢系統(tǒng)。熊志剛[4]等人引入分時(shí)段體檢預(yù)約模式，設(shè)計(jì)了分時(shí)段體檢預(yù)約管理系統(tǒng)，通過(guò)合理控制人流方式達(dá)到人均縮短40min左右的效果。董秀敏[5]學(xué)者在大批量體檢人員的管理中應(yīng)用排隊(duì)論，根據(jù)體檢項(xiàng)目的空閑概率、體檢客戶排隊(duì)等待時(shí)間，求出列隊(duì)長(zhǎng)度繼而確定診室的開(kāi)放數(shù)量。何雅慶[6-7]等學(xué)者提出在動(dòng)態(tài)規(guī)劃算法、不完全數(shù)獨(dú)算法、排隊(duì)論、時(shí)間唯一理論的基礎(chǔ)上，通過(guò)數(shù)值計(jì)算、邏輯推理、系統(tǒng)構(gòu)架，進(jìn)行體檢排隊(duì)系統(tǒng)的設(shè)計(jì)。王穎純[8]等學(xué)者根據(jù)元胞自動(dòng)機(jī)的模擬從而得到了體檢人員的體檢科目順序及時(shí)間安排。

目前，針對(duì)智能導(dǎo)檢的研究仍處于薄弱階段，為體檢客戶預(yù)測(cè)待檢行程可以使得體檢客戶提前做好相應(yīng)檢查準(zhǔn)備，對(duì)體檢步驟全面把握。為了能在縮短顧客整體逗留時(shí)間的同時(shí)為顧客預(yù)測(cè)待檢行程，本文運(yùn)用Dancing Links實(shí)現(xiàn)算法X以解決廣義覆蓋問(wèn)題，構(gòu)建基于Dancing Links三重約束的智能導(dǎo)檢路徑優(yōu)化模型，并根據(jù)時(shí)間成本最低原則摘選體檢路線，體檢客戶可實(shí)時(shí)知曉體檢整體行程及其變更結(jié)果。為體檢排隊(duì)的智能化、自動(dòng)化研究提供新方法。

1 相關(guān)知識(shí)

1.1 精確覆蓋

“精確覆蓋”是指在一個(gè)全集Y中若干子集的集合為S，求S的子集S*，滿足Y的每一個(gè)元素在S*中恰好出現(xiàn)一次。在計(jì)算機(jī)科學(xué)中，“精確覆蓋”問(wèn)題是指找出滿足要求的一種覆蓋，或證明其不存在[9]。由于解決精確覆蓋問(wèn)題已延展至信息科學(xué)[10]、自動(dòng)化系統(tǒng)設(shè)計(jì)[11]、通信工程[12]及密鑰管理[13]等諸多領(lǐng)域，因此國(guó)內(nèi)外學(xué)者對(duì)于此問(wèn)題的研究較為深入[14]。李肯立[15]等學(xué)者根據(jù)精確覆蓋問(wèn)題DNA計(jì)算求解過(guò)程中的并行計(jì)算需求，提出了一種求解精確覆蓋問(wèn)題的DNA計(jì)算模型和基于分治方法的DNA計(jì)算機(jī)算法。

1.2 X算法

X算法[16]是一個(gè)遞歸、非確定性、深度優(yōu)先的回溯算法。它是由Donald Knuth創(chuàng)建的并可用于查找精確覆蓋問(wèn)題的所有解決方案的算法。公式1為二進(jìn)制矩陣。X算法步驟為：①如果矩陣A為空矩陣，則當(dāng)前記錄的解為可行解;算法終止，成功返回。②否則選擇矩陣A中“1”的個(gè)數(shù)最少的列c。③a.如果存在A[r][c]=1的行r，將行r放入可行解列表，進(jìn)入步驟④;b.如果不存在A[r][c]=1的行r，則剩下的矩陣不可能完成精確覆蓋，說(shuō)明選擇有錯(cuò)或者無(wú)解，需要回溯，并且恢復(fù)此次刪除的行和列，然后跳到步驟③a。④對(duì)于所有的滿足A[r][j]=1的列j，對(duì)于所有滿足A[i][j]=1的行i，將行i從矩陣A中刪除;最后將列j從矩陣A中刪除。⑤在不斷減少的矩陣A上遞歸重復(fù)調(diào)用上述算法;回溯的實(shí)質(zhì)是在問(wèn)題的解空間進(jìn)行深度優(yōu)先搜索，X算法在回溯中的用法具有重要意義。

[ABCDEFG001011010010010110010100100001000010001101]? ⑴

1.3 廣義覆蓋

基本的精確覆蓋問(wèn)題可以進(jìn)一步將約束分為primary及secondary，可稱其為主要約束及次要約束。廣義覆蓋問(wèn)題要求一組行剛好覆蓋每個(gè)主要約束列一次，并且每個(gè)次要約束列最多被覆蓋一次[17]。廣義覆蓋問(wèn)題與精確覆蓋問(wèn)題解決方法幾乎相同，唯一區(qū)別為通過(guò)僅對(duì)主要約束列創(chuàng)建一個(gè)列標(biāo)頭的循環(huán)列表來(lái)初始化數(shù)據(jù)結(jié)構(gòu)，每個(gè)次要約束列的頭應(yīng)具有指向其自身的L和R字段，算法的其余部分與精確覆蓋完全一樣，所以我們?nèi)詫⑵浞Q為算法Dancing Links X（縮寫：DLX）[16]。

1.4 Dancing Links

Dancing Links是Donald Knuth建議的有效實(shí)現(xiàn)X算法的技術(shù)。Knuth假設(shè)x為雙向鏈的一個(gè)結(jié)點(diǎn)，L[x]是指向x的左元素，R[x]是指向x的右元素。下面描述了對(duì)x的兩個(gè)操作，公式⑵代表從雙向鏈表中刪除x，公式⑶代表將x插入雙向鏈表中。

[LRx←Lx， RLx←Rx]? ⑵

[LRx←x，? ? ? RLx←x]? ⑶

如公式⑴給定一個(gè)二進(jìn)制矩陣，Dancing Links將1表示為數(shù)據(jù)對(duì)象。每個(gè)數(shù)據(jù)對(duì)象x具有字段L[x]，R[x]，U[x]，D[x]和C[x]，這些字段用于鏈接到左，右，上和下分別占1的任何其他單元。在合適的單元格中沒(méi)有對(duì)應(yīng)的1的任何鏈接將改為鏈接到其自身[16]。如圖1為依據(jù)給定的二進(jìn)制矩陣構(gòu)建的交叉十字循環(huán)雙向鏈。DLX在緩存和回溯的過(guò)程中擁有著高效、高速、空間耗用低等特性。

2 基于Dancing Links X的智能導(dǎo)檢模型

2.1 問(wèn)題描述

首先是隊(duì)列問(wèn)題，科室、項(xiàng)目、體檢客戶均存在差異性，體檢客戶檢查套餐及項(xiàng)目可進(jìn)行個(gè)性化選擇，并且不同項(xiàng)目服務(wù)時(shí)間具有各異性。其次是科室診室數(shù)量設(shè)置問(wèn)題，體檢中心為平均檢查時(shí)間較長(zhǎng)的科室分配多個(gè)診室，此時(shí)要把科室數(shù)量不同的因素考慮到體檢客戶排隊(duì)算法當(dāng)中。最后是待檢路徑預(yù)測(cè)問(wèn)題，為方便顧客提前知曉待檢項(xiàng)目的順序及檢測(cè)時(shí)間點(diǎn)，以便顧客提前做好相應(yīng)準(zhǔn)備。目前體檢排隊(duì)問(wèn)題均屬于多診室串聯(lián)排隊(duì)性質(zhì)，項(xiàng)目服務(wù)時(shí)間大致恒定。體檢中心需要為體檢客戶分配合理的檢查順序，以使得體檢客戶逗留時(shí)間最短。

2.2 智能導(dǎo)檢模型構(gòu)建

通過(guò)對(duì)體檢中心的調(diào)查，本文確定了每個(gè)項(xiàng)目的大致時(shí)間，并預(yù)先設(shè)定每個(gè)時(shí)間塊均為1分鐘。本文為科室及檢查項(xiàng)目設(shè)定編號(hào)并標(biāo)識(shí)對(duì)應(yīng)診室數(shù)量，如表1為體檢項(xiàng)目時(shí)間及項(xiàng)目編碼標(biāo)識(shí)表。根據(jù)體檢特性分析可知：①每位體檢客戶要完成個(gè)人體檢單中全部確定待檢項(xiàng)目;②每位體檢客戶在同一時(shí)間里只能進(jìn)行一個(gè)項(xiàng)目檢查;③每位體檢客戶同一檢查項(xiàng)目做一次;④體檢項(xiàng)目均有其固定科室;⑤不同項(xiàng)目服務(wù)時(shí)間具有各異性;⑥不同科室的診室數(shù)量不同。根據(jù)以上特性并依據(jù)表2，本文將項(xiàng)目、診室、科室及項(xiàng)目起止時(shí)間點(diǎn)構(gòu)建為三重約束。Constraint 1：一般情況每位體檢客戶同一科室只能進(jìn)入一次，不得進(jìn)行二次檢查。列元素代表科室編號(hào)，行元素代表診室編號(hào)。

根據(jù)所有列元素不得重復(fù)原則可知同一科室不得重復(fù)進(jìn)入，如圖2 Constraint 1所示。Constraint 2：科室與項(xiàng)目所屬關(guān)系為固定狀態(tài)。列元素代表項(xiàng)目編號(hào)，行元素代表診室編號(hào)，科室包含固定項(xiàng)目，科室下的診室均可對(duì)固定項(xiàng)目進(jìn)行檢測(cè)。根據(jù)所有列元素不得重復(fù)原則可知所有檢查項(xiàng)目不得重復(fù)，并且同一科室所有檢查項(xiàng)目一次檢測(cè)完成，如圖2 Constraint 2所示。Constraint 3：項(xiàng)目檢查時(shí)間不得沖突。列元素代表時(shí)間軸，行元素代表診室編號(hào)，根據(jù)所有列元素不得重復(fù)原則可知同一時(shí)間不得在不同科室檢查，如圖2 Constraint 3所示。根據(jù)以上三重約束，本文考慮依據(jù)廣義覆蓋問(wèn)題構(gòu)建智能導(dǎo)檢模型，通過(guò)Dancing Links列舉所有可行性解，并根據(jù)生成的滿足給定約束條件的方案列表摘選路徑。

3 實(shí)驗(yàn)分析

DLX選擇主列中1最少的行元素E1，并將其置于可行解中，同時(shí)將時(shí)間沖突行元素摘除，接下來(lái)在主列中選擇1最少的行元素D1與D2并執(zhí)行D1，時(shí)間、科室、項(xiàng)目沖突行元素有A3、B1、B2、D2，將其摘除之后違反約束1及約束2，輸出錯(cuò)誤分支并回溯及選擇D2。以此遍歷所有分支，搜索所有可行解，如圖2結(jié)論得出三種時(shí)間路線圖，時(shí)間路線均滿足三重約束，均為可行性解，如圖3所示。根據(jù)DLX將三種結(jié)果對(duì)照表1進(jìn)行實(shí)例化分析，整理可行性解及其時(shí)間成本，時(shí)間成本=離開(kāi)時(shí)間-進(jìn)入時(shí)間，本文應(yīng)用DLX篩選所有可行方案，最終以時(shí)間成本最低為最優(yōu)解輸出體檢時(shí)間路線。如圖4所示，最終摘選方案二作為當(dāng)前方案。

4 總結(jié)

本文將排隊(duì)問(wèn)題轉(zhuǎn)化為廣義覆蓋問(wèn)題，繼而應(yīng)用Dancing Links X算法解決廣義覆蓋問(wèn)題。通過(guò)構(gòu)建Dancing Links X三重約束與體檢排隊(duì)模式相結(jié)合的方式篩查可行性解，并得到較為滿意的可行方案以及最優(yōu)解，完成體檢行程預(yù)判及時(shí)間成本最小化輸出。本文使用了X算法、廣義覆蓋及Dancing Links對(duì)體檢排隊(duì)進(jìn)行順序規(guī)劃，并取得了較好結(jié)果，最終實(shí)現(xiàn)為體檢客戶智能預(yù)測(cè)整體待檢行程。表明通過(guò)Dancing Links X實(shí)現(xiàn)智能導(dǎo)檢是可行的，為智能導(dǎo)檢排隊(duì)問(wèn)題提供新方法，為實(shí)施健康中國(guó)戰(zhàn)略提供新思路。

參考文獻(xiàn)（References）：

[1] 中共中央國(guó)務(wù)院印發(fā)《“健康中國(guó)2030”規(guī)劃綱要》[J].中華人民共和國(guó)國(guó)務(wù)院公報(bào)，2016（32）：5-20

[2] 國(guó)務(wù)院辦公廳關(guān)于印發(fā)中國(guó)防治慢性病中長(zhǎng)期規(guī)劃（2017—2025年）的通知[J].中華人民共和國(guó)國(guó)務(wù)院公報(bào)，2017（7）：17-24

[3] 季克峰，趙凱，李慧杰，等.排隊(duì)論在體檢導(dǎo)檢中的應(yīng)用研究[J].中國(guó)數(shù)字醫(yī)學(xué)，2021，16（1）：60-62

[4] 熊志剛，周旖旎.分時(shí)段體檢預(yù)約管理系統(tǒng)研究與設(shè)計(jì)[J].中國(guó)數(shù)字醫(yī)學(xué)，2020，15（12）：27-29，97

[5] 董秀敏.排隊(duì)論與人性化服務(wù)結(jié)合用于大批體檢人員的管理[J].中國(guó)誤診學(xué)雜志，2010，10（14）：3377

[6] 何雅慶，謝應(yīng)朗，宋勤，等.體檢排隊(duì)系統(tǒng)的理論基礎(chǔ)[J].中國(guó)醫(yī)學(xué)創(chuàng)新，2013，10（19）：139-142

[7] 何雅慶，謝應(yīng)朗，宋勤，等.體檢排隊(duì)系統(tǒng)數(shù)學(xué)模型的制作[J].中國(guó)醫(yī)藥科學(xué)，2013，3（6）：152-154

[8] 王穎純，岳磊，刑蕊，等.現(xiàn)代體檢管理信息系統(tǒng)的析與設(shè)計(jì)[J].天津理工大學(xué)學(xué)報(bào)，2011，27（4）：56-57

[9] 姜華林.基于精確覆蓋的應(yīng)用算法研究[J].電腦知識(shí)與技術(shù)，2018，14（35）：61-62

[10] 林浩.信息需求網(wǎng)絡(luò)上最優(yōu)連接問(wèn)題[J].系統(tǒng)工程學(xué)報(bào)，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下一代通信網(wǎng)精確覆蓋系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)[J].移動(dòng)通信，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] 胡沁，寧愛(ài)兵，茍海雯，等.精確覆蓋問(wèn)題的加權(quán)分治算法[J].運(yùn)籌與管理，2020，29（4）：179-186

[15] 李肯立，劉杰，楊磊，等.精確覆蓋問(wèn)題的O（1.414^n）鏈數(shù)DNA計(jì)算機(jī)算法[J].計(jì)算機(jī)研究與發(fā)展，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