智能引领的p-center解决方案

问题：P・Center问题

P・Center问题

摘要

问题：从一个点集合中选择p个点作为中心点，并把其余分配到某个选择点，使得

全部点到其对应中心点距离加起来最小。

针对问题，分析得出p-center问题实质为选址问题。其研究背景为工厂选址，属于

运筹学中经典问题之一。利用智能算法中模拟退火随机局域搜索算法进行求解最小值。

详细步骤为：因为题目中未提供点集合，所以首先经过文件查阅⑴和生活实际得到可靠

二维数据点分布，即表示一个点集合，存放方式为文件存放（data.txt）；其次加载点集

合数据，采取模拟退火算法随机局域搜索算法⑵进行处理：

1）初始化：中心点个数夕=4,温度7=1000,温度缩减系数a=0.999,最大

迭代次数Iter—200。

解释：因为P-Center问题是以工厂选址问题，加上编写二维数据分布情况，所

以建立工厂数量为事先已知条件，即夕=4；初试温度设置是影响搜索性能主要

原因之一。初始化温度高，则搜索到全局最优值可能性大，但计算时间大幅度增

力口；反之，缩短了计算时间，但性能并不优越。所以采取数次试验方式确定温度

T=1000；为了确保较大搜索空间，所以让系数靠近于1；经过数次试验，确

定迭代次数=200,此时结果较为理想。

2）迭代叶二200次，循环第三步到第四步。

3）从临域中选择最好解，即确定最优值：产生新值才_〃。犷=x+Ax；增量

Af=f（x_new）-f{x}；若AF>0,则接收作为新解，否者以概率

exp（-△//（奴））接收〃邮作为新解。

4）T逐步降低，且7>rn,最终跳至第二步。

5）得到距离最小值

然后经过模拟退火局部搜索算法，得迭代情况为:

»an)oox>o

・1上・

最终经过模拟退火局部搜索算法，得出分配图为:

得出四个粗五角星为各自中心点，其中颜色相同属于各自颜色中心点，即相同颜色距离

各自中心点最短。经过Python得出最近距离为：102.

问题扩充：针对P-Center问题，还能够经过k-means聚类算法⑶进行处理，得到与

最近搜索算法•样结果。

关键词：P-Center选址问题模拟退火随机局域搜索算法K-Means聚类算法

目录

P-Center问题1

摘要1

1问题重述5

2数据预处理5

2.1数据来源5

2.2数据预处理方法5

2.3数据选取参考原则6

3问题分析6

3.1问题6

4问题假设6

5符号说明7

6模型的建立与求解7

6.1解法一8

6.1.1模拟退火随机局部搜索算法8

6.1.2算法求解9

6.2解法二12

6.2.1K-Means聚类算法12

6.2.2算法求解12

7模型的评价13

8参考文献14

附录14

附录一模拟退火随机局域搜索算法Python代码15

附录一聚类算法Python代码20

附录三迭代次数与目标函数关系28

附录四结论图42

1问题重述

选址问题是运筹学中经典问题之一。经典选址问题包含连续选址问题、离散选址问

题、P-Median问题以及P-Center问题等。该问题属于P-Center问题，从一个点集合中

选择P个点作为中心点，并把其余点分配到某个选择点，使得全部点到其对应中心点距

离加起来最小。

2数据预处理

注：数据存放形式为:data.txt,可在附件一中查看

2.1数据起源

（1）文件查阅

（2）生活实际

2.2数据预处理方法

（1）数据选取：去除无效数据以及噪声数据。

（2）数据整合：将若干个数据库整合成一个数据存放结构。

（3）数据代替：将杂乱数据代替成易处理数据。

（4）数据变换：将原始数据转换为适合任务定价形式。

2.3数据选取参考标准

（1）统一数据源编码。

（2）去除唯一属性。

（3）去除重复属性。

（4）去除可忽略字段。

（5）深入处理：去除异常数据，去除附带噪声数据，填充空缺值、丢失值。

3问题分析

3.1问题

首先，经过文件查阅和生活实际得到可靠二维数据点分布，将此二维分布作为数据点集

合，然后经过模拟退火最近搜索算法⑷进行迭代优化，最终得到全部点到其中心点距离。

4问题假设

L假设依照数据特征或者政策（比如工厂政策）确定，即已经确定P-Cente「中p中心

个数。

2.假设点集合为二维集合，不包含任何三维或者多维信息。

5符号说明

6模型建立与求解

选址问题现在有多个求解方法，大致分为定性和定量两类：定性方法主要是结合层次分

