algorithm - 有状态的旅行推销员

Question

假设我们有一个有向图。我们希望通过在该图的边缘上移动来恰好访问每个节点一次。每个节点都标注了一个或多个标签；一些节点可能共享标签，甚至具有完全相同的标签集。在我们行走的过程中，我们正在收集我们遇到的每个 不同 标签的列表 - 我们的目标是找到尽可能推迟获取新标签的行走。

用旅行者的类比来重申这一点，假设一位地毯销售员正试图决定他应该从哪个供应商那里购买地毯。他列出了该市所有地毯厂的 list 。他约见了每家工厂，并收集他们生产的各种地毯的 sample 。

假设我们有 3 个工厂，生产以下种类的地毯:

F1: C1, C2, C3
F2: C1, C4
F3: C1, C4, C5

推销员可以采取以下路线:

1. 从 F1 开始，收集 C1、C2、C3。去F2，收集C4(因为他已经有了C1)。去F3，收集C5(他已经有C1和C4)。
2. 从 F1 开始，收集 C1、C2、C3。去F3，收集C4和C5。去 F2，什么也不收集(因为事实证明他已经拥有了他们所有的地毯)。
3. 从 F2 开始，收集 C1、C4。去F1，收集C2、C3。前往 F3 并收集 C5。
4. 从 F2 开始，收集 C1、C4。去F3，收集C5。前往 F1 并收集 C3。
5. 从 F3 开始，收集 C1、C4、C5。去F1，收集C2，C3。转到 F2，什么也不收集。
6. 从 F3 开始，收集 C1、C4、C5。去F2，什么都不收集。前往 F1，收集 C2、C3。

请注意，有时销售员会去参观一家工厂，即使他知道他已经为他们生产的每种地毯收集了 sample 。这个类比在这里有点不合理，但假设他必须去拜访他们，因为不出席他的约会是不礼貌的。

现在，地毯 sample 很重，我们的业务员正在步行。距离本身并不是非常重要(假设每条边的成本为 1)，但他不想随身携带一大堆样本。因此，他需要计划他的行程，以便最后参观有很多稀有地毯的工厂(并且他必须在那里提取很多新 sample )。

对于上面的示例路径，这里是每段旅程携带的样本数量(第 2-4 列)，以及总和(第 5 列)。

1    0    3    4    7
2    0    3    5    8
3    0    2    4    6
4    0    2    3    5
5    0    3    5    8
6    0    3    3    6

现在我们可以看到路线2非常糟糕:首先他必须从F1携带3个样本到F3，然后他必须从F3携带5个样本到F2!相反，他本可以选择路线 4 - 他将先从 F2 携带 2 个样本到 F3，然后再从 F3 携带 3 个样本到 F1。

此外，如最后一列所示，通过每条边携带的样本的总和是衡量他必须携带多少样本的一个很好的指标:他携带的样本数量不能减少，所以尽早访问不同的工厂on 必然会使总和膨胀，而低总和只有通过访问类似的工厂且地毯很少才有可能。

这是一个已知问题吗？有算法可以解决吗？

注意:我建议在根据我的示例问题做出假设时要小心。我当场想出了它，为了简洁起见故意让它变小。可以肯定的是，它无法捕捉到许多边缘情况。

Answer 1

由于图的规模很小，我们可以考虑使用位掩码和动态规划来解决这个问题(类似于我们解决旅行商问题的方法)

假设我们总共有 6 个城市要访问。所以起始状态为 0，结束状态为 111111b 或十进制的 127。

从每一步来看，如果状态为x，我们可以很容易地计算出推销员携带的样本数量，从状态x到状态y的成本就是从x到y新增的样本数量倍 未到访城市的数量。

 public int cal(int mask) {
    if (/*Visit all city*/) {
        return 0;
    }

    HashSet<Integer> sampleSet = new HashSet();//Store current samples
    int left = 0;//Number of unvisited cities
    for (int i = 0; i < numberOfCity; i++) {
        if (((1 << i) & mask) != 0) {//If this city was visited
            sampleSet.addAll(citySample[i]);
        } else {
            left++;
        }
    }
    int cost;
    for (int i = 0; i < numberOfCity; i++) {
        if (((1 << i) & mask) == 0) {
            int dif = number of new sample from city i;
            cost = min(dif * left + cal(mask | (1 << i));

        }
    }
    return cost;
}