問題:尋找到N個點距離和最小的點
思路:
深度截圖20170422001700.png
import numpy as np
from matplotlib import pyplot as plt
# p到points的距離和
def f(p, points) :
return np.sum(np.sum((p - points) ** 2, axis=1) ** 0.5)
# 距離和函數在p點的梯度
def fgrad(p, points):
dx = np.sum((p[0] - points[:, 0]) / np.sum((p - points) ** 2, axis=1) ** 0.5)
dy = np.sum((p[1] - points[:, 1]) / np.sum((p - points) ** 2, axis=1) ** 0.5)
return np.array([dx, dy])
# points = np.random.rand(20, 2) # 隨機或者自定義幾個點阱缓，尋找距離這些點之和最小值的點
points = np.array([
[0,0],
[0,2],
[2,0],
[2,2]
]) # 定義一個正方形
x = np.random.rand(2) # x為隨機初始點
step = 0.2
xhistory = x #用來存儲歷史值
for k in range(100):
l = f(x, points)
xk = x - step * fgrad(x, points)
lk = f(xk, points)
if l - lk > 1e-8:
x = xk
xhistory = np.vstack((xhistory, x))
elif l - lk <0:
#步子太大揪罕，超過極值后調整步伐大小
step *= 0.5
else:
break
print(xhistory)
[[ 0.17005619 0.77382012]
[ 0.45001009 0.81002093]
[ 0.61803208 0.85141979]
[ 0.7298659 0.88861665]
[ 0.80752889 0.91829 ]
[ 0.86240553 0.94071626]
[ 0.90147962 0.95722978]
[ 0.9294022 0.96923281]
[ 0.94939105 0.97790027]
[ 0.96371305 0.98413816]
[ 0.97397936 0.98861982]
[ 0.98134014 0.99183687]
[ 0.98661833 0.99414511]
[ 0.99040338 0.99580088]
[ 0.99311776 0.99698848]
[ 0.99506437 0.99784024]
[ 0.99646039 0.9984511 ]
[ 0.99746154 0.99888919]
[ 0.99817953 0.99920337]
[ 0.99869444 0.99942869]
[ 0.99906371 0.99959028]
[ 0.99932853 0.99970617]
[ 0.99951845 0.99978928]
[ 0.99965465 0.99984888]
[ 0.99975233 0.99989162]
[ 0.99982238 0.99992228]
[ 0.99987262 0.99994426]]
# print(points[:, 0])
plt.plot(points[:, 0], points[:, 1], 'bo')
plt.plot(xhistory[:, 0], xhistory[:, 1], 'ro')
plt.plot(xhistory[:, 0], xhistory[:, 1], 'k-')
plt.title(u'迭代次數 = %d, 距離和 = %.3f, 極值點 = (%.3f, %.3f), 最后步長 = %f' % (k, l, x[0], x[1], step))
plt.show()
output_7_0.png
