数学研发论坛

 找回密码
 欢迎注册
查看: 426|回复: 15

[讨论] 有多少条路径:通过一个含单向边的蜂窝状网络

[复制链接]
发表于 2022-11-17 11:48:13 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
通过一个蜂巢状网络从A走到B,其中有向边只能单向通过,任何边都不许重复经过。问有多少条可行路径。
二极管路线.png
精华
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-11-17 12:58:45 | 显示全部楼层
我只会一个思路,穷举法!然后看其中哪些是符合要求的。给每一个节点搞上编号,然后全排列,
然后看哪些排列符合要求,删除掉那些不符合要求的排列,然后问题解决。
这是我能想到的唯一的解决办法!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-11-17 14:16:13 | 显示全部楼层
设白色反向箭头为 n 个,则路径层数为 `2n+1`, 记第 i 层的路径数为 `{a_i}`, \[\begin{equation}a_i=\begin{cases}
i+1, & \text{ if } i\le n+1\\
2n+3-i, & \text{ if } i >n+1
\end{cases}\end{equation}\]不通过任何白色箭头的路径数为\[\begin{equation} a_1\cdot(a_2-1)\cdot a_3\cdot\cdots\cdot(a_{2n}-1)\cdot a_{2n+1}:=A \end{equation}\]
一、假定不通过第i-2层和第i+2层、只通过第 i 层的白色箭头,则仅影响第i-1和第i+1层的可行路径,不会影响更远。相关的路径可分为两类:
1、通过前一层和第 i 层的上半层,过白色箭头后转到第 i 层和后一层的下半层,所以该类路径数为\[\begin{equation}
\frac{a_{i-1}}2\cdot\frac{a_{i}-1}2\cdot\frac{a_{i}-1}2\cdot\frac{a_{i+1}}2
\end{equation}\]2、上述路径的镜像路径。
所以总的可选路径数为2·(3), 即\[\begin{equation}
\frac{a_{i-1}\cdot(a_{i}-1)^2\cdot a_{i+1}}8
\end{equation}\]相对于不过白色箭头通过这3层的路径数\(a_{i-1}(a_i-1)a_{i+1}\),单独通过第 i 层白色箭头产生的路径倍增系数为\[\begin{equation}\frac{a_{i}-1}8\end{equation}\]
二、假定不通过第i-4层和第i+2层、只通过第 i-2 层和第 i 层的白色箭头,则将影响第i-3,i-1和i+1层的可行路径,不会影响更远。相关的路径可分为两类:
1、通过前一层和第 i-2 层的上半层,过 i-2 层的白色箭头后转到第 i-1 层和第 i 层下半层,通过第 i 层白色箭头后转到第 i 层和第 i+1 层上半层,所以该类路径数为\[\begin{equation}
\frac{a_{i-3}\cdot(a_{i-2}-1)^2\cdot a_{i-1}\cdot(a_{i}-1)^2\cdot a_{i+1}}{128}
\end{equation}\]
2、上述路径的镜像路径。
所以总的可选路径为2·(6), 即\[\begin{equation}
\frac{a_{i-3}\cdot(a_{i-2}-1)^2\cdot a_{i-1}\cdot(a_{i}-1)^2\cdot a_{i+1}}{64}
\end{equation}\] 相对于不过白色箭头通过这5层的路径数产生的路径倍增系数为\[\begin{equation}
\frac{a_{i-2}-1}8\cdot\frac{a_{i}-1}8
\end{equation}\]可见通过各层白色箭头的路径倍增系数不受白色箭头是否相邻的影响。
所以通过第`i_1,i_2,\cdots,i_r`层白色箭头的可行路径数为\[
A\cdot \prod^r_{j=1}\frac{a_{i_j}-1}8\tag{9}\]
故全部可行路径数为\[
A \sum_{遍历组合}\cdot \prod^r_{j=1}\frac{a_{i_j}-1}8=A\cdot\left(1+\frac{a_2-1}8\right)\left(1+\frac{a_4-1}8\right)\cdot\cdots\cdot\left(1+\frac{a_{2n}-1}8\right)\tag{10}\]
对于n=3, A=1024, 所以总路径数`=1024\cdot\left(1+\frac{3-1}8\right)\left(1+\frac{5-1}8\right)\left(1+\frac{3-1}8\right)=2400`
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-11-17 16:11:25 | 显示全部楼层
未标记方向的边可以双向通过么?

