algorithm - 找到从一个城市到另一个城市的路径，然后在没有城市重新访问的情况下返回

Question

我在 usaco 上发现了算法问题，我无法链接到真正的问题，因为它需要身份验证，所以粘贴它。

You have just won a contest where the prize is a free vacation in Canada. You must travel via air, and the cities are ordered from east to west. In addition, according to the rules, you must start at the further city west, travel only east until you reach the furthest city east, and then fly only west until you reach your starting location. In addition, you may visit no city more than once (except the starting city, of course).

Given the order of the cities, with the flights that can be done (you can only fly between certain cities, and just because you can fly from city A to city B does not mean you can fly the other direction), calculate the maximum number of cities you can visit.

这是动态规划教程文本的一部分。本教程中还给出了解决方案的建议。

Imagine having two travelers who start in the western most city. The travelers take turns traveling east, where the next traveler to move is always the western-most, but the travelers may never be at the same city, unless it is either the first or the last city. However, one of the traveler is only allowed to make "reverse flights," where he can travel from city A to city B if and only if there is a flight from city B to city A.

It's not too difficult to see that the paths of the two travelers can be combined to create a round-trip, by taking the normal traveler's path to the eastern-most city, and then taking the reverse of the other traveler's path back to the western-most city. Also, when traveler x is moved, you know that the traveler y has not yet visited any city east of traveler x except the city traveler y is current at, as otherwise traveler y must have moved once while x was west of y.

据我了解解决方案，我认为可以通过为前向输出城市保留一个一维表和反向输出城市表来完成解决方案。例如。如果我有 5 个城市，A、B...E 按所需方向定向，城市之间的有向图是 A 是起始城市，E 是目的地。

   A | B | C | D | E
A  0 | 1 | 0 | 0 | 0
B  0 | 0 | 1 | 1 | 0
C  1 | 0 | 0 | 0 | 1
D  0 | 0 | 0 | 0 | 1
E  0 | 0 | 1 | 0 | 0

我保留了两个表，一个用于即将离任的城市，我将通过将第一个城市初始化为 1 来填充它，即。访问的最大城市数，然后对于每个下一个条目，扫描存在到当前城市的路径的所有先前城市，然后选择最大值，对反向旅行者执行相同的操作。

table[i] = Max(j=i to 0) (table[j])

我会在目的地城市有最大值，但这并不能保证任何城市都不会重复。如果我在数组字段中保留一个条目以及最大数量，我将无法将它从正向切换到反向。我正在学习动态编程，所以可能我没有得到正确的想法。这是我为图表构建的表格

A | B | C | D | E
1 | 2 | 3 | 3 | 4
1 | 1 | 2 | 1 | 3

所以将从两者中取最大。请提供方向/提示，以便我可以朝着正确的方向前进。

附言。这不是作业题

Answer 1

您使用这两个表的方法独立地为每个旅行者建模状态，作为已经访问的城市数量，结合该旅行者当前停留的位置。正如您自己发现的那样，这不会阻止两次访问一个城市。

相反，我将使用三个元素对状态进行建模:一位旅行者当前所在的城市、另一位旅行者所在的城市，以及他们总共访问过的城市数量，即他们个人计数的总和.所以你会有一个 2d 表，而不是你的两个 1d 表。单元格 (f, r) 将包含当正向旅行者在城市 f 而反向旅行者在在城市 r。

您可能会按照最小元素的顺序遍历这些状态。这意味着您接下来将扩展一个您尚未扩展的状态，并且这两个数字中较小的一个在所有未扩展状态中是最小的。如果处于那种状态，f <r，那么您将使用它来更新状态(f'，r>) 与 f'> r，如果有从 f 到 f' 的航类。另一方面，如果 r <f 你用 r 更新 (f, r') '> f 和从 r' 到 r 的航类。

在伪代码中:

first = (f: 0, r: 0)  # tuple with two members, called f and r
todo = set { first }  # a set with a tuple as its only element
visited = a map from tuples to integers, unset values defaulting to 0
visited[first] = 1
while todo is not empty:
  best = ∞
  cur = null
  for t in todo:
    if min(t.f, t.r) < best:
      best = min(t.f, t.r)
      cur = t
  todo.remove(cur)
  if (cur.f < cur.r):
    for f' in cities where flights from f arrive:
      next = (f: f', r: cur.r)  # keep r but use f' as the new f
      todo.add(next)            # will do nothing if it already is in the set
      visited[next] = max(visited[next], visited[cur] + 1)
  else:
    for r' in cities where flights to r depart:
      next = (f: cur.f, r: r')
      todo.add(next)
      visited[next] = max(visited[next], visited[cur] + 1)
best = 0
for cur in keys of visited:
  if best < visited[cur]:
    if there is a flight from cur.f to cur.r: # can close the tour
      best = visited[cur]
return best