0

私は、100、500 などの多数の都市を使用する TSP に取り組んでいます。貪欲なアルゴリズムを使用してコードを記述し、コマンド ライン引数を使用して正常に動作します。しかし、以下の形式のファイルから入力を取得する必要があります。

  1. 最初の行は都市の数です

  2. 2行目は「ユークリッド」または「非ユークリッド」です

  3. 3 行目から、n 都市の座標 (float) が得られます。

  4. 座標の後に、各都市の nxn 距離行列があります。

そのようなものは、都市の数を5にすることができます

5

ユークリッド

1.3 4.2

1.6 -3.5

1.4 1.5

6.4 3.6

4 2.4

5x5 のコスト マトリックスになりました。

すべての入力を配列に格納するにはどうすればよいですか? (n,euclidean/non-euclidean,coordinates,matrix) 入力を受け取った後、マトリックス自体を処理する必要があります。

4

1 に答える 1

1

すべてを 1 つの配列に格納することはしません。まず第一に、都市の数を読むことについて心配してください。それがわかったら、2 つの配列を割り当てることができます。1 つは各都市の座標を含む構造体を保持し、もう 1 つはコストを格納する 2D 配列です。

これは、都市を見て数えることを前提としています。この例では、座標 1.3 4.2 の都市は都市 0 になります (配列の位置 0 に格納されます)。1.6 -3.5 の都市は 1 位などになります。基本的には次のようになります。

  • 都市の数 x を読み取ります。
  • ユークリッドかどうかを読み取り、それを変数に格納します。
  • x 要素の配列都市を割り当て、別の 2 次元配列x による x のコストを割り当てます。
  • 各都市の座標を読み取り、cities[i]に格納します(都市は、座標を格納するための 2 つの float を持つ構造体の配列でなければなりません);
  • 各行 i (0 から始まる i) およびその行の各列 j (これも 0 から始まる) に対して、cost[i][j] を入力の値に設定します。

このアプローチを実装するコードは次のとおりです。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFSIZE 32

struct city {
    float c1;
    float c2;
};

int main(void) {
    int citiesNo, i, j;
    struct city *cities;
    float **cost;
    char line[BUFSIZE], euclidean[BUFSIZE];
    fgets(line, BUFSIZE, stdin);
    citiesNo = atoi(line);
    fgets(line, BUFSIZE, stdin);
    strcpy(euclidean, line);

    cities = malloc(sizeof(struct city)*citiesNo);
    cost = malloc(sizeof(float *)*citiesNo);

    for (i = 0; i < citiesNo; i++)
        cost[i] = malloc(sizeof(float)*citiesNo);

    /* Read coordinates */
    for (i = 0; i < citiesNo; i++)
        scanf("%f %f", &(cities[i].c1), &(cities[i].c2));

    /* Read costs */
    for (i = 0; i < citiesNo; i++)
        for (j = 0; j < citiesNo; j++)
            scanf("%f", &(cost[i][j]));

    /* Everything is stored now... */

    return 0;
}

scanf("%d", &citiesNo) がバッファーに改行を残し、その後の fgets() 呼び出しが空の行を返すため、最初に fgets が使用されました。必要に応じて、両方の fgets() を scanf() に置き換えることができます。バッファー サイズのチェックを行わないため、ユークリッド文字列を scanf で読み取らなかっただけです。入力が常に正しい形式であれば、これは問題ではありません。

このコードを実行すると、「euclidean」または「not euclidean」を含む文字列が変数euclideanに格納されます。

于 2013-10-10T09:29:24.987 に答える