1樓：zephyr
帶資源約束的最短路徑(shortest path problem with resource constraints),以下簡稱SPPRC
帶資源約束的基本最短路徑問題(Elementary shortest path problem with resource constraints)，以下簡稱ESPPRC。
巨集觀上來講，從名字上看，SPPRC是把"elementary"約束給鬆弛了的。Elementary意為：每乙個點只能被訪問一次。鬆弛了乙個約束，大體上會使得原問題簡單一些。
你從標籤演算法的角度解釋的話：
微觀上來講，對SPPRC問題，乙個點i上附著的標籤最多是多少個？ 如果 是時間窗的話。但是如果給ESPPRC定義標籤，為了「elementary」，標籤中必須包含過去訪問的所有點，如果以0,1來表示每個點是否被訪問了，總共有n個點的話，附著在i上的標籤最多可以是：
。標籤演算法對於標籤的數量非常敏感，所以這就是為什麼ESPPRC比SPPRC難求解。這也是為什麼當時間窗寬的時候列生成並不好用了。
如果從計算複雜度角度出發的話，ESPPRC可以退化成乙個"0-1揹包問題"(鬆弛時間窗，所有的點與點之間距離為0)，那麼它一定至少是NP hard。同時它也可以退化成乙個帶時間間隔的任務排序問題[1]，說明它至少是strongly NP hard，故沒有偽多項式演算法。至於SPPRC有偽多項式演算法見[2]。
SPPRC和ESPPRC的中間地帶，也就是說如何鬆弛「Elementary」是列生成解VRP的核心。80年代末到2023年，這期間有很多技術出來，比如2-cycle elimination，k-cycle elimination，ng-route。
[1] Dror M. Note on the complexity of the shortest path models for column generation in VRPTW. Operations Research.
1994 Oct;42(5):977-8.
[2] Desrochers M, Desrosiers J, Solomon M. A new optimization algorithm for the vehicle routing problem with time windows. Operations research.
1992 Apr;40(2):342-54.
為什麼光會沿光程最短的路徑傳播？
小夢 你可以假設光延所有可能路徑傳播。我們來看乙個A到B的傳播，B在介質中。因為某一處的電磁場是能影響這一點的所有電磁場的疊加，這裡考慮了光會路過所有可能路徑，所以B的光是這些所有路徑光的疊加。可以把這些光對應的傳播時間和位置畫出來。不同傳播時間的光束，其相位不一樣。在我們計算B點的光時，計算的簡單...
問乙個問題,為什麼當遇到災難且資源有限 如救生艇不夠 的時候,要優先照顧老人兒童
桃源碧池 他們可以撲騰，也許可以活命。他們不能撲騰，所以需要優先。又不是滅種，需要留種。再說，那麼多紀元，情感紀元並非最優越。地球並不熱衷繁衍。 廣寒 嗯，第一次被邀，謝。周琳的答案裡的原則應該是弱肉強食的叢林法則吧，那是自然規律，但是人類之所以自稱為高等生物，不過是建立了倉廩實而知禮節，衣食足而知...
裝箱問題為什麼是NP完全的？
facetothefate 這個證明很簡單，所以經常省略。經常作為國外大學的課後作業。所以首先一定不要搞混什麼是P問題，什麼是NP問題 P問題 有多項式複雜度的解 NP問題 在多項式時間裡可以驗證 證明 裝箱問題是NP complete 假設我們有乙個物品集合 I 其中i屬於I有乙個大小Si屬於 0...