2-opt法がわかりません。

Question

今,c言語でNN法やった後に改善法で2-opt法を実行するプログラムを書いているんですけど、アルゴリズムは、理解できたですけどうまく書きあらわすことができないんで皆様の力を貸して欲しいです。その回答をみながら勉強させて欲しいです。

コード
``#include <stdio.h> #include <stdlib.h>  #include <string.h> #include <math.h>


struct City {
	int id;
	float x;
	float y;
};

struct City city_data[1000000];
int city_data_num = 0;

/* The program starts here */
int main(int argc, char** argv)
{
	char line[512];
	FILE* fp;

	/* check the number of arguments */
	if (argc != 2) {
		printf("usage: ./a.out input_file_name\n");
		exit(1);
	}

	/* check whether the file can be opened */
	fp = fopen(argv[1], "r");
	if (fp == NULL) {
		printf("The file (%s) cannot be opened!\n", argv[1]);
		exit(1);
	}
	
	/* read city data and write the position of each city into the array "city_data" */
	while(fgets(line, sizeof(line), fp)) {
		char* line_r;
		line_r = strtok(line, " \t\n");
		city_data[city_data_num].id = (int)strtol(line_r, NULL, 10);
		line_r = strtok(NULL, " \t\n");
		city_data[city_data_num].x = (float)strtod(line_r, NULL);
		line_r = strtok(NULL, " \t\n");
		city_data[city_data_num].y = (float)strtod(line_r, NULL);
		city_data_num++;
	}

	/* do traveling and calculate the distance */
	do_travel(); //nn法のソースコートは省いています。
   
}

Comments

[Zuishin]

インデントはとても大事です。include も巨大化させる意味はありませんし、「#」が消えています。

[WoodenHamlet]

質問を書き込むときに「B I A ○ □ ” </> 三 三 ― ＜＞」みたいなボタンが書き込み欄の上にあると思います。その</>ボタンがソースコードを打ち込むときに使うボタンです。一度押してみてください。使い方は直感的に判るはずです。

[Zuishin]

修正ありがとうございます。おしい。もうちょっと頑張ってみてください。

[WoodenHamlet]

その</>ボタンは何のためのボタンなのか考えてみて、そして自分の質問文がよみやすく表示されているのかどうか読み直して。ボタンを押しゃー良いみたいな話じゃないでしょう

Answer 1

未だ質問が見づらいままですが，一応回答をば．

実装方法としては，巡回路を配列で持っている場合とリストで持っている場合で違ってくるのですが，もし配列で巡回路を持っているなら，2本の枝交換は実質配列内の部分要素列をひっくり返す操作と同じなので，それで実装できます．

typedef struct {
  unsigned length;
  unsigned *data;
} path_t;

void apply_2opt(path_t* path, unsigned i, unsigned j)
{
  unsigned start = (i < j ? i : j);  // 開始点のインデックス
  unsigned end   = (i < j ? j : i);  // 終了点のインデックス
  // 開始点から終了点まで前と後ろを入れ替える
  while(start < end) {
    unsigned tmp      = path->data[start];
    path->data[start] = path->data[end];
    path->data[end]   = tmp;
    ++start;
    --end;
  }
}

コードとか間違ってるかもしれないので，その辺は自分で確認しながらやってみてください．

ちなみにリストの方（なんかもっと簡単な方法があったはずだけど，忘れたのでベタな方法で）

typedef struct _path_t {
  unsigned city;
  struct _path_t* prev_city;
  struct _path_t* next_city;
} path_t;

void swap_prev_next(path_t* path)
{
  path_t* tmp = path->next_city;
  path->next_city = path->prev_city;
  path->prev_city = tmp;
}

void apply_2opt(path_t* path, unsigned i, unsigned j)
{
  // 開始点を求める
  path_t* start = path;
  while(start->city != i) start = start->next_city;
  // 終了点を求める
  path_t* end = path;
  while(end->city != j) end = end->next_city;
  // 間をひっくり返す
  path_t* p = start;
  while(p != end) {
    path_t* old_next = p->next;
    swap_prev_next(p);
    p = old_next;
  }
  // 両端をひっくり返す
  path_t* tmp      = start->next_city;
  start->next_city = end->prev_city;
  end->prev_city   = tmp;
}