我正在嘗試對3D 問題中的“島嶼最大面積”問題使用演算法，因此它更像是島嶼的最大體積。我使用 200x200x200 體素的總體積作為輸入，但我遇到了麻煩，因為當我輸入的體積中有非常大的“孤島”（Ubunut 終端中的“核心轉儲”）時它不起作用。這是我為將其應用于我的 3D 問題所做的修改的代碼：
class Solution3D:
def dfs3D(self, grid, r, c, l):
grid[r][c][l] = 0
num = 1
lst = [(r-1, c, l), (r 1, c, l), (r, c-1, l), (r, c 1, l), (r, c, l-1), (r, c, l 1)]
for row, col, leh in lst:
if row >= 0 and col >= 0 and leh >= 0\
and row < len(grid) and col < len(grid[0]) and leh < len(grid[0][0])\
and grid[row][col][leh] == 1:
num = self.dfs3D(grid, row, col, leh)
return num
def maxAreaOfIsland3D(self, grid):
area_islands = 0
for r in range(len(grid)):
for c in range(len(grid[0])):
for l in range(len(grid[0][0])):
if grid[r][c][l] == 1:
area_islands = max(area_islands, self.dfs3D(grid, r, c, l))
return area_islands
這個實作效率太低了嗎？我怎樣才能讓它不那么需要記憶體，以便我可以在大島上使用它？
非常感謝！
uj5u.com熱心網友回復：
得到了一些東西。大約需要一分鐘和 6GB 的 RAM
- 首先我發現邊緣使用
sklearn.image.grid_to_graph，這是相當快的 - 接下來我構建
networkx圖 - 這是計算時間和 RAM 使用的瓶頸 - 最后，我在這個圖中找到所有連接的子圖并回傳
import numpy as np
import networkx as nx
import sklearn.feature_extraction.image
grid_size = 4 # manual check -> for seed 0: 38 nodes, largest subgraph has 37 connected nodes, correct
grid_size = 200
random_grid = np.random.RandomState(seed=0).randint(0, 2, size=(grid_size, grid_size, grid_size))
G = nx.Graph()
print('finding edges...')
graph = sklearn.feature_extraction.image.grid_to_graph(grid_size, grid_size, grid_size, mask=random_grid)
print('buidling graph...')
G.add_edges_from(np.vstack([graph.col, graph.row]).T)
print('finding subgraphs...')
subgraphs = nx.connected_components(G)
sorted_subgraphs = sorted(subgraphs, key=len, reverse=True)
G0 = G.subgraph(sorted_subgraphs[0])
print('Largest subgraph size: ', len(G0))
Largest subgraph size: 3909288
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/353918.html
上一篇：對E(startTime,endTime)的排序串列進行二分搜索，以查找與給定時間范圍(t1,t2)匹配的所有E
下一篇：基于圖堆的優先佇列實作