[已解决]分享一个自己写的BFS算法加每一步都会输出。求一个DFS（递归）的代码，有没有大牛能码

LXMARCO

急急急！求走过路过大佬们能否指点一下。DFS递归时老是出错，希望能用PYTHON写
1        1        1        1        1        1        1        1
1        0        0        0        0        0        0        1
1        0        0        0        0        0        0        1
1        0        0        0        0        0        0        1
1        1        1        1        0        0        0        1
1        1        1        1        0        0        0        1
1        0        0        0        0        0        0        1
1        0        0        0        0        0        0        1
1        0        0        0        0        0        0        1
1        1        1        1        1        1        1        1
随意定起点终点。我就想知道怎么个递归方法，希望大佬们能配上讲解！  磕头感谢！！ （最好也能像我写的BFS样输出每一步，没有也行）

下面是我自己码的BFS代码分享给大家。


#! /usr/bin/env python

FILE_NAME = " "
START_X = 2
START_Y = 2
END_X = 7
END_Y = 2

class Node:
    def __init__(self, x, y, myId, parentId):
        self.x = x
        self.y = y
        self.myId = myId
        self.parentId = parentId
    def dump(self):
        print("---------- x "+str(self.x)+\
                         " | y "+str(self.y)+\
                         " | id "+str(self.myId)+\
                         " | parentId "+str(self.parentId))

nodes = []

init = Node(START_X, START_Y, 0, -2)
# init.dump()

nodes.append(init)

charMap = []

def dumpMap():
    for line in charMap:
        print (line)

with open(FILE_NAME) as f:
    line = f.readline()
    while line:
        charLine = line.strip().split(',')
        charMap.append(charLine)
        line = f.readline()

charMap[START_X][START_Y] = '3'
charMap[END_X][END_Y] = '4'


dumpMap()

done = False
goalParentId = -1

while not done:
    print("--------------------- number of nodes: "+str(len(nodes)))
    for node in nodes:
        node.dump()


        # up
        tmpX = node.x - 1
        tmpY = node.y
        if( charMap[tmpX][tmpY] == '4' ):
            print("up: GOALLLL!!!")
            goalParentId = node.myId
            done = True
            break
        elif ( charMap[tmpX][tmpY] == '0' ):   # 这里不能用else,因为 ‘1’ 墙壁会出错
            print("up: mark visited")
            newNode = Node(tmpX, tmpY, len(nodes), node.myId)
            charMap[tmpX][tmpY] = '2'
            nodes.append(newNode)
            

        # down
        tmpX = node.x + 1
        tmpY = node.y
        if( charMap[tmpX][tmpY] == '4' ):
            print("down: GOALLLL!!!")
            goalParentId = node.myId
            done = True
            break
        elif ( charMap[tmpX][tmpY] == '0' ):
            print("down: mark visited")
            newNode = Node(tmpX, tmpY, len(nodes), node.myId)
            charMap[tmpX][tmpY] = '2'
            nodes.append(newNode)
            
  

        # right
        tmpX = node.x
        tmpY = node.y + 1
        if( charMap[tmpX][tmpY] == '4' ):
            print("right: GOALLLL!!!")
            goalParentId = node.myId
            done = True
            break
        elif ( charMap[tmpX][tmpY] == '0' ):
            print("right    : mark visited")
            newNode = Node(tmpX, tmpY, len(nodes), node.myId)
            charMap[tmpX][tmpY] = '2'
            nodes.append(newNode)
           

        # left
        tmpX = node.x
        tmpY = node.y - 1
        if( charMap[tmpX][tmpY] == '4' ):
            print("left: GOALLLL!!!")
            goalParentId = node.myId
            done = True
            break
        elif ( charMap[tmpX][tmpY] == '0' ):
            print("left: mark visited")
            newNode = Node(tmpX, tmpY, len(nodes), node.myId)
            charMap[tmpX][tmpY] = '2'
            nodes.append(newNode)

        dumpMap()

print("%%%%%%%%%%%%%%%%%%%")
ok = False
while not ok:
    for node in nodes:
        if( node.myId == goalParentId ):
            node.dump()
            goalParentId = node.parentId
            if( goalParentId == -2):
                print("%%%%%%%%%%%%%%%%%2")
                ok = True

最佳答案

月排行榜 / 总排行榜

Unicorn#

2019-10-21 21:30:27

这个用DFS有点难....
因为它上下级关系不明确，就是很难制定一个好的深搜顺序
关于如何确定选项的优先级，这里应该不是最优解，但是时间有限，这样也行
望采纳

text = []

f = open('puzzle.txt')
content = f.read().split('\n')
for each_line in content:
    temp = []
    for i in each_line.split():
        temp.append(int(i))
    text.append(temp)


