0

巡回セールスマンの問題に取り組む任務があります。嘘をつくつもりはありませんが、私が現在行っている部分については、彼らが求めていることを実際には完全には理解していません。なんとなくわかりますが、完全ではありません。

セールスマンのおおよその距離を計算しています。ビットセットの 2 次元配列を作成する必要があると思いますか? とにかく値をバイナリで保存します。0 は都市が訪問されていないことを表し、1 は訪問されたことを表します。

私たちには非常に役立つアルゴリズムが与えられています。ここにいる誰かが最初のステップを手伝ってくれるなら、私はそれを完成させることができるはずです:

Create memoisation table [N][(1 << N)]

(ここで、N = 都市の数)。1 << N は、都市の数 (たとえば 5) を 2 進数に変換し、セットを 1 桁左に移動することを意味します。

私の主な問題は次のとおりです。

  1. N をバイナリに変換する (これが私がする必要があることだと思いますか?)
  2. セットを 1 つ左に移動する
  3. 実際にこれらのサイズの 2 次元配列を作成すると...

私はここで間違っている可能性があります。実際、おそらくその可能性はかなり高いです...どんな助けも大歓迎です、ありがとう!

4

1 に答える 1

0

ここで、"<<" 演算子は左シフトを意味し、">>" は右シフトを意味するという一般規則があります。任意の数値を 1 だけ右にシフトすることは 2 で除算することと同等であり、任意の数値を 2 だけ左にシフトすることは 2 を乗算することと同等です。たとえば、数値 7 (バイナリ 111) を考えてみましょう。したがって、7 << 1 は 7 * 2 = 14 である 1110 になり、7 >> 1 は 7 / 2 = 3 である 11 になります。

したがって、数値 N をバイナリとしてビットセット配列に変換するアルゴリズムは次のとおりです。

  1. N mod 2 (N を 2 で割った余りを取る)
  2. 残りをコレクションに格納します (つまり、 List、Array、Stack )
  3. N を 2 で割る
  4. N/2 >1 の場合 N/2 でステップ 1 から繰り返します
  5. それ以外の場合は、配列を逆にして、ビットセットを取得します。

セットを左に 1 に移動します。1 つ左にシフトすることを意味する場合は、N<<1 で実行できます

これは、C ++で2次元配列を作成する方法です

[変数型] TwoDimensionalArray[サイズ][サイズ];

この問題については、C++ビットセットについて読みたいと思うかもしれませんが、ビットセットを使用して簡単に実装できます。そのためには、使用するビットセットのサイズを把握するだけです。たとえば、N の最大値が 15 の場合、ビットセット サイズ 4 が必要です。4 ビットで表現できる最大数は 15 (バイナリ 1111) であるためです。お役に立てれば。

于 2013-06-03T04:35:29.023 に答える