3

我正在启动一些 lua 脚本，似乎陷入了一个简单的问题。

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

这是我的注释代码。每次我运行它时，我都会得到一个“尝试索引字段'？' （零值）”（我觉得解决方案很简单，但我似乎无法解决问题。任何帮助将不胜感激）：

function adj(bodies) --returns, from a 1d array of vertices called "bodies", a square adjacency matrix (a matrix of size number_of_vertices x number_of_vertices that tells, with a ones, if vertices are connected, or with 'infs' if they are not connected)
    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 is another function I wrote to see if, well, two particular vertices are actually connected. If they are, distance is 1, if not, distance is inf.
                dist[i][j] = 1
            else dist[i][j] = math.huge
            end
        end
    end
    return adjMatrix
end

function PhysicsDebugDraw:fw(adjMatrix) --I pass adjMatrix to this function

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]) -- the problem is here I suspect...
            end
        end
    end
    return d
end
4

1 回答 1

1

您没有显示其结构adjMatrix或其布局的实际外观，但从您的三重嵌套循环来看，它的用法可能不正确。

请注意 variablesk和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持有key部分是一个合理的开始。

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返回一个方形矩阵。那就是它的宽度==高度
  • “空”单元格表示为无穷大
  • 与表的（或python dict）转换后adj的行和列是连续的
  • 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-21T18:24:23.077 回答