專(zhuān)家、醫(yī)生和科學(xué)家表示，為了限制冠狀病毒感染，人們?cè)谏缃唤佑|中應(yīng)保持至少 1 米的人際社交距離。但是，獨(dú)自呆在家里，被感染的風(fēng)險(xiǎn)為零。本文不打算談?wù)撚嘘P(guān)冠狀病毒的醫(yī)學(xué)或科學(xué)新聞。它將提出一種替代算法，用于在明確定義的區(qū)域內(nèi)進(jìn)行人員分布，以使他們盡可能遠(yuǎn)離。顯然，所提出的方法不是解決問(wèn)題的最佳解決方案之一；它基于蒙特卡洛系統(tǒng)。該系統(tǒng)提供了一種最簡(jiǎn)單的人員分配方式。

目標(biāo)
該程序的最終目標(biāo)是將一定數(shù)量的人放置在特定的空間中，使他們之間的距離足夠遠(yuǎn)，以避免病毒傳播的風(fēng)險(xiǎn)?？捎每臻g由一個(gè)網(wǎng)格或 N × M 方陣表示。人由同一網(wǎng)格上的標(biāo)記表示。為了實(shí)現(xiàn)這一目標(biāo)，有許多方法和許多數(shù)學(xué)和 IT 程序。無(wú)論如何，它是一個(gè)旨在最大化人與人之間距離的系統(tǒng)。該問(wèn)題可以通過(guò)使用線性規(guī)劃系統(tǒng)、非線性規(guī)劃系統(tǒng)、遞歸算法或使用蒙特卡羅研究來(lái)解決。顯然，后者不能確保出色的結(jié)果，但對(duì)于大多數(shù)應(yīng)用程序來(lái)說(shuō)，它是更復(fù)雜和要求更高的程序的有效替代方案。

蒙特卡洛方法
蒙特卡洛方法是一種基于隨機(jī)抽樣獲得數(shù)值結(jié)果的計(jì)算方法。它用于通過(guò)模擬獲得估計(jì)。它基于一種算法，該算法生成一系列彼此不相關(guān)的隨機(jī)數(shù)，這些隨機(jī)數(shù)遵循這種現(xiàn)象的可能分布。

網(wǎng)格
為了表示空間上的人，我們可以使用由許多單元格組成的 2D 網(wǎng)格 (N × M)。我們可以將網(wǎng)格或矩陣想象成一個(gè)棋盤(pán)，上面放置了一些人或物體（圖 1）。網(wǎng)格按行和列組織，因此任何編程語(yǔ)言都可以輕松管理它。組織、填充、滾動(dòng)和查詢矩陣相對(duì)容易。為了獲得這些結(jié)果，我們可以使用兩個(gè)嵌套的迭代循環(huán)和一些“if”條件。網(wǎng)格（方陣）代表人們可以在上面的有用空間。每個(gè)單位對(duì)應(yīng)1米；因此，每邊10個(gè)方格組成的網(wǎng)格相當(dāng)于100平方米的面積。該算法考慮了一個(gè)人和另一個(gè)人之間的傾斜距離。在橫向位置的情況下，將使用勾股定理計(jì)算距離。

圖 1：網(wǎng)格類(lèi)似于棋盤(pán)，棋子必須放在盡可能遠(yuǎn)的位置。

我們可以使用什么編程語(yǔ)言？
這是計(jì)算機(jī)程序員最關(guān)鍵的問(wèn)題之一。有數(shù)百種編程語(yǔ)言，每種都有其優(yōu)點(diǎn)和缺點(diǎn)。我們算法面臨的問(wèn)題與研究有關(guān)。這是一個(gè)涉及數(shù)十億次迭代的蠻力程序。很明顯，為了我們的目的，必須使用一種速度極快的編程語(yǔ)言?？梢允褂酶?jiǎn)單、更圖形化的語(yǔ)言更好地以圖形格式表示最終信息，但我們決定考慮速度和性能方面，以涵蓋執(zhí)行期間的最高計(jì)算次數(shù)。此外，為了提供通用代碼，我們更喜歡使用適用于任何環(huán)境和任何操作系統(tǒng)的 C 語(yǔ)言。

