人工智能导论作业

def build_tree():return {'type': 'max','children': [{'type': 'min','children': [{'type': 'max', 'children': [{'type': 'leaf', 'name': 'A', 'val': 15},{'type': 'leaf', 'name': 'B', 'val': 9}]},{'type': 'max', 'children': [{'type': 'min', 'children': [{'type': 'leaf', 'name': 'C', 'val': 5},{'type': 'leaf', 'name': 'D', 'val': 7}]},{'type': 'min', 'children': [{'type': 'leaf', 'name': 'E', 'val': 1},{'type': 'leaf', 'name': 'F', 'val': -2}]}]},{'type': 'max', 'children': [{'type': 'leaf', 'name': 'G', 'val': -1},{'type': 'leaf', 'name': 'H', 'val': 3}]}]},{'type': 'min','children': [{'type': 'max', 'children': [{'type': 'leaf', 'name': 'I', 'val': 6},{'type': 'leaf', 'name': 'J', 'val': 3}]},{'type': 'max', 'children': [{'type': 'leaf', 'name': 'K', 'val': 8},{'type': 'leaf', 'name': 'L', 'val': 1}]},{'type': 'max', 'children': [{'type': 'min', 'children': [{'type': 'leaf', 'name': 'M', 'val': -1},{'type': 'leaf', 'name': 'N', 'val': 4}]},{'type': 'min', 'children': [{'type': 'leaf', 'name': 'O', 'val': 1},{'type': 'leaf', 'name': 'P', 'val': 6}]}]}]},{'type': 'min','children': [{'type': 'max', 'children': [{'type': 'leaf', 'name': 'Q', 'val': 12},{'type': 'leaf', 'name': 'R', 'val': 10}]},{'type': 'max', 'children': [{'type': 'leaf', 'name': 'S', 'val': 14},{'type': 'leaf', 'name': 'T', 'val': 7}]},{'type': 'max', 'children': [{'type': 'leaf', 'name': 'U', 'val': 3},{'type': 'leaf', 'name': 'V', 'val': 2}]}]}]}def alpha_beta(node, alpha, beta, pruned_nodes):if node['type'] == 'leaf':return node['val'], node['name']if node['type'] == 'max':best_val = float('-inf')best_child = Nonefor idx, child in enumerate(node['children']):val, name = alpha_beta(child, alpha, beta, pruned_nodes)if val > best_val:best_val = valbest_child = namealpha = max(alpha, best_val)if beta <= alpha:for remaining in node['children'][idx+1:]:collect_leaves(remaining, pruned_nodes)breakreturn best_val, best_childelse: best_val = float('inf')best_child = Nonefor idx, child in enumerate(node['children']):val, name = alpha_beta(child, alpha, beta, pruned_nodes)if val < best_val:best_val = valbest_child = namebeta = min(beta, best_val)if beta <= alpha:for remaining in node['children'][idx+1:]:collect_leaves(remaining, pruned_nodes)breakreturn best_val, best_childdef collect_leaves(node, pruned_nodes):if node['type'] == 'leaf':pruned_nodes.append((node['name'], node['val']))returnfor child in node['children']:collect_leaves(child, pruned_nodes)def get_optimal_path(tree):path = []def trace(n, alpha, beta):if n['type'] == 'leaf':path.append(n['name'])return n['val']if n['type'] == 'max':best_val = float('-inf')best_child = Nonefor child in n['children']:val = trace(child, alpha, beta)if val > best_val:best_val = valbest_child = childalpha = max(alpha, best_val)if beta <= alpha:breakreturn best_valelse:best_val = float('inf')best_child = Nonefor child in n['children']:val = trace(child, alpha, beta)if val < best_val:best_val = valbest_child = childbeta = min(beta, best_val)if beta <= alpha:breakreturn best_valtrace(tree, float('-inf'), float('inf'))path.reverse()return pathif __name__ == "__main__":tree = build_tree()pruned = []final_val, _ = alpha_beta(tree, float('-inf'), float('inf'), pruned)path = get_optimal_path(tree)print("=" * 30)print("α-β剪枝结果")print("=" * 30)print(f"最终根节点值: {final_val}")print(f"最优路径: {' -> '.join(path)}")print("\n被剪枝的叶子节点:")for name, val in pruned:print(f"  {name}: {val}")