p = []  #跟踪进度
final_p = []  #储存目前最优路径
l = 255   #储存步数

start_x = int(input('输入起始行：'))
start_y = int(input('输入起始列：'))
end_x = int(input('输入终止行：'))
end_y = int(input('输入终止列：'))

#获取前进方向顺序。并非最优解。
#从当前位置直接指向目标位置，使用右手定则。
class Dir(list):
    def __init__(self, x, y):
        if end_x > x:
            dx = 1
        elif end_x < x:
            dx = -1
        else:
            dx = 0
        if end_y > y:
            dy = 1
        elif end_x < y:
            dy = -1
        else:
            dy = 0
        bas = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        temp = [(dx, 0),(0, dy),(-dx, 0),(0, -dy)]
        for each in temp:
            if each == (0, 0):
                continue
            elif each not in self:
                self.append(each)
        for each in bas:
            if each not in self:
                self.append(each)

def dfs(x, y):
    global text, p, l, final_p
    if len(p) > l:
        return
    p.append((x, y))
    text[x][y] = -1
    if x == end_x and y == end_y:
        l = len(p)
        final_p = p[:]
        text[x][y] = 0
        p.remove((x, y))
        return
    for each in Dir(x, y):
        temp_x = x + each[0]
        temp_y = y + each[1]
        if check(temp_x, temp_y):
            dfs(temp_x, temp_y)
    p.remove((x, y))
    return

#检查输入坐标是否已遍历或被阻挡
def check(x, y):
    if x > len(text)-1 or x < 0 or\
       y > len(text[x])-1 or y < 0 or\
       text[x][y]:
        return False
    else:
        return True

if __name__ == '__main__':
    dfs(start_x, start_y)
    if final_p:
        print(final_p)
    else:
        print('无法到达')
    

跳转到最佳答案楼层

Unicorn#

正在写啦
晚点回复

Unicorn#

这个用DFS有点难....
因为它上下级关系不明确，就是很难制定一个好的深搜顺序
关于如何确定选项的优先级，这里应该不是最优解，但是时间有限，这样也行
望采纳

text = []

f = open('puzzle.txt')
content = f.read().split('\n')
for each_line in content:
    temp = []
    for i in each_line.split():
        temp.append(int(i))
    text.append(temp)


p = []  #跟踪进度
final_p = []  #储存目前最优路径
l = 255   #储存步数

start_x = int(input('输入起始行：'))
start_y = int(input('输入起始列：'))
end_x = int(input('输入终止行：'))
end_y = int(input('输入终止列：'))

#获取前进方向顺序。并非最优解。
#从当前位置直接指向目标位置，使用右手定则。
class Dir(list):
    def __init__(self, x, y):
        if end_x > x:
            dx = 1
        elif end_x < x:
            dx = -1
        else:
            dx = 0
        if end_y > y:
            dy = 1
        elif end_x < y:
            dy = -1
        else:
            dy = 0
        bas = [(1, 0), (0, 1), (-1, 0), (0, -1)]
        temp = [(dx, 0),(0, dy),(-dx, 0),(0, -dy)]
        for each in temp:
            if each == (0, 0):
                continue
            elif each not in self:
                self.append(each)
        for each in bas:
            if each not in self:
                self.append(each)

def dfs(x, y):
    global text, p, l, final_p
    if len(p) > l:
        return
    p.append((x, y))
    text[x][y] = -1
    if x == end_x and y == end_y:
        l = len(p)
        final_p = p[:]
        text[x][y] = 0
        p.remove((x, y))
        return
    for each in Dir(x, y):
        temp_x = x + each[0]
        temp_y = y + each[1]
        if check(temp_x, temp_y):
            dfs(temp_x, temp_y)
    p.remove((x, y))
    return

#检查输入坐标是否已遍历或被阻挡
def check(x, y):
    if x > len(text)-1 or x < 0 or\
       y > len(text[x])-1 or y < 0 or\
       text[x][y]:
        return False
    else:
        return True

if __name__ == '__main__':
    dfs(start_x, start_y)
    if final_p:
        print(final_p)
    else:
        print('无法到达')
    

LXMARCO

Unicorn# 发表于 2019-10-21 21:30
这个用DFS有点难....
因为它上下级关系不明确，就是很难制定一个好的深搜顺序
关于如何确定选项的优先级 ...

很感谢!!   你这个好像类似于DFS不过严格来说又不太是，不过还是学到了很多！！谢谢你

LXMARCO

Unicorn# 发表于 2019-10-21 21:30
这个用DFS有点难....
因为它上下级关系不明确，就是很难制定一个好的深搜顺序
关于如何确定选项的优先级 ...