算法
該過(guò)程的算法非常簡(jiǎn)單（圖 2）。令人驚訝的不是真正的方法，而是代碼執(zhí)行的大量工作。實(shí)際上，在無(wú)限循環(huán)中，地圖不斷被破壞和重建以尋找最佳解決方案。C 語(yǔ)言的速度有助于實(shí)現(xiàn)更實(shí)用、更強(qiáng)大的搜索。代碼執(zhí)行以下階段：變量和函數(shù)的準(zhǔn)備以及主函數(shù)的執(zhí)行。在其中，循環(huán)執(zhí)行以下任務(wù)：重置網(wǎng)格，在網(wǎng)格上隨機(jī)放置人口，以及確定（打?。┳罴丫嚯x。所有這些工作都以非常高的速度進(jìn)行。

圖 2：程序流程圖

軟件
您將找到本文所附的程序源代碼 (.C)。它分為幾個(gè)邏輯部分。它從包含文件開(kāi)始，其中加載了軟件中使用的函數(shù)的原型，例如在數(shù)學(xué)庫(kù)中。然后我們可以找到列數(shù)、行數(shù)、人數(shù)等全局值的定義。這些值在整個(gè)程序中是全局可見(jiàn)的。用戶可以自由修改這三個(gè)值（圖 3），但重要的是要記住，如果值太高，搜索時(shí)間會(huì)受到影響。

圖 3：您可以修改三個(gè)定義來(lái)改變研究領(lǐng)域。

程序的下一部分包含函數(shù)的原型。然后我們可以看到全局變量的定義。最后，“main()”函數(shù)開(kāi)始。它包含一個(gè)非常短的無(wú)限循環(huán)，其中重復(fù)以下功能：

電網(wǎng)重置；

人口的隨機(jī)分布；

計(jì)算最佳距離；

確定最佳結(jié)果的可視化；

將結(jié)果導(dǎo)出到 Octave。

這些任務(wù)被循環(huán)和無(wú)限期地執(zhí)行，因?yàn)樗鼈儼凇皐hile”循環(huán)中。源代碼中使用了以下 UDF 函數(shù)：

第一個(gè)函數(shù)是“print_matrix()”。它在屏幕上顯示矩陣。

下一個(gè) UDF 函數(shù)是“reset_matrix()”。它使用雙嵌套循環(huán)將存儲(chǔ)“-”字符的網(wǎng)格歸零。

下一個(gè)函數(shù)是“place_random_people()”。它將人置于矩陣內(nèi)。條件控制確保良好的定位并在單元格已被人占用時(shí)丟棄隨機(jī)數(shù)，重復(fù)提取。

下一個(gè) UDF 浮點(diǎn)函數(shù)是“calculate_distance()”。它計(jì)算兩點(diǎn)之間的距離。它計(jì)算并返回人與人之間的最小距離。注意，如果點(diǎn)是傾斜排列的，軟件使用勾股定理來(lái)計(jì)算相對(duì)距離。

下一個(gè)函數(shù)“export_coords()”將數(shù)據(jù)導(dǎo)出到 Octave 數(shù)學(xué)環(huán)境，以優(yōu)雅地顯示結(jié)果。

添加特定功能后，軟件總是會(huì)生成不同的隨機(jī)序列。事實(shí)上，在清單的開(kāi)頭插入以下語(yǔ)句就足夠了：

srand (時(shí)間 (NULL));

通過(guò)消除這條指令，生成的數(shù)字的順序總是相同的，這對(duì)調(diào)試程序很有用。目前，該程序會(huì)找到人與人之間的最小距離，因此會(huì)最大化這個(gè)數(shù)字。要在代碼中實(shí)現(xiàn)的其他標(biāo)準(zhǔn)可以如下：

最小距離的最大化

平均距離最大化

不同區(qū)域的距離最大化

編譯
編譯源代碼很容易。您無(wú)需修改代碼即可將源代碼與其他編譯器一起使用。如下圖，根據(jù)使用的編譯器，可以找到一些編譯的例子。一些解決方案為速度優(yōu)化提供支持：

海合會(huì)

gcc distance.c -Wall -O3

TCC

tcc 距離.c

橙色 C/C++ 編譯器

occ 距離.c

