TSP.c

//「あるセールスマンが幾つかの都市を一度ずつ訪問して出発点に戻ってくるときに、移動距離が最短になる経路」を求める(全探索)。

//このプログラムでは、セールスマンが巡回しなければならない街の数nを入力した場合に、自動的に街に'A'から始まるASCIIコード
//に対応した名前が街名として順次割り当てられます。セールスマンは'A'からスタートし、最終的に'A'に戻ってくるものとしています。

//また、経路A->Bと、経路B->Aは同じものとみなしますので入力は必要最低限の項目を1回ずつ行うことになります。
//(A->Bを入力したらB->Aを入力する必要はないものとする)。
//通れないルートが有る場合、例えばA->C(またはC->A)には交通手段がないときには、経路入力の時に0を入力して下さい。
//その道を通るルートの計算を除外します。

//経路に負の数の入力はできません。
//また、街の数は今回4~32に制限させていただきました。4以下の数では経路を選択する意味がなく、あまりに大きい値は処理に時間がかかるためです。


#include<stdio.h>
#include<stdlib.h>
#include<limits.h>

#define DEBUG

int min_distance = INT_MAX;//最小の距離


//1つの街は、その街の名前(A~...)と他の街への距離というデータを持つ。自分自身の距離は0としておく。
struct City
{
  char name;//都市名
  int *distance;//他の街への距離を格納する
};

//街を巡回する順路を決定するためのリスト
struct List
{
  struct List *pre;//前
  struct List *next;//次(NULLなら存在しない)
  struct City *city;
}root;

//前方のリストの名前を確認し発見したら1を返す
int ExistSame(struct List* list, char city_name)
{
  if (list->pre == NULL)
    return 0;
  if (list->city->name == city_name)
    return 1;
  return ExistSame(list->pre, city_name);
}

//自分自身と前方のリストの距離を加算して返す再帰関数
void AddPreDistance(struct List *list, int* add)
{
  if (list->pre != NULL)
  {
    if (list->city->distance[list->pre->city->name - 'A'] == 0)
    {
      *add = INT_MAX;
      return;
    }
    *add += list->city->distance[list->pre->city->name - 'A'];
    AddPreDistance(list->pre, add);
  }
}

//経路表示用関数
void ShowList(struct List *list)
{
  if (list == NULL)
    return;
  ShowList(list->pre);
  printf("%c", list->city->name);
}

//リストを作って1パターン出来るごとに経路を計算して必要があれば更新する関数
void CreateAndCalc(struct List *list, struct City *city, int city_num)
{
  int buf;//経路の長さを保存しておく
  struct List nextList = { list, NULL, NULL };//次のリスト

  for (int i = 1; i < city_num; ++i)
  {
    if (!ExistSame(list, (char) (i + 'A')))
    {
      nextList.city = &city[i];
      list->next = &nextList;
      CreateAndCalc(list->next, city, city_num);
    }
  }
  if (list->next == NULL)
  {
    buf = list->city->distance[0];
    if (buf == 0)//0(交通が出来ない)と指定されているのにそこを通ろうとしてしまえばアウト
    {
#ifdef DEBUG//デバッグ用
      buf = INT_MAX;
      goto SHOW_DEBUG;
#endif
      return;
    }
    AddPreDistance(list, &buf);
    if (min_distance > buf)
      min_distance = buf;
#ifdef DEBUG
  SHOW_DEBUG :
    ShowList(list);
    printf(" = %d\n", buf);
#endif
  }
}


int main()
{
  int n;//都市数
  struct City *city;//街の順番

  //都市数の決定(1~3は無意味。今回は入力値を４~32に制限する)
  printf("Input city num : ");
  scanf("%d", &n);
  if (n < 4 || 32 < n)
    return 0;
    
  //都市の生成
  city = (struct City*)malloc(n*sizeof(struct City));
  //他の街への距離を格納する配列の確保
  for (int i = 0; i < n; ++i)
    city[i].distance = (int*) malloc(n*sizeof(int));
    
  //街の名前の決定(勝手にAから順に割り振られる)
  for (int i = 0; i < n; ++i)
    city[i].name = (char) ('A' + i);
  //距離の入力(不正な距離の入力検査は今回行っていない)
  printf("\nInput Distance\n");
  for (int i = 0; i < n; ++i)
    for (int j = i; j < n; ++j)
      if (i == j)
        city[i].distance[j] = 0;
      else
      {
        printf("%c to %c : ", city[i].name, (char) ('A' + j));
        scanf("%d", &city[i].distance[j]);
        if (city[i].distance[j] < 0)
          return 0;
        city[j].distance[city[i].name - 'A'] = city[i].distance[j];
      }
  puts("");
  root.pre = NULL;
  root.city = &city[0];

  CreateAndCalc(&root, city, n);

  printf("\n-----------------------------------\n");
  printf("Shortest path : %d", min_distance);
  printf("\n-----------------------------------\n");

  for (int i = 0; i < n; ++i)
    free(city[i].distance);
  free(city);

  return 0;
}