今天的議題要來討論一個有趣的演算法問題 騎士旅程
其中我們不會講述過多的演算法設計
因為牽涉到太多數學及演算法設計的問題
因此將著重在給予算法後 如何將其實作出來
然後特別感謝我的大學好朋友--顏姓同學
一起熬夜研究該問題
我先附上維基的參考資料
https://zh.wikipedia.org/wiki/騎士巡邏
簡單的說 就是在一個西洋棋盤上
給你一隻騎士
要找出一個不重複卻走過棋盤上每一格的路徑
而西洋棋的騎士跟象棋中的馬走法是一樣的
乍看之下 這個問題很困難
但還好有厲害的數學家 給予了我們很好的解決方法
想法是這樣的：
在騎士開始移動前 每一個格子在棋盤上都有固定的方法可以被走到
舉例來說 在最棋盤邊角的地方
(圖是用小畫家繪製 別太苛刻)
也就是在1的位置上
騎士只能從8或6的位置走到
因此我們給定這一格的degree為2
一開始先將棋盤上每一格的degree算出
就可以先做出這樣的矩陣
一開始我們用8*8為例
而該矩陣我們稱之為degree map
而有了該矩陣後
我們只要選擇走degree值較低的路徑
就可以確定可以盡量避免走到死路
但這樣還是有個問題
就是即使在開始前degree較高的地方
也有可能因為騎士走了一段時間後讓他的degree變低
因此在這邊我們採用動態的degree map
也就是在騎士每走一步時 都去更新degree map
在了解想法後 我們的目標就很明確了
第一步 先建立degree map
第二步 建立騎士走的路徑
第三步 給定騎士開始的位置
第四步 開始旅程
第五步 輸出結果
開始吧！
首先先建立degree map與移動方位
## 產生degree map
degree_map = [[2,3,4,4,4,4,3,2],
[3,4,6,6,6,6,4,3],
[4,6,8,8,8,8,6,4],
[4,6,8,8,8,8,6,4],
[4,6,8,8,8,8,6,4],
[4,6,8,8,8,8,6,4],
[3,4,6,6,6,6,4,3],
[2,3,4,4,4,4,3,2]]
## 8個移動方位
dx = [-2, -1, 1, 2, -2, -1, 1, 2]
dy = [1, 2, 2, 1, -1, -2, -2, -1]
這一步很簡單
後面會講到自己產出degree map的方法
接著給定開始位置
## 輸入初始位置
input_num = input('請輸入位置(介在0~7)(用空格隔開):')
input_num = list(input_num.split())
[a, b] = [int(input_num[0]), int(input_num[1])]
while a < 0 or a > 7 or b < 0 or b > 7:
input_num = input('請輸入位置(介在0~7)(用空格隔開):')
input_num = list(input_num.split())
[a, b] = [int(input_num[0]), int(input_num[1])]
print(a)
print(b)
這邊讓使用者可以自行輸入開始位置
由於input函數進來的值是字串
因此將他利用split切開後在轉成數字存入list中
也用了一個簡單的例外處理
超出棋盤則要使用者重新輸入
接著產生一個可以儲存輸出結果的棋盤
## 產生棋盤
cbx = 8; cby = 8 # width and height of the chessboard
cb = [[0 for x in range(cbx)] for y in range(cby)] # chessboard
cb
裡面先填上0
接著要讓騎士開始旅程了
其中有幾點需要注意
1.不能超出棋盤
2.找下一個位置 也就是可行路徑中最小的
3.更新degree map
## 路徑及搜尋
for i in range(0, 64):
degree_map[a][b] = 0
cb[a][b] = i+1
## 在最後一步不跳出error
if cb[a][b] == 64:
break
## 找出合法路徑
available_path = []
for j in range(0,8):
if a+dx[j] >= 0 and a+dx[j] <= 7 and b+dy[j] >= 0 and b+dy[j] <= 7:
available_path.append([dx[j], dy[j]])
else:
continue
## 減去可行路徑的degree(dynamic)
possible_path = []
possible_path_degree = []
for k in range(0, len(available_path)):
degree_map[a+available_path[k][0]][b+available_path[k][1]] -= 1
possible_path.append([available_path[k][0], available_path[k][1]])
possible_path_degree.append(degree_map[a+available_path[k][0]][b+available_path[k][1]])
while min(possible_path_degree) < 0:
min_index = possible_path_degree.index(min(possible_path_degree))
del possible_path[min_index]
del possible_path_degree[min_index]
min_index = possible_path_degree.index(min(possible_path_degree))
move = possible_path[min_index]
a += move[0]
b += move[1]
上半比較簡單
因為共有64步要走 因此迴圈跑64次
然後讓騎士走到的位置上寫下這是第幾步
到最後一步直接結束
然後是把可以走的路徑寫到available path這個list中
再從available list為基礎調整degree
就可以找出下一步的可能走向及其degree
而當可行走法的degree為負值時 便將他從possible path刪除
最後就可以選定方向為degree最小的走法了
上面這一部分可能有一點複雜 可以多看幾次code~
最後就是將結果輸出了
for i in range(0, len(cb)):
for j in range(0, len(cb[i])):
print('%3d' % cb[i][j], end='')
print('\n')
稍微將其格式化 可以善用這個類似C的語法
有興趣的可以看看這個大大整理的很詳盡
https://www.itread01.com/content/1548549397.html
就可以把結果印出來看看啦
所以今天學到的有：
Warnsdorff演算法
格式化輸入輸出
騎士旅程的解決
而如果要從8*8擴充到無限大的棋盤應該如何做呢
其實只要改一點點的程式碼便可囉
但礙於篇幅關係 我就放在下一篇了
也要再次感謝我的大學好朋友--顏姓同學給的協助
也期待未來繼續分享各式案例給大家囉~
沒有留言:
張貼留言