# 一个recursive的深度优先算法问题

**我自己写了一些代码，想知道哪里出了问题，更改的代码已经写在里面了**

用recursion来计算两点之间最短距离

例如有一个file

```
a,b,5
a,c,8
b,d,6
c,d,2
d,e,12
d,f,2
e,g,3
f,g,7
```

通过代码能变成如图的map

读取文件和生成map的代码已经写出来了

剩下的就是如何计算a到g的最短距离，有点懵逼，没啥思路，已写代码如下哈

```
"""
Graph search to find shortest path between two cities.
A road map is represented as a directed graph.
Edges represent road segments and are labeled with distances.
Nodes represent cities.
Wne use depth first search to find the shortest distance
between two cities. During the depth-first search from
start to end, we compute a shortest known distance to here from start
attribute for each node. After completion of depth first search,
destination city should be labeled with the shortest distance from
the start city.
"""
import argparse
def read_distancesmap_file:
"""Read a distance table from a named file into a dict
mapping sources to lists of destination, distance pairs.
Args:
map_file: A readable text file in which each line either
begins with # indicating a comment line or is of the form
from location, to location, distance or time, for example
Minis Tirith,Cair Andros,5
indicating one can travel from Minis Tirith to Cair Andros in 5.0 hours.
Returns:
Dict in which each entry d[from] is a list [to, cost, to, cost, ... ]
where from is a location name, to is a location name, and cost is time
or distance
as a floating point number. If x,y,z appears in the input file, then
we should have both d[x] contains y,z and d[y] contains x,z, i.e.,
we assume that roads are bi-directional.
"""
connections = dict
for line in map_file:
line = line.strip
if line.startswith"#" or line=="" :
# print"Skipping comment: ", line
continue ## Discard and go on to next
# print"Processing line: ", line
fields = line.split","
place_from = fields[0]
place_to = fields[1]
cost = floatfields[2]
if not place_from in connections:
connections[place_from] = [ ]
connections[place_from].append place_to, cost
if not place_to in connections:
connections[place_to] = [ ]
connections[place_to].append place_from, cost
return connections
def show_roadsroads:
"""Print roads from dict for debugging.
Args:
roads: A dict in which
roads[Chicago] == ["Atlanta", 30.0, "Austin", 25.0]
means that there is a 30.0 mile road from Chicago to Atlanta and a
25.0 mile road from Chicago to Austin.
Returns:
nothing
Effects:
Prints a textual representation of the road connections
"""
for from_place in roads:
printfrom_place + ":"
for hop in roads[from_place]:
to_place, dist = hop
print"\t->" + to_place + " " + strdist + ""
def dfsplace, dist_so_far, roads, distances:
"""Depth-first search, which may continue from from_place if dist_so_far
is the shortest distance at which it has yet been reached.
Args:
place: Currently searching from here
dist_so_far: Distance at which from_place has been reached
this time which may not be the shortest path to from_place
roads: dict mapping places to lists of hops of the form place, hop-distance
distances: dict mapping places to the shortest distance at which they
have been reached so far up to this time.
"""
distances = []
dist_so_far = distances[place]
if place not in distances:
distances[place] = dist_so_far
for city,dist in road[place]:
for i in city:
dfsi,dist_so_far,roads,distances
else:
if distances[place]<=dist_so_far:
distances[place] = dist_so_far
#FIXME
# Consider cases:
# - Weve never been at place before so its not in distances
# - Weve been at place before, on a path as short as this one in distances
# - Weve been here before, but this way is shorter dist_so_far
# Consider which are base cases, and which require recursion.
# For the cases that require recursion, what is the progress step?
def main:
"""
Main program gets city pair and map file name,
reports distance or reports lack of connectivity.
"""
parser = argparse.ArgumentParser
description="Find shortest route in road network"
parser.add_argumentfrom_place,
help = "Starting place quoted if it contains blanks"
parser.add_argumentto_place,
help = "Destination place quoted if it contains blanks"
parser.add_argumentmap_file, type=argparse.FileTyper,
help = "Name of file containing road connections and distances"
args = parser.parse_args
start_place = args.from_place
destination = args.to_place
roads = read_distancesargs.map_file
if not start_place in roads:
print"Start place ", start_place, " is not on the map"
exit1
if not destination in roads:
print"Destination ", destination, " is not on the map"
exit1
distances = { }
dfsstart_place, 0.0, roads, distances
if destination in distances :
print"Distance from {} to {} is {}".format
start_place,destination, distances[destination]
else:
print"You cant get from {} to {}".formatstart_place, destination
if __name__ == "__main__":
main
```

求大神啊~

上周通过office hour问过GTF之后自己成功那个写出来一个代码可以运行

```
def dfsplace, dist_so_far, roads, distances:
"""Depth-first search, which may continue from from_place if dist_so_far
is the shortest distance at which it has yet been reached.
Args:
place: Currently searching from here
dist_so_far: Distance at which from_place has been reached
this time which may not be the shortest path to from_place
roads: dict mapping places to lists of hops of the form place, hop-distance
distances: dict mapping places to the shortest distance at which they
have been reached so far up to this time.
"""
if place not in distances:
distances[place] = dist_so_far
for city,dist in roads[place]:
dfscity,dist_so_far+dist,roads,distances
else:
if distances[place] > dist_so_far:
distances[place] = dist_so_far
for city,dist in roads[place]:
dfscity,dist_so_far+dist,roads,distances
```

最后得到将近满分的评分，缺憾在于可以将两个for loop变成一个。标准答案professor还没有上传，上传后我也会更新上来。

标准答案如下

```
def dfsplace, dist_so_far,roads,distances:
if place not in distances or place in distances and dist_so_far < distances[place]:
distances[place] = dist_so_far
for routes in roads[place]:
next_place, dist = routes
dfsnext_place, dist_so_far + dist, roads, distances
```

代码里提示说使用深度搜索优先算法depth first search了。

一条路走到底，每一步选择一个未走过的点。

最新文章

- 如何用终端或者python测试一个ss帐号的延迟?
- (澳门新葡京官网) 有一个数组，从中挑ABC三个整数，让ABC三个整数加起来等于0，看有多少个这样的数组？
- pandas中axis的疑惑？
- urllib爬虫下载图片，很简单的程序，但是输出结果却不定，很奇怪
- segmentfault的url怎么实现的？
- (澳门新葡京官网) Django HttpResponse为什么不能返回字典？
- 哪里有稳定的地震数据接口？
- Gunicorn启动Flask如何执行启动上下文环境？
- Scrapy 1.1.2 怎么用？
- (澳门新葡京官网) python mysqldb备份数据库表 有时候断连接的问题。
- 含中文JSON未能按期待进行dumps，(\xxx\xxx\xxx)?
- (澳门新葡京官网) python 中的maketrans在utf-8文件中该怎么使用
- 如何让dataframe A 的一列与dataframe B的一列相减 相加结果记到A的c列？
- smtp发邮件的附件，对方收到的是乱码
- 在python进行方差分析时，残差的自由度总是为0.

广告位