Python-VBA编程500例-015-03(入门级)

目录

1、 ​​​​​​​飞行棋(SPFA): 

1-1、Python：

1-2、VBA：

2、相关文章：

Python算法之旅：http://iyenn.com/rec/1699032.html?spm=1001.2014.3001.5502

个人主页：非风V非雨-CSDN博客

欢迎志同道合者一起交流学习，我的QQ:94509325/微信

        飞行棋(Flying Chess)算法是一种搜索算法，主要用于解决图搜索和路径规划问题。它的主要特点是可以“飞跃”到棋盘上任何位置，从而大大减少了搜索的时间和空间复杂度。以下是一些飞行棋算法的实际应用场景：

1、路径规划：在机器人领域，飞行棋算法可以用于规划机器人的运动路径。机器人可以根据当前的位置和目标位置，通过飞行棋算法找到一条最优的路径。

2、网络路由：在计算机网络中，飞行棋算法可以用于数据包的路由选择。通过计算数据包从源节点到目标节点的最优路径，可以提高网络传输的效率。

3、资源分配：在资源分配问题中，飞行棋算法可以用于寻找最优的资源分配方案。例如，在任务调度问题中，可以使用飞行棋算法找到最优的任务分配方案。

4、旅行商问题：在经典的旅行商问题(TSP)中，飞行棋算法可以用于寻找最短的旅行路线。旅行商需要访问一组城市，并在这些城市之间旅行，目标是找到一条总距离最短的路线。

5、图像分割：在计算机视觉领域，飞行棋算法可以用于图像分割问题。通过对图像进行网格化处理，可以将图像分割问题转化为图搜索问题，进而使用飞行棋算法求解。

6、游戏AI：在游戏开发中，飞行棋算法可以用于游戏AI的实现。例如，在策略游戏中，AI可以使用飞行棋算法来规划单位的移动和攻击。

7、模拟实验与科学研究：在科学研究中，有时需要模拟随机过程来观察和分析系统的行为。飞行棋算法的原理可以用于构建简单的随机模型，用于模拟和测试某些现象或系统的特性。例如，在生物学或物理学领域，研究人员可能会使用类似的随机算法来模拟种群动态、粒子运动等复杂过程。

        总之，飞行棋算法在很多需要解决图搜索和路径规划问题的领域都有实际应用场景。

1、 ​​​​​​​飞行棋(SPFA): 
1-1、Python：
  1. # 1.问题描述：
  2. # 一维棋盘，起点在棋盘的最左侧，终点在棋盘的最右侧，棋盘上有几个位置和其他位置相连，如果pos1和pos2相连，但连接是单向的，即当棋子落在位置pos1时，
  3. # 可以选择不投骰子，直接移动棋子从pos1到pos2，但不能从pos2移动到pos1.给定这个棋盘的长度length和位置的相连情况connections，用六面骰子(点数1-6)，
  4. # 问最少需要投几次骰子才能到达终点？
  5. # 2.问题示例：
  6. # 输入length = 10 和 connections = [[2, 10]]，输出结果为1；即0 -> 2(投骰子)， 2 -> 10(直接相连)；输入length = 15 和 connections =
  7. # [[2, 8], [6, 9]]，输出结果为2，即0 -> 6(投骰子)， 6 -> 9(直接相连)，9 -> 15(投骰子).
  8. # 3.代码实现：
  9. class Solution:
  10.     def flying_chess(self, length, connections) :
  11.         # 初始化距离数组，所有位置到起点的初始距离设为无穷大
  12.         dist = [float('inf')] * (length + 1)
  13.         # 初始化访问数组，记录位置是否被访问过
  14.         vis = [0] * (length + 1)
  15.         # 初始化队列，用于广度优先搜索
  16.         Q = [0] * (length + 1)
  17.         # 队列起始位置
  18.         st = 0
  19.         # 队列结束位置
  20.         ed = 0
  21.         # 起点到起点的距离为0
  22.         dist[1] = 0
  23.         # 标记起点为已访问
  24.         vis[1] = 1
  25.         # 将起点加入队列
  26.         Q[ed] = 1
  27.         # 队列结束位置向后移动
  28.         ed += 1
  29.         # 当队列不为空时，执行循环
  30.         while st < ed:
  31.             # 队列头部元素出队
  32.             u = Q[st]
  33.             # 队列起始位置向后移动
  34.             st += 1
  35.             # 标记当前位置为未访问，因为接下来要检查它的邻居
  36.             vis[u] = 0
  37.             # 遍历所有的连接点
  38.             for roads in connections:
  39.                 # 如果连接点的起点不是当前位置，则跳过
  40.                 if roads[0] != u:
  41.                     continue
  42.                 # 连接点的目标位置
  43.                 v = roads[1]
  44.                 # 如果通过当前位置到达目标位置的距离更短，则更新距离
  45.                 if dist[v] > dist[u]:
  46.                     dist[v] = dist[u]
  47.                     # 如果目标位置未被访问过
  48.                     if vis[v] == 0:
  49.                         # 标记目标位置为已访问
  50.                         vis[v] = 1
  51.                         # 将目标位置加入队列
  52.                         Q[ed] = v
  53.                         # 队列结束位置向后移动
  54.                         ed += 1
  55.             # 遍历从当前位置连续向前跳1到6步的所有可能位置
  56.             for i in range(1, 7):
  57.                 # 如果跳步后的位置超出了棋盘长度，则停止检查
  58.                 if i + u > length:
  59.                     break
  60.                 # 跳步后的位置
  61.                 v = i + u
  62.                 # 如果通过当前位置连续跳步到达目标位置的距离更短，则更新距离
  63.                 if dist[v] > dist[u] + 1:
  64.                     dist[v] = dist[u] + 1
  65.                     # 如果目标位置未被访问过
  66.                     if vis[v] == 0:
  67.                         # 标记目标位置为已访问
  68.                         vis[v] = 1
  69.                         # 将目标位置加入队列
  70.                         Q[ed] = v
  71.                         # 队列结束位置向后移动
  72.                         ed += 1
  73.         # 返回从起点到终点的最少步数
  74.         return dist[length]
  75. # 主函数
  76. if __name__ == '__main__':
  77.     # 初始化棋盘长度
  78.     length = 15
  79.     # 初始化跳点集合
  80.     connections = [[2, 8], [6, 9]]
  81.     # 创建Solution对象
  82.     solution = Solution()
  83.     # 输出棋盘长度
  84.     print("棋盘长度：", length)
  85.     # 输出跳点连接
  86.     print("跳点连接：", connections)
  87.     # 调用flying_chess函数并输出结果
  88.     print("最少需要步数：", solution.flying_chess(length, connections))
  89. # 4.运行结果：
  90. # 棋盘长度： 15
  91. # 跳点连接： [[2, 8], [6, 9]]
  92. # 最少需要步数： 2
