旅行推销员，有状态 [英] A travelling salesman that has state

问题描述

让我们说我们有一个有向图。我们想通过上行驶本图的边，以访问每个节点一次。每个节点都标注有一个或多个标签;一些节点可以共享的标签，甚至有完全相同的一组标签。因为我们走我们的路，我们正在收集每一个列表的不同的的我们遇到的标记 - 我们的目标是要找到它推迟购置新的标签尽可能的走

Let's say we have a directed graph. We want to visit every node exactly once by traveling on the edges of this graph. Every node is annotated with one or more tags; some nodes may share tags, and even have the exact same set of tags. As we go along our walk, we are collecting a list of every distinct tag we have encountered - our objective is to find the walk which postpones acquisition of new tags as much as possible.

要重申这是一个旅行者的比喻，让我们说，地毯推销员正试图决定哪个供应商，他应该获得他的地毯从。他提出在全市所有的地毯工厂的名单。他预约witht每个工厂，并收集各类地毯，他们做出的样本。

To restate this as a traveler analogy, let's say that a carpet salesman is trying to decide which supplier he should acquire his carpets from. He makes a list of all the carpet factories in the city. He makes an appointment witht every factory, and collect samples of the kinds of carpet they make.

让我们说我们有3个工厂，生产以下几种地毯：

Let's say we have 3 factories, producing the following kinds of carpet:

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

售货员可以采取以下途径：

The salesman could take the following routes:

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。

请注意如何有时候，业务员拜访，即使他知道他已经收集了样品为每一种地毯他们生产工厂。这个比喻在这里打破了一点，但让我们说，他必须拜访他们，因为这将是粗鲁地没​​有露面，他的任命。

Note how sometimes, the salesman visits a factory even though he knows he has already collected a sample for every kind of carpet they produce. The analogy breaks down here a bit, but let's say he must visit them because it would be rude to not show up for his appointment.

现在，该地毯样品是沉重的，而我们的销售员正行驶在脚下。本身距离不是非常重要的（假设每条边已经耗费1），但他不希望随身携带一大堆样品任何比他更需要的地方。因此，他需要这样他访问具有很多罕见的地毯（和在那里他将不得不拿起了很多新的样品）的工厂计划他的行程最后。

Now, the carpet samples are heavy, and our salesman is traveling on foot. Distance by itself isn't hugely important (assume every edge has cost 1), but he doesn't want to carry around a whole bunch of samples any more than he needs to. So, he needs to plan his trip such that he visits the factories which have a lot of rare carpets (and where he will have to pick up a lot of new samples) last.

有关上面的例子中的路径，在这里是在旅途的每个腿进行采样数（列2-4），和总和（第5列）。

For the example paths above, here are the numbers of samples carried at each leg of the journey (columns 2-4), and the sum (column 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 - 他将进行第2样品F2至F3，然后从F3 3个样品到F1

We can see now that route 2 is very bad: first he had to carry 3 sample from F1 to F3, then he had to carry 5 samples from F3 to F2! Instead, he could have went with route 4 - he would carry first 2 samples from F2 to F3, and then 3 samples from F3 to F1.

另外，如图中的最后一列，通过每一个边缘承载的样本的总和是一个好的度量他多少样本不得不携带整体：样品他进行不能减少的数量，因此早期来访多样工厂上必然膨胀的总和，和一个低总和是唯一可能通过访问同类工厂很少地毯。

Also, as shown in the last column, the sum of the samples carried through every edge is a good metric for how many samples he had to carry overall: The number of samples he is carrying cannot decrease, so visiting varied factories early on will necessarily inflate the sum, and a low sum is only possible by visiting similar factories with few carpets.

这是一个已知的问题？是否有一个算法来解决呢？

Is this a known problem? Is there an algorithm to solve it?

注：我会建议并注意使基于我的榜样问题的假设。我想出了它在现场，并刻意保持它小，简洁。可以肯定有它未能赶上许多边缘情​​况。

Note: I would recommend being careful about making assumptions based on my example problem. I came up with it on the spot, and deliberately kept it small for brevity. It is certain there are many edge cases that it fails to catch.

推荐答案

由于图形的尺寸小，我们可以考虑使用位掩码和动态规划以解决这个问题（类似与我们如何解决旅行商问题）

As the size of the Graph is small, we can consider using bit-mask and dynamic programming to solve this problem (Similar with how we solve the traveling salesman problem)

假设我们共有6个城市参观。这样的起始状态是0，结局是111111b或十进制127

Assume that we have total 6 cities to visit. So the starting state is 0 and the ending is 111111b or 127 in decimal.

这是每一个步骤，如果状态为x，我们可以很容易地计算采样售货员正在实施的数量，从国家的费用为X到Y国将成为新加入的样本数量从X到Y的次的未访问的城市的数量。

From each step, if the state is x, we can easily calculate the number of sampling the salesman is carrying, and the cost from state x to state y will be the number of newly added samples from x to y times the number of unvisited cities .

 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;
}

这篇关于旅行推销员，有状态的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！