實(shí)驗(yàn)
我們已準(zhǔn)備好嘗試該程序。第一個(gè)要進(jìn)行的測(cè)試涉及小范圍內(nèi)的幾個(gè)人。要設(shè)置的值是：

/*——————定義——————*/

#define 列 6

#define 行 6

#定義人 6

使用命令“distance.exe”啟動(dòng)程序執(zhí)行后，我們將在監(jiān)視器上看到第一個(gè)結(jié)果，顯示網(wǎng)格上人員的最佳配置（圖 4）。如果計(jì)算機(jī)找到更好的結(jié)果，這些結(jié)果將顯示在屏幕上并作為新的解決方案呈現(xiàn)。這些解決方案尋找人與人之間的最大距離。

圖 4：6 人的 6 × 6 網(wǎng)格的解決方案

更強(qiáng)大的實(shí)驗(yàn)可以在更大的區(qū)域內(nèi)使用更多的人進(jìn)行。下一個(gè)實(shí)驗(yàn)應(yīng)具有以下值：

/*——————定義——————*/

#define 列 20

#define 行 10

#定義人 16

在這種情況下，處理步驟更重。解決方案的顯示速度要慢得多，而且不是最好的。圖 5顯示了一種可能的解決方案，但不是最佳解決方案。

圖 5：16 人的 20 × 10 網(wǎng)格的解決方案

變化
兩個(gè)人之間的距離可以用不同的方式和許多標(biāo)準(zhǔn)來(lái)衡量（圖 6）。一種方法是將距離計(jì)算為理論矩形三角形的斜邊，如果人們傾斜排列的話。這種計(jì)算是最真實(shí)的，因?yàn)樗ǔＲ赃@種方式發(fā)生。

d = sqrt([cat1 × cat1] + [cat2 × cat2]);

另一種方法將距離視為兩個(gè)人之間的平方數(shù)。在這種情況下，人的位置是直角還是斜角都沒(méi)有區(qū)別。

d = abs(cat1) + abs(cat2);

程序員可以選擇計(jì)算距離的首選方法。

圖 6：測(cè)量?jī)牲c(diǎn)之間距離的不同標(biāo)準(zhǔn)

圖形結(jié)果
C語(yǔ)言程序直接在視頻上顯示人的位置地圖。這種可視化是在終端上進(jìn)行的；因此，圖形方面不是非常令人愉快。然而，該程序提供了一個(gè)數(shù)據(jù)導(dǎo)出功能，允許將信息和點(diǎn)的坐標(biāo)導(dǎo)出到文本文件，并允許作為腳本直接導(dǎo)入 Octave 數(shù)學(xué)環(huán)境。這樣，從圖形的角度來(lái)看，地圖與人的可視化更加令人愉快和有吸引力。正是當(dāng)程序找到一個(gè)新的解決方案時(shí)，除了在監(jiān)視器上顯示結(jié)果之外，它還將它們作為 Octave 的腳本保存到一個(gè)文本文件 (distance.m) 中，其中包含繪制圖形地圖的有用信息（圖 7）。這樣，顯示的地圖將與文本地圖相同，但具有更加美觀和優(yōu)雅的圖形外觀。

圖 7：文字地圖和圖形地圖是等價(jià)的。

下面，我們可以看到一個(gè) Octave 腳本的示例：

堅(jiān)持，稍等;

情節(jié)（19、9、'b*'、'線寬'、11）；

情節(jié)（15、9、'b*'、'線寬'、11）；

情節(jié)（12、9、'b*'、'線寬'、11）；

情節(jié)（ 9 ， 9 ， 'b*' ， '線寬' ， 11）；

線（[-0.5,19.500000]，[-0.500000，-0.500000]，'顏色'，'k'）；

線（[-0.5,19.500000]，[0.500000,0.500000]，'顏色'，'k'）；

線（[-0.5,19.500000]，[1.500000,1.500000]，'顏色'，'k'）；

線（[-0.5,19.500000]，[2.500000,2.500000]，'顏色'，'k'）；

線（[18.500000,18.500000]，[-0.5,9.500000]，'顏色'，'k'）；

線（[19.500000,19.500000]，[-0.5,9.500000]，'顏色'，'k'）；

暫緩；

非常大的數(shù)字！

