3131210 发表于 2023-10-8 20:39:14

【已解决】如何寻找最短经过路径

本帖最后由 3131210 于 2023-10-12 18:45 编辑

想用递归的办法实现寻找最短经过路径,数据如下(有附件文本,内容一致),有AB两列
想实现如下功能,函数有2个参数,一个是当前路径(A列),一个是目标路径(B列),返回的内容是所经过的路径
例子1:1-10的最短路径为1-8-10   参数1=1   参数2=10   返回1-8-10
例子2:5-1的最短路径为5-8-1      参数1=5    参数2=1   返回5-8-1
数据只有部分,实际可能会有更多层级(超过10以上),而且也有可能不存在最短路径(也有可能A无法到达B路径,这个时候可以返回-1或者其他),所以需要一个递归的函数

有没有这方面的大神来一个


A-B
1-3
1-4
1-7
1-8
2-3
2-4
2-5
2-9
2-10
3-1
3-2
3-8
4-1
4-2
4-7
4-8
4-9
5-2
5-8
5-10
6-7
6-9
7-1
7-4
7-6
7-9
8-1
8-3
8-4
8-5
8-9
8-10
9-2
9-4
9-6
9-7
9-8
9-10
10-2
10-5
10-8
10-9

绿色风 发表于 2023-10-8 21:52:36

说实话,没看明白是结果是怎么得来的。另外游戏寻路可以参照搜索论坛“ A*星寻路 ”

vigiles 发表于 2023-10-8 22:15:28

看起来不是最短路径,而是唯一路径

3131210 发表于 2023-10-9 12:05:03

本帖最后由 3131210 于 2023-10-9 12:07 编辑

绿色风 发表于 2023-10-8 21:52
说实话,没看明白是结果是怎么得来的。另外游戏寻路可以参照搜索论坛“ A*星寻路 ”
这个只是模拟的样本少
比如1能去到的地方有 3 4 7 8
然后3478分别递归,看能去到哪里。
能去到的地方也是在表里面可以找到一一对应的

由于8能去到10,3 4 7无法直接去到10,但是可以去到别的地方(所以这里就需要一直递归下去,并且要避免路径往回走的问题,直到走到10或者全部走完,也没走到10,此时返回一个-1也可以)
所以1到10的最短路径是 1 8 10

3131210 发表于 2023-10-9 12:06:44

vigiles 发表于 2023-10-8 22:15
看起来不是最短路径,而是唯一路径

肯定是最短路径,要不停的递归,且要避免递归的时候走回头路,再加上模拟的样本比较少,实际不止1到10
可能会有1到10000 中间一直递归

vigiles 发表于 2023-10-9 19:53:18

我理解有误吧,你给出的两列里,1到10,8是唯一的路径。如果数据都是如此,只要把起点的右边和目标的左边比较,相同的就是路径,大概不算是递归吧。

3131210 发表于 2023-10-9 20:24:40

本帖最后由 3131210 于 2023-10-9 20:26 编辑

如果数据特别多的话 比如从1000到8000
1000可以去到2000 3000 4000 5000 6000 7000
然后2000 3000 4000 5000 6000 7000 里面又可以分别去到很多地方   最终辗转都可以去到8000
所以要递归所有可能 并在答案里面找出经过最少的路径

比如1000-3000-5000-8000      最短
      但是也有1000-3000-6000-7000-8000 或者    1000-2000-3000-4000-5000-6000-8000
      路径不唯一

afan 发表于 2023-10-9 21:24:57

3131210 发表于 2023-10-9 20:24
如果数据特别多的话 比如从1000到8000
1000可以去到2000 3000 4000 5000 6000 7000
然后2000 3000 4000 ...

建议直接逐级循环查找,找出来即是最短的。用递归会慢且有限制,而且找到了还要比对层数。

3131210 发表于 2023-10-9 22:01:42

afan 发表于 2023-10-9 21:24
建议直接逐级循环查找,找出来即是最短的。用递归会慢且有限制,而且找到了还要比对层数。

如果不知道要找几级的话,要怎么写逐级循环    有可能有十多级才找到 也有可能2 3级就找到了

afan 发表于 2023-10-9 22:10:15

3131210 发表于 2023-10-9 22:01
如果不知道要找几级的话,要怎么写逐级循环    有可能有十多级才找到 也有可能2 3级就找到了

不确定的循环用 While 或 Do,每层用A列捕获所有的B列……

3131210 发表于 2023-10-9 22:52:33

afan 发表于 2023-10-9 22:10
不确定的循环用 While 或 Do,每层用A列捕获所有的B列……

每层用A列捕获所有的B列,每层的数据怎么样存放比较好

afan 发表于 2023-10-10 10:51:21

3131210 发表于 2023-10-9 22:52
每层用A列捕获所有的B列,每层的数据怎么样存放比较好

可以用字符串或者数组保存吧,比如以行为单位,每行保存一段路径,完成该路径捕获后删除,循环添加与删除

3131210 发表于 2023-10-10 11:09:12

本帖最后由 3131210 于 2023-10-10 11:19 编辑

倒是整了一个出来
循环的函数是这个,有点丑,大佬能不能把第一次循环(5-11行)也包含在DO里面,精简和美化一下   完整测试代码在附件

Func _GetMapPath($NowID, $NeedID, $mDepth = 10) ;现在的ID,要去的ID,搜索深度
      Local $filter = $NowID & '|'
      Local $arr1, $arr2, $arr3

      $arr1 = StringRegExp($MapPathList, '(?m)^' & $NowID & '-(?!' & StringTrimRight($filter, 1) & ' & )(\d+)', 3)
      If @error Then Return -1 ;没有找到任何路径
      $filter &= _ArrayToString($arr1, '|') & '|' ;增加过滤列表
      For $i = 0 To UBound($arr1) - 1
                If $arr1[$i] = $NeedID Then Return $NowID & '-' & $NeedID
                $arr1[$i] = $NowID & '-' & $arr1[$i]
      Next

      Do
                For $i = 0 To UBound($arr1) - 1 ;遍历数组1
                        $arr3 = StringRegExp($MapPathList, '(?m)^' & StringRegExpReplace($arr1[$i], '\d+-', '') & '-(?!' & StringTrimRight($filter, 1) & ' & )(\d+)', 3)
                        If @error Then ContinueLoop
                        $filter &= _ArrayToString($arr3, '|') & '|' ;增加过滤列表

                        For $j = 0 To UBound($arr3) - 1
                              If $arr3[$j] = $NeedID Then Return $arr1[$i] & '-' & $NeedID
                              $arr3[$j] = $arr1[$i] & '-' & $arr3[$j]
                        Next
                        _ArrayConcatenate($arr2, $arr3) ;合并到数组2
                Next

                $arr1 = $arr2
                ReDim $arr2
                $mDepth -= 1
      Until $mDepth = 1

      Return -1
EndFunc   ;==>_GetMapPath




afan 发表于 2023-10-10 12:57:55

3131210 发表于 2023-10-10 11:09
倒是整了一个出来
循环的函数是这个,有点丑,大佬能不能把第一次循环(5-11行)也包含在DO里面,精简和美化 ...

这样不就ok了,哪有什么丑的,只要运行正确,效率不低就是王道~

afan 发表于 2023-10-10 13:04:30

本帖最后由 afan 于 2023-10-12 19:31 编辑

之前看示例以为路径只有3节,那样的话一个正则就解决了
页: [1] 2
查看完整版本: 【已解决】如何寻找最短经过路径