# 全国34个省级行政区陆地相邻关系字典
province_neighbor_data = {'北京市': ['天津市', '河北省'],'天津市': ['北京市', '河北省'],'河北省': ['北京市', '天津市', '山西省', '河南省', '山东省', '辽宁省', '内蒙古自治区'],'山西省': ['河北省', '河南省', '陕西省', '内蒙古自治区'],'内蒙古自治区': ['河北省', '山西省', '陕西省', '宁夏回族自治区', '甘肃省', '辽宁省', '吉林省', '黑龙江省'],'辽宁省': ['河北省', '内蒙古自治区', '吉林省'],'吉林省': ['辽宁省', '内蒙古自治区', '黑龙江省'],'黑龙江省': ['吉林省', '内蒙古自治区'],'上海市': ['江苏省', '浙江省'],'江苏省': ['上海市', '浙江省', '安徽省', '山东省'],'浙江省': ['上海市', '江苏省', '安徽省', '福建省', '江西省'],'安徽省': ['江苏省', '浙江省', '江西省', '湖北省', '河南省', '山东省'],'福建省': ['浙江省', '江西省', '广东省'],'江西省': ['浙江省', '安徽省', '福建省', '湖北省', '湖南省', '广东省'],'山东省': ['河北省', '江苏省', '安徽省'],'河南省': ['河北省', '山西省', '安徽省', '湖北省', '陕西省'],'湖北省': ['河南省', '安徽省', '江西省', '湖南省', '重庆市', '陕西省'],'湖南省': ['湖北省', '江西省', '广东省', '广西壮族自治区', '贵州省', '重庆市'],'广东省': ['福建省', '江西省', '湖南省', '广西壮族自治区', '香港特别行政区', '澳门特别行政区'],'广西壮族自治区': ['广东省', '湖南省', '贵州省', '云南省'],'海南省': [],'重庆市': ['湖北省', '湖南省', '四川省', '贵州省'],'四川省': ['重庆市', '陕西省', '甘肃省', '青海省', '西藏自治区', '云南省', '贵州省'],'贵州省': ['重庆市', '湖南省', '广西壮族自治区', '云南省', '四川省'],'云南省': ['广西壮族自治区', '贵州省', '四川省', '西藏自治区'],'西藏自治区': ['四川省', '青海省', '新疆维吾尔自治区', '云南省'],'陕西省': ['山西省', '河南省', '湖北省', '重庆市', '四川省', '甘肃省', '宁夏回族自治区', '内蒙古自治区'],'甘肃省': ['陕西省', '宁夏回族自治区', '内蒙古自治区', '新疆维吾尔自治区', '青海省', '四川省'],'青海省': ['甘肃省', '四川省', '西藏自治区', '新疆维吾尔自治区'],'宁夏回族自治区': ['陕西省', '甘肃省', '内蒙古自治区'],'新疆维吾尔自治区': ['甘肃省', '青海省', '西藏自治区'],'香港特别行政区': ['广东省'],'澳门特别行政区': ['广东省'],'台湾省': []
}# 可用着色颜色集合
color_list = ['红', '橙', '青', '黑', '粉']def check_safe_color(area, choose_color, neighbor_dict, used_color_map):# 校验相邻区域是否同色near_areas = neighbor_dict[area]for near in near_areas:if near in used_color_map and used_color_map[near] == choose_color:return Falsereturn Truedef arrange_by_link_num(link_info):# 按邻接数量由多到少重排省份area_names = list(link_info.keys())area_names.sort(key=lambda name: len(link_info[name]), reverse=True)return area_namesdef dfs_color_fill(area_seq, link_map, pos=0, color_record=None):# 深度优先回溯完成地图着色if color_record is None:color_record = dict()# 全部区域着色完成if pos >= len(area_seq):return dict(color_record)now_area = area_seq[pos]for c in color_list:if check_safe_color(now_area, c, link_map, color_record):color_record[now_area] = cres = dfs_color_fill(area_seq, link_map, pos + 1, color_record)if res is not None:return res# 回溯撤销
            color_record.pop(now_area)return Noneif __name__ == '__main__':sort_area_list = arrange_by_link_num(province_neighbor_data)final_color_result = dfs_color_fill(sort_area_list, province_neighbor_data)if final_color_result:print('全国省级行政区地图着色分配结果：')output_data = list(final_color_result.items())row_num = 5for idx in range(0, len(output_data), row_num):temp_row = output_data[idx:idx+row_num]show_str = ''for name, clr in temp_row:show_str += f'{name}→{clr}    'print(show_str)else:print('无法完成合法地图着色')