发表更新游记/报告19 分钟读完 (大约2823个字)

TSP问题求解初探——一次差点失败的算法比赛报告

这是 2024 年全球校园人工智能算法精英大赛——算法巅峰赛的解题报告（游记）。

前情提要

友人 X 向我介绍了这个比赛，说这是神秘算法线上水赛，遂给江苏省人工智能协会上交 500 大洋。

比赛分为两个部分：第一部分是抽取算法题限时解答，第二部分是“优化算法题”（任何文件都没有更具体的说法）。

第一部分

某一天晚上抱着一鼓作气的心态拿了电脑去七楼自习室准备通宵。结果抽到的题目都很简单，不论组委会标定的难度，所以题目都忘记了。整场比赛最难的是特判“没有任何输入”的情况，以及应对神秘的输入格式，以下是一个例子：

题目要求：输入 $n$ 个点，每个点有 $x, y$ 两个坐标。

一般算法竞赛的输入格式可能是：

1
2
3
4
5
6
5
3 4
4 3
1 5
5 1
7 2

然而这个神秘输入格式竟然是：

1
[(3, 4),(4, 3),(1, 5),(5, 1),(7, 2)]

没有 $n$ 值，带了一堆无意义的标点（可能是 Python 生成直接输出）。然而更逆天的数据还在后面：

1
[]

$n = 0$，是的，第一次在算法比赛特判这种情况。做到这里的时候已经无语苦笑了。

虽然数据很逆天，但是一小时还是顺利拿满 $420$ 分。没想到更逆天的还在后面——

第二部分

题目大意：给定一些环，要求你在每个环上任选一点做 TSP 问题，求最优解的选点与路径。有 $3$ 次提交机会，邀请新人砍一刀 可以获得至多 $10$ 次额外提交。

输入格式：

1
[(3, 4),(4, 3),(1, 5),(5, 1),(7, 2)]@[(1, 1),(4, 5),(1, 4)]

一眼 NP 问题，所以完全没奔着求精确解，然后开始考虑启发式算法。想起计算思维课提到过用遗传算法解决类似问题，但是最后没有写这种方法，而是准备仿照 OI 的风格，打一个模拟退火。

具体来说，最优路径的结果可以抽象成一组 $1 \sim n$ 之间的排列，以及它们对应多边形中选择的点，以上一共 $2n$ 个数据。解空间值域的有限性启示我们采用启发式算法解决本问题。算法首先设定初始温度并生成随机的一个解，然后对此解做变换并降低温度（乘以降温因子）。随着温度降低，做的变换也逐渐保守，接受局部更劣解的概率也更低（$P=e^{-\frac{\delta}{T}}$），最后期望生成的解收敛在全局最优解附近。

考虑变换分成四个阶段对应温度逐渐降低、“活性”逐渐下降的过程，在最开始是完全随机生成凸包排列与选点，然后是交换一对凸包顺序并重新选点，再后是重新选点，最后是修改一对选点。每一阶段开始前继承上一阶段最好结果，最后输出结果。

代码比较好写，参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
struct Point {
  int x, y;
  Point() : x(0), y(0) {}
  Point(int x, int y) : x(x), y(y) {}
  bool operator<(const Point& other) const {
    if (x != other.x) return x < other.x;
    return y < other.y;
  }
}; //“点”的类型
double Rand() { return (double)rand() / RAND_MAX; }
double dis(Point X, Point Y) {
  double ans = sqrtl((X.x - Y.x) * (X.x - Y.x) + (X.y - Y.y) * (X.y - Y.y));
  return ans;
}
struct Closure {
  vector<Point> point;
  unsigned int size() { return point.size(); }
  Point& operator[](int x) { return point[x]; }
  void insert(Point x) { point.push_back(x); }
  void forget() { point.clear(); }
}; //“环”的类型
vector<Closure> plate;
vector<int> permu, choice;          // current
vector<int> bestPermu, bestChoice;  // historical best
int closure_cnt, epoch_cnt;

