(a) と (b) では、2 交換変換演算子を想定して、パス表現で TSP ツアーである解 A と B を、ツアー C、D、E、F、G の中の可能な隣接に接続します。
(a) A: 1 2 3 4 5 6 7
C: 1 3 5 7 2 4 6
D: 1 2 5 4 3 6 7
E: 2 3 1 7 5 4 6
F: 4 1 7 5 3 2 6
G: 1 2 3 7 6 5 4
(b) B: 1 3 2 7 5 4 6
C: 1 3 5 7 2 4 6
D: 1 2 5 4 3 6 7
E: 2 3 1 7 5 4 6
F: 4 1 7 5 3 2 6
G: 1 2 3 7 6 5 4
これが私に何を求めているのか、私にはわかりません。
定義(問題のテキストから推測されます。これについてはクラスでも説明したかもしれません)
パス表現の TSP ツアー:
1 から 7 までの数字の順序付けられたシーケンス。各数字は 1 回だけ引用されます。
各桁は、巡回セールス担当者が訪れた都市を表します。
たとえば、D:1 2 5 4 3 6 7は、営業担当者が都市 1 で開始し、都市 2 に移動し、
次に都市 5 に移動し、都市 7 で終了することを示します。
この時点で、「ストップ」の概念を導入し、これらに次のラベルを付けると便利です。小文字、a trhu g. (問題のさまざまなパスを識別するために使用される大文字とはまったく関係ありません)。
D パスでは、a 停留所は都市 1、c 停留所は都市 5 などです。
2 交換変換演算子
正確に 2 つの都市を交換する (より正確には、都市を 2 つの停留所と交換する) ことによって TSP パスを変換する操作。
したがって、2 交換変換操作は、パス X、2 つのストップ インデックス m、n の 3 つの引数を取り、m と n の都市が交換されたパス X' を返す操作として理解できます。
この操作を Swp() と呼ぶと、次のように記述できます。
Swp(A, c, e) = 1 2 5 4 3 6 7
割り当て(あなたの使命、それを受け入れますか ;-) )
は、パス表現の TSP ツアーであるソリューション A と B を、ツアー C、D、E、F、G の中の可能な隣人に接続
します。 A（またはB）の「隣接」パスであるC、D、EF、およびG（大文字、つまりパス）の間で識別します。つまり、これらのうちどれが単一のSwpでA（またはB）から派生できるかを識別します() 操作 (そして、おそらく前述の操作パラメーターを提供するため)。
拡張により、割り当ては、最小数のステップで、A から別のパスに移動するために必要な Swp() 操作の (複数ある可能性があるためではない) リストを見つける必要があるものとして解釈できます。