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

3131210

想用递归的办法实现寻找最短经过路径，数据如下（有附件文本，内容一致），有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

绿色风

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

vigiles

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

3131210

绿色风 发表于 2023-10-8 21:52
说实话，没看明白是结果是怎么得来的。另外游戏寻路可以参照搜索论坛“ A*星寻路 ”

这个只是模拟的样本少
比如1能去到的地方有 3 4 7 8
然后3  4  7  8  分别递归，看能去到哪里。
能去到的地方也是在表里面可以找到一一对应的

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

3131210

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

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

vigiles

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

3131210

如果数据特别多的话 比如从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

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

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

3131210

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

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

afan

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

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

3131210

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

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

afan

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

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

3131210

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

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

        $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[0]
                $mDepth -= 1
        Until $mDepth = 1

        Return -1
EndFunc   ;==>_GetMapPath

afan

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

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

afan

之前看示例以为路径只有3节，那样的话一个正则就解决了