人在網(wǎng)格上的定位相當(dāng)于組合計(jì)算的“簡(jiǎn)單組合”的計(jì)算。簡(jiǎn)單組合的數(shù)量如圖 8所示。以下是一些顯著結(jié)果的例子：

6行×6列×6人：1,947,792種組合

20行×10列×16人：169,152,626,591,028,520,278,300種組合

50行×20列×40人：555,974,423,571,664,033,815,804,589,243,553,849,851,258,056,649,719,919,687,842,027,223,208,475種組合

我們可以立即理解，對(duì)于這些非常高的數(shù)字，蠻力方法是無(wú)法解決的。

圖 8：簡(jiǎn)單組合的公式

結(jié)論
本文介紹的研究方法不是最好的，也無(wú)法找到最好的結(jié)果。獲得的組合可用于對(duì)本文主題中提出的問(wèn)題進(jìn)行一般估計(jì)。蒙特卡洛方法有很多限制，例如它的相對(duì)緩慢。否則不可能，因?yàn)槌绦蚩梢陨傻臄?shù)據(jù)和信息數(shù)量非常多（數(shù)十億個(gè)組合），沒(méi)有計(jì)算機(jī)或人類(lèi)能夠計(jì)算出這樣的數(shù)字。對(duì)于相對(duì)較少的信息，達(dá)到最終解決方案很簡(jiǎn)單。但是如果對(duì)象的數(shù)量或網(wǎng)格的尺寸增加，計(jì)算時(shí)間將成倍增長(zhǎng)。增加搜索參數(shù)很不方便。該程序采用的方法也被定義為“蠻力”。計(jì)算上，這是一項(xiàng)非常繁重的工作，不能確定最終結(jié)果，并且可能會(huì)多次重復(fù)相同的解決方案。但是這種方法對(duì)于所有那些運(yùn)行參數(shù)和因變量非常多的研究應(yīng)用來(lái)說(shuō)確實(shí)很有用。有時(shí)，尋找可能的解決方案可能會(huì)持續(xù)一整夜，尤其是在網(wǎng)格非常大且人數(shù)眾多的情況下。搜索時(shí)間還取決于計(jì)算機(jī)的速度和使用的編譯器類(lèi)型。本文中進(jìn)行的實(shí)驗(yàn)可以為程序員創(chuàng)建更復(fù)雜和更復(fù)雜的程序提供新的思路。它代表了未來(lái)功能發(fā)展的起點(diǎn)。該程序的一個(gè)有趣的實(shí)現(xiàn)也可以包含人工智能。為這個(gè)非常復(fù)雜的目的確定最終解決方案可能很有用。本文所附的操作代碼是用 C 語(yǔ)言編寫(xiě)的，可以很容易地翻譯成任何其他編程語(yǔ)言。程序注釋足夠，任何程序員也可以找到其他點(diǎn)來(lái)修改和改進(jìn)它。除了提供教學(xué)實(shí)用程序之外，本文中采用的過(guò)程在代碼編寫(xiě)和使用方面都非常有趣。該系統(tǒng)是完全自主的，因?yàn)槌绦蛱峁┑慕Y(jié)果是不可預(yù)測(cè)的，因?yàn)閿?shù)據(jù)和信息是隨機(jī)處理的。任何程序員也可以找到其他點(diǎn)來(lái)修改和改進(jìn)它。除了提供教學(xué)實(shí)用程序之外，本文中采用的過(guò)程在代碼編寫(xiě)和使用方面都非常有趣。該系統(tǒng)是完全自主的，因?yàn)槌绦蛱峁┑慕Y(jié)果是不可預(yù)測(cè)的，因?yàn)閿?shù)據(jù)和信息是隨機(jī)處理的。任何程序員也可以找到其他點(diǎn)來(lái)修改和改進(jìn)它。除了提供教學(xué)實(shí)用程序之外，本文中采用的過(guò)程在代碼編寫(xiě)和使用方面都非常有趣。該系統(tǒng)是完全自主的，因?yàn)槌绦蛱峁┑慕Y(jié)果是不可預(yù)測(cè)的，因?yàn)閿?shù)據(jù)和信息是隨機(jī)處理的。

審核編輯 黃昊宇