搜索树，图算法，深度优化与广度优化 2021

city_name re.findall(r name: (w ) , city)[0] loaction re.findall(r geoCoord:[(d .d ),s(d .d )] , city)[0] city_loaction[city_name] tuple(map(float,loaction)) return city_loaction city_info get_city_info(coordination_source) 2.1.2 城市直接距离计算

使用球面坐标的距离计算公式 得到城市直接距离。

import math
def geo_distance(origin, destination):
 Calculate the Haversine distance.
 Parameters
 ----------
 origin : tuple of float
 (lat, long)
 destination : tuple of float
 (lat, long)
 Examples
 --------
 origin (48.1372, 11.5756) # Munich
 destination (52.5186, 13.4083) # Berlin
 round(distance(origin, destination), 1)
 504.2
 lat1, lon1 origin
 lat2, lon2 destination
 radius 6371 # km
 dlat math.radians(lat2 - lat1)
 dlon math.radians(lon2 - lon1)
 a (math.sin(dlat / 2) * math.sin(dlat / 2) 
 math.cos(math.radians(lat1)) * math.cos(math.radians(lat2)) *
 math.sin(dlon / 2) * math.sin(dlon / 2))
 c 2 * math.atan2(math.sqrt(a), math.sqrt(1 - a))
 d radius * c
 return d
def get_city_distance(city1,city2):
 return geo_distance(city_info[city1],city_info[city2])
get_city_distance( 杭州 , 上海 )

2.1.3 计算可以到达的城市关系

# 绘制当前图像
city_graph nx.Graph()
city_graph.add_nodes_from(list(city_info.keys())) 
nx.draw(city_graph, city_info, with_labels True, node_size 10)
threshold 600 
from collections import defaultdict
def build_connection(city_info):
 cities_connection defaultdict(list)
 cities list(city_info.keys())
 for c1 in cities:
 for c2 in cities:
 if c1 c2 : continue
 if get_city_distance(c1,c2) threshold:
 cities_connection[c1].append(c2)
 return cities_connection
# 得到能够到达的城市关系
cities_connection build_connection(city_info)

2.1.4 查找相互连接的城市路径

BFS 1 version

def search_1(graph,start,destination):
 pathes [[start]]
 visited set()
 while pathes:
 path pathes.pop(0)
 froniter path[-1]
 if froniter in visited: continue
 successsors graph[froniter]
 for city in successsors:
 if city in path: continue # check loop
 new_path path [city]
 pathes.append(new_path) #bfs
 #pathes [new_path] pathes #dfs
 if city destination:
 return new_path
 visited.add(froniter)
search_1(cities_connection, 上海 , 香港 )
# [ 上海 , 合肥 , 香港 ]

Optimal search using variation of BFS

def search_2(graph,start,destination,search_strategy):
 pathes [[start]]
 #visited set()
 while pathes:
 path pathes.pop(0)
 froniter path[-1]
 #if froniter in visited : continue
 #if froniter destination:
 # return path
 successsors graph[froniter]
 for city in successsors:
 if city in path: continue # check loop
 new_path path [city]
 pathes.append(new_path) #bfs
 pathes search_strategy(pathes)
 # visited.add(froniter)
 if pathes and (destination pathes[0][-1]):
 return pathes[0] 

当存在多个路径时 按照城市的距离进行排序操作。

def sort_by_distance(pathes):
 def get_distance_of_path(path):
 distance 0
 for i,_ in enumerate(path[:-1]):
 distance get_city_distance(path[i],path[i 1])
 return distance
 return sorted(pathes,key get_distance_of_path)

功能实现

search_2(cities_connection, 北京 , 上海 ,search_strategy sort_by_distance)
# [ 北京 , 天津 , 上海 ]

三、 编辑距离的练习

def Levenshtein_Distance_Recursive(str1, str2): 
 if len(str1) 0: return len(str2) 
 elif len(str2) 0: return len(str1) 
 elif str1 str2: return 0 
 d 0 if str1[len(str1)-1] str2[len(str2)-1] else 1
 return min(Levenshtein_Distance_Recursive(str1, str2[:-1]) 1, Levenshtein_Distance_Recursive(str1[:-1], str2) 1, Levenshtein_Distance_Recursive(str1[:-1], str2[:-1]) d)

四、总结

搜索算法可以解决 路径规划 国家象棋 象棋等问题。

围棋的搜索时间复杂度太高 搜索解决不了后来人们就发明出了新的算法 新的算法 时间复杂度更低。

深度学习深度强化学习