algorithm - 边缘可以被障碍物阻挡的图搜索算法-6ren

algorithm - 边缘可以被障碍物阻挡的图搜索算法

转载作者：塔克拉玛干更新时间：2023-11-03 05:25:36

25

4

我想在有向图上的两个顶点之间找到一条低成本路径，其中每条边的成本都相同。算法的易实现性和执行时间非常重要，所以如果算法更简单、更快，我愿意牺牲一个接近最优的最优解。

边缘可以被障碍物阻挡。一条边被阻塞的概率是事先已知的。阻塞是相互独立的。当到达边缘头部的顶点时，发现边缘未被阻塞或被阻塞。

我的问题类似于加拿大旅行者问题，但我的理解是随机规划问题的解决方案相对难以实现，并且寻找最优策略所花费的时间可能相对较长。

目前，我正在考虑将问题转换为确定性问题，以便可以使用 A* 等搜索算法来解决它。这是一个好方法吗？如果是，我该怎么做？

最佳答案

此问题是一个部分可观察的马尔可夫决策过程 (POMDP)。 POMDP 可以确定性地解决，但通常使用随机算法来找到近似最优解。找到真正的最优策略没有多项式时间解，即使是近似解也可能很慢。从好的方面来说，一旦您找到政策，就可以很快地遵循它。

一些可用的求解器:

关于algorithm - 边缘可以被障碍物阻挡的图搜索算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15595722/

25

4

0

java - 寻找距离玩家最近的物体(障碍物)
我有一个程序可以检查距离以及玩家是否与障碍物发生碰撞。我现在尝试计算障碍数组中的哪个障碍最接近移动的玩家，然后返回该障碍的索引。这是我到目前为止所拥有的: public static int
unity3d - unity NavMesh 障碍物
我尝试在 Unity 中创建 RTS 游戏，但在寻路方面遇到问题。我使用 NavMesh 进行寻路，效果很好:单位避免静态对象。但单位不会互相回避。有一个名为 NavMesh Obstacle 的组件
python - 当主要玩家与图像(障碍物)发生碰撞时，您如何让游戏结束？
import math import random import pygame from pygame.locals import * import sys def events(): for
python - Pygame 中的 2D 光线转换和矩形碰撞(视线，障碍物)
新程序员在我的腰带下使用了三个月的 Python(只有几周的 pygame)...... 我正在设计一个 2-D、自上而下的游戏，并且一直在尝试设置障碍来打破 sprite LOS。我目前的尝试是让每
python - 将带有空格的数据帧转换为数字、障碍物 - 空格(例如 3 014.0 即 '3\xa0014.0' )
我有一个数据框，其中存储的不是预期的数值“Object”类型的数据看起来像 3 014.0，即“3\xa0014.0”，而不是 3014.0 - 空格(即“\xa0”) - 造成转换问题问题:有什么