//超参数
const double Threshold[4] = {50000, 10000, 2500, 0};
const double initTemperature = 100000.0;
const double lowThreshold = 0.0005;
const double stepRatio = 0.99314159;
const double MAX_TIME = 9.4;

double answer = 1145141919810.0;

//神秘的处理输入方式，结尾居然没有换行！喜欢getline()的选手要注意
void input() {
  string s;
  getline(cin, s);
  int len = s.length();
  int tempx = 0, tempy = 0, cnt = 0;
  Closure c;
  for (int i = 0; i < len; i++) {
    if ('0' <= s[i] && s[i] <= '9') {
      if (cnt % 2 == 0) {
        tempx *= 10;
        tempx += s[i] - '0';
      } else {
        tempy *= 10;
        tempy += s[i] - '0';
      }
    } else if (s[i] == ',' || s[i] == '@') {
      cnt += 1;
    } else if (s[i] == ')') {
      c.insert(Point(tempx, tempy));
      tempx = 0;
      tempy = 0;
    } else if (s[i] == ']') {
      plate.push_back(c);
      c.forget();
    }
  }
  return;
}

//求每一个解的距离
double dist(vector<int>& _permu, vector<int>& _choice) {
  double ans = 0.0;
  /*map<Point, int> mp;
  for (int i = 0; i < plate.size(); i++) {
    if (mp[plate[_permu[i]][_choice[i]]] > 0) {
      ans = 1145141919810.0;
      return ans;
    }
    mp[plate[_permu[i]][_choice[i]]]++;
  } */ //伏笔
  for (int i = 0; i < plate.size(); i++) {
    if (i != plate.size() - 1) {
      ans += dis(plate[_permu[i]][_choice[i]],
                 plate[_permu[i + 1]][_choice[i + 1]]);
    } else {
      ans += dis(plate[_permu[i]][_choice[i]], plate[_permu[0]][_choice[0]]);
    }
  }
  return ans;
}

//模拟退火，启动！
void simulateAnneal() {
  bool trigger1 = false, trigger2 = false, trigger3 = false;
  auto seed = chrono::system_clock::now().time_since_epoch().count();
  mt19937 generator(seed);
  uniform_int_distribution<int> distribution(1, 2147483647);
  uniform_real_distribution<double> distribution2(0, 1);
  double Temperature = initTemperature;
  vector<int> nowpermu(permu), nowchoice(choice);
  while (Temperature > lowThreshold) {
    if (Temperature > Threshold[0]) {
      shuffle(nowchoice.begin(), nowchoice.end(), default_random_engine(seed));
      for (int i = 0; i < closure_cnt; i++) {
        nowchoice[i] = distribution(generator) % (plate[nowpermu[i]].size());
      }
    } else if (Temperature > Threshold[1]) {
      if (!trigger1) {
        trigger1 = true;
        nowpermu = bestPermu, nowchoice = bestChoice;
      }
      int i = distribution(generator) % closure_cnt,
          j = distribution(generator) % closure_cnt;
      swap(nowpermu[i], nowpermu[j]);
      for (int i = 0; i < closure_cnt; i++) {
        nowchoice[i] = distribution(generator) % (plate[nowpermu[i]].size());
      }
    } else if (Temperature > Threshold[2]) {
      if (!trigger2) {
        trigger2 = true;
        nowpermu = bestPermu, nowchoice = bestChoice;
      }
      for (int i = 0; i < closure_cnt; i++) {
        nowchoice[i] = distribution(generator) % (plate[nowpermu[i]].size());
      }
    } else {
      if (!trigger3) {
        trigger3 = true;
        nowpermu = bestPermu, nowchoice = bestChoice;
      }
      int i = distribution(generator) % closure_cnt,
          j = distribution(generator) % closure_cnt;
      nowchoice[i] = distribution(generator) % (plate[nowpermu[i]].size());
      nowchoice[j] = distribution(generator) % (plate[nowpermu[j]].size());
    }
    // new solution generated.
    // if better : reserved, updated;
    // if not : probability -> updated.
    double newanswer = dist(nowpermu, nowchoice);
    double lastanswer = dist(permu, choice);  // current;
    double delta = newanswer - lastanswer;    //<0:ac>0:prob
    if (delta < 0) {
      // reserve!
      if (newanswer < answer) {
        // best arrived!
        bestPermu = nowpermu;
        bestChoice = nowchoice;
        answer = newanswer;
      }
    }
    if (exp(-delta / Temperature) > distribution2(generator)) {
      // update!
      permu = nowpermu;
      choice = nowchoice;
    }
    // cerr << Temperature << " " << answer << endl;
    Temperature *= stepRatio;
  }
  epoch_cnt++;
}

