如何计算所有可能路径的最小所需边数？

Question

我不是数学家，所以如果我使用了错误的词汇，请原谅。这不适用于任何作业或家庭作业。

从点 (0,0) 到 (4, -1) 有五种可能的 'taxi-cab' 路径。令 n = 点之间的绝对差之和，5。从一个到另一个的路径数 = (n * n-1) / 2 = 10。从一个点到另一个，一半 = 5.

但是当我手绘这个时，我数了 13 'edges'（正确的术语？）在所有使用的节点或顶点（？）之间。这是我想为任何 n 维图（最多 6 维）计算的数字。向量(4, -1)是如何得出13的？

Answer 1

如果x-difference为dx，y-difference为dy，则边数为

NE = dx*(dy+1) + dy*(dx+1)

（水平边数+垂直边数）

对于您的案例 dx=4, dy=1，并且 NE =4*2+5*1=13
对于 dx=4, dy=2 NE= 4*3+5*2=22

相同的逻辑适用于 n-dimensional 网格。比如3D有

dy*(dx+1)*(dz+1) vertical edges (along OY)
dx*(dy+1)*(dz+1) horizontal edges (along OX)
dz*(dx+1)*(dy+1) edges in depth (along OZ)

为 3x3x3 立方体提供 144 条边

简单Python（适用于任何语言）程序来计算任何维度的数量：

def numedges(dims:list):
    prod = 1
    for dim in dims:
        prod *= (dim + 1)
    ne = 0
    for dim in dims:
        ne += prod * dim // (dim+1)    #integer division
    return ne

print(numedges([2,4]))
print(numedges([3,3,3]))
print(numedges([2,3,4,5,6,7]))

>>>
22
144
96408

使用reduce：

from functools import reduce
def numedges(dims:list):
    product = reduce(lambda x,y: x*(y+1), dims, 1)
    return(reduce(lambda x,y: x+product*y//(y+1), dims, 0))

如何计算所有可能路径的最小所需边数？

How to calculate minimum required edges for all possible paths?

geometry

nodes

graph-theory

edges

vertices