1-2、VBA：
  1. Rem 自定义函数，功能：飞行棋(SPFA)
  2. Function flying_chess(length As Integer, connections As Variant) As Variant
  3.     Dim dist() As Double
  4.     Dim vis() As Integer
  5.     Dim Q() As Integer
  6.     Dim st As Integer
  7.     Dim ed As Integer
  8.     Dim u As Integer
  9.     Dim v As Integer
  10.     Dim i As Integer
  11.     Dim roads As Variant
  12.       
  13.     ' 初始化数组
  14.     ReDim dist(1 To length + 1)
  15.     ReDim vis(1 To length + 1)
  16.     ReDim Q(1 To length + 1)
  17.       
  18.     ' 初始化距离和访问状态
  19.     For i = 1 To length + 1
  20.         dist(i) = 99 ^ 99
  21.         vis(i) = 0
  22.     Next i
  23.       
  24.     ' 设置起点和队列
  25.     st = 1
  26.     ed = 1
  27.     dist(1) = 0
  28.     vis(1) = 1
  29.     Q(ed) = 1
  30.     ed = ed + 1
  31.       
  32.     ' 主循环
  33.     While st < ed
  34.         u = Q(st)
  35.         st = st + 1
  36.         vis(u) = 0
  37.           
  38.         ' 遍历连接
  39.         For Each roads In connections
  40.             v = roads(1)
  41.             If v <= length Then
  42.                 If dist(roads(1)) > dist(v) Then
  43.                     dist(v) = dist(u)
  44.                     If vis(v) = 0 Then
  45.                         vis(v) = 1
  46.                         Q(ed) = v
  47.                         ed = ed + 1
  48.                     End If
  49.                 End If
  50.             End If
  51.         Next roads
  52.           
  53.         ' 遍历跳跃
  54.         For i = 1 To 6
  55.             v = u + i
  56.             If v > length Then Exit For
  57.             If dist(v) > dist(u) + 1 Then
  58.                 dist(v) = dist(u) + 1
  59.                 If vis(v) = 0 Then
  60.                     vis(v) = 1
  61.                     Q(ed) = v
  62.                     ed = ed + 1
  63.                 End If
  64.             End If
  65.         Next i
  66.     Wend
  67.       
  68.     ' 返回到达指定长度的最少步数
  69.     flying_chess = dist(length)
  70. End Function
  71. Rem 执行过程，功能：调用自定义函数flying_chess，以弹窗方式输出结果
  72. Sub TestRun()
  73.     ' 定义变量
  74.     Dim length As Integer
  75.     Dim connections As Variant
  76.     Dim result As Integer
  77.     Dim i As Integer, j As Integer
  78.     
  79.     ' 输入棋盘长度
  80.     length = 15
  81.     ' 输入跳点集合，针对每个子区间，都可以直连，即骰子投出2时，可以实现先走两步，再通过起跳点2直接到达8的位置；骰子投出6时，可以实现先走六步，再通过起跳点6直接到达9的位置
  82.     connections = Array(Array(2, 8), Array(6, 9))
  83.     ' 调用自定义函数，返回到达指定长度的最少步数
  84.     result = flying_chess(length, connections)
  85.     '输出结果
  86.     MsgBox "棋盘长度：" & length & vbCrLf & _
  87.            "跳点连接：" & vbCrLf & Join(Application.Transpose(Application.index(connections, 0, 1)), ", ") & " => " & Join(Application.Transpose(Application.index(connections, 0, 2)), ", ") & vbCrLf & _
  88.            "最少需要步数：" & result, vbInformation, "飞行棋"
  89. End Sub

注意：1-2中的代码需粘贴到你的VBA编辑器中，按F5执行TestRun程序，以弹窗方式输出结果。

2、相关文章：

2-1、Python-VBA编程500例-015-01(入门级)

2-2、Python-VBA编程500例-015-02(入门级)

2-3、Python-VBA编程500例-016(入门级) 

2-4、Python-VBA编程500例-017(入门级) 

Python算法之旅：http://iyenn.com/rec/1699032.html?spm=1001.2014.3001.5502
个人主页：非风V非雨-CSDN博客
欢迎志同道合者一起交流学习，我的QQ:94509325/微信：

文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树首页概览60120 人正在系统学习中
遨游码海，我心飞扬
微信名片
注：本文转载自blog.csdn.net的神奇夜光杯的文章"https://blog.csdn.net/ygb_1024/article/details/136957946"。版权归原作者所有，此博客不拥有其著作权，亦不承担相应法律责任。如有侵权，请联系我们删除。
复制链接
相关推荐
发表评论

评论记录：

未查询到任何数据！