论坛 › 数据结构与算法 › 分享一个自己写的BFS算法加每一步都会输出。求一个DFS（递归）的代码，有没有大牛能码

LXMARCO 发表于 2019-10-21 17:40:30

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

急急急！求走过路过大佬们能否指点一下。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 = '3'
charMap = '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 == '4' ):
            print("up: GOALLLL!!!")
            goalParentId = node.myId
            done = True
            break
      elif ( charMap == '0' ):   # 这里不能用else,因为 ‘1’ 墙壁会出错
            print("up: mark visited")
            newNode = Node(tmpX, tmpY, len(nodes), node.myId)
            charMap = '2'
            nodes.append(newNode)
            

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


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

      # left
      tmpX = node.x
      tmpY = node.y - 1
      if( charMap == '4' ):
            print("left: GOALLLL!!!")
            goalParentId = node.myId
            done = True
            break
      elif ( charMap == '0' ):
            print("left: mark visited")
            newNode = Node(tmpX, tmpY, len(nodes), node.myId)
            charMap = '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 18:18:03

正在写啦
晚点回复

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 = -1
    if x == end_x and y == end_y:
      l = len(p)
      final_p = p[:]
      text = 0
      p.remove((x, y))
      return
    for each in Dir(x, y):
      temp_x = x + each
      temp_y = y + each
      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)-1 or y < 0 or\
       text:
      return False
    else:
      return True

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

LXMARCO 发表于 2019-10-22 22:26:23

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

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

LXMARCO 发表于 2019-10-22 22:27:17

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

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

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

    # mark as visited
    grid = 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# 发表于 2019-10-22 22:46:43

本帖最后由 Unicorn# 于 2019-10-22 23:31 编辑

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 发表于 2019-10-23 17:11:45

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 = '2'
path_map = '4'
load_map()
paso_final = []


def DFS_search(x, y):
    if path_map == '4':
      print('found at %d,%d' % (x, y))
      paso_final.append((x, y))
      print(paso_final)
      load_map()
      return True
    elif path_map == '1':
      print('wall at %d,%d' % (x, y))
      load_map()
      return False
    elif path_map == '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 = '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# 发表于 2019-10-23 17:28:49

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

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

查看完整版本: 分享一个自己写的BFS算法加每一步都会输出。求一个DFS（递归）的代码，有没有大牛能码