数学研发论坛

 找回密码
 欢迎注册
查看: 775|回复: 48

[原创] 正方形网格里的最长路

[复制链接]
发表于 2022-8-21 16:50:15 | 显示全部楼层 |阅读模式

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

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

x
假设地图是n行n列的正方形格子,

起点在第1行第1列,

终点在第n行第n列,

每步的走法有上下左右4种。

问题1:

如何在某些格子里设置障碍,

才能使得起点到终点只有1条路,

且该路径的长度达到最大呢?

问题2:

如果不限制起点和终点的位置,

那么起点到终点之间的最短路径长度的最大值是多少?

#####

对于较小的n,我希望找到准确解。

对于较大的n,我希望找到与n有关的渐进公式。

例如,当n=7时,

问题1我最多可以构造出长度为31格的路径:

1.png

上图中的“×”表示障碍。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-8-21 18:45:50 | 显示全部楼层
允许斜对角运动么?

点评

默认是上下左右走,不允许斜走的。如果允许,一般会特意说明。  发表于 2022-8-21 22:50
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-8-22 06:40:21 | 显示全部楼层
问题1:

如何在某些格子里设置障碍,

才能使得起点到终点只有1条路,

且该路径的长度达到最大呢?

解法1:

一共有$n^2$个格子,每个格子要么放障碍,要么不放障碍,

因此一共有$2^{n^2}$种放障碍的方案。

对这$2^{n^2}$种放障碍的方案逐一判断是否存在路径,

如果存在,就求出最短路径长度,

然后输出最短路径长度最长的那条路径,结果如下:

  1. n=1: 1
  2. 1

  3. n=2: 3
  4. 11
  5. 01

  6. n=3: 5
  7. 111
  8. 001
  9. 001

  10. n=4: 7
  11. 1111
  12. 0001
  13. 0001
  14. 0001

  15. n=5: 17
  16. 11111
  17. 00001
  18. 11111
  19. 10000
  20. 11111

  21. n=6: 23
  22. 110111
  23. 010101
  24. 110101
  25. 101101
  26. 101001
  27. 111001
复制代码

输出的“n=6: 23”表示当n=6时,路径长度的最大值是23,

后面是具体的方案,其中“1”表示通路,“0”表示障碍

问题2:

如果不限制起点和终点的位置,

那么起点到终点之间的最短路径长度的最大值是多少?

解:

枚举起点、终点和$2^{n^2}$种放障碍的方案,

然后输出最短路径长度最长的那条路径,结果如下:

  1. n=1: 1
  2. 1

  3. n=2: 3
  4. 11
  5. 10

  6. n=3: 7
  7. 111
  8. 101
  9. 110

  10. n=4: 11
  11. 1111
  12. 1001
  13. 1011
  14. 1100

  15. n=5: 17
  16. 11101
  17. 10101
  18. 10101
  19. 11011
  20. 01110

  21. n=6: 24
  22. 110111
  23. 010101
  24. 110101
  25. 101101
  26. 101011
  27. 111010
复制代码

这种解法的优点是不会遗漏任何解,缺点是慢。

n=6用时12小时,

n=7预计用时10年。

你们有更好的解法吗?

点评

用插头动态规划算法,预计可以解决21*21以内的规模,但我一直腾不出时间写这个算法  发表于 2022-8-25 12:13
你现在最优可以计算到n是多少了?  发表于 2022-8-25 09:19
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-8-22 09:38:49 | 显示全部楼层
KeyTo9_Fans 发表于 2022-8-22 06:40
问题1:

如何在某些格子里设置障碍,

能否找到递推关系?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-8-22 09:58:52 | 显示全部楼层
KeyTo9_Fans 发表于 2022-8-22 06:40
问题1:

如何在某些格子里设置障碍,


你是用暴力搜索吧?n=7用不了那么久吧?你划分得太细了。

点评

细分为2*2的多个组合,可能会减少运算量。  发表于 2022-8-23 09:29
因为一共有49个格子,所以我是按2的49次方乘以49的运算量来估算所需时间的  发表于 2022-8-22 22:57
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-8-22 10:14:17 | 显示全部楼层
本人創作的弈棋《巫師與殺手》,殺手的行動方式,跟本主題類似。巫師放置的地符,相當於他的障礙物。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-8-22 11:47:24 | 显示全部楼层
ejsoon 发表于 2022-8-22 10:14
本人創作的弈棋《巫師與殺手》,殺手的行動方式,跟本主題類似。巫師放置的地符,相當於他的障礙物。

规则恐怕只有你懂……
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-8-22 23:18:15 | 显示全部楼层
aimisiyou 发表于 2022-8-22 11:47
规则恐怕只有你懂……

我可以做動畫或錄視頻。當然文字版規則其實也寫的很詳盡了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-8-23 00:15:43 | 显示全部楼层
本帖最后由 ejsoon 于 2022-8-23 07:45 编辑
aimisiyou 发表于 2022-8-22 11:47
规则恐怕只有你懂……


巫0.png

行棋至此,輪到殺手行動,其實巫師已經輸了,因為殺手只要「左下下下右右」六步,就能正好射殺巫師。

這局巫師只是失誤,一般棋局不會這麼快就結束。
  • 那麼為甚麼殺手要走「六步」?

    $rarr$因為此時場上一共有六個地符(白色棋子),包括巫師腳下也有一個。

    (當棋局進展到中局時,殺手可能要走十幾步。這時殺手可能會因無路可走而輸掉。)
  • 殺手如何射殺巫師?

    $rarr$在殺手的回合中,如果行走結束時,停在與巫師同一條線但不同區的地方,就能擊斃對方。

    本棋棋盤是6x6,一個區就是3x3。如果殺手跟巫師處在同一個區,巫師不會遭到射殺。

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-8-23 10:36:59 | 显示全部楼层
本帖最后由 aimisiyou 于 2022-8-23 13:10 编辑

F(N)=F(N-4)+4*N-4,    N>=5。
F(1)=1
F(2)=3
F(3)=5
F(4)=7
F(5)=11
F(6)=23
F(7)=29
看来往后面结果就不对了。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2022-10-3 06:50 , Processed in 0.092585 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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