求助路径算法！

yjh_27

香川群子 发表于 2015-5-21 16:57
你的递归计算结果，有些房间是被反复通过的。（同一房间进出多次）

这个应该不是合理的路径。

思路一致，只是检查是否进过房间的方法不同。
错误在没忽略起点，改1为0即可。

Dim arr()
Dim brr(1 To 100, 1 To 1) As String
Dim bi As Integer
Dim js As Integer

Sub aa()
ks = [a20]
js = [a21]
arr1 = [B2:e13]

arr = arr1
bi = 0
Call xz(ks, 1, ks)


Range("a25").Resize(bi, 1) = brr
End Sub

Sub xz(fjh, bs, jl)
'fjh房间号, bs步数, jl记录
Dim jl1 As String
For i = bs To UBound(arr, 2)
    If arr(fjh, i) = "" Then   '本房间走完
        Exit For
    ElseIf arr(fjh, i) = js Then  '到出口
        bi = bi + 1
        brr(bi, 1) = jl & "," & arr(fjh, i)
    Else    '进下一间
        fl = Split(jl, ",")
        For j = UBound(fl) To 0 Step -1
            If Val(fl(j)) = arr(fjh, i) Then Exit For
        Next
        If j < 0 Then
            jl1 = jl & "," & arr(fjh, i)
            Call xz(arr(fjh, i), 1, jl1)
        End If
    End If
Next

End Sub

香川群子

我自己模拟增加了一个里程表。

用递归算法可知，经过城市最少的不一定是里程最短的路径。

yjh_27

1. Dim arr()
   
2. Dim brr(1 To 100, 1 To 1) As String
   
3. Dim bi As Integer
   
4. Dim js As Integer
   
5. 
   
6. Sub aa()
   
7. tt = Timer
   
8. ks = [a20]
   
9. js = [a21]
   
10. arr1 = [B2:e13]
    
11. 
    
12. arr = arr1
    
13. bi = 0
    
14. 'Call xz(ks, 1, ks)
    
15. 
    
16. ReDim abjrr(1 To UBound(arr)) As Boolean
    
17. abjrr(ks) = True
    
18. Call xz1(ks, 1, ks, abjrr)
    
19. 
    
20. 
    
21. Range("a25").Resize(100, 1).ClearContents
    
22. Range("a25").Resize(bi, 1) = brr
    
23. MsgBox Timer - tt
    
24. End Sub
    
25. 
    
26. Sub xz1(fjh, bs, jl, bj)
    
27. 'fjh房间号, bs步数, jl记录
    
28. For i = bs To UBound(arr, 2)
    
29.     If arr(fjh, i) = "" Then   '本房间走完
    
30.         Exit For
    
31.     ElseIf arr(fjh, i) = js Then  '到出口
    
32.         bi = bi + 1
    
33.         brr(bi, 1) = jl & "," & arr(fjh, i)
    
34.     Else    '进下一间
    
35.         If Not bj(arr(fjh, i)) Then
    
36.             bj1 = bj
    
37.             bj1(arr(fjh, i)) = True
    
38.             Call xz1(arr(fjh, i), 1, jl & "," & arr(fjh, i), bj1)
    
39.         End If
    
40.     End If
    
41. Next
    
42. 
    
43. End Sub
    

复制代码

香川群子

yjh_27 发表于 2015-5-21 17:39

嗯，加入了检查房间是否已进入过的记录数组……

呵呵，这就和原来的代码有根本性的算法改变了，虽然看上去递归结构基本没变。

Nick_Chen0622

香川群子 发表于 2015-5-20 09:52
字典+数组算法，循环计算得到最短路径。

香川老师，请问一下：这个迷宫路径的解题思路是什么啊？我下载了您的附件，发现计算都很好，但是我想知道你写这些代码的逻辑是什么样子的，，，能教一下我吗？非常感谢。

ykqrs

香川群子 发表于 2015-5-20 08:37
根据楼主相邻房间表，拓扑画出各个房间的平面图：

这个平面图画得好，请问是根据什么思路设计的？有没有什么算法？

ykqrs

C:\Users\Administrator\Desktop

ykqrs

ykqrs

代码老是需要审核，唉。。。。。
这个题和竞赛区的一道题类似，拿来改改就能用