调度算法 - 只有首次访问付费

Question

我需要知道之前是否已经研究过以下问题:

让我们有一个有向无环图G.图是连通的,它只有一个源顶点(没有编程节点)和恰好一个汇点顶点(没有传出节点).

每个顶点都被分配了美元和非颜色的非负价格.

目标是找到从开始到水槽的步行,最大化访问边缘的价格总和.

问题是,只有在第一次访问特定颜色的顶点时才会收到价格.例如,当我们以价格1美元购买红色顶点时,那么蓝色一个价格为2美元,然后红色价格为30美元,总价格为3美元.

我特定问题的大致尺寸:50000个顶点,3000种颜色,从开始到下沉的典型步行长度约200个边缘.

             ------>[B red $1]---                   ---->[E red $1]----
            /                    \                 /                   \
[A black $0]                      ==>[D black $0]==                     ==>[G black $0]
            \                    /                 \                   /
             ---->[C green $2]---                   ->[F green $1000]--

Answer 1

有趣的问题。它是 NP 困难的，但与近似算法文献中的任何经典都没有相似之处。

通过示例证明从集合覆盖实例 {{1, 2, 3}, {2, 4}, {3, 4}, {4, 5}} 进行归约。所有边缘均向下。

 s:$0
 | \
 |   \
 |     \
 |     1:$100
 |      |
!A:$1  2:$100
 |      |
 |     3:$100
 |     /
 |   /
 | /
 *:$0
 | \
 |   \
 |     \
 |     2:$100
!B:$1   |
 |     4:$100
 |     /
 |   /
 | /
 *:$0
 | \
 |   \
 |     \
 |     3:$100
!C:$1   |
 |     4:$100
 |     /
 |   /
 | /
 *:$0
 | \
 |   \
 |     \
 |     4:$100
!D:$1   |
 |     5:$100
 |     /
 |   /
 | /
 t:$0

我不知道是否有一个好的近似算法（这种减少并不排除它）。使用单位流而不是路径的 LP 松弛可能足以满足分支定界的工作。