多路径算法问题

如图所示:
image.png
现在有这样一组路径,物体从1开始出发,目标点是5,先从逆时针看,物体可选路径为
1 => 11 => 2 => 3 => 4 => 5
1 => 11 => 12 => 4 => 5
如果物体到达结点11后,2号结点拥堵不可行走,就选择12号结点。这样的话是不是从一开始就要先计算出1到5的可行通路,在到达每个结点后动态切换路径?还是有别的更好的方式,像这种结点形式的,如果不考虑最短路径,用什么数据结构表示比较好呢?请各位指点一下。

阅读 2.7k
4 个回答

如同楼上所说,用有向图处理。
数据结构可以用二维数组a来维护,只填充10
如一共有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个节点为例解释
image

如图,用他们的有向图结构定义如下,

const map = [
    [0, 1, 1, 0],
    [0, 0, 0, 0],
    [0, 1, 0, 1],
    [0, 1, 0, 0],
];

如果在节点1,那么就取节点1可走的下一步节点列表

const nexts = getNext(0); // 返回 [1, 2]

function getNext(currentNode) {
    return map[currentNode]
        .map((value, index) => value ? index : null)
        .filter(item => item !== null)
}

依次类推,挨个查找,直到终点

。。你好像没表达清楚你的问题,不知道你到底要问啥,
前提条件:
求解:
疑问:

新手上路,请多包涵
class {
  int val; //节点值
  List next; //逆时针的下一个节点指针
}

这个是图论研究的对象,比如有向图(类似有单行道情况)的路径优化问题,
常规是先列出所有可行解,排列得出最优解,但结合中间诸如临时断道等情况,其实还是路径优化问题,只是变成分阶段的路径优化,或者说动态调整问题。
在图论中,每两点间路径可以有权重值(可以是直接的距离值,也可以是计算出的路径时间等等),通过这个就可以开始计算和优化。

撰写回答
你尚未登录,登录后可以
  • 和开发者交流问题的细节
  • 关注并接收问题和回答的更新提醒
  • 参与内容的编辑和改进,让解决方法与时俱进
推荐问题