-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathkm3maxdistance.py
170 lines (148 loc) · 8.55 KB
/
km3maxdistance.py
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
import time
import numpy as np
# # from helloword import cellnum
# from helloword import Region
# from helloword import User
# # from helloword import usernum
import math
import copy
# print("22",Region)
class km():
def __init__(self,region,user):
self.sumlackbike=0
self.ep=1e-10
self.region=region
self.user=user
self.usernum=len(self.user)
# self.cellnum=cellnum
# km最优匹配
# 车匹配区域，左边表示车，相当于用户数，右边表示区域内缺车数（即缺的车数总和）
# 生成的数组（用户横坐标，用户纵坐标，区域缺车横坐标，区域缺车纵坐标，权值（两者之间的距离1/d））
def build_graph(self):
for i in range(len(self.region)):
if (self.region[i][2] > 0):
self.sumlackbike += self.region[i][2]
self.adj = [[0 for i in range(int(self.sumlackbike))] for i in range(int(self.usernum))]
for i in range(self.usernum):
a = 0
for j in range(len(self.region)):
if (self.region[j][2] > 0):
for k in range(self.region[j][2]):
a += 1
# 计算用户目的地和各个缺车区域之间的距离
d = -math.sqrt(math.pow((self.user[i][2] - self.region[j][3]), 2) + math.pow((self.user[i][3] - self.region[j][4]), 2))
# 将大于用户最大步行距离
if(-d>self.user[i][4]):
d=-np.inf
# (处理d，将d变为整数来进行匹配)
else:
d=round(d,2)*100
self.adj[i][a - 1] = [self.user[i][2], self.user[i][3], self.region[j][3], self.region[j][4], d]
self.adj_matrix = [[0 for i in range(self.sumlackbike)] for i in range(self.usernum)]
for i in range(self.usernum):
for j in range(self.sumlackbike):
self.adj_matrix[i][j] = self.adj[i][j][4]
if(self.sumlackbike<self.usernum):
self.adj_matrix=np.transpose(self.adj_matrix)
# 有可能出现usernum或sumlackbike为0的情况
# print("sumlackbike", self.sumlackbike)
self.label_left=np.max(self.adj_matrix,axis=1) # 取大函数，axis=1表示横向
self.label_right=np.zeros(max(self.usernum,self.sumlackbike))
self.match_right=np.ones(max(self.usernum,self.sumlackbike))*np.nan #初始化匹配结果
self.visit_left=np.zeros(min(self.usernum,self.sumlackbike))
self.visit_right=np.zeros(max(self.usernum,self.sumlackbike)) # visit_right表示右边的缺车是否匹配
self.slack_right=np.ones(max(self.usernum,self.sumlackbike))*np.inf # np.inf表示最大的正数,记录每个汉子如果能被妹子倾心最少还需要多少期望值
# 寻找增广路，深度优先
def find_path(self,i):
self.visit_left[i] = 1
for j, match_weight in enumerate(self.adj_matrix[i]): # enumerate是内置函数，输出的是（计数值，值）
if self.visit_right[j]: continue # 已被匹配（解决递归中的冲突）（跳过当前循环的剩余语句，进行下一句循环）
gap =self.label_left[i] + self.label_right[j] - match_weight # （匹配时两方的期望和要等于两人之间的好感度即match_right）计算代沟
# print("gap",i,j,gap)
if gap <= self.ep:
# 找到可行匹配
self.visit_right[j] = True
if np.isnan(self.match_right[j]) or self.find_path(int(self.match_right[j])): # j未被匹配，或虽然j已被匹配，但是j的已匹配对象有其他可选
self.match_right[j] = i
return True
else:
# 计算变为可行匹配需要的顶标改变量
if self.slack_right[j] > gap: self.slack_right[j] = gap # slack理解为该缺车为了被用户匹配，还需要多少期望值，来最小化它
return False
# km主函数
def KM(self):
distance=0
if (self.usernum <= self.sumlackbike): # 每个用户都可以被匹配的情况下
for i in range(self.usernum):
#重置辅助变量
self.slack_right=np.ones(max(self.usernum,self.sumlackbike))*np.inf
while True: # 为每个用户找到缺车区域，若找不到就降低期望值，直到找到为止(由于两边数量不一样，不一定给每个用户都能找到匹配# )
#每一轮需重置辅助变量
if(self.label_left[i]==-np.inf):
break
self.visit_left = np.zeros(min(self.usernum, self.sumlackbike))
self.visit_right = np.zeros(max(self.usernum, self.sumlackbike)) # visit_right表示右边的缺车是否匹配
if self.find_path(i): break # 如果找到匹配项就退出，未找到则降低期望值
d = np.inf # 最小可降低的期望值，其表示最大的正数
for j, slack in enumerate(self.slack_right):
if not self.visit_right[j] and slack < d:
d = slack
for k in range(self.usernum):
if self.visit_left[k]: self.label_left[k] -= d # 所有访问过的用户降低期望值
for n in range(self.sumlackbike):
if self.visit_right[n]:
self.label_right[n] += d # 所有访问过的男生增加期望值
# print("match_right", self.match_right)
# print("slack_right", self.slack_right)
# print("label_left", self.label_left)
# print("label_right", self.label_right)
for t,weight in enumerate(self.match_right):
if not np.isnan(self.match_right[t]):
distance += self.adj[int(weight)][t][4]
self.user[int(weight)][5]=self.adj[int(weight)][t][2]
self.user[int(weight)][6]=self.adj[int(weight)][t][3]
else: # 用户数大于缺车数时，反过来，用户来匹配缺车数
# 初始化辅助变量
for i in range(self.sumlackbike):
self.slack_right = np.ones(max(self.usernum, self.sumlackbike)) * np.inf
while True: #
if (self.label_left[i]==-np.inf):
break
self.visit_left = np.zeros(min(self.usernum, self.sumlackbike))
self.visit_right = np.zeros(max(self.usernum, self.sumlackbike)) # visit_right表示右边的缺车是否匹配
if self.find_path(i):
break # 如果找到匹配项就退出，未找到则降低期望值
d = np.inf # 最小可降低的期望值
for j, slack in enumerate(self.slack_right):
if not self.visit_right[j] and slack < d: #and两者都满足 visit—_righe为0且slack<d时成立
d = slack
for k in range(self.sumlackbike):
if self.visit_left[k]: self.label_left[k] -= d # 所有访问过的女生降低期望值
for n in range(self.usernum):
if self.visit_right[n]:
self.label_right[n] += d # 所有访问过的男生增加期望值
# print("match_right", self.match_right)
# print("slack_right", self.slack_right)
# print("label_left", self.label_left)
# print("label_right", self.label_right)
# print(self.match_right)
for t,weight in enumerate(self.match_right):
if not np.isnan(self.match_right[t]):
distance+=self.adj[t][int(weight)][4]
self.user[t][5]=self.adj[t][int(weight)][2]
self.user[t][6]=self.adj[t][int(weight)][3]
# print("kmdistance",distance)
# print("matchright",self.match_right)
return self.user
# 求出所有的匹配的t好感度之和
# 根据match_right[i]来确定用户和那一区域匹配
# init_User=copy.deepcopy(User)
# # print("User",User)
# # print("init_User",init_User)
# # print("Region",Region)
# pso=km(region=Region,user=init_User)
# pso.build_graph()
# uuser=pso.KM()
# print(uuser)
# print("Region",Region)
# print("inituser",init_User)