点评

显然啊:如果不允许通行,则AB间就无通路;如果非双向,何苦要将单向的特别标注出来  发表于 2022-11-17 19:56
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-11-21 11:33:54 | 显示全部楼层
本帖最后由 王守恩 于 2022-11-21 19:06 编辑
hujunhua 发表于 2022-11-17 14:16
设白色反向箭头为 n 个,则路径层数为 `2n+1`, 记第 i 层的路径数为 `{a_i}`, \[\begin{equation}a_i=\begi ...

闷了几天,小心翼翼还是问:
用1格(从A到第1个白箭头前面的点):有2条路径
用4格(从A到第2个白箭头前面的点):有10条路径
用9格(从A到第3个白箭头前面的点):有100条路径
用16格(从A到B):有2400条路径
站在棱形中间列看:到起点是几条路,到终点也是同样的路,
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-11-22 09:21:43 | 显示全部楼层
本帖最后由 王守恩 于 2022-11-22 09:24 编辑
王守恩 发表于 2022-11-21 11:33
闷了几天,小心翼翼还是问:
用1格(从A到第1个白箭头前面的点):有2条路径
用4格(从A到第2个白箭头前面 ...

我们想要的是一条路(站在棱形中间列:看到起点是几条路,看到终点也是同样的路)
用1格(从A到第1个白箭头前面的点):有2条路径。2=1×1×2+0×0×2
用4格(从A到第2个白箭头前面的点):有10条路径。10=2×2×2+(2/2×1)×(2/2×1)×2,其中:2=1×2+0
用9格(从A到第3个白箭头前面的点):有100条路径。100=5×5×4+0×0×2,其中:5=2×2+2/2×1
用16格(从A到B):有2400条路径。2400=20×20×4+(20/2×2)×(20/2×2)×2,其中:20=5×4+0
用25格:60000=100×100×6+0×0×2,其中:100=20×4+20/2×2
用36格:3780000=600×600×2+(600/2×3)×(600/2×3)×2,其中:600=100×6+0
用49格:162000000=4500×4500×2+0×0×2,其中:4500=600×6+600/2×3
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 6 天前 | 显示全部楼层
小心翼翼还是问:从A到B, 标准答案是多少?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 3 天前 | 显示全部楼层
王守恩 发表于 2022-11-26 08:05
小心翼翼还是问:从A到B, 标准答案是多少?


先把2#的(1)代入(2), 得到A的公式\[A=\begin{cases}n!!^3(n+2)!!&=2^{2n+1}k!^3(k+1)!,&\text{if }n=2k\\(n-1)!!(n+1)!!^3&=2^{2n+1}k!(k+1)!^3,&\text{if }n=2k+1\end{cases}\]再把2#的(1)代入(10), 得到确切的计算公式\[Answer=\begin{cases}\D\frac{k!^3(k+1)!(k+4)!^2}{288},&\text{if }n=2k\\\D\frac{k!(k+1)!^3(k+4)!(k+5)!}{288},&\text{if }n=2k+1\end{cases}\]
对于1楼的图,`n=3,k=1, A=2^7·2^3=2^{10}, Answer=\D\frac{2^3·5!·6!}{288}=2400`
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 3 天前 | 显示全部楼层
hujunhua 发表于 2022-11-29 00:01
先把2#的(1)代入(2), 先得到A的公式\[A=\begin{cases}n!!^3(n+2)!!&=2^{2n+1}k!^3(k+1)!,&\text{if }n=2k ...

谢谢 hujunhua !

我们想要的是一条路。

1,把蜂窝状网络画成上下错位小方格,水平边表示单向桥,垂直边表示双向路。

2,站在中间列桥:看到起点有几条路,看到终点也有同样几条路。

3,站在任意的桥:看到起点有几条路,看到终点有几条路,两者相乘。

4,起点可以设在任意点,终点也可以设在任意点,站在桥上看是关键。

5,解一道题,抓几座关键桥,从起点到终点,总要过这几座关键桥。

6,或者说:抓住前进桥就可以,返回桥可以不管。

7,同样的,用这样的想法,去解决类似问题。

点评

你的总结性发言,是建立在自己对问题深刻的领悟上。  发表于 3 天前
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2022-12-2 20:43 , Processed in 0.078678 second(s), 21 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表