void output() {
  cout << '[';
  for (int i = 0; i < closure_cnt; i++) {
    cout << "(" << plate[bestPermu[i]][bestChoice[i]].x << ", "
         << plate[bestPermu[i]][bestChoice[i]].y << ")";
    if (i != closure_cnt - 1) cout << ",";
  }
  cout << ']' << endl;
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  auto seed = chrono::system_clock::now().time_since_epoch().count();
  mt19937 generator(seed);
  uniform_int_distribution<int> distribution(1, 2147483646);
  input();
  closure_cnt = plate.size();
  permu = vector<int>(closure_cnt, 0);
  for (int i = 0; i < closure_cnt; i++) permu[i] = i;
  choice = vector<int>(closure_cnt, 0);
  for (int i = 0; i < closure_cnt; i++) {
    choice[i] = distribution(generator) % (plate[permu[i]].size());
  }
  bestPermu = permu;
  bestChoice = choice;
  answer = dist(permu, choice);
  //卡时间技巧：只要没有到一个接近上限的时间，就继续从上一次解出发做模拟退火
  while ((double)clock() / CLOCKS_PER_SEC < MAX_TIME) simulateAnneal();
  output();
  return 0;
}

理论上选择合适的超参数就能得到比较可爱的解。

问题来了：怎么定义合适？不像其他赛道，这道题一没有正确的测试用例（给了一组并非最优的），二没有公开评分标准。于是只能猜测评分只与答案和最优解的接近程度有关。考虑到基于 MST 的做法能做到最优解的 $2$ 倍以内，小数据用暴力跑出精确解，并定义：

  • 小数据得分 $\text{Acc} = 1-\frac{Dist(解)-Dist(暴力)}{Dist(暴力)}$；

  • 大数据得分 $\text{Exp}=0.7 \text{Average(Dist(解))+0.15Max(Dist(解))+0.15Min(Dist(解))}$

作为对组委会标准的模拟。

暴力代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
#include <bits/stdc++.h>
#define DEBUG false
#define LOG true
#include <chrono>
#include <random>
using namespace std;
struct Point {
  int x, y;
  Point() : x(0), y(0) {}
  Point(int x, int y) : x(x), y(y) {}
};
double Rand() { return (double)rand() / RAND_MAX; }
double dis(Point X, Point Y) {
  double ans = sqrtl((X.x - Y.x) * (X.x - Y.x) + (X.y - Y.y) * (X.y - Y.y));
  return ans;
}
struct Closure {
  vector<Point> point;
  unsigned int size() { return point.size(); }
  Point& operator[](int x) { return point[x]; }
  void insert(Point x) { point.push_back(x); }
  void forget() { point.clear(); }
};
vector<Closure> plate;
vector<int> permu, choice;          // current
vector<int> bestPermu, bestChoice;  // historical best
int closure_cnt, epoch_cnt;

