圆形容器内的等圆装配问题在众多领域中有广泛的应用, 可以用来对多种组合优化问题进行建模.
圆形容器内的等圆装配问题主要研究使用大圆装小圆的问题.
例如, 光纤电缆的制造与建筑材料运输等众多应用场景都可以建模为等圆装配问题.
在理论上, 等圆装配问题是经典的非线性连续优化问题, 其求解算法往往还涉及物理系统模拟.
高效的等圆装配问题求解算法具有极其重要的理论与应用价值.

圆形容器内的等圆装配算法训练

问题概述

给定若干单位圆, 请将其无重叠地放置于一个圆形容器内, 使该圆形容器的半径最小 (即容器半径与等圆半径的比例最小).

  • 参考文献.
    • [1] X. Lai, J.-K. Hao, D. Yue, Z. Lü, and Z.-H. Fu, “Iterated dynamic thresholding search for packing equal circles into a circular container,” European Journal of Operational Research, vol. 299, no. 1, pp. 137–153, May 2022, doi: 10.1016/j.ejor.2021.08.044.
    • [2] http://www.packomania.com

命令行参数

请大家编写程序时支持两个命令行参数, 依次为运行时间上限 (单位为秒) 和随机种子 (0-65535).
算例文件已重定向至标准输入 stdin/cin, 标准输出 stdout/cout 已重定向至解文件 (如需打印调试信息, 请使用标准错误输出 stderr/cerr).
例如, 在控制台运行以下命令表示调用可执行文件 peccp.exe 在限时 600 秒, 随机种子为 12345 的情况下求解路径为 ../data/n50.txt 的算例, 解文件输出至 sln.n50.txt:

1
peccp.exe 600 123456 <../data/n50.txt >sln.n50.txt

  • 运行时间上限.
    • 超出运行时间上限后测试程序会强行终止算法, 请确保在此之前已输出解 (最好还能自行正常退出).
  • 随机种子设置.
    • 使用 C 语言随机数生成器请用 srand.
    • 使用 C++ 随机数生成器 (如 mt19937) 请在构造时传参或调用 seed() 方法设置.

输入的算例文件格式

单独一行给出 3 个由空白字符分隔的整数, 分别表示单位圆数 N, 文献中的最优容器与等圆半径的比例 R, 用于判断单位圆是否重叠的数值误差上限 E (不超过 double 类型的精度).
事实上, 测试平台并不会进行重叠检查, 而是直接计算最小间距得到不重叠的最大半径, 故正常情况下数值误差上限 E 没有实质性作用, 仅供参考.

例如, 以下算例文件表示需放置 2 个单位圆, 圆心距大于 2.0 - 1e-15 时认为两圆不相交, 若等圆半径为 1 则大圆半径为 2.

1
2 2.0 1e-15

⯈ 验证浮点数精度
运行下面代码可以发现, 当 x < 1e-16 后, 2 - x == 2 为真, 即 double 的有效数字位数不超过 16 位.
这意味着两个大于 1 的数若差值在 1e-16 之内, 其 double 类型的二进制表示相同.
1
2
3
4
5
#include <stdio.h>
void main() {
	for (double x = 1; x > 1e-20; x /= 10) { printf("%e: %d\n", x, ((2 - x) == 2)); }
	for (double x = 1; x > 1e-20; x /= 2) { printf("%e: %d\n", x, ((2 - x) == 2)); }
}


输出的解文件格式

输出 N 行整数表示 N 个等圆相对容器圆心 (0, 0) 的位置, 第 i 行表示第 i 个等圆的圆心坐标.
每行 2 个由空白字符分隔的整数, 分别为第 i 个等圆的圆心横坐标和圆心纵坐标.
其中坐标支持两种格式:
(1) 所有等圆与容器圆心距均小于 1, 表示容器半径为 1, 最大化等圆的半径 r;
(2) 存在等圆与容器圆心距大于等于 1, 表示等圆半径为 1, 最小化容器的半径 R.
显然 r:1 = 1:R.

例如, 以下解文件表示 2 个半径为 1 的等圆圆心坐标分别为 (0, -1) 和 (0, 1), 容器半径为 2:

1
2
0 -1
0 1

上述解文件与以下解文件等价, 即 2 个半径为 0.5 的等圆圆心坐标分别为 (0, -0.5) 和 (0, 0.5), 容器半径为 1:

1
2
0 -0.5
0 0.5

