在这种特殊情况下如何避免嵌套 for 循环？

Question

我写了一个BFS（Breadth First Search）路径规划算法。它在小网格（例如 15 x 15）上工作得很好，但是当涉及到更大的网格（例如 150 x 250）时，它就很糟糕了。使用 tic 和 toc 命令，我发现它花费最多时间的地方（效率最低的位）并且问题与嵌套有关循环。我知道使用嵌套 for 循环被认为是不好的，我需要帮助将其替换为其他东西（尽可能避免使用循环）。

for j=1:length(F)
    for k = 1:length(Closed)
        if(F(j) == Closed(k))
            F(j) = 0;
        end
    end
end

Closed = [Closed current];

这段代码的目的是替换F的元素，也就是父节点（我们来自哪里）。这样就可以忽略任何重复。

F 是一个 1 by n 向量存储可以从当前节点移动的邻居节点。

注意：我使用的是 8-connected space，因此 n 总是小于 8。

Closed初始化为一个空向量，用于存储访问过的节点列表（水平拼接）
current是1到37901之间的数字，代表当前节点。

我知道还有一个关于嵌套循环，但我的问题不同。感谢您的帮助！

Answer 1

这段代码慢的原因不是你有嵌套循环，而是你实现了一个 O(n²) 算法。

您应该使用逻辑数组来指示 "closed" 的节点。这将使查找更有效率。

假设您有 N = 37901 个节点。这样初始化你的 Closed 数组：

Closed = false(1,N);

现在要检查节点 F(j) 是否已关闭，您可以简单地执行 Closed(F(j))，如果它已关闭，则将是 true。

现在你的循环可以替换为

F(Closed(F)) = [];
Closed(current) = true;

因为 Closed(F) 是一个与 F 大小相同的数组，对于封闭节点也是如此。您可以使用此数组索引到 F，并删除所有关闭的节点。我正在删除那些节点，而不是为它们分配 0，以便 F 始终可以用于索引到 Closed。如果我们在那里写 0，它就不再是一个逻辑数组。如果你不需要改变 F 的形状，你必须在索引之前做一些额外的测试。

请注意 Closed = [Closed current] 也比 Closed(current) = true 慢很多，因为它创建了一个新数组，旧的 Closed 数组被复制到其中。

请注意，您可以删除代码中的嵌套循环，如下所示，但不一定会更快，因为算法仍然是 O(n²) (您正在将 F 中的每个元素与 Closed).

中的每个元素进行比较

for j=1:length(F)
   if any(F(j) == Closed)
      F(j) = 0;
   end
end

在这种特殊情况下如何避免嵌套 for 循环？

How to avoid nested for loops in this particular case?

performance

matlab

nested-loops