析法和含糊综正当对各方案进行指标评价，最终得出最优选址；定量方法主要是松弛算

法和启发式算法以及二者结合。而本题处理是P-Center问题，即使用启发式算法-智能

算法模拟退火随机局部搜索算法⑸进行处理。

6.1解法

6.1.1模拟退火随机局部搜索算法

模拟退火算法是一个贪心算法，不过其搜索过程引入了随机原因。在迭代更新可行解时,

以一定概率来接收一个比当前解要差解，所以有可能会跳出局部最优解，达成全局最优

解，其搜索原理以下列图：

图1模拟退火随机局部搜索算法示意图

假定当前可行解为x,迭代更新后解为＞new,那么对应〃能量差〃定义为:

△f=f(x_new)—f(x)

以对应概率接收新值，此概率为:

exp(-孝)最小值优化问题

夕(Af)=K1

exp(^)最大值优化问题

模拟退火随机局域搜索算法思绪为:

图2模拟退火随机局域搜索算法思绪图

6.1.2算法求解

注：详细Python程序见附录一与附件一

依照算法思想，经过Python得到迭代与目标函数关系为:

180-

17o

16o

r5o

W

*

14

吗o

生

HL3o

L2o

11O

100-,,

6i5075100125150175200

速代次发

图3模拟退火训练曲线图

能够看出经过200次迭代，优化目标函数处于相对稳定状态。详细目标函数与迭代次数

对应关系见附录，以下为部分对应关系：

第186次迭代:目标函数=186,193903261

第187次迭代:目标函数=215.784785022

第188次迭代:目标函数=186.998732666

第189次迭代:目标函数=166.417149078

第190次迭代:目标函数=224,515369868

第191次迭代:目标函数=240,503650114

第192次迭代:目标函数=224,599534187

第193次迭代:目标函数=245,57430458

第194次迭代:目标函数=331,210864乃8

第195次迭代,目标函数=236.657697786

第196次迭代:目标函数=244.844816837

第197次迭代:目标函数=238,634981095

第198次迭代:目标函数=267,60921475

第199次迭代:目标函数=231,441025132

图4部分迭代次数与目标函数关系

最终得出点集合分配图为:

图5点集合分配图

得出四个粗五角星为各自中心点，其中颜色相同属于各自颜色中心点，即相同颜色距离

各自中心点最短。经过Python得出最近距离为：102.

6.2解法二

经过智能算法中模拟退火随机局域搜索算法能够得出对应结论，为了检验以及去探索更

多处理方式，使用了聚类算法，以下为模型以及过程。详细Python代码见附录二以及

附件一。

6.2.1K-Means聚类算法

算法过程以下：

1）从N个点中随机选取p个点作为中心点

2）对剩下点测量到其每个中心点距离，并把它归到中心点类

3）重新计算已经得到各个类中心点

4）迭代第二步、第三步直至新中心点与原中心点相等或者小于指定阈值，算法结束

6.2.2算法求解

经过Python程序将经过文件查找点集合数据data.txt进行聚类分析，得到与局域搜索算

法类似分配图，以下列图所表示:

Distributiondiagram

图6聚类分析分配图

此图解释与模拟退火随机局域搜索算法相同，不再重复解释。

一样能够得出全部点到对应中心点距离最小为：102.。

7模型评价

7.1模型优缺点

模型优点:

（1）经过模拟退火随机局域搜索算法应用十分广泛，能够高效处理NP完全问题

（2）模拟退火随机搜索算法与K-Means聚类算法相互结合，相互印证，使得数据

准确性得以确保。

（3）经过模拟退火算法与K-Means算法得出点集合分配图能够形象生动得出二维

数据关系.

模型缺点:

(1)模拟退火随机局域搜索算法初始化设置必须准确，要经过数次试验才能得到

适宜初始化值。

8参考文件

[1]CCEHC:Anefficientlocalsearchalgorithmforweightedpartialmaximum

satisfiability,ArtificialIntelligence,z

[2]LocalSearchforMinimumWeightDominatingSetwithTwo-LevelConfigurationChecking

andFrequencyBasedScoringFunction,JournalofArtificialIntelligenceResearch(JAIR),,

⑶王守强.多中心点聚类问题随机算法[D].山东大学,.

⑷朱泓丞.设施选址问题研究与应用[D].中国科学技术大学,.

⑸蒋建林,徐进澎，文杰.基于单亲遗传模拟退火算法顶点P-中心问题[J].系统工程学

报〃26(03):414-420.

