理解CPM算法

咱們來想一下，如果一個工作有N個子任務完成，子任務需要按照某種規則順序執行，每個子任務都有在落後於計劃日期的情況下執行所需要的時間。為了最小化整體延遲成本，需要確定一個最佳的執行順序。這種應用場景時常出現在施工項目、新產品研發、電影和影視製作等多個領域。因此，提出了CPM算法。

一、CPM算法簡介

CPM全稱是Critical Path Method（關鍵路徑法）,是一種網絡圖分析方法。CPM算法能夠根據所有子任務的完成時間和前置約束關係，確定工作完成所需要的最短時間和每個子任務的最早開始時間和最晚開始時間。

二、如何進行CPM分析

CPM分析的第一步是創建一個網絡圖，然後對網絡圖進行拓撲排序。拓撲排序主要是在已知節點依賴關係的情況下，將圖中所有節點排列成一個線性序列。這樣的處理措施就可以形成一個建立在每個子任務完成時間上的流程圖。 每個節點代表一項活動，邊代表活動間的先後次序關係。

    function cpm(nodes) {
        const edges = {}
        const visited = {}
        const stack = []

        // 找到長度為0的節點
        nodes.forEach(node => (visited[node.id] = false))
        nodes.filter(node => !node.edgesTo.length).forEach(node => dfs(node, visited, stack, edges))

        let cnt = 0
        let time = {}
        for (const node of nodes) time[node.id] = { earliestStart: 0, latestStart: Infinity }

        while (stack.length) {
            const node = stack.pop()

            if (!visited[node.id]) {
                visited[node.id] = true
                cnt++
            }

            for (let i = 0; i < node.edgesFrom.length; i++) {
                const edgeNodeId = node.edgesFrom[i]
                const updateList = forwardUpdate(node, time, edges, edgeNodeId)
                time = { ...time, ...updateList }
            }

            if (!cnt) time[node.id].earliestStart = 0

            for (let i = 0; i < node.edgesTo.length; i++) {
                const edgeNodeId = node.edgesTo[i]
                const updateList = backwardUpdate(node, time, edges, edgeNodeId)
                time = { ...time, ...updateList }
            }
        }

        return time
    }

三、CPM分析的主要優勢

CPM分析有許多優點：

1、確定工程任何時間的瓶頸。

2、可以對某些節點出現延誤時產生的影響進行評估。如果有一個不重要的節點延遲了，對整個工程時間不會產生太大影響。而如果一條關鍵路徑上面的節點延遲了時間，那麼 代價將非常高昂。

3、允許以合理的成本（以時間為單位）內快速安排活動的完成，有效地利用資源。

四、總結

由以上分析可以得出結論：關鍵路徑法是一種很實用的項目管理工具，主要用於提高項目管理人員對項目進行計劃、監督、預測和控制的管理效能，其優點顯著，這對於提高企業的經濟效益是非常有幫助的。