如何计算所有可能路径的最小所需边数?
How to calculate minimum required edges for all possible paths?
我不是数学家,所以如果我使用了错误的词汇,请原谅。这不适用于任何作业或家庭作业。
从点 (0,0) 到 (4, -1) 有五种可能的 'taxi-cab' 路径。令 n = 点之间的绝对差之和,5。从一个到另一个的路径数 = (n * n-1) / 2 = 10。从一个点到另一个,一半 = 5.
但是当我手绘这个时,我数了 13 'edges'(正确的术语?)在所有使用的节点或顶点(?)之间。这是我想为任何 n 维图(最多 6 维)计算的数字。向量(4, -1)是如何得出13的?
如果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))
我不是数学家,所以如果我使用了错误的词汇,请原谅。这不适用于任何作业或家庭作业。
从点 (0,0) 到 (4, -1) 有五种可能的 'taxi-cab' 路径。令 n = 点之间的绝对差之和,5。从一个到另一个的路径数 = (n * n-1) / 2 = 10。从一个点到另一个,一半 = 5.
但是当我手绘这个时,我数了 13 'edges'(正确的术语?)在所有使用的节点或顶点(?)之间。这是我想为任何 n 维图(最多 6 维)计算的数字。向量(4, -1)是如何得出13的?
如果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))