一骑红尘妃子笑，CodeBuddy 运荔枝

一骑红尘妃子笑CodeBuddy 运荔枝故事背景适逢荔枝盛产季节圣人唐玄宗为博美人杨贵妃一笑钦点荔枝使负责将荔枝从岭南今广东运往长安今西安。众人皆知荔枝一日色变二日香变三日味变那么这跨越五千里的保鲜任务在当时近乎天方夜谭根本无法完成。那么在这样的情景下“荔枝使” 该如何做才能不被砍头保留小命呢CodeBuddy 自告奋勇答应帮助 “荔枝使” 一同协定荔枝运送路线从而保证完成这个看似不可能的任务。故事背景适逢荔枝盛产季节圣人唐玄宗为博美人杨贵妃一笑钦点荔枝使负责将荔枝从岭南今广东运往长安今西安。众人皆知荔枝一日色变二日香变三日味变那么这跨越五千里的保鲜任务在当时近乎天方夜谭根本无法完成。那么在这样的情景下“荔枝使” 该如何做才能不被砍头保留小命呢CodeBuddy 自告奋勇答应帮助 “荔枝使” 一同协定荔枝运送路线从而保证完成这个看似不可能的任务。任务要求目标使用以下城市图用你熟悉的算法如 Dijkstra、A*找出从深圳→西安的最优路线并输出路径和总代价城市图如下括号中的数字代表运输时间单位小时city_graph{深圳:{广州:1.5,东莞:1.0},广州:{深圳:1.5,韶关:2.5,长沙:5.5},东莞:{深圳:1.0,惠州:1.2},惠州:{东莞:1.2,武汉:8.0},韶关:{广州:2.5,长沙:4.0},长沙:{韶关:4.0,武汉:3.0,郑州:8.0},武汉:{惠州:8.0,长沙:3.0,郑州:4.5,西安:10.0},郑州:{长沙:8.0,武汉:4.5,洛阳:2.0},洛阳:{郑州:2.0,西安:5.0},西安:{武汉:10.0,洛阳:5.0}}任务实现这里基于上面的故事背景以及官方提供的任务目标和城市图信息我们将我们的需求整理后输入 CodeBuddy 对话框看是否可以达到我们的最终目标你是一个算法专家使用以下城市图用你熟悉的算法比如 Dijkstra或者其他算法找出从深圳→西安的最优路线并输出路径和总成本 其中每小时需要换一匹马一匹马的价格为 25 贯 城市图如下括号中的数字代表运输时间单位小时 city_graph { 深圳: {广州: 1.5, 东莞: 1.0}, 广州: {深圳: 1.5, 韶关: 2.5, 长沙: 5.5}, 东莞: {深圳: 1.0, 惠州: 1.2}, 惠州: {东莞: 1.2, 武汉: 8.0}, 韶关: {广州: 2.5, 长沙: 4.0}, 长沙: {韶关: 4.0, 武汉: 3.0, 郑州: 8.0}, 武汉: {惠州: 8.0, 长沙: 3.0, 郑州: 4.5, 西安: 10.0}, 郑州: {长沙: 8.0, 武汉: 4.5, 洛阳: 2.0}, 洛阳: {郑州: 2.0, 西安: 5.0}, 西安: {武汉: 10.0, 洛阳: 5.0} }将以上整理的内容放入 CodeBuddy 的 AI 对话框中此时 CodeBuddy 的 Craft 会基于我们的问题进行问题分析问题分析结束后会使用 Dijkstra 算法来找出从深圳到西安的最优路线并编写一个 Python 程序来实现这个算法CodeBuddy 在使用 Python 语言编写程序实现这个算法之后Craft 会自动询问我们是否运行这个 Python 程序来获取结果。点击【运行】Craft 会自动使用execute_command工具来运行这个 Python 脚本自动运行 Python 脚本后出现了乱码不用慌在 Craft 检测到输出结果出现了中文编码问题导致显示为乱码的时候Craft 会自动分析原因这可能是因为 Windows 系统的命令行默认编码与 Python 脚本的编码不匹配导致的。同时 Craft 自动修改 Python 脚本确保它能正确处理中文字符。在脚本开头添加编码声明并确保输出时使用正确的编码。再次自动运行 Python 脚本后可以获取到我们想要的结果在返回结果中我们可以看到详细的最优路线信息以及每一段落成的时长消耗和最后计算得出的总时长和总成本那么对于上面的荔枝运送线路是否真的是最优线路总时长以及总成本都是最优呢为了保证这一点Craft 基于城市图信息自动生成了其他荔枝运送线路并验证其他荔枝运行线路是否比当下的线路更好通过对比发现路线 深圳 → 广州 → 长沙 → 武汉 → 西安 正是我们本次需要的最优路线是既能保证荔枝在一日之内抵达西安同时又能保证运输成本最优的运输荔枝线路到这里我们帮助荔枝使运送荔枝的任务就算完成了。算法源码为了方便大家有需要的小伙伴来参考这里我附上 find_optimal_route.py 的源码内容#!/usr/bin/env python# -*- coding: utf-8 -*-importheapqimportsys# 设置控制台输出编码ifsys.platformwin32:importio sys.stdoutio.TextIOWrapper(sys.stdout.buffer,encodingutf-8)defdijkstra(graph,start,end): 使用 Dijkstra 算法找出从起点到终点的最短路径 参数: graph: 城市图格式为字典的字典 start: 起始城市 end: 目标城市 返回: shortest_path: 最短路径的城市列表 total_time: 总时间 # 初始化距离字典所有城市的距离设为无穷大distances{city:float(infinity)forcityingraph}# 起点到自身的距离为 0distances[start]0# 初始化优先队列priority_queue[(0,start)]# 初始化前驱字典用于重建路径previous{city:Noneforcityingraph}whilepriority_queue:# 获取当前距离最小的城市current_distance,current_cityheapq.heappop(priority_queue)# 如果已经到达终点结束搜索ifcurrent_cityend:break# 如果当前距离大于已知距离跳过ifcurrent_distancedistances[current_city]:continue# 检查当前城市的所有邻居forneighbor,timeingraph[current_city].items():# 计算通过当前城市到达邻居的距离distancecurrent_distancetime# 如果找到更短的路径更新距离ifdistancedistances[neighbor]:distances[neighbor]distance previous[neighbor]current_city heapq.heappush(priority_queue,(distance,neighbor))# 重建最短路径shortest_path[]current_cityendwhilecurrent_city:shortest_path.append(current_city)current_cityprevious[current_city]# 反转路径使其从起点开始shortest_path.reverse()# 如果没有找到路径返回空列表和无穷大ifshortest_path[0]!start:return[],float(infinity)returnshortest_path,distances[end]defcalculate_cost(total_time,cost_per_hour25): 计算总成本 参数: total_time: 总时间小时 cost_per_hour: 每小时的成本贯 返回: total_cost: 总成本贯 # 向上取整因为每小时需要换一匹马importmath hoursmath.ceil(total_time)returnhours*cost_per_hourdefmain():# 城市图city_graph{深圳:{广州:1.5,东莞:1.0},广州:{深圳:1.5,韶关:2.5,长沙:5.5},东莞:{深圳:1.0,惠州:1.2},惠州:{东莞:1.2,武汉:8.0},韶关:{广州:2.5,长沙:4.0},长沙:{韶关:4.0,武汉:3.0,郑州:8.0},武汉:{惠州:8.0,长沙:3.0,郑州:4.5,西安:10.0},郑州:{长沙:8.0,武汉:4.5,洛阳:2.0},洛阳:{郑州:2.0,西安:5.0},西安:{武汉:10.0,洛阳:5.0}}start_city深圳end_city西安# 找出最短路径shortest_path,total_timedijkstra(city_graph,start_city,end_city)ifshortest_path:# 计算总成本total_costcalculate_cost(total_time)# 打印结果print(f从{start_city}到{end_city}的最优路线:)print( → .join(shortest_path))# 打印每段路程的时间print(\n详细路程:)foriinrange(len(shortest_path)-1):current_cityshortest_path[i]next_cityshortest_path[i1]timecity_graph[current_city][next_city]print(f{current_city}→{next_city}:{time}小时)print(f\n总时间{total_time}小时)print(f总成本{total_cost}贯 (每小时 25 贯))else:print(f无法从{start_city}到达{end_city})if__name____main__:main()进阶挑战对于上面的 Python 脚本的算法实现是在最优情况下的结果。那么在实际情况下在运送荔枝的途中可能会遇到各种各样的情况比如在运送荔枝的路上遇到山体滑坡导致断路不可达只能更换其他路线那么在这种情况下如何改造上述 Python 脚本可以根据实际情况快速计算得出新的运输路线就显得很有必要。那么我们基于以上的想法增加新的断路应对逻辑。在 Craft 对话框中输入我们的考虑对以上的算法增加断路逻辑支持可以指定具体城市名不可达同时快速生成新的最优路线的功能在整理了关于在运送荔枝路途中可能遇到的断路情况后Craft 针对我们的考虑进行了详细的分析并修改 Python 算法脚本内容在增加了断路逻辑之后的 Python 脚本自动运行会输出我们原始的最优路线结果cmd.exe /cpython find_optimal_route.py从深圳到西安的最优路线深圳 → 广州 → 长沙 → 武汉 → 西安 详细路程: 深圳 → 广州1.5 小时 广州 → 长沙5.5 小时 长沙 → 武汉3.0 小时 武汉 → 西安10.0 小时 总时间20.0 小时 总成本500 贯(每小时25贯)Process finished withexitcode0同时为了测试断路逻辑Craft 根据现有的线路指定一些城市为不可达。比如将武汉设为不可达这应该会迫使算法找到一条不经过武汉的路线那么得到的结果是根据结果分析得出我们将武汉设为不可达时算法成功找到了一条替代路线深圳 → 广州 → 长沙 → 郑州 → 洛阳 → 西安总时间为 22.0 小时比原来的路线多了 2 小时。将广州和东莞都设为不可达这应该会阻断所有从深圳出发的路线得到的结果是将长沙设为不可达这应该会迫使算法找到一条不经过长沙的路线得到的结果是在 Craft 自动对 Python 脚本的断路逻辑进行测试后确认了断路逻辑的正确为了让开发者更好的理解当前的 Python 脚本Craft 对断路逻辑的相关参数做了详细的说明介绍以及使用示例下面我们来自行尝试一下阻断长沙后的执行情况吧将最后一条示例命令复制并执行python find_optimal_route.py--start深圳--end西安--unavailable长沙在命令窗口执行上述命令后可以得到我们的结果到这里我们就为我们的荔枝运输路线增加了应对突发情况的快速响应最优路线情况。其实在现实情况中荔枝运输路线要远比算法中的复杂只是同样的人的力量也是不容小觑的这里我们就以上述两种情况来为 “荔枝使” 生成算法最优路线让荔枝从岭南今广东运往长安今西安完成荔枝使 的最终使命。进阶算法源码进阶算法源码是增加了断路逻辑后的 Python 脚本支持输入出发城市到达城市及不可达城市具体的语法操作如下# 默认最优路线python find_optimal_route.py# 指定单个不可达城市python find_optimal_route.py--unavailable武汉# 指定多个不可达城市python find_optimal_route.py--unavailable广州 东莞# 指定起点和终点可选python find_optimal_route.py--start深圳--end西安--unavailable长沙源码内容#!/usr/bin/env python# -*- coding: utf-8 -*-importheapqimportsysimportargparse# 设置控制台输出编码ifsys.platformwin32:importio sys.stdoutio.TextIOWrapper(sys.stdout.buffer,encodingutf-8)defdijkstra(graph,start,end,unavailable_citiesNone): 使用 Dijkstra 算法找出从起点到终点的最短路径 参数: graph: 城市图格式为字典的字典 start: 起始城市 end: 目标城市 unavailable_cities: 不可达的城市列表 返回: shortest_path: 最短路径的城市列表 total_time: 总时间 # 如果 unavailable_cities 为 None初始化为空列表ifunavailable_citiesisNone:unavailable_citiesset()else:unavailable_citiesset(unavailable_cities)# 检查起点和终点是否在不可达城市列表中ifstartinunavailable_cities:print(f错误起点{start}在不可达城市列表中)return[],float(infinity)ifendinunavailable_cities:print(f错误终点{end}在不可达城市列表中)return[],float(infinity)# 创建一个新图排除不可达的城市new_graph{}forcity,neighborsingraph.items():ifcitynotinunavailable_cities:new_graph[city]{}forneighbor,timeinneighbors.items():ifneighbornotinunavailable_cities:new_graph[city][neighbor]time# 检查起点和终点是否在新图中可能因为不可达城市而被孤立ifstartnotinnew_graphorendnotinnew_graph:return[],float(infinity)# 初始化距离字典所有城市的距离设为无穷大distances{city:float(infinity)forcityinnew_graph}# 起点到自身的距离为 0distances[start]0# 初始化优先队列priority_queue[(0,start)]# 初始化前驱字典用于重建路径previous{city:Noneforcityinnew_graph}whilepriority_queue:# 获取当前距离最小的城市current_distance,current_cityheapq.heappop(priority_queue)# 如果已经到达终点结束搜索ifcurrent_cityend:break# 如果当前距离大于已知距离跳过ifcurrent_distancedistances[current_city]:continue# 检查当前城市的所有邻居forneighbor,timeinnew_graph[current_city].items():# 计算通过当前城市到达邻居的距离distancecurrent_distancetime# 如果找到更短的路径更新距离ifdistancedistances[neighbor]:distances[neighbor]distance previous[neighbor]current_city heapq.heappush(priority_queue,(distance,neighbor))# 重建最短路径shortest_path[]current_cityendwhilecurrent_city:shortest_path.append(current_city)current_cityprevious[current_city]# 反转路径使其从起点开始shortest_path.reverse()# 如果没有找到路径返回空列表和无穷大ifshortest_path[0]!start:return[],float(infinity)returnshortest_path,distances[end]defcalculate_cost(total_time,cost_per_hour25): 计算总成本 参数: total_time: 总时间小时 cost_per_hour: 每小时的成本贯 返回: total_cost: 总成本贯 # 向上取整因为每小时需要换一匹马importmath hoursmath.ceil(total_time)returnhours*cost_per_hourdefparse_args():解析命令行参数parserargparse.ArgumentParser(description寻找最优路线支持指定不可达城市)parser.add_argument(--start,typestr,default深圳,help起始城市)parser.add_argument(--end,typestr,default西安,help目标城市)parser.add_argument(--unavailable,typestr,nargs*,help不可达的城市列表用空格分隔)returnparser.parse_args()defmain():# 解析命令行参数argsparse_args()# 城市图city_graph{深圳:{广州:1.5,东莞:1.0},广州:{深圳:1.5,韶关:2.5,长沙:5.5},东莞:{深圳:1.0,惠州:1.2},惠州:{东莞:1.2,武汉:8.0},韶关:{广州:2.5,长沙:4.0},长沙:{韶关:4.0,武汉:3.0,郑州:8.0},武汉:{惠州:8.0,长沙:3.0,郑州:4.5,西安:10.0},郑州:{长沙:8.0,武汉:4.5,洛阳:2.0},洛阳:{郑州:2.0,西安:5.0},西安:{武汉:10.0,洛阳:5.0}}# 获取起点和终点start_cityargs.start end_cityargs.end unavailable_citiesargs.unavailableor[]# 验证城市是否存在于图中all_citiesset(city_graph.keys())ifstart_citynotinall_cities:print(f错误起点{start_city}不存在于城市图中)returnifend_citynotinall_cities:print(f错误终点{end_city}不存在于城市图中)returnforcityinunavailable_cities:ifcitynotinall_cities:print(f警告不可达城市{city}不存在于城市图中)# 如果指定了不可达城市显示提示ifunavailable_cities:print(f指定的不可达城市{, .join(unavailable_cities)})# 找出最短路径shortest_path,total_timedijkstra(city_graph,start_city,end_city,unavailable_cities)ifshortest_path:# 计算总成本total_costcalculate_cost(total_time)# 打印结果print(f\n从{start_city}到{end_city}的最优路线:)print( → .join(shortest_path))# 打印每段路程的时间print(\n详细路程:)foriinrange(len(shortest_path)-1):current_cityshortest_path[i]next_cityshortest_path[i1]timecity_graph[current_city][next_city]print(f{current_city}→{next_city}:{time}小时)print(f\n总时间{total_time}小时)print(f总成本{total_cost}贯 (每小时 25 贯))else:print(f\n无法从{start_city}到达{end_city})ifunavailable_cities:print(这可能是因为指定的不可达城市阻断了所有可能的路径)if__name____main__:main()故事最后最终我们成功为荔枝使规划出荔枝从岭南今广东火速运抵长安今西安的最优路线让这穿越千里的鲜果速递成为可能衷心助他完成这一历史使命。这场跨越时空的荔枝速运深刻印证高效算法是基石善用 AI 如虎添翼——CodeBuddy 在手智解难题天下我有标签: CodeBuddyDijkstra 算法Python路径规划