提交要求

  • 发送至邮箱 szx@duhe.tech.
  • 邮件标题格式为 “Challenge2023PECCP-姓名-学校-专业“.
  • 邮件附件为单个压缩包 (文件大小 2M 以内), 文件名为 “姓名-学校-专业“, 其内包含下列文件.
    • 必要 算法的可执行文件 (Windows 平台).
    • 必要 算法源码.
      • 可重入 (可在同一线程内反复调用而不会出现数据初始化错误或内存泄漏).
      • 可并发 (可在同一进程内的多个线程同时运行多个算法求解实例而互不干扰, 满足此要求一般不能有全局的非只读变量).
      • 可伸缩 (数据结构可以根据算例规模动态申请内存, 而非根据预先指定的编译期常量进行内存分配).
    • 可选 算法在各算例上的运行情况概要, 至少包括以下几项信息 (可选, 仅在无法成功调用算法输出可通过检查程序的解时作为参考).
      • 算例名.
      • 容器半径 (大于等于 1) 或等圆半径 (小于 1).
      • 计算耗时.
    • 可选 算法在各算例上求得的颜色数最少的解文件 (可选, 仅在无法成功调用算法输出可通过检查程序的解时作为参考).
  • 其他所有问题通用的要求见 SmartLab Challenge - ReadMe.

例如:

1
2
3
4
5
6
7
8
9
10
11
12
13
苏宙行-华科-计科.zip
|   peccp.exe
|   results.csv
|
+---src
|       main.cpp
|       algorithm.cpp
|       algorithm.h
|
+---results
        n50.txt
        n51.txt
        ...

算例清单

下载地址: https://gitee.com/suzhouxing/npbenchmark.data/tree/data/PECCP/Instance

算例规模从小到大依次为 (求解难度不一定随规模增加):

n50
n51
n52
n53
n54
n55
n56
n57
n58
n59
n60
n61
n62
n63
n64
n65
n66
n67
n68
n69
n70
n71
n72
n73
n74
n75
n76
n77
n78
n79
n80
n81
n82
n83
n84
n85
n86
n87
n88
n89
n90
n91
n92
n93
n94
n95
n96
n97
n98
n99
n100
n101
n102
n103
n104
n105
n106
n107
n108
n109
n110
n111
n112
n113
n114
n115
n116
n117
n118
n119
n120
n121
n122
n123
n124
n125
n126
n127
n128
n129
n130
n131
n132
n133
n134
n135
n136
n137
n138
n139
n140
n141
n142
n143
n144
n145
n146
n147
n148
n149
n150
n151
n152
n153
n154
n155
n156
n157
n158
n159
n160
n161
n162
n163
n164
n165
n166
n167
n168
n169
n170
n171
n172
n173
n174
n175
n176
n177
n178
n179
n180
n181
n182
n183
n184
n185
n186
n187
n188
n189
n190
n191
n192
n193
n194
n195
n196
n197
n198
n199
n200
n201
n202
n203
n204
n205
n206
n207
n208
n209
n210
n211
n212
n213
n214
n215
n216
n217
n218
n219
n220
n221
n222
n223
n224
n225
n226
n227
n228
n229
n230
n231
n232
n233
n234
n235
n236
n237
n238
n239
n240
n241
n242
n243
n244
n245
n246
n247
n248
n249
n950
n951
n952
n953
n954
n955
n956
n957
n958
n959
n960
n961
n962
n963
n964
n965
n966
n967
n968
n969
n970
n971
n972
n973
n974
n975
n976
n977
n978
n979
n980
n981
n982
n983
n984
n985
n986
n987
n988
n989
n990
n991
n992
n993
n994
n995
n996
n997
n998
n999
n1000
n1001
n1002
n1003
n1004
n1005
n1006
n1007
n1008
n1009
n1010
n1011
n1012
n1013
n1014
n1015
n1016
n1017
n1018
n1019
n1020
n1021
n1022
n1023
n1024
n1025
n1026
n1027
n1028
n1029
n1030
n1031
n1032
n1033
n1034
n1035
n1036
n1037
n1038
n1039
n1040
n1041
n1042
n1043
n1044
n1045
n1046
n1047
n1048
n1049
n1950
n1951
n1952
n1953
n1954
n1955
n1956
n1957
n1958
n1959
n1960
n1961
n1962
n1963
n1964
n1965
n1966
n1967
n1968
n1969
n1970
n1971
n1972
n1973
n1974
n1975
n1976
n1977
n1978
n1979
n1980
n1981
n1982
n1983
n1984
n1985
n1986
n1987
n1988
n1989
n1990
n1991
n1992
n1993
n1994
n1995
n1996
n1997
n1998
n1999
n2000
n2001
n2002
n2003
n2004
n2005
n2006
n2007
n2008
n2009
n2010
n2011
n2012
n2013
n2014
n2015
n2016
n2017
n2018
n2019
n2020
n2021
n2022
n2023
n2024
n2025
n2026
n2027
n2028
n2029
n2030
n2031
n2032
n2033
n2034
n2035
n2036
n2037
n2038
n2039
n2040
n2041
n2042
n2043
n2044
n2045
n2046
n2047
n2048
n2049