附录

注：详细代码见附件

附录一模拟退火随机局域搜索算法Python代码

importnumpyasnp

importmatplotlib.pyplotaspit

importmatplotlib

importscipy.spatial.distanceasDS

importrandom

zandaoguangfont=matplotlib.font_manager.FontProperties(fname='a.TTF')

deff(x):

min

目标函数，全部点到中心点距离和

:paramx:list表示中心点序号

:paramdataSet:数据集

:return:

min

distances=DS.cdist(dataSet,dataSet[x,:])#用于计算两个输入集合距离

M二np.min(distances,axis=l)#得出附近点到中心点最小值

retumsum(M)#将最小值累加得到最小距离

deffind_next(x):

min

从邻域中选择最好解

:paramx:

:paramdataSet:

:return:最优值

min

ind=random.sample(range(p)/l)

x_new=list.copy(x)

tmp:random.sample(range(dataSet.shape[0]),l)#dataSet.shape[0]返回行数

whiletmp[O]inx:

tmp=random.sample(range(dataSet.shape[O]),1)

x_new[int(ind[O])]=tmp[O]

iff(x_new)<f(x):

returnx_new

else:

ifrandom.random()<np.exp(-(f(x_new)-f(x))/T):#模拟退火算法关键

returnx_new

else:

returnx

#得到数据

print("第一步：加载数据")

dataSet=[]

fileln=open('data.txt')

forlineinfileln.readlines():

lineArr=line.strip().split('')

dataSet.append([float(lineArr[0]),float(lineArr[-l])])

dataSet=np.array(dataSet)

p=4#设定问题p中心参数值

T=1000#模拟退火初始温度

a=0.999#温度降低系数，为了确保较大搜索空间，所以非常靠近于1

lter=200#最大迭代次数

#模拟退火

#param:history统计距离和最优值，方便比较最小值

#param:best_x统计当前距离和最小值

x二random.sample(range(dataSet.shape[0]),p)#随机产生初始解

best_x=x

history=[]

foriinrange(lter):

print(,第％d次迭代：目标函数二%5'%(行仅)))

x=find_next(x)

T*=a

iff(x)<f(best_x):

best_x=x

history.append(f(best_x))

print('距离和最小为％s'%f(best_x))

#模拟退火局部搜索训练曲线图

#resul:t得出模拟退火迭代次数与目标函数值关系

plt.figure(O)

plt.plotfrangefljter+lj^istory/r-1)

plt.xlabel('迭代次数fontproperties二zandaoguangfont)

plt.ylabelf目标函数值',fontproperties=zandaoguangfont)

plt.title('模拟退火训练曲线图,,fontproperties:zandaoguangfont)

#数据分配图

#用红蓝黄绿等颜色代表p中心中p类

#其中经过搜索后p个中心点用markersize=10五边形表示

#相同颜色点相比较与相同颜色加粗markersize=10五边形，即相同颜色以相同颜色加粗

五边形为中心，此时距离最近。

plt.figure(l)

distances=DS.cdist(dataSet,dataSet[best_x,:])

sorted_dist=np.argsort(distances,axis=l)

color=['r.7b.,；y.,；g.']

colo^I'rp'/bp'/yp'/gp']

foriinrange(p):

ind=sorted_dist[:,0]==i

plt.plot(dataSet[ind,0],dataSet[ind,lLcolor[i])

plt.plot(dataSet[best_x[i],0]/dataSet[best_x[i]/l]/Color0[i],markersize=10)

plt.title('分配图)fontproperties:zandaoguangfont)

plt.showf)

附录二聚类算法Python代码

fromnumpyimport*

importmatplotlib.pyplotaspit

importKMeans

##得到数据…

print("第一步：加载数据…,,)

dataSet=[]

fileln=openf'data.txt")

forlineinfileln.readlines():

temp=[]

lineArr=line.strip().split('\t')

temp.append(float(lineArr[0]))

temp.append(float(lineArr[l]))

dataSet.append(temp)

fileln.closed

##进行聚类…

print(“第二步：进行聚类…”)

dataSet=mat(dataSet)

#设置为4个中心点

k=4

#调用KMeans文件中定义kmeans方法。

centroids,clusterAssment=KMeans.kmeans(dataSetzk)

##第三步：显示结果…

#数据分配图

#用不一样种颜色代表p中心中p类

#其中经过搜索后p个中心点用markersize=10五边形表示

#相同颜色点相比较与相同颜色加粗markersize=10五边形，即相同颜色以相同颜色加粗

五边形为中心，此时距离最近。

print（"第三步：显示结果…"）

KMeans.showClusterfdataSet,k,centroids,clusterAssment）

Kmeans.py

#################################################

#kmeans:k-meanscluster

#Author:ZanDaoguang

#Date:/03/09

#HomePage:

#Email:

#################################################

fromnumpyimport*

importtime

importmatplotlib.pyplotaspit

#calculateEuclideandistance

defeuclDistance(vectorl,vector2):

returnsqrt(sum(power(vector2-vectorl,2)))#求这两个矩阵距离，vector1、2均为

矩阵

#initcentroidswithrandomsamples

#在样本集中随机选取k个样本点作为初始质心

definitCentroidstdataSet,k):

numSamples,dim=dataSet.shape#矩阵行数、列数

centroids=zeros((k,dim))#感觉要不要你都能够

foriinrange(k);

index=int(random.uniform(0,numSamples))#随机产生一个浮点数，然后将其

转化为int型

centroidsli,:]=dataSet[indexz:]

returncentroids

#k-meanscluster

#dataSet为一个矩阵

#k为将dataSet矩阵中样大分成k个类

defkmeans(dataSetzk):

numSamples=dataSet.shape[O]#读取矩阵dataSet第一维度长度，即取得有多少个

样本数据

#firstcolumnstoreswhichclusterthissamplebelongsto,

#secondcolumnstorestheerrorbetweenthissampleanditscentroid

clusterAssment=matfzerosffnumSamples,2)))#得到一个N*2零矩阵

