2

usacoのアルゴリズムに問題が見つかりました。認証が必要なため、実際の問題にリンクできません。貼り付けてください。

賞品がカナダでの無料休暇であるコンテストに勝ちました。あなたは飛行機で旅行しなければなりません、そして都市は東から西に順序付けられます。さらに、規則に従って、あなたはさらに西の都市から出発し、最も遠い都市の東に到達するまで東にのみ移動し、次に出発地に到達するまで西にのみ飛行する必要があります。さらに、あなたは一度だけ都市を訪れることができます（もちろん、出発都市を除いて）。

都市の順序を考慮して、実行可能なフライトを使用して（特定の都市間でのみ飛行でき、都市Aから都市Bに飛行できるからといって、他の方向に飛行できるわけではありません）、最大数を計算します。あなたが訪れることができる都市の。

これは、動的計画法に関するチュートリアルテキストの一部です。チュートリアルにも解決策の提案があります。

最西端の都市から出発する2人の旅行者がいると想像してみてください。旅行者は交代で東に移動します。次に移動する旅行者は常に最西端ですが、最初または最後の都市でない限り、旅行者が同じ都市にいることはありません。ただし、旅行者の1人は、B市からA市へのフライトがある場合に限り、A市からB市への旅行が可能な「逆便」のみを行うことができます。

通常の旅行者のパスを最東端の都市に移動し、もう一方の旅行者のパスを逆にして西部に戻ることで、2人の旅行者のパスを組み合わせて往復を作成できることを確認するのはそれほど難しくありません。 -ほとんどの都市。また、旅行者xが移動した場合、旅行者yは、現在の都市旅行者yを除いて、旅行者xの東の都市をまだ訪問していないことがわかります。そうでない場合、旅行者yはxがyの西にある間に一度移動したはずです。

解決策を理解している限り、順方向の発信都市の1次元テーブルと、逆方向の発信都市のテーブルを保持することで解決できると思います。例えば。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

発信都市用に2つのテーブルを保持しています。最初の都市を1として初期化して入力します。訪問した最大都市の数、次に次のエントリごとに、現在の都市へのパスが存在する以前のすべての都市をスキャンし、最大を選択して、リバーストラベラーに対して同じことを行います。

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

目的地の都市で最大になりますが、これはどの都市も繰り返されないことを保証するものではありません。配列フィールドに最大数とともにもう1つのエントリを保持すると、順方向から逆方向に切り替えることができなくなります。私は動的計画法を学んでいるので、正しい考えが得られなかったのかもしれません。これは私がグラフ用に作成したテーブルです

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

したがって、両方から最大になります。私が正しい方向に進むことができるように、方向/ヒントを提供してください。

PS。これは宿題の質問ではありません

4

1 に答える 1

0

2つのテーブルを使用したアプローチでは、各旅行者の状態を個別にモデル化します。これは、すでに訪問した都市の数と、その旅行者が現在滞在している場所を組み合わせたものです。あなたが自分自身を知ったように、それは二度都市を訪れることを妨げることはありません。

代わりに、状態をモデル化するために3つの要素を使用します。1人の旅行者が現在いる都市、もう1人の旅行者がいる都市、および訪問した都市の総数、つまり個々の数の合計です。したがって、2つの1Dテーブルではなく、1つの2Dテーブルがあります。セル（f、r ）には、順方向の旅行者が都市fにいて、逆方向の旅行者が都市rにいるときに訪問した都市の中で最もよく知られている数が含まれます。

おそらく、これらの状態を最小要素の順に繰り返すでしょう。つまり、次に、まだ展開していない状態を展開し、展開されていないすべての状態の中で、これら2つの数値のうち小さい方が最小になることを意味します。その状態でf < rの場合、 fからf'へのフライトがある場合は、これを使用して状態（ f'、r）をf' > rで更新します。一方、r < fの場合、（f、r'）をr' > fで更新し、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
于 2012-10-26T21:10:32.117 に答える