'max area of islands'算法的 3D 实现过程中核心转储

Question

我正在尝试使用一种算法来解决这个问题"岛的最大面积"；在三维问题中，所以它更像是岛的最大体积。我使用了200x200x200体素的总体积作为输入，但我遇到了麻烦，因为当我输入的体积中有很大的"孤岛"时(在Ubunde终端中"堆转储"(，它不起作用。以下是我为将其应用于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

这种实施是否效率太低？我怎么能让它不那么需要内存，这样我就可以在大岛上使用它了？

非常感谢！

Answer 1

有所收获。大约需要1分钟和6GB的RAM

1. 首先我使用sklearn.image.grid_to_graph找到边，这很快
2. 接下来我构建networkx图——这是计算时间和RAM使用的瓶颈
3. 最后，我找到了这个图中所有连通的子图，并返回

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