作為幾何演算法的軟體開發人員，我多次遇到以下問題，但我從未真正滿足于我如何解決它。
問題陳述
想象一下 3D 笛卡爾空間中的多米諾骨牌，面部持有 3D 坐標(x, y, z)。這個游戲的另一個條件是，每個坐標在游戲中只存在一次，并且準確地寫在兩塊石頭的表面上。一旦找到一對匹配的面孔，就會找到一對多米諾骨牌。路徑被定義為多米諾骨牌的有序串列，其中串列中每兩個成對的相鄰元素（多米諾骨牌）形成一個匹配。在一場多米諾骨牌游戲中可以有多條路徑。
例子
在玩排序游戲之前和之后的示例如下所示：
游戲 1：單一路徑作為結果。
游戲 2：作為結果的多條路徑。
是否有 aa) 高效和 b) 優雅的解決方案來解決這個問題？
帶有while回圈的簡單解決方案
我最好的猜測如下：
Let the input list of dominos be called list.
Let the currently forming path be an ordered list called cur_path.
Let the resulting list of paths be called results.
While (list is not empty)
If (cur_path is empty)
Draw random piece of domino from list and put into cur_path.
Continue
Else
// Search equals finding a match for open ends of cur_path,
// i.e. the first and the last domino in cur_path.
Search in list for matching domino
If (Found matching domino)
Draw found piece from list and put at correct position into cur_path
Else
// We have not found a match amongst all residual dominos.
// Store current path into result paths and begin new.
Store cur_path in results.
Clear variable cur_path.
Continue
return results
你會看到我對所有元素進行了while回圈。O(n2)。這個解決方案有兩種我不喜歡的方法。首先，我不喜歡 while 回圈，因為它們總是受限于不確定的條件。其次，我不喜歡忽略多米諾骨牌的幾何資訊來縮小匹配的搜索空間。您是否認為像邊界體積層次方法這樣的排序層次結構過于矯枉過正而無法解決這個問題？
uj5u.com熱心網友回復：
這在O(n).
這是未經測驗的 Python：
tiles_at = {} # will map coordinates to tiles.
for tile in all_tiles:
for face in tile.faces:
if face not in tiles_at:
tiles_at[face] = [tile]
else:
tiles_at[face].append(tile)
is_used = set() # will hold the used tiles
paths = [] # will hold the final answer. Does not find loops.
for face, tiles in tiles_at.items():
if 1 == len(tiles) and tiles[0] not in is_used:
# Found the start of a path.
is_used.add(tiles[0])
last_face = face
last_tile = tiles[0]
if face != tiles[0].faces[0]:
last_tile = last_tile.flip()
path = [last_tile]
# Find the path
while True:
# Find the unused face.
last_face = last_tile.faces[1]
# Find the next tile in the path, if any.
if 1 == len(tiles_at[last_face]):
break # EXIT LOOP AT END OF PATH
elif last_tile == tiles_at[last_face][0]:
last_tile = tiles_at[last_face][1]
else:
last_tile = tiles_at[last_face][0]
# We used this tile
is_used.add(last_tile)
if last_face == last_tile.faces[1]:
last_tile = last_tile.flip()
path.append(last_tile)
# and record the path
paths.append(path)
這個想法是O(n)掃描以將瓷磚的所有面添加到哈希中。掃描以查找所有可能的O(n)起點，并為每個起點掃描路徑，該路徑將在所有路徑上僅訪問每個O(n)圖塊一次。
其中，結合起來，是O(n)。
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/464739.html
上一篇：這個演算法是如何實作滑動視窗的？