多路径算法问题

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

阅读 267
评论
    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)
    }

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

      • 333

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

        • 1
        • 新人请关照
        class {
          int val; //节点值
          List next; //逆时针的下一个节点指针
        }
          • 3.4k

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

            撰写回答

            登录后参与交流、获取后续更新提醒

            相似问题
            推荐文章