double answer = 1145141919810.0;
void input() {
  string s;
  getline(cin, s);
  int len = s.length();
  int tempx = 0, tempy = 0, cnt = 0;
  Closure c;
  for (int i = 0; i < len; i++) {
    if ('0' <= s[i] && s[i] <= '9') {
      if (cnt % 2 == 0) {
        tempx *= 10;
        tempx += s[i] - '0';
      } else {
        tempy *= 10;
        tempy += s[i] - '0';
      }
    } else if (s[i] == ',' || s[i] == '@') {
      cnt += 1;
    } else if (s[i] == ')') {
      c.insert(Point(tempx, tempy));
      // cout << "caught:" << tempx << "," << tempy << endl;
      tempx = 0;
      tempy = 0;
    } else if (s[i] == ']') {
      plate.push_back(c);
      c.forget();
    }
  }
  return;
}
double dist(vector<int>& _permu, vector<int>& _choice) {
  double ans = 0.0;
  for (int i = 0; i < plate.size(); i++) {
    if (i != plate.size() - 1) {
      ans += dis(plate[_permu[i]][_choice[i]],
                 plate[_permu[i + 1]][_choice[i + 1]]);
    } else {
      ans += dis(plate[_permu[i]][_choice[i]], plate[_permu[0]][_choice[0]]);
    }
  }
  return ans;
}

void output() {
  cerr << answer << endl;
  if (DEBUG) {
    cerr << "shortest path = " << answer << endl;
    cerr << "plan:" << endl;
  }
  cout << '[';
  for (int i = 0; i < closure_cnt; i++) {
    cout << "(" << plate[bestPermu[i]][bestChoice[i]].x << ", "
         << plate[bestPermu[i]][bestChoice[i]].y << ")";
    if (i != closure_cnt - 1) cout << ",";
  }
  cout << ']' << endl;
}
void dfs(int cur) {
  if (cur == closure_cnt) {
    if (dist(permu, choice) < answer) {
      bestChoice = choice;
      bestPermu = permu;
      answer = dist(bestPermu, bestChoice);
    }
    return;
  }
  for (int i = 0; i < plate[permu[cur]].size(); i++) {
    choice[cur] = i;
    dfs(cur + 1);
  }
  return;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  input();
  if (DEBUG) cerr << "111" << endl;
  closure_cnt = plate.size();
  permu = vector<int>(closure_cnt, 0);
  for (int i = 0; i < closure_cnt; i++) permu[i] = i;
  choice = vector<int>(closure_cnt, 0);
  for (int i = 0; i < closure_cnt; i++) choice[i] = 0;
  do {
    dfs(0);
  } while (next_permutation(permu.begin(), permu.end()));
  output();
  if (LOG) fclose(stderr);
  if (LOG) cerr << "END" << endl;
  return 0;
}

写了 Shell 脚本方便测试：

1
2
3
4
5
6
7
8
9
$folderPath = "./sample"
$files = Get-ChildItem -Path $folderPath -File
Remove-Item -Path "./out.txt"

foreach ($file in $files) {
    $filePath = $file.FullName
    Write-Host "Processing file: $filePath"
    Get-Content $filePath | & ./main.exe
}

生成测试数据的代码实在有点丑陋，就不放了，做法是随机选点，然后随机半径转 $2 \pi$ 即可。

测了十几组，最后收到了 $\text{Acc}=0.99699, \text{Exp} \leq 30000$ 的好结果，遂提交。结果发现，虽然官方测试数据里有环有重复点，但是我们不能选重复点（即使这样更优）！我尽量忍住对组委会的反感，把上文代码的「伏笔」加了回去，再提交一发，但是没有得到很好的分数。

面对题目的各种语焉不详，这时候已经完全不想打了。不过意识到「伏笔」对测试结果有影响，重新测了一遍，挑了一个稍微看得过去的解提交了，得到了更低的分数（笑），算是草草结束了这场比赛，在当时的排名得到省级二等奖。

总结，以及反转？

  • 第一阶段随机选点真的有意义吗？

的确，这样其实损失了之前轮次最优解的信息。对大数据作图也能注意到其实只有第一轮在第一、二阶段发生了距离的骤降。也许可以只在前几轮次跑第一、二阶段，通过大量遍历找局部较优解。

  • 怎么找参数？测参数还能更自动化吗？

