【已解决】如何寻找最短经过路径
本帖最后由 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
说实话，没看明白是结果是怎么得来的。另外游戏寻路可以参照搜索论坛“ A*星寻路 ” 看起来不是最短路径，而是唯一路径 本帖最后由 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
vigiles 发表于 2023-10-8 22:15
看起来不是最短路径，而是唯一路径
肯定是最短路径，要不停的递归，且要避免递归的时候走回头路，再加上模拟的样本比较少，实际不止1到10
可能会有1到10000 中间一直递归 我理解有误吧，你给出的两列里，1到10,8是唯一的路径。如果数据都是如此，只要把起点的右边和目标的左边比较，相同的就是路径，大概不算是递归吧。 本帖最后由 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
路径不唯一
3131210 发表于 2023-10-9 20:24
如果数据特别多的话 比如从1000到8000
1000可以去到2000 3000 4000 5000 6000 7000
然后2000 3000 4000 ...
建议直接逐级循环查找，找出来即是最短的。用递归会慢且有限制，而且找到了还要比对层数。 afan 发表于 2023-10-9 21:24
建议直接逐级循环查找，找出来即是最短的。用递归会慢且有限制，而且找到了还要比对层数。
如果不知道要找几级的话，要怎么写逐级循环 有可能有十多级才找到 也有可能2 3级就找到了 3131210 发表于 2023-10-9 22:01
如果不知道要找几级的话，要怎么写逐级循环 有可能有十多级才找到 也有可能2 3级就找到了
不确定的循环用 While 或 Do，每层用A列捕获所有的B列…… afan 发表于 2023-10-9 22:10
不确定的循环用 While 或 Do，每层用A列捕获所有的B列……
每层用A列捕获所有的B列，每层的数据怎么样存放比较好 3131210 发表于 2023-10-9 22:52
每层用A列捕获所有的B列，每层的数据怎么样存放比较好
可以用字符串或者数组保存吧，比如以行为单位，每行保存一段路径，完成该路径捕获后删除，循环添加与删除 本帖最后由 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
3131210 发表于 2023-10-10 11:09
倒是整了一个出来
循环的函数是这个，有点丑，大佬能不能把第一次循环(5-11行)也包含在DO里面，精简和美化 ...
这样不就ok了，哪有什么丑的，只要运行正确，效率不低就是王道~ 本帖最后由 afan 于 2023-10-12 19:31 编辑
之前看示例以为路径只有3节，那样的话一个正则就解决了
页:
[1]
2