clusterChanged=True

##step1:initcentroids

#在样本集中随机选取个样本点作为初始质心

centroids=initCentroids(dataSetyk)k

whileclusterChanged:

clusterChanged=False

##foreachsample

foriinrange(numSamples):#range

minDist=100000.0

minindex=0

##foreachcentroid

##step2:findthecentroidwhoisclosest

#计算每个样本点与质点之间距离，将其归内到距离最小那一簇

forjinrange(k):

distance=euclDistance(centroids[j,dataSet[i,:])

ifdistance<minDist:

minDist=distance

minindex=j

##step3:updateitscluster

#k个簇里面与第i个样本距离最小标号和距离保留在clusterAssment中

#若全部样本不在改变，则退出while循环

ifclusterAssment[i,0]!=minindex:

clusterChanged=True

clusterAssment[i,:]=minindex,minDist**2#两个**表示是minDist平方

##step4:updatecentroids

forjinrange(k):

#clusterAssment[:,O].A==j是找出矩阵clusterAssment中第一列元素中等于j

行下标，返回是一个以array列表，第一个array为等于j下标

pointsInCluster=dataSetlnonzerofclusterAssmentf:,0].A==j)[0]]#将dataSet

矩阵中相对应样本提取出来

centroids。，:]=mean(pointslnCluster,axis=0)#计算标注为j全部样本平均

值

print(,聚类完成！)

returncentroids,clusterAssment

#showyourclusteronlyavailablewith2-Ddata

Centroids为k个类别，其中保留着每个类别质心

#clusterAssment为样本标识，第一列为此样本类别号，第二列为到这类别质心距离

defshowClusterfdataSet,k,centroids,clusterAssment):

numSamples,dim=dataSet.shape

ifdim!=2:

print("Sorry!Icannotdrawbecausethedimensionofyourdataisnot2!")

rpturn1

；；，A

mark=['or','ob','og'okr'z'+^'sr','dr\'<r'z'pr']

ifk>len(mark):

print("对不起，您输入k太大了，请联络管理员山东科技大学咎道广")

return1

#drawallsamples

foriinrange(numSamples):

markindex=int(clusterAssment[i,0])#为样本指定颜色

plt.plot(dataSet[i,0],dataSet[i,1],mark[marklndex])

mark=「Dr','Db'JDg','Dk‘，"bj+b','sb'Jdb','<b'Jpb']

#drawthecentroids

foriinrange(k):

plt.plot(centroids[i,0],centroids[i,1],mark[i],markersize=10)

plt.title('Distributiondiagram')

plt.show()

附录三迭代次数与目标函数关系

第。次迭代：目标函数二179.

第1次迭代：目标函数二205.

第2次迭代：目标函数二179.

第3次迭代：目标函数二190.

第4次迭代：目标函数二186.

第5次迭代：目标函数二255.

第6次迭代：目标函数二237.

第7次迭代：目标函数二360.

第8次迭代：目标函数二235.13584001

第9次迭代：目标函数二245.