我找到了一个if回溯递归的DFS，但是没怎么看懂他if是怎么递归和回溯的。。。。求大佬解释解释谢谢
grid = [[0, 0, 0, 0, 0, 1],
        [1, 1, 0, 0, 0, 1],
        [0, 0, 0, 1, 0, 0],
        [0, 1, 1, 0, 0, 1],
        [0, 1, 0, 0, 1, 0],
        [0, 1, 0, 0, 0, 2]]

def search(x, y):
    if grid[x][y] == 2:
        print ('found at %d,%d' % (x, y))
        return True
    elif grid[x][y] == 1:
        print ('wall at %d,%d' % (x, y))
        return False
    elif grid[x][y] == 3:
        print ('visited at %d,%d' % (x, y))
        return False
   
    print ('visiting %d,%d' % (x, y))

    # mark as visited
    grid[x][y] = 3

    # explore neighbors clockwise starting by the one on the right
    if ((x < len(grid)-1 and search(x+1, y))
        or (y > 0 and search(x, y-1))
        or (x > 0 and search(x-1, y))
        or (y < len(grid)-1 and search(x, y+1))):
        return True

    return False

search(0, 0)

Unicorn#

LXMARCO 发表于 2019-10-22 22:27
我找到了一个if回溯递归的DFS，但是没怎么看懂他if是怎么递归和回溯的。。。。求大佬解释解释谢谢
grid  ...

这个是有问题的
就是我之前提到的 选项优先级不确定的问题
它使用的优先级是
右>下>左>右
那么最终得到的几乎不可能是最优解
例如：   箭头代表经过 #为开始 &为结束
1        1        1        1        1        1        1        1
1        →     →        →       &        0        #        1
1        ↑       ←       ←       ←       ←       ↓        1
1        0        0        0        →       ↑        ↓        1
1        1        1        1        ↑         ←       ↓        1
1        1        1        1        →        ↑        ↓        1
1        0        0        0        ↑       ←        ↓        1
1        →      →      →      →        ↑        ↓        1
1        ↑        ←     ←       ←       ←      ←        1
1        1        1        1        1        1        1        1
显然， 它给出的路线并非最优解
事实上，它只给出了一个遍历全图的像无头苍蝇一样的方式。
我只是对优先级做了设定：
x向趋近目标>y向趋近目标>-x向趋近目标>-y向趋近目标
这样较好地完成剪枝，减少运行时间。多数情况能提供最优解
我还给了最优解检测：记录每次的路程，取最小

LXMARCO

Unicorn# 发表于 2019-10-22 22:46
这个是有问题的
就是我之前提到的 选项优先级不确定的问题
它使用的优先级是

嗯嗯，是的，我明白你得意思，相当于在DFS上优化了。  谢谢你的分享，哈哈，我在DFS和你的基础上又写了个优化DFS方法，到时候交作业的时候和DFS,BFS，优化，A-start对比下。谢谢你!!g感谢！

下面是我码的DFS，应该没啥问题。（改变顺序有bug，不过这个顺序ok的*-*，分享给你啦）。
FILE_NAME = "C："


START_X = int(input('Enter the starting line：'))
START_Y = int(input('Enter the starting column：'))
END_X = int(input('Enter the end line：'))
END_Y = int(input('Enter the end column：'))
path_map = []


def load_map():
    for line in path_map:
        print(line)


with open(FILE_NAME) as f:
    line = f.readline()
    while line:
        path_line = line.strip().split(',')
        path_map.append(path_line)
        line = f.readline()


path_map[START_X][START_Y] = '2'
path_map[END_X][END_Y] = '4'
load_map()
paso_final = []


def DFS_search(x, y):
    if path_map[x][y] == '4':
        print('found at %d,%d' % (x, y))
        paso_final.append((x, y))
        print(paso_final)
        load_map()
        return True
    elif path_map[x][y] == '1':
        print('wall at %d,%d' % (x, y))
        load_map()
        return False
    elif path_map[x][y] == '3':
        print('visited at %d,%d' % (x, y))
        load_map()
        return False

    print('visiting %d,%d' % (x, y))

    paso_final.append((x, y))
    # mark as visited
    path_map[x][y] = '3'
    load_map()
    # explore neighbors clockwise starting by the one on the right
    if ((x < len(path_map) - 1 and DFS_search(x + 1, y))
            or (y > 0 and DFS_search(x, y - 1))
            or (x > 0 and DFS_search(x - 1, y))
            or (y < len(path_map) - 1 and DFS_search(x, y + 1))):
        return True

    return False

DFS_search(START_X, START_Y)

Unicorn#

LXMARCO 发表于 2019-10-23 17:11
嗯嗯，是的，我明白你得意思，相当于在DFS上优化了。  谢谢你的分享，哈哈，我在DFS和你的基础上又写了个 ...

这就是右＞下＞左＞上的DFS顺序鸭
我的是相当于给了他一个类函数来分析DFS顺序