在Lua中迭代2D数组

2013-7-21 19:49:13
收藏：0
阅读：115
评论：1

我开始一些lua脚本，并似乎被一个简单的问题困住了。

实际上，我正在尝试实现一个 Floyd-Warschall 算法，计算图中每个顶点之间所有最短路径（http://en.wikipedia.org/wiki/Floyd–Warshall_algorithm 为算法的简要解释）。它最初是用python编写的（这是代码https://gist.github.com/DavidCain/4032399）。我的版本略有不同，为了使它适合我的主代码，但基本上是相同的东西。

这是我的注释代码。每次运行时，我都会得到一个“attempt to index field '?' (A nil value)”错误（我觉得解决方案足够简单，但似乎无法解决。感谢任何帮助）：

function adj(bodies) --返回一个正方形邻接矩阵（一个大小为number_of_vertices x number_of_vertices的矩阵，如果顶点被连接，则以1告诉，如果未连接，则为“infs”）的1d顶点数组中的“bodies”
    n = table.getn(bodies)
    dist = {}
    for _,i in pairs(bodies) do
        dist[i] = {}
        for _,j in pairs(bodies) do
            if i == j then
                dist[i][j] = 0
            end
            if areConnected(i,j) == true then --areConnected是我编写的另一个函数，用于查看实际上两个特定顶点是否连接。如果是，则距离为1，如果不是，则距离为inf。
                dist[i][j] = 1
            else dist[i][j] = math.huge
            end
        end
    end
    return adjMatrix
end

function PhysicsDebugDraw: fw（adjMatrix） - 我将adjMatrix传递给此函数

d = adjMatrix

    for _,k in pairs(d) do
        for _,i in pairs(d) do
            for _,j in pairs(d) do
                d[i][j] = math.min(d[i][j], d[i][k] + d[k][j]) - 问题可能在这里...
            end
        end
    end
    return d
end
点赞
用户234175
用户234175

你没有展示 adjMatrix 的结构或其实际布局，但是从你的三重嵌套循环中可以看出，它的使用可能是不正确的。

注意，这里的变量 k、i 和 j：

for _,k in pairs(d) do
  for _,i in pairs(d) do
    for _,j in pairs(d) do
      d[i][j] = math.min(d[i][j], d[i][k] + d[k][j])
    end
  end
end

不是你的 adjMatrix 的键，而是键值对的值部分。请记住，pairs 在每次迭代时返回键和值。但是，在最里层的循环中，你使用 值 作为键来访问 adjMatrix 的内容。

没有看到 adjMatrix 的实际结构，很难建议一个可以正确迭代它的解决方案。但是将 k、i 和 j 保持为键的部分是一个合理的开始。

for k in pairs(d) do
  for i in pairs(d) do
    for j in pairs(d) do
      d[i][j] = math.min(d[i][j], d[i][k] + d[k][j])
    end
  end
end

请注意，如果你的 adjMatrix 使用数字作为键，并且是连续的（没有跳过任何数字），则可以使用 #adjMatrix 而不是 pairs(adjMatrix)。

编辑： 查看您的 Python 版本后，我作出了以下观察：

  • adj 返回类似正方形矩阵的东西，其宽度 == 长度
  • “空”单元格表示为无穷大
  • 将 adj 转换后，表格（或 Python 字典）的行和列是连续的
  • fw 制作了 g 的“浅”副本

假设上述不变量是正确的（如果它们不是，请告诉我），那么以下将是在 Lua 中更忠实的翻译：

function shallow_copy(g)
  local h = {}
  for k, v in pairs(g) do
    h[k] = v
    end
  return h
  end

--[[
eg.
g = {
        {0, 3, 8, math.huge, -4},
        {math.huge, 0, math.huge, 1, 7},
        {math.huge, 4, 0, math.huge, math.huge},
        {2, math.huge, -5, 0, math.huge},
        {math.huge, math.huge, math.huge, 6, 0},
    }
--]]
function fw(g)
  local d = shallow_copy(g)
  for k = 1, #d do
    for i = 1, #d do
      for j = 1, #d do
        d[i][j] = math.min(d[i][j], d[i][k] + d[k][j])
        end
        end
        end

  return d
  end

你可以假装 end 关键字是看不见的。：P

2013-07-21 18:24:23

作者:

用户1208142

用户1208142
推荐文章