第10次迭代：目标函数二247.

第11次迭代：目标函数二273.

第12次迭代：目标函数二280.

第13次迭代：目标函数二280.

第14次迭代：目标函数二198.

第15次迭代：目标函数二195.

第16次迭代：目标函数二277.82403

第17次迭代：目标函数二292.

第18次迭代：目标函数二190.

第19次迭代：目标函数二191.

第20次迭代：目标函数二123.

第21次迭代：目标函数二190.

第22次迭代：目标函数二189.

第23次迭代：目标函数二187.

第24次迭代：目标函数二187.

第25次迭代：目标函数二216.

第26次迭代：目标函数二264.

第27次迭代：目标函数二264.

第28次迭代：目标函数二181.

第29次迭代：目标函数二122.

第30次迭代：目标函数二186.

第3次迭代:目标函数二256.

第32次迭代：目标函数二237.

第33次迭代：目标函数二191.

第34次迭代：目标函数二216.

第35次迭代：目标函数二147.

第36次迭代:目标函数二222.

第37次迭代:目标函数二215.

第38次迭代：目标函数二204.

第39次迭代：目标函数二197.

第40次迭代：目标函数二188.

第41次迭代：目标函数二265.

第42次迭代：目标函数二163.

第43次迭代：目标函数二162.

第44次迭代：目标函数二164.

第45次迭代：目标函数二161.

第46次迭代：目标函数二204.73869345

第47次迭代：目标函数二162.

第48次迭代：目标函数二178.51942545

第49次迭代：目标函数二173.

第50次迭代：目标函数二169.

第51次迭代:目标函数二168.

第52次迭代：目标函数二245.

第53次迭代：目标函数二169.

第54次迭代：目标函数二116.

第55次迭代：目标函数二171.

第56次迭代：目标函数二167.

第57次迭代：目标函数二163.

第58次迭代:目标函数二167.

第59次迭代：目标函数二186.81606983

第60次迭代：目标函数二173.

第61次迭代:目标函数二171.

第62次迭代：目标函数二165.

第63次迭代：目标函数二171.

第64次迭代：目标函数二258.

第65次迭代：目标函数二300.

第66次迭代：目标函数二245.

第67次迭代：目标函数二158.

第68次迭代：目标函数二181.

第69次迭代：目标函数二190.

第70次迭代：目标函数二245.

第71次迭代：目标函数二187.41644075

第72次迭代：目标函数二185.

第73次迭代：目标函数二192.

第74次迭代：目标函数二203.

第乃次迭代：目标函数二179.

第76次迭代：目标函数二176.

第77次迭代：目标函数二177.

第78次迭代：目标函数二261.

第79次迭代：目标函数二186.

第80次迭代：目标函数二111.

第81次迭代:目标函数二164.

第82次迭代：目标函数二199.

第83次迭代：目标函数二201.

第84次迭代：目标函数二200.

第85次迭代：目标函数二226.

第86次迭代:目标函数二162.

第87次迭代：目标函数二180.

第88次迭代：目标函数二186.

第89次迭代：目标函数二184.

第90次迭代：目标函数二175.

第91次迭代：目标函数二134.

第92次迭代：目标函数二188.

第93次迭代：目标函数二178.

第94次迭代：目标函数二179.

第95次迭代:目标函数二244.

第96次迭代：目标函数二170.

第97次迭代：目标函数二251.

第98次迭代：目标函数二170.

第99次迭代：目标函数二263.

第100次迭代：目标函数=266.

第101次迭代：目标函数二233.

第102次迭代：目标函数二236.

第103次迭代：目标函数二225.

第104次迭代：目标函数二256.

第105次迭代：目标函数二253.

第106次迭代：目标函数二192.

第107次迭代：目标函数二178.

第108次迭代：目标函数二181.81273764

第109次迭代:目标函数二209.9163263

第110次迭代:目标函数二213.

第111次迭代：目标函数二188.

第112次迭代:目标函数二123.

第113次迭代：目标函数二105.

第114次迭代：目标函数二170.

第115次迭代：目标函数二162.

第116次迭代：目标函数二202.

第117次迭代：目标函数二208.

第118次迭代：目标函数二199.

第119次迭代:目标函数二147.2914882

第120次迭代:目标函数二209.

第121次迭代:目标函数二188.

第122次迭代:目标函数二254.

第123次迭代:目标函数二182.

第124次迭代:目标函数二232.

第125次迭代:目标函数二169.

第126次迭代:目标函数二170.

