數學模型作業（3）

1. 數學模型作業（2）中計算歐式距離有誤，已更改。
2. 內容（程式碼）接數學模型作業（2）
3. 初學python和數學模型，不足之處請大佬指出。
4. 給個贊（上次已經騙過關注了~~~）

0. 匯入相關引數

shape = 613
alpha1 = 25
alpha2 = 15
beta1 = 20
beta2 = 25
theta = 30
delta = 0.001

1. 建立 List 格式的垂直校正點集合 V 和水平校正點集合 H，儲存在一個 txt檔案中。

# 建立垂直校正點集合V和水平校正點集合H
V = []
H = []
VH = []
for i in range(0, shape):
    if prop[i] == 1:
        V.append(i)
    if prop[i] == 0:
        H.append(i)
VH = V + H
file = open('校正點集合.txt', 'w')
for i in range(len(VH)):
    s = str(VH[i]) + '\n'
    file.write(s)
file.close()

2. 用 python 輸出減少邊之後最短路模型的鄰接矩陣，存放在
   excel 檔案中。

• 分析：
  （1） 剪枝可以剪去任意點為起點到垂直校正點不符合垂直校正條件的枝
  （2）剪枝可以剪去任意點為起點到水平校正點不符合水平校正條件的枝
  （3） 剪枝可以剪去以B點為終點，距離超過$\theta /\delta$的枝
• 安裝gurobi，參考另一篇（Gurobi9.0.3安裝）
• 將距離矩陣dist轉換為tupledict型別，用dict_dist存放鄰接矩陣（要呼叫gurobi庫：from gurobipy import *）

# 將距離矩陣dist轉換為tupledict型別，用dict_dist存放鄰接矩陣
dict_dist = {}
for i in range(shape):
    for j in range(shape):
        dict_dist[i, j] = dist[i][j]
dict_dist = tupledict(dict_dist)

• 剪枝實現

# step1:剪去到垂直校正點不符合要求的邊
for i in range(1, shape-1):
    for j in V:
        if dist[i][j] > min(alpha1, alpha2) / delta:
            dict_dist[i, j] = 0
# step2:剪去到水平校正點不符合要求的邊
for i in range(1, shape-1):
    for j in H:
        if dist[i][j] > min(beta1, beta2) / delta:
            dict_dist[i, j] = 0
# step3:剪去距離終點B超過30000m的邊
for i in range(shape-1):
    if dist[i][shape-1] > theta / delta:
        dict_dist[i, shape-1] = 0
# 定義邊集
edge = []
for i in range(shape):
    for j in range(shape):
        if dict_dist[i, j] != 0:
            edge.append((i, j))
print("剪枝之後的邊數：", len(edge))

• 鄰接矩陣存入excel表格

# 將 剪枝後的鄰接矩陣寫入到 dict_dist_save.xlsx 中
dict_dist_save = np.zeros(shape=(shape, shape))
for i in range(shape):
    for j in range(shape):
        dict_dist_save[i][j] = dict_dist[i, j]
dict_dist_save = pd.DataFrame(dict_dist_save)
writer = pd.ExcelWriter('dict_dist.xlsx')
dict_dist_save.to_excel(writer, 'sheet1')
writer.save()

3. 結果