有向无环图可定向最优边着色：最小复用文件数求解咨询

问题描述 #

• 现有P个需串行执行且无中断的进程，部分进程依赖其他进程的输出
• 依赖规则：每个进程最多读取R个输入文件，可写入0或1个输出文件，且无法即时重写输入文件
• 调度规则：无输入依赖的进程优先启动，所有依赖满足的进程可任意顺序执行
• 文件特性：可被多次读取，不再需要时可被重写
• 模型抽象：因无循环依赖，进程可视为有向无环图（DAG）的顶点，文件视为边

核心需求 #

找到一种进程执行顺序，使得满足所有进程依赖所需的可复用文件数最小（至少尽可能小）

个人分析 #

• 文件总数下限：理论下限为图的最大入度加1，但并非总能达到该下限。例如将9个进程构造成上下两个K₃,₃（所有边向下指向，多条出边对应同一可重复读取的输出文件），此时无法将文件总数压缩至3+1=4
• 暴力法不可行：典型场景下P超过10000，遍历所有拓扑排序执行顺序来比较缓冲区数量的成本过高
• 关联算法推测：该问题与边着色问题高度相关，但输出需统一颜色的特性令人困惑，确信存在对应知名算法，寻求解决方案

内容的提问来源于stack exchange，提问作者hidefromkgb