用 Python 做商管程式設計（一） Week 5e

05-e01 旅行者問題
Logistics and transportation 物流與運輸
Travelling salesperson problem(TSP)
定義 : 從某點出發，經過每個點恰好一次，且回到原點，找最短距離。


greedy 走法 :
在一開始先往距離最近點出發，
在每一個點都往尚未走過且最近的點移動，
重複直到走回原點。

05-e02 TSP實作
---code
# set up the distance matrix
numLoc  = 5
dst = [[0, 9, 6, 7, 4],
              [9, 0, 5, 9, 6],
     [6, 5, 0, 3, 1],
     [7, 9, 3, 0, 4],
     [4, 6, 1, 4, 0]]

origin = 0
# tour : a list that will contain the solution
# tourLen : the total distance of the solution
# unvisited : a list that contains those unvisited locations at any time
tour = [origin]
tourLen = 0
unvisited = []

for i in range(numLoc):
unvisited.append(i)

unvisited.remove(origin)

# print(tour,tourLen,unvisited)

cur = origin
for i in range(numLoc-1):
# find the next location to visit
next = -1
minDst = 999
for j in unvisited:
if dst[cur][j] < minDst:
next = j
minDst = dst[cur][j]
# update tour, unvisited, tourLen, cur
tour.append(next)
cur = next
unvisited.remove(next)
tourLen += minDst
print(tour,tourLen)
#back to origin
tour.append(origin)
tourLen += dst[cur][origin]
#print
print(tour,tourLen)

---
05-e03 用檔案輸入資料
同上TSP，使用者自己輸入距離
code 部分 numLoc , dst 做修正
---code
numLoc = int(input())
dst = []
for i in range(numLoc):
dst.append(input().split()) #空格切開,以list形式append
for j in range(numLoc):
dst[i][j] = int(dst[i][j])
---
用檔案輸入
同目錄下新增一個檔案 : TSP_in.txt
輸入測試檔案，例如:
3
0 3 8
3 0 5
8 5 0

打開cmd ，移動到該目錄，python xxx.py < TSP_in.txt
用 " < " 這個符號，即可讓檔案讀入右方檔案資料