方法對道路進行離散化，以的速度行走一分鐘的距離作為步長，一分鐘時間的選擇是參照問題叁的結果要求來設定的，步長。用線性插值的方法，從道路的一個方向進行線性插值，實現將每條道路離散化的目標，考慮到有些道路不是的整數倍，我們就一般情況進行討論，其分析示意圖如圖3所示。道路ab長度為個與長度的和，為了更精確處理cb段道路，那么就要考慮在cb之間是否要插入一個新的點，根據的長度不同，其對應的處理方式也有所不同。

圖3 道路離散化分析示意圖

引進臨界指數，選取大小的準那么是使盡量離散化后警車等效的平均巡邏速度和題目給定的速度〔〕的差值盡量小，經過計算得時，不再插入新的坐標點時能使整個區域的道路離散效果較好。此時，將cb段長度設定為處理，于是離散后的ab道路長度會比實際長度短些；當時，需要在兩個點之間再插入一點，因為這樣處理能使整個區域的整體道路的離散化效果比擬理想。如圖3所示，在c與b間再插入新的坐標點，插入的位置在距c點的d點處,這樣處理后所得的道路長度比實際長度長了。采用這樣的方法進行線性插值，我們使用atb編程實現對整個區域道路的離散，所得的離散結果如圖4所示，離散后共得到762個節點，比原始數據多了455個節點，離散后的節點數據見附件中的“newpottxt〞。

圖4 整個區域離散結果圖

采用這種插值方法道路離散后，將直線上的無窮多個點轉化有限個點，便于分析問題和實現相應的算法，由圖4可知，所取得的整體離散效果還是比擬理想的。

513 分區域求解警車數目的算法設計

考慮到警車配置和巡邏方案需要滿足：警車在接警后叁分鐘內趕到普通部位案發現場的比例不低于90，趕到重點部位必須控制在兩分鐘之內的要求。設計算法的目標就是求解出在滿足d1情況下，總的警車數目最小，即每個區域都盡可能多地覆蓋道路節點。由于警車的初始位置是未知的，我們可設警車初始?？奎c在道路上的任一點，即分布在圖4所示的762個離散點中的某些點節點上，總體思路是讓每兩輛車之間盡量分散地分布，一輛警車管轄一個分區，用這些分區覆蓋整個區域。

于是我們設計算法1，步驟如下所示：

step1：將整個區域預分配為個分區，每個分區分配一輛警車，警車的初始?？课恢迷O在預分配區中心的道路節點上，假設區域的中心不在道路節點上，那么將警車放在離中心最近的道路節點上；

step2：統計分區不能覆蓋的節點，調整警車的初始停靠點，使分區覆蓋盡可能多的道路節點，調整分為區內調整和區間調整方案：〔1〕區內調整按照模擬退火思想構造的函數，在區間調整調整車輛初始點的位置〔后文中有詳細說明〕，當分區內節點數較多時，調整的概率小些，分區內節點數較少時，調整的概率大些，〔2〕當區域中存在未被覆蓋的節點或節點群〔大于等于叁個節點集中在一個范圍內〕時，將警車初始位置的調整方向為朝著這些未被覆蓋的節點按一定的規那么〔在

對算法的幾點說明：

〔1〕該算法所取的車輛數是由多到少進行計算的，初始值設為20，這個值的選取是根據區域圖估算的。

(2)預分區的優點在于使警車的初始位置盡可能均勻地分散分布，警車的初始?？奎c在一個分區的中心點附近尋找得到，比起在整個區域隨機生成停靠點，計算效率明顯得到提高。

預分配之后，需要對整個區域不斷地進行調整，調整時需要考慮調整方向和 調整概率。

警車調整借鑒的是模擬退火算法的方法，為了使分區內包含道路節點數較多的分區的初始停車點調整的概率小些，而分區內包含道路節點數的少的分區內的初始停車點調整的概率大些，我們構造了一個調整概率函數,

〔1〕

〔1〕式中，均為常數，為整個區域車輛數，為第分區內覆蓋的節點數，為時間，同時也能表征模擬退火的溫度變化情況：初始溫度較高，區域調整速度較快，隨著時間的增加，溫度不斷下降，區域調整速度逐漸變慢，這個調整速度變化也是比擬符合實際情況的。

由式〔1〕可以得出調整概率函數，假設在相同的溫度〔時間〕的條件下，由于總的車輛數目是定值，當時，即第分區內的節點數大于第分區的節點數時，分區調整的概率大些，分區的調整概率小些。分析其原因：當分區內包含了較多的節點個數時，該分區的警車初始?？课恢眠x取地比擬適宜了，而當分區內包含的道路節點數較少時，說明警車的初始?？课恢脹]有選好，需要更大概率的調整，這樣的結論也是比擬客觀的。

對于所有分區外未被覆蓋的道路節點和很多節點〔稱之為節點群〕，用來調整警車位置遷移的方向，其分析示意圖如圖5所示。調整方案目標是使未被覆蓋的節點數盡量的少。在設計調整方向函數時，需要考慮：〔1〕節點群內節點的