推荐|Python-VBA编程500例-015-02(入门级)

1、飞行棋(动态规划):

1-1、Python：

1-2、VBA：

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

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

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

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

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

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

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

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

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

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

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

1、飞行棋(动态规划):

1-1、Python：


# 1.问题描述：
# 一维棋盘，起点在棋盘的最左侧，终点在棋盘的最右侧，棋盘上有几个位置和其他位置相连，如果pos1和pos2相连，但连接是单向的，即当棋子落在位置pos1时，
# 可以选择不投骰子，直接移动棋子从pos1到pos2，但不能从pos2移动到pos1.给定这个棋盘的长度length和位置的相连情况connections，用六面骰子(点数1-6)，
# 问最少需要投几次骰子才能到达终点？
# 2.问题示例：
# 输入length = 10 和 connections = [[2, 10]]，输出结果为1；即0 -> 2(投骰子)， 2 -> 10(直接相连)；输入length = 15 和 connections =
# [[2, 8], [6, 9]]，输出结果为2，即0 -> 6(投骰子)， 6 -> 9(直接相连)，9 -> 15(投骰子).
# 3.代码实现：
class Solution:
    def flying_chess(self, length, connections):
        '''
        初始化dp数组，dp[i]表示到达位置i所需的最少步数
        dp数组被初始化为float('inf')，其中，float('inf')表示正无穷大，意味着一开始我们假设到达每个位置所需的最少步数是一个非常大的数(即不可能到达)
        然后，随着算法的进行，我们根据可以跳跃的距离和跳点来逐步更新这个数组，直到找到真正的最少步数.
        '''
        dp = [float('inf')] * (length + 1)
        dp[0] = 0  # 起始点不需要步数，这里的理解非常重要
 
        # 跳点集合，使用字典形式存储，方便快速查找
        jump_dict = {j[1]: j[0] for j in connections}
        # 遍历棋盘上的每个位置
        for i in range(1, length + 1):
            # 遍历所有可能的跳跃距离
            for j in range(1, min(i, 6) + 1):
                # 更新到达当前位置所需的最少步数
                dp[i] = min(dp[i], dp[i - j] + 1)
            # 检查是否有跳点可以直接到达当前位置
            if i in jump_dict:
                dp[i] = min(dp[i], dp[jump_dict[i]])
        # 返回到达指定长度的最少步数
        return dp[length]
# 主函数
if __name__ == '__main__':
    # 输入棋盘长度
    length = 15
    # 输入跳点集合
    connections = [[2, 8], [6, 9]]
    # 调用自定义函数
    solution = Solution()
    # 输出结果
    print("棋盘长度：", length)
    print("跳点连接：", connections)
    print("最少需要步数：", solution.flying_chess(length, connections))
# 4.运行结果：
# 棋盘长度： 15
# 跳点连接： [[2, 8], [6, 9]]
# 最少需要步数： 2

1-2、VBA：


Rem 自定义函数，功能：飞行棋(动态规划)
Function flying_chess(length As Integer, connections As Variant) As Integer
    ' 初始化dp数组，dp(i)表示到达位置i所需的最少步数
    Dim dp() As Double
    Dim i As Integer, j As Integer
    Dim minSteps As Double
    Dim jumpDict As Object
    Dim conn As Variant
    
    ReDim dp(length)
    ' 填充dp数组为足够大的数
    For i = 0 To length
        dp(i) = 99 ^ 99
    Next i
    ' 起始点不需要步数，这里的理解非常重要
    dp(0) = 0
    ' 跳点集合，使用字典形式存储，方便快速查找
    Set jumpDict = CreateObject("Scripting.Dictionary") ' 此处需要引用控件：Microsoft Scripting Runtime，即对应系统路径下的动态库：C:\Windows\SysWOW64\scrrun.dll
    ' 将连接转换为字典
    For Each conn In connections
        jumpDict.Add conn(1), conn(0)
    Next conn
    ' 遍历棋盘上的每个位置
    For i = 1 To length
        ' 遍历所有可能的跳跃距离
        For j = 1 To Application.WorksheetFunction.Min(i, 6)
            ' 更新到达当前位置所需的最少步数
            minSteps = dp(i - j) + 1
            If minSteps < dp(i) Then
                dp(i) = minSteps
            End If
        Next j
        ' 检查是否有跳点可以直接到达当前位置
        If jumpDict.Exists(i) Then
            minSteps = dp(jumpDict(i))
            If minSteps < dp(i) Then
                dp(i) = minSteps
            End If
        End If
    Next i
    ' 返回到达指定长度的最少步数
    flying_chess = dp(length)
End Function
Rem 执行过程，功能：调用自定义函数flying_chess，以弹窗方式输出结果
Sub TestRun()
    ' 定义变量
    Dim length As Integer
    Dim connections As Variant
    Dim result As Integer
    Dim i As Integer, j As Integer
    
    ' 输入棋盘长度
    length = 15
    ' 输入跳点集合，针对每个子区间，都可以直连，即骰子投出2时，可以实现先走两步，再通过起跳点2直接到达8的位置；骰子投出6时，可以实现先走六步，再通过起跳点6直接到达9的位置
    connections = Array(Array(2, 8), Array(6, 9))
    ' 调用自定义函数，返回到达指定长度的最少步数
    result = flying_chess(length, connections)
    '输出结果
    MsgBox "棋盘长度：" & length & vbCrLf & _
           "跳点连接：" & vbCrLf & Join(Application.Transpose(Application.index(connections, 0, 1)), ", ") & " => " & Join(Application.Transpose(Application.index(connections, 0, 2)), ", ") & vbCrLf & _
           "最少需要步数：" & result, vbInformation, "飞行棋"
End Sub