V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
Raven316
V2EX  ›  问与答

算法相关,有依赖关系的日程顺序安排问题

  •  
  •   Raven316 · 2020-04-24 14:26:31 +08:00 · 1386 次点击
    这是一个创建于 1434 天前的主题,其中的信息可能已经有所发展或是发生改变。
    有 n 个日程,互相可能有先后依赖关系,例如 A 必须在 B 之前执行,依赖关系可以用 N*N 的 01 矩阵表示。

    求:给出要执行的日程,ABCD 等等,返回一个合法的执行顺序。

    感觉应该是非常基础的问题,无奈还是不会。。

    我现在想的方法是类似穷举:
    依次取任意一个没有任何依赖的日程,执行日程 A 后,把只依赖日程 A 的日程设为无依赖;依次深度优先搜索,无合法日程顺序就搜索另一个叶子。。。

    有没有更好的方法
    17 条回复    2020-04-24 16:20:08 +08:00
    imn1
        1
    imn1  
       2020-04-24 14:40:24 +08:00
    字段都没有给出没法回答

    原则是同一时间、同一空间、同一人,无法做两件事
    但这个顶多只是排序,并不能确定依赖关系,依赖关系必须有字段说明
    Raven316
        2
    Raven316  
    OP
       2020-04-24 14:52:54 +08:00
    @imn1 啥字段,没懂啊
    leishi1313
        3
    leishi1313  
       2020-04-24 14:56:02 +08:00 via Android   ❤️ 1
    topological sort
    favourstreet
        4
    favourstreet  
       2020-04-24 15:04:22 +08:00
    楼主如果不需要优化的算法一个栈就搞定了,这肯定是最简单的。计算带括号有各种优先级的表达式不就是楼主说的 n 个日程,有依赖关系(括号外依赖括号内的结果)这种问题吗。
    Raven316
        5
    Raven316  
    OP
       2020-04-24 15:05:54 +08:00
    @favourstreet 好像不是吧,感觉楼上说的 topological sort 就是我想要的答案了
    snowfuck
        6
    snowfuck  
       2020-04-24 15:26:15 +08:00
    我感觉也像有向无环图拓扑排序
    Raven316
        7
    Raven316  
    OP
       2020-04-24 15:27:39 +08:00
    @snowfuck 就是了
    imn1
        8
    imn1  
       2020-04-24 15:42:13 +08:00
    @Raven316 #2
    16:00 - 17:00 总结会议
    17:00 打卡下班
    17:00 - 18:00 买菜
    -----------
    这些日程不是同一件事,是没有依赖关系的,所以肯定需要一个字段表明是有关联的同一件事
    这个字段的表述方式就决定了算法,如果是父子级(或前置项)表述,自然就是拓扑等方法;
    如果是 path 方式表述,如:
    庆生宴 /买菜
    庆生宴 /准备 /食材清洗
    庆生宴 /准备 /食材预处理
    庆生宴 /准备 /调料准备
    庆生宴 /做菜
    ……
    有 xpath selector 等方法,当然日程不会写这么细,只是举个例子
    mikulch
        9
    mikulch  
       2020-04-24 15:44:55 +08:00
    斧王头像最近又出现了,似乎之前消失了一段时间啊。
    linvon
        10
    linvon  
       2020-04-24 15:52:56 +08:00
    拓扑排序,每次清掉入度为零的节点就 OK 了
    xupefei
        11
    xupefei  
       2020-04-24 15:54:27 +08:00 via iPhone
    标准的 topological sort 问题。

    昨天还有一群人说刷 leetcode 没用,这不就用到了吗?
    Raven316
        12
    Raven316  
    OP
       2020-04-24 15:55:07 +08:00
    @imn1 啊。。还是没看懂,可能我表达的不好吧

    @mikulch 作为人人讨厌的喷子低调了一段时间
    Raven316
        13
    Raven316  
    OP
       2020-04-24 15:55:27 +08:00
    @xupefei 对啊,就是工作中用到了。。
    imn1
        14
    imn1  
       2020-04-24 16:05:35 +08:00
    @Raven316 #12
    想了想,应该是你所说的“日程”和我理解不一样
    你所说的应该是类似项目管理的 item,项目管理自然就是同一件事
    我理解的是日历管理的日程(事件 /任务),这个就方方面面,事情多了去,完全不能确定是关联事件
    Raven316
        15
    Raven316  
    OP
       2020-04-24 16:06:36 +08:00
    @imn1 我随便起了个名字,不知道起啥名字好
    yukong
        16
    yukong  
       2020-04-24 16:18:12 +08:00
    看看 拓扑排序
    yukong
        17
    yukong  
       2020-04-24 16:20:08 +08:00
    dfs bfs 都可以 构造好临接链表去描述有向图 构造一个入度 map 首先找到入度为 0 的节点 通过 bfs 或 dfs 遍历其连接节点 并且更新节点的入度即可
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1964 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 16:22 · PVG 00:22 · LAX 09:22 · JFK 12:22
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.