第127次迭代:目标函数二188.

第128次迭代:目标函数二102.

第129次迭代:目标函数二186.11050464

第130次迭代:目标函数二188.60993634

第131次迭代:目标函数二275.

第132次迭代：目标函数二362.

第133次迭代：目标函数二270.

第134次迭代：目标函数二250.

第135次迭代：目标函数二240.15223

第136次迭代：目标函数二194.

第137次迭代：目标函数二159.9543548

第138次迭代：目标函数二113.

第139次迭代：目标函数二197.

第140次迭代:目标函数二188.

第141次迭代：目标函数二209.

第142次迭代：目标函数二177.

第143次迭代：目标函数二177.

第144次迭代：目标函数二177.

第145次迭代：目标函数二177.

第146次迭代：目标函数二123.

第147次迭代：目标函数二178.

第148次迭代：目标函数二181.

第149次迭代：目标函数二180.

第150次迭代:目标函数二179.

第151次迭代:目标函数二179.

第152次迭代:目标函数二178.

第153次迭代:目标函数二267.

第154次迭代:目标函数二177.

第155次迭代:目标函数二184.

第156次迭代:目标函数二255.

第157次迭代:目标函数二249.

第158次迭代:目标函数二307.

第159次迭代:目标函数二250.

第160次迭代:目标函数二196.

第161次迭代:目标函数二196.

第162次迭代：目标函数=209,33031066

第163次迭代：目标函数二204.

第164次迭代：目标函数=211.

第165次迭代：目标函数二149.

第166次迭代：目标函数二192.

第167次迭代：目标函数二140.

第168次迭代：目标函数二181.94000428

第169次迭代:目标函数二160.

第170次迭代:目标函数二160.

第171次迭代：目标函数二110.

第172次迭代:目标函数二115.

第173次迭代:目标函数二114.

第174次迭代:目标函数二114.

第175次迭代:目标函数二196.53638158

第176次迭代:目标函数二212.

第177次迭代：目标函数二191.

第178次迭代：目标函数二202.

第179次迭代：目标函数二180.

第180次迭代：目标函数二280.

第181次迭代：目标函数二177.

第182次迭代：目标函数二277.

第183次迭代：目标函数二284.

第184次迭代:目标函数二178.

第185次迭代：目标函数二186.85188453

第186次迭代：目标函数二186.

第187次迭代：目标函数二215.

第188次迭代:目标函数二186.

第189次迭代:目标函数二166.

第190次迭代:目标函数二224.

第191次迭代:目标函数二240.

第192次迭代：目标函数二224.

第193次迭代：目标函数二245.57430458

第194次迭代：目标函数二331.

第195次迭代：目标函数二236.

第196次迭代：目标函数二244.

第197次迭代：目标函数二238.

第198次迭代：目标函数=267.60921475

第199次迭代：目标函数二231.

距离和最小为102.4019743

附录四结论图

O

18

l7O

6

lO

r5O

lO

4

愫

#LO

H3

L2O

l1O

l0O

02550T5100125150175200

速代次数

图7模拟退火迭代训练曲线图

分配•四

04

图8模拟退火随机局域搜索算法分配图

Distributiondiagram

图9聚类算法分配图

C++代码

#include<iostream>

#include<algorithm>

#include<string>

#include<math.h>

#include<fstream>

#include<vector>

#include<iomanip>

#include<sstream>

#include<time.h>

#defineMAXle9

usingnamespacestd;

structpoint{

doublex;

doubley;

}；

inip=4,T=1000,Iler=200;

doublea=0.999;

vector<point>dataset;

doublegetdis(pointpl,pointp2)

returnsqrt(pow((pl.x-p2.x),2)+pow((pl.y-p2.y),2));

)

doublef(vector<int>x)

doublesum=0;

vector<vector<double»dis;

dis.resize(4);

for(inti=0;i<4;i++)

dis[i].resize(dataset.size());

for(inti=0;i<dataset.sizef);i++)

{

dis[0][i]=getdis(dataset[i]zdataset[x[0]]);

dis[l][i]=geldis(ddlasel[i]Adaldbet[x[l]]);

dis[2][i]=getdis(dataset[i]zdataset[x[2]]);

dis[3][i]=getdis(dataset[i]zdataset[x[3]]);

)

vector<double>mindis;

doublemin;

for(inti=0;i<dataset.size();i++)

min=dis[O][i];

if(min>dis[l][i])min=dis[l][i];

if(min>dis[2][i])min=dis[2][i];

if(min>dis[3][i])min=di