参数随手填的，事实上第一组已经很优秀了。一种做法是让喜欢的人发一大串数字，从中找符合范围的数字，放缩填进去试试。测试过程可以更自动化，不过自动化实现毕竟也要时间，我还是卡 ddl 做的，所以很遗憾没有具体实现。

  • 群里有人讨论遗传，为什么选模拟退火算法？

有点执念。这是学 OI 之初就听说的神秘算法（喜欢的人在那时候也觉得这个算法本身很神奇），而且一位同学也在百度之星用这个算法获得了一个 AC。

  • 为什么卡 ddl 做？

想了一段时间，到后期已经被语焉不详的规则折磨疯了，不是很想打了。希望组委会明年能改进吧。

后续：作弊的人有点多，排名上升了数十位，惊险拿到国三。

发表更新题解2 分钟读完 (大约342个字)

题解 P5238 【整数校验器】

这是一道比较简单的题，涉及少量字符串相关知识。

需要注意的点：

  • 合法性判定

  • 带正负的高精大小比对

部分坑点：

  • 双负时绝对值大的数反而小

  • 需要依据正负性选择判定大小方法，且须在判定时去掉符号

  • “-“是一部分数据，因为：

    保证 $x$ 长度至少为 11 且仅由 ‘0’~’9’ 及 ‘-‘ 构成，且 ‘-‘ 只会出现在第一个字符。

好了，一切尽在代码中。上代码——

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<iostream>
#include<string>
using namespace std;
bool pn(string a) //正负判定
{
    if(a[0]=='-') return false;
    else return true;
}
int comp(string a,string b) //比对
{
    if(pn(a)==true && pn(b)==false) return 1;
    if(pn(a)==false && pn(b)==true) return 0;
    //前置判定，省去一边去一遍不去之苦
    if(pn(a)==true && pn(b) ==true) //双正判定
    {
        if(a.length()>b.length()) return 1;
        if(a.length()<b.length()) return 0;
        for(int y=0;y<a.length();y++)
        {
            if(a[y]>b[y]) return 1;
            if(a[y]<b[y]) return 0;
        }
        return 2;
    }
    if(pn(a)==false && pn(b)==false) //双负判定（注意几乎是反过来的！）
    {
        if(a.length()<b.length()) return 1;
        if(a.length()>b.length()) return 0;
        for(int y=1;y<a.length();y++) //习惯于忽略负号
        {
            if(a[y]<b[y]) return 1;
            if(a[y]>b[y]) return 0;
        }
        return 2;
    }
}
bool val(string a) //合法性判定
{
    if(a=="0") return true; //对0提前判定，避免与后冲突
    if(a=="-") return false; //这种数据害得我最终分少了10分
    if(a[0]=='-' && a[1]=='0') return false; //-0~类
    if(a[0]=='0') return false; //0~类
    return true;
}
string l,r;
int t;
int main()
{
    cin>>l>>r>>t;
    string temp;
    for(int f=0;f<t;f++)
    {
        cin>>temp;
        if(comp(temp,l)!=0 && comp(temp,r)!=1 && val(temp)==true)
        {
            cout<<'0'<<endl;
            continue;
        }
        if(val(temp)==false)
        {
            cout<<'1'<<endl;
            continue;
        }

        if(comp(temp,l)==0 || comp(temp,r)==1)
        {
            cout<<'2'<<endl;
            continue;
        }    
    }
    return 0;
}
发表更新1 分钟读完 (大约123个字)

Hello World

Welcome to Hexo! This is your very first post. Check documentation for more info. If you get any problems when using Hexo, you can find the answer in troubleshooting or you can ask me on GitHub.

Quick Start

Create a new post

1
$ hexo new "My New Post"

More info: Writing

Run server

1
$ hexo server

More info: Server

Generate static files

1
$ hexo generate

More info: Generating

Deploy to remote sites

1
$ hexo deploy

More info: Deployment

关注我

链接

分类

最新文章

归档

标签

启发式算法1
字符串处理1
模拟1
算法1
算法巅峰赛1

订阅更新

follow.it

×