深度优先搜索 寻路问题:
解题思路 从城市:1开始深度优先遍历整个图,找到所有能过到达 N 的走法, 选一个最优的。
从城市 1开始深度优先遍历整个图,找到所有能过到达 N 的走法, 选一个最优的。
优化: 1) 如果当前已经找到的最优路径长度为L ,那么在继续搜索的过程中,总长度已经大 于L的走法,就可以直接放弃,不用走到底了。
从城市 1开始深度优先遍历整个图,找到所有能到达 N 的走法, 选一个最优的。
优化: 1) 如果当前已经找到的最优路径长度为L ,那么在继续搜索的过程中,总长度已经大 于L的走法,就可以直接放弃,不用走到底了。
2) 用midL[k][m] 表示:走到城市k时总过路费为m的条件下,最优路径的长度。若在 后续的搜索中,再次走到k时,如果总路费恰好为m,且此时的路径长度已经超过 midL[k][m],则不必再走下去了。
特别声明:以上内容(如有图片或视频亦包括在内)为自媒体平台“网易号”用户上传并发布,本平台仅提供信息存储服务。
Notice: The content above (including the pictures and videos if any) is uploaded and posted by a user of NetEase Hao, which is a social media platform and only provides information storage services.