如图所示:
现在有这样一组路径,物体从1开始出发,目标点是5,先从逆时针看,物体可选路径为
1 => 11 => 2 => 3 => 4 => 5
1 => 11 => 12 => 4 => 5
如果物体到达结点11后,2号结点拥堵不可行走,就选择12号结点。这样的话是不是从一开始就要先计算出1到5的可行通路,在到达每个结点后动态切换路径?还是有别的更好的方式,像这种结点形式的,如果不考虑最短路径,用什么数据结构表示比较好呢?请各位指点一下。
如图所示:
现在有这样一组路径,物体从1开始出发,目标点是5,先从逆时针看,物体可选路径为
1 => 11 => 2 => 3 => 4 => 5
1 => 11 => 12 => 4 => 5
如果物体到达结点11后,2号结点拥堵不可行走,就选择12号结点。这样的话是不是从一开始就要先计算出1到5的可行通路,在到达每个结点后动态切换路径?还是有别的更好的方式,像这种结点形式的,如果不考虑最短路径,用什么数据结构表示比较好呢?请各位指点一下。
这个是图论研究的对象,比如有向图(类似有单行道情况)的路径优化问题,
常规是先列出所有可行解,排列得出最优解,但结合中间诸如临时断道等情况,其实还是路径优化问题,只是变成分阶段的路径优化,或者说动态调整问题。
在图论中,每两点间路径可以有权重值(可以是直接的距离值,也可以是计算出的路径时间等等),通过这个就可以开始计算和优化。
10 回答11.1k 阅读
15 回答8.4k 阅读
6 回答3k 阅读
5 回答4.8k 阅读✓ 已解决
4 回答3.1k 阅读✓ 已解决
8 回答6.2k 阅读
2 回答2.6k 阅读✓ 已解决
如同楼上所说,用有向图处理。
数据结构可以用二维数组
a
来维护,只填充1
或0
。如一共有
12
个节点,那应该是是一个12 x 12
的二维数组。假设i为横坐标,j为纵坐标,如果
a[i][j] === 1
,标识,节点i
可以走向节点j
,如果a[i][j] === 0
,标识,节点i
无法可以走向节点j
。反之a[j][i]
为节点j
是否可以走向节点i
12个节点有点多,我们以4个节点为例解释

如图,用他们的有向图结构定义如下,
如果在节点1,那么就取节点1可走的下一步节点列表
依次类推,挨个查找,直到终点