最优选址类问题
本帖最后由 linkz 于 2020-6-17 22:14 编辑在一个编号为0到1000的坐标轴上，假设有100个住户，每个住户的地址按0到1000随机编号。现在市长需要修一个公园，目的是让该公园到每一个市民家里的距离之和为最小值。因此，市长需要从每个市民那里收集信息，但是每个市民都极度自私，希望公园到自己家的距离最短。市长目前有三个备选方案：1.自己随机选择地址，不考虑任何信息。 2.将市民报告的地址按升序排列，选择排序后最左边的的地址。 3.统计好所有100个住户的地址后，求平均值 这三个备选方案的优缺点是什么，有没有一个新方法去得到更好的效果
限制条件：1.每个住户只能上报一次地址；2.每个市民都希望公园距离自己家的距离最小，因此可能会上报一个虚假的地址； 3.每个市民不知道彼此上报的地址，也就是信息不互通，不存在共谋行为。（修改下第三个条件，假如信息完全公开，每个居民都知道其他所有居民的地址）
新增两个条件，4. 居民的地址可以和公园的地址相同，也就是居民在1，公园也可以在15. 可以有几个居民的地址是一样的（有居民可能是一起住的公寓）
我这边想的是用random函数建立随机数，但是最开始时，每个住户本身又有一个精确的地址。现在就很头大，不知道该怎么用python去实现。有大佬在吗～可以一起讨论一下下，有代码更好哦！小弟在此谢过！！
本帖最后由 java2python 于 2020-6-17 09:57 编辑
市长目前有三个备选方案：
1.自己随机选择地址，不考虑任何信息。
2.将市民报告的地址按升序排列，选择排序后最左边的的地址。
3.统计好所有100个住户的地址后，求平均值
【效果】
*****************************************
1.效果看运气
2.效果不佳，因为离最左边用户最近，那么公园位置往右移动一点，就是离这家虽然会远一点，但离其他99家都会近一点
3.相对1,2，效果最好（实际考虑到住户会谎报地址，也不是很完美）
*****************************************
限制条件：
1.每个住户只能上报一次地址；
2.每个市民都希望公园距离自己家的距离最小，因此可能会上报一个虚假的地址；
3.每个市民不知道彼此上报的地址
假设：
市民都是知道别的市民的地址
假设市民认为别的市民都是老实的
对市民来说
市长的方案1，他们的任何努力都是无效的
市长的方案2，取最左边的地址，也就是最小的地址，那么他们的努力也是无效的
市长的方案3，求公园离住户的平均值中最小的地点，这个他们才是他们的努力有效果的方案
市民知道后方案3后会采取的策略：
比如：假如100个住户的地址均匀分布在1-1000位置上，按照方案三，公园位置应该在500这个点上，
那么住址700位置住户，知道方案3，为了离自己近，他会报1000，如此公园位置会从500，向1000方向偏移一点。
同理，住址300的住户，会报0，这个不像住址700的住户那么的肯定，因为万一是采用方案2，这一上报，会使自己离公园更远。
而700的住户，他上报1000是不存在这种可能性的。
所以对单个住户来说，对于三个方案，他必须做到，让自己上报的住址，最后结果离自己最近：
*方案1：三分之一可能性，努力无效，这条在作为住户来说，他应该不考虑这种情况，他只考虑2,3对自己是好处还是坏处就行了
*方案2：三分之一可能性，住户应该如实上报自己地址
*方案3：三分之一可能性，住户应该上报平均后使公园往自己住址偏移的方案
--------------------------------------------------------
经过这个考虑过程，住址300的住户，会选择上报最左边住户的住址，因为万一是方案2，那么和本来一样，他没有损失，万一方案三，他得益
说了一大堆，如何程序化：
*随机生成100个住户住址
对于每个住户：
他上报1----------1000中一个：
三分之一可能性：方案2，他最终离公园是多少
三分之一可能性：方案3，他最终离公园是多少
两个之和后，取小的值。
方案2公园地址=最左住户
对用户N，他的方案测试：
最小距离和=10000
for 上报地址 = 0 -- 1000{
方案3公园地址=100住户地址平均（其他住户就是原来地址，他的地址用的是上报地址）
距离和=绝对值（他的实际住址-方案3公园地址)+绝对值(他的实际住址-方案2公园地址)
if 距离和<最小距离和 {
最小距离和 = 距离和
最小距离住址 = 上报地址
}
}
print(最小距离住址,最小距离和)
这是对于单个用户的，对于所有100个，就在外面再加一层循环。
如果市民之间的信息是不共享的，那么要满足“希望公园到自己家的距离最短”，当然是直接上报公园就是自己家的位置，那么其实所有上报的点就是100个住户家的位置。然后不就是“最小二乘法”的问题了么？ jerryxjr1220 发表于 2020-6-17 07:49
如果市民之间的信息是不共享的，那么要满足“希望公园到自己家的距离最短”，当然是直接上报公园就是自己家 ...
对哦。那假如信息共享应该怎么算{:5_99:} java2python 发表于 2020-6-17 09:56
市长目前有三个备选方案：
1.自己随机选择地址，不考虑任何信息。
2.将市民报告的地址按升序排列，选择 ...
那请问有没有一个比三更好的方法呢 0-0 linkz 发表于 2020-6-18 05:30
那请问有没有一个比三更好的方法呢 0-0
即便是假定了每个住民，都会认为别的住民是老实的，他的实际地址和选址，你需要模拟一千次
而对于所有住民，你需要模拟100*1000次。
方案三比1,2好的基础，是每个住民都会如实上报，而实际根本不是这个情况，所以需要过滤不良信息。就是通过他的上报数据，还原他真是数据。比如700的上报1000，那么真实住址大概率是多少？或者说这个实际推不出。但30个人上报1000，那么他们真实住址的平均位于哪里，这个可能是能够比较确切知道的。
这个需要以前面100*1000次的模拟结果为基础。 本帖最后由 java2python 于 2020-6-18 10:08 编辑
用python模拟一下，结果如下：
平均住址： 520
真实地址=9,虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=24,虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=28,虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=30,虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=31,虚报地址=9 ,方案二，方案三最短路径和=511
真实地址=44,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=45,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=61,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=63,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=84,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=111,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=115,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=118,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=118,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=123,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=125,虚报地址=9 ,方案二，方案三最短路径和=510
真实地址=165,虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=167,虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=203,虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=213,虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=215,虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=221,虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=224,虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=230,虚报地址=9 ,方案二，方案三最短路径和=509
真实地址=239,虚报地址=8 ,方案二，方案三最短路径和=509
真实地址=256,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=286,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=289,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=289,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=311,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=313,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=328,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=332,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=335,虚报地址=9 ,方案二，方案三最短路径和=508
真实地址=349,虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=357,虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=390,虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=397,虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=408,虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=411,虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=421,虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=429,虚报地址=9 ,方案二，方案三最短路径和=507
真实地址=442,虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=454,虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=464,虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=492,虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=508,虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=510,虚报地址=9 ,方案二，方案三最短路径和=506
真实地址=531,虚报地址=901 ,方案二，方案三最短路径和=529
真实地址=537,虚报地址=907 ,方案二，方案三最短路径和=541
真实地址=554,虚报地址=924 ,方案二，方案三最短路径和=575
真实地址=556,虚报地址=926 ,方案二，方案三最短路径和=579
真实地址=595,虚报地址=965 ,方案二，方案三最短路径和=657
真实地址=598,虚报地址=968 ,方案二，方案三最短路径和=663
真实地址=598,虚报地址=968 ,方案二，方案三最短路径和=663
真实地址=607,虚报地址=977 ,方案二，方案三最短路径和=681
真实地址=614,虚报地址=984 ,方案二，方案三最短路径和=695
真实地址=622,虚报地址=992 ,方案二，方案三最短路径和=711
真实地址=625,虚报地址=995 ,方案二，方案三最短路径和=717
真实地址=632,虚报地址=902 ,方案二，方案三最短路径和=732
真实地址=642,虚报地址=912 ,方案二，方案三最短路径和=752
真实地址=647,虚报地址=917 ,方案二，方案三最短路径和=762
真实地址=659,虚报地址=929 ,方案二，方案三最短路径和=786
真实地址=685,虚报地址=955 ,方案二，方案三最短路径和=838
真实地址=693,虚报地址=963 ,方案二，方案三最短路径和=854
真实地址=695,虚报地址=965 ,方案二，方案三最短路径和=858
真实地址=695,虚报地址=965 ,方案二，方案三最短路径和=858
真实地址=704,虚报地址=974 ,方案二，方案三最短路径和=876
真实地址=706,虚报地址=976 ,方案二，方案三最短路径和=880
真实地址=722,虚报地址=992 ,方案二，方案三最短路径和=912
真实地址=736,虚报地址=906 ,方案二，方案三最短路径和=941
真实地址=778,虚报地址=948 ,方案二，方案三最短路径和=1025
真实地址=783,虚报地址=953 ,方案二，方案三最短路径和=1035
真实地址=789,虚报地址=959 ,方案二，方案三最短路径和=1047
真实地址=789,虚报地址=959 ,方案二，方案三最短路径和=1047
真实地址=798,虚报地址=968 ,方案二，方案三最短路径和=1065
真实地址=801,虚报地址=971 ,方案二，方案三最短路径和=1071
真实地址=806,虚报地址=976 ,方案二，方案三最短路径和=1081
真实地址=810,虚报地址=980 ,方案二，方案三最短路径和=1089
真实地址=827,虚报地址=997 ,方案二，方案三最短路径和=1123
真实地址=843,虚报地址=913 ,方案二，方案三最短路径和=1156
真实地址=847,虚报地址=917 ,方案二，方案三最短路径和=1164
真实地址=848,虚报地址=918 ,方案二，方案三最短路径和=1166
真实地址=851,虚报地址=921 ,方案二，方案三最短路径和=1172
真实地址=855,虚报地址=925 ,方案二，方案三最短路径和=1180
真实地址=859,虚报地址=929 ,方案二，方案三最短路径和=1188
真实地址=877,虚报地址=947 ,方案二，方案三最短路径和=1224
真实地址=892,虚报地址=962 ,方案二，方案三最短路径和=1254
真实地址=895,虚报地址=965 ,方案二，方案三最短路径和=1260
真实地址=926,虚报地址=996 ,方案二，方案三最短路径和=1322
真实地址=942,虚报地址=912 ,方案二，方案三最短路径和=1355
真实地址=954,虚报地址=924 ,方案二，方案三最短路径和=1379
真实地址=958,虚报地址=928 ,方案二，方案三最短路径和=1387
真实地址=962,虚报地址=932 ,方案二，方案三最短路径和=1395
真实地址=971,虚报地址=941 ,方案二，方案三最短路径和=1413
真实地址=981,虚报地址=951 ,方案二，方案三最短路径和=1433
真实地址=981,虚报地址=951 ,方案二，方案三最短路径和=1433
真实地址=984,虚报地址=954 ,方案二，方案三最短路径和=1439
真实地址=996,虚报地址=966 ,方案二，方案三最短路径和=1463
真实地址=997,虚报地址=967 ,方案二，方案三最短路径和=1465
import random
#import math
class Address:
def __init__(self,true_addr):
self.true_addr = true_addr
self.min_distance = 10000
self.min_addr = 0
def print_msg(self):
return "真实地址=%d,虚报地址=%d ,方案二，方案三最短路径和=%d" % (self.true_addr,self.min_addr,self.min_distance)
true_addr = []
for i in range(100):
true_addr.append(random.randint(0,1000))
true_addr.sort()
min_addr = min(true_addr)
sum_addr = sum(true_addr)
all_addr = []
for t in true_addr:
addr = Address(t)
for a in range(1001):
plan2_addr = min(a,min_addr)
plan3_addr = (sum_addr+(a - t))//100
distance = abs(t-plan2_addr)+abs(t-plan3_addr)
if distance < addr.min_distance:
addr.min_distance = distance
addr.min_addr = a
all_addr.append(addr)
print("平均住址：",sum_addr//100)
for a in all_addr:
print(a.print_msg()) 本帖最后由 java2python 于 2020-6-18 11:11 编辑
经过许多次测试：
真实地址=11,虚报地址=11 ,方案二，方案三最短路径和=461
真实地址=33,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=50,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=57,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=59,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=71,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=82,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=83,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=88,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=90,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=90,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=92,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=94,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=101,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=113,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=115,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=118,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=126,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=126,虚报地址=11 ,方案二，方案三最短路径和=460
真实地址=155,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=166,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=168,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=172,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=177,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=178,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=185,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=191,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=204,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=225,虚报地址=11 ,方案二，方案三最短路径和=459
真实地址=238,虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=274,虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=278,虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=285,虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=292,虚报地址=11 ,方案二，方案三最短路径和=458
真实地址=337,虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=350,虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=355,虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=361,虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=370,虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=378,虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=407,虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=415,虚报地址=11 ,方案二，方案三最短路径和=457
真实地址=432,虚报地址=10 ,方案二，方案三最短路径和=457
真实地址=436,虚报地址=11 ,方案二，方案三最短路径和=456
真实地址=440,虚报地址=11 ,方案二，方案三最短路径和=456
真实地址=450,虚报地址=11 ,方案二，方案三最短路径和=456
真实地址=452,虚报地址=11 ,方案二，方案三最短路径和=456
真实地址=470,虚报地址=249 ,方案二，方案三最短路径和=459 <---虚报地址发生变动的那个住户，是离平均值最近的，只需要调查这个用户的真是地址就行了
真实地址=483,虚报地址=962 ,方案二，方案三最短路径和=478
真实地址=501,虚报地址=980 ,方案二，方案三最短路径和=514
真实地址=506,虚报地址=985 ,方案二，方案三最短路径和=524
真实地址=506,虚报地址=985 ,方案二，方案三最短路径和=524
真实地址=508,虚报地址=987 ,方案二，方案三最短路径和=528
真实地址=513,虚报地址=992 ,方案二，方案三最短路径和=538
真实地址=517,虚报地址=996 ,方案二，方案三最短路径和=546
真实地址=523,虚报地址=902 ,方案二，方案三最短路径和=559
真实地址=531,虚报地址=910 ,方案二，方案三最短路径和=575
真实地址=536,虚报地址=915 ,方案二，方案三最短路径和=585
真实地址=545,虚报地址=924 ,方案二，方案三最短路径和=603
真实地址=554,虚报地址=933 ,方案二，方案三最短路径和=621
真实地址=577,虚报地址=956 ,方案二，方案三最短路径和=667
真实地址=591,虚报地址=970 ,方案二，方案三最短路径和=695
真实地址=592,虚报地址=971 ,方案二，方案三最短路径和=697
真实地址=595,虚报地址=974 ,方案二，方案三最短路径和=703
真实地址=596,虚报地址=975 ,方案二，方案三最短路径和=705
真实地址=605,虚报地址=984 ,方案二，方案三最短路径和=723
真实地址=624,虚报地址=903 ,方案二，方案三最短路径和=762
真实地址=636,虚报地址=915 ,方案二，方案三最短路径和=786
真实地址=656,虚报地址=935 ,方案二，方案三最短路径和=826
真实地址=667,虚报地址=946 ,方案二，方案三最短路径和=848
真实地址=689,虚报地址=968 ,方案二，方案三最短路径和=892
真实地址=695,虚报地址=974 ,方案二，方案三最短路径和=904
真实地址=696,虚报地址=975 ,方案二，方案三最短路径和=906
真实地址=714,虚报地址=993 ,方案二，方案三最短路径和=942
真实地址=734,虚报地址=913 ,方案二，方案三最短路径和=983
真实地址=735,虚报地址=914 ,方案二，方案三最短路径和=985
真实地址=740,虚报地址=919 ,方案二，方案三最短路径和=995
真实地址=768,虚报地址=947 ,方案二，方案三最短路径和=1051
真实地址=774,虚报地址=953 ,方案二，方案三最短路径和=1063
真实地址=775,虚报地址=954 ,方案二，方案三最短路径和=1065
真实地址=784,虚报地址=963 ,方案二，方案三最短路径和=1083
真实地址=801,虚报地址=980 ,方案二，方案三最短路径和=1117
真实地址=802,虚报地址=981 ,方案二，方案三最短路径和=1119
真实地址=817,虚报地址=996 ,方案二，方案三最短路径和=1149
真实地址=822,虚报地址=901 ,方案二，方案三最短路径和=1160
真实地址=822,虚报地址=901 ,方案二，方案三最短路径和=1160
真实地址=823,虚报地址=902 ,方案二，方案三最短路径和=1162
真实地址=824,虚报地址=903 ,方案二，方案三最短路径和=1164
真实地址=828,虚报地址=907 ,方案二，方案三最短路径和=1172
真实地址=830,虚报地址=909 ,方案二，方案三最短路径和=1176
真实地址=834,虚报地址=913 ,方案二，方案三最短路径和=1184
真实地址=842,虚报地址=921 ,方案二，方案三最短路径和=1200
真实地址=848,虚报地址=927 ,方案二，方案三最短路径和=1212
真实地址=852,虚报地址=931 ,方案二，方案三最短路径和=1220
真实地址=870,虚报地址=949 ,方案二，方案三最短路径和=1256
真实地址=879,虚报地址=958 ,方案二，方案三最短路径和=1274
真实地址=932,虚报地址=911 ,方案二，方案三最短路径和=1381
真实地址=943,虚报地址=922 ,方案二，方案三最短路径和=1403
真实地址=964,虚报地址=943 ,方案二，方案三最短路径和=1445
真实地址=982,虚报地址=961 ,方案二，方案三最短路径和=1481
真实平均住址： 472
虚报平均住址： 499
小于平均住址的住户数： 48
小于虚报平均住址的住户数： 48
java2python 发表于 2020-6-18 11:07
经过许多次测试：
真实地址=11,虚报地址=11 ,方案二，方案三最短路径和=461
真实地址=33,虚报地址=11 ...
假如市长提前已经确定了方案2或者方案3，居民们也都知道市长确定的方案，是不是最后算绝对值那里就需要换式子了？大佬你的代码是不是相当于是一个将方案2和3结合在一起的新方案？ java2python 发表于 2020-6-18 09:57
用python模拟一下，结果如下：
真的太感谢，居然还费心写了这么多代码！！ linkz 发表于 2020-6-19 08:11
假如市长提前已经确定了方案2或者方案3，居民们也都知道市长确定的方案，是不是最后算绝对值那里就需要换 ...
不是大佬。
这个题目：市长有三个方案，这个是公开的，市民当然应该知道。
实际市民的努力只有在市长采用方案三的时候才能体现：比如最左住址是15，这位市民的住址是100，为了让平均住址往100方向移动（正常是500左右），他应该虚报住址0，但是考虑到市长可能采用方案二，这样，他虚报0，公园反而比原来往左移了15，离他更远了。
因为市民不知道市长会采用哪个方案，所以应该要把方案二，方案三的距离加起来。是这个意思。
对市民来说，他是这么考虑的，那么市长需要在市民上报数据的基础上，考虑到这个，对数据进行过滤。
但实际呢，要恢复到真实数据，是很困难的。
对题目，并不是说要完美解决这个题目，进行一定的思考，用某种方案去尝试解决，这过程有些时候不是一步到达。必须模拟看看，发现数据中有什么规律，然后在此基础上，再尝试处理。总之我的表达能力很有限，就是这么个意思。 java2python 发表于 2020-6-19 08:26
不是大佬。
这个题目：市长有三个方案，这个是公开的，市民当然应该知道。
实际市民的努力只有在市长采 ...
不不，我的意思是，单独讨论方案2和方案3，相当于市长只公布2、3中的一个，市民知道市长颁布这一个方案后进行上报。 linkz 发表于 2020-6-20 03:20
不不，我的意思是，单独讨论方案2和方案3，相当于市长只公布2、3中的一个，市民知道市长颁布这一个方案后 ...
如果只公布方案2，取最左住民的地址，那么市民就随意报了（当然不会报比最左的还小，那样更远，没好处），因为他们改变不了什么，当然最左的住民离公园最近，他一定是报真是地址的。
如果只公布方案3，那么左边的住户的一定会报0，这样能把公园往自己方向拉，右边一定会报1000，同样道理。
市长公布了1,2,3三个方案，实际住民认为这三个都有可能，在这种情况下，因为对于方案一，是随机的，他们改变不了什么，那么针对方案2，方案3，他们会尽力选择自己有利的数据上报。 java2python 发表于 2020-6-20 03:33
如果只公布方案2，取最左住民的地址，那么市民就随意报了（当然不会报比最左的还小，那样更远，没好处） ...
好叻，谢谢大佬，这么晚还在 1.排除虚报情况，因为普通算法里考虑这种情况不现实。
2.想要求最短距离之和，首先你要知道距离之和怎么求。给个公式
假设p为公园位置，a为第i个居民的位置
那么距离之和的求法是
for (; i < 100; i++)
{
sum = sum+abs(p-a);
}
3.要找最优解，因为地址只有1001个，所以可以直接暴力求解，把公园可能的1001个位置都算一遍，求最小值
4.优化：最优解的最小值不可能小到最小地址，最大值不可能高于最大地址，所以小于最小地址和大于最大地址的选项就不用算了
5.像求中位数、平均值等算法求得的都是近似的最优解，但并不是最优解，可以理解为贪心法。
页:
[1]