資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究Python程式：查詢連線所有點的最小成本
假設我們有一個名為points的陣列，其中包含一些點，格式為 (x, y)。現在，連線兩個點 (xi, yi) 和 (xj, yj) 的成本是它們之間的曼哈頓距離，公式為 |xi - xj| + |yi - yj|。我們必須找到使所有點連線的最小成本。
因此，如果輸入類似於 points = [(0,0),(3,3),(2,10),(6,3),(8,0)]，則輸出將為 22，因為
因此，這裡的總距離為 (6+5+3+8) = 22。
為了解決這個問題，我們將遵循以下步驟：
- points_set := 一個新的集合，包含從 0 到 points 大小 - 1 的數字
- heap := 建立一個堆，包含 (0, 0) 對
- visited_node := 一個新的集合
- total_distance := 0
- 當堆不為空且 visited_node 的大小 < points 的大小時，執行以下操作
- (distance, current_index) := 從堆中刪除元素
- 如果 visited_node 中不存在 current_index，則
- 將 current_index 插入 visited_node
- 從 points_set 中刪除 current_index
- total_distance := total_distance + distance
- (x0, y0) := points[current_index]
- 對於 points_set 中的每個 next_index，執行以下操作
- (x1, y1) := points[next_index]
- 將 (|x0 - x1| + |y0 - y1| , next_index) 插入堆中
- 返回 total_distance
示例
讓我們看看以下實現，以便更好地理解：
import heapq def solve(points): points_set = set(range(len(points))) heap = [(0, 0)] visited_node = set() total_distance = 0 while heap and len(visited_node) < len(points): distance, current_index = heapq.heappop(heap) if current_index not in visited_node: visited_node.add(current_index) points_set.discard(current_index) total_distance += distance x0, y0 = points[current_index] for next_index in points_set: x1, y1 = points[next_index] heapq.heappush(heap, (abs(x0 - x1) + abs(y0 - y1), next_index)) return total_distance points = [(0,0),(3,3),(2,10),(6,3),(8,0)] print(solve(points))
輸入
[(0,0),(3,3),(2,10),(6,3),(8,0)]
輸出
22
更新於: 2021年10月4日
394 次瀏覽
廣告