我有一個(gè) 8x10 矩陣，里面有一些方塊：no = [(2,4),(3,4),(6,4),(7,4),(2,5),(3,5),(6,5),(7,5)]我需要弄清楚兩點(diǎn)之間的最短（曼哈頓）路徑是否作為嵌套元組（如 ((0,5),(6,2)) 提供給此函數(shù)）包含任何塊，并圍繞它重新路由.現(xiàn)在要做到這一點(diǎn)，我試圖以應(yīng)用為歐氏距離的作品，要看到，如果邏輯?是之間的界限一和乙通過增加從距離一到?從距離?到乙，看它是否等于A到B，但我不相信數(shù)學(xué)...def manhattan_dist(move): #order doesn't matter a = move[0][0] b = move[0][1] c = move[1][0] d = move[1][1] mandist = abs(a-c)+abs(b-d) if (any (abs(a-box[0])+abs(b-box[1])) == (mandist-(abs(c-box[0])+abs(d-box[1]))) for box in no): print("blocked") #calculate go-around logic return mandist它打印 "blocked" for manhattan_dist(((0,1),(0,7)))，所以我知道我在 python 中也做錯(cuò)了。
2 回答
呼啦一陣風(fēng)
TA貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超6個(gè)贊
由于缺乏代表而回答而不是評(píng)論（......我是新來的）。
在我看來有點(diǎn)不明確。曼哈頓距離沒有一條最短路徑……事實(shí)上，根據(jù)定義，它有許多最短路徑。
所以也許試著澄清你的意思？
順便說一句，如果您想知道曼哈頓的任何路徑是否被阻塞，那么這僅意味著您有一個(gè)帶有
min([a, c]) < box[0] < max([a, c]) and min([b, d]) < box[1] < max([b, d])
由于評(píng)論中的討論而進(jìn)行編輯：
首先，總是有精確的abs(a-c) + abs(b-d) 選擇 abs(a-c)具有最小曼哈頓距離的路徑。（對(duì)于錯(cuò)誤的符號(hào)表示抱歉；只是遵循問題參數(shù)，不幸的是缺乏乳膠支持）。
如果你正確地通過幾何體，所有被阻擋的最小路徑都非常棘手，不會(huì)很快。我沒有立即看到避免循環(huán)遍歷所有路徑的方法，通過將路徑分類為分層樹并在方塊被阻塞時(shí)刪除完整分支來獲得一些優(yōu)化......
有只小跳蛙
TA貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超8個(gè)贊
現(xiàn)在要做到這一點(diǎn)，我試圖應(yīng)用適用于歐幾里德距離的邏輯，通過將 A 到 C 的距離添加到 C 到 B 的距離并查看它是否等于從 A 到 B
您在此處使用的數(shù)學(xué)概念稱為“度量”。這只是您已經(jīng)熟悉的歐幾里得距離的概括。有關(guān)詳細(xì)信息，請(qǐng)參閱維基百科文章。曼哈頓距離滿足度量的所有要求。這意味著，你可以放心，如果d(A, B) + d(B, C) = d(A, C)在B一些最短路徑上的謊言之間A和C。與歐幾里德距離不同，從A到到的路徑可能有許多C相同的距離，其中許多路徑可能經(jīng)過B。
添加回答
舉報(bào)
0/150
提交
取消