鱼C论坛

 找回密码
 立即注册
查看: 1894|回复: 7

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

[复制链接]
发表于 2019-10-21 17:40:30 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能^_^

您需要 登录 才可以下载或查看,没有账号?立即注册

x
急急急!求走过路过大佬们能否指点一下。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
最佳答案
2019-10-21 21:30:27
这个用DFS有点难....
因为它上下级关系不明确,就是很难制定一个好的深搜顺序
关于如何确定选项的优先级,这里应该不是最优解,但是时间有限,这样也行
望采纳
  1. text = []

  2. f = open('puzzle.txt')
  3. content = f.read().split('\n')
  4. for each_line in content:
  5.     temp = []
  6.     for i in each_line.split():
  7.         temp.append(int(i))
  8.     text.append(temp)


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

  12. start_x = int(input('输入起始行:'))
  13. start_y = int(input('输入起始列:'))
  14. end_x = int(input('输入终止行:'))
  15. end_y = int(input('输入终止列:'))

  16. #获取前进方向顺序。并非最优解。
  17. #从当前位置直接指向目标位置,使用右手定则。
  18. class Dir(list):
  19.     def __init__(self, x, y):
  20.         if end_x > x:
  21.             dx = 1
  22.         elif end_x < x:
  23.             dx = -1
  24.         else:
  25.             dx = 0
  26.         if end_y > y:
  27.             dy = 1
  28.         elif end_x < y:
  29.             dy = -1
  30.         else:
  31.             dy = 0
  32.         bas = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  33.         temp = [(dx, 0),(0, dy),(-dx, 0),(0, -dy)]
  34.         for each in temp:
  35.             if each == (0, 0):
  36.                 continue
  37.             elif each not in self:
  38.                 self.append(each)
  39.         for each in bas:
  40.             if each not in self:
  41.                 self.append(each)

  42. def dfs(x, y):
  43.     global text, p, l, final_p
  44.     if len(p) > l:
  45.         return
  46.     p.append((x, y))
  47.     text[x][y] = -1
  48.     if x == end_x and y == end_y:
  49.         l = len(p)
  50.         final_p = p[:]
  51.         text[x][y] = 0
  52.         p.remove((x, y))
  53.         return
  54.     for each in Dir(x, y):
  55.         temp_x = x + each[0]
  56.         temp_y = y + each[1]
  57.         if check(temp_x, temp_y):
  58.             dfs(temp_x, temp_y)
  59.     p.remove((x, y))
  60.     return

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

  69. if __name__ == '__main__':
  70.     dfs(start_x, start_y)
  71.     if final_p:
  72.         print(final_p)
  73.     else:
  74.         print('无法到达')
  75.    
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2019-10-21 18:18:03 | 显示全部楼层
正在写啦
晚点回复
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-10-21 21:30:27 | 显示全部楼层    本楼为最佳答案   
这个用DFS有点难....
因为它上下级关系不明确,就是很难制定一个好的深搜顺序
关于如何确定选项的优先级,这里应该不是最优解,但是时间有限,这样也行
望采纳
  1. text = []

  2. f = open('puzzle.txt')
  3. content = f.read().split('\n')
  4. for each_line in content:
  5.     temp = []
  6.     for i in each_line.split():
  7.         temp.append(int(i))
  8.     text.append(temp)


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

  12. start_x = int(input('输入起始行:'))
  13. start_y = int(input('输入起始列:'))
  14. end_x = int(input('输入终止行:'))
  15. end_y = int(input('输入终止列:'))

  16. #获取前进方向顺序。并非最优解。
  17. #从当前位置直接指向目标位置,使用右手定则。
  18. class Dir(list):
  19.     def __init__(self, x, y):
  20.         if end_x > x:
  21.             dx = 1
  22.         elif end_x < x:
  23.             dx = -1
  24.         else:
  25.             dx = 0
  26.         if end_y > y:
  27.             dy = 1
  28.         elif end_x < y:
  29.             dy = -1
  30.         else:
  31.             dy = 0
  32.         bas = [(1, 0), (0, 1), (-1, 0), (0, -1)]
  33.         temp = [(dx, 0),(0, dy),(-dx, 0),(0, -dy)]
  34.         for each in temp:
  35.             if each == (0, 0):
  36.                 continue
  37.             elif each not in self:
  38.                 self.append(each)
  39.         for each in bas:
  40.             if each not in self:
  41.                 self.append(each)

  42. def dfs(x, y):
  43.     global text, p, l, final_p
  44.     if len(p) > l:
  45.         return
  46.     p.append((x, y))
  47.     text[x][y] = -1
  48.     if x == end_x and y == end_y:
  49.         l = len(p)
  50.         final_p = p[:]
  51.         text[x][y] = 0
  52.         p.remove((x, y))
  53.         return
  54.     for each in Dir(x, y):
  55.         temp_x = x + each[0]
  56.         temp_y = y + each[1]
  57.         if check(temp_x, temp_y):
  58.             dfs(temp_x, temp_y)
  59.     p.remove((x, y))
  60.     return

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

  69. if __name__ == '__main__':
  70.     dfs(start_x, start_y)
  71.     if final_p:
  72.         print(final_p)
  73.     else:
  74.         print('无法到达')
  75.    
复制代码
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-10-22 22:26:23 | 显示全部楼层
Unicorn# 发表于 2019-10-21 21:30
这个用DFS有点难....
因为它上下级关系不明确,就是很难制定一个好的深搜顺序
关于如何确定选项的优先级 ...

很感谢!!   你这个好像类似于DFS不过严格来说又不太是,不过还是学到了很多!!谢谢你
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 2019-10-22 22:27:17 | 显示全部楼层
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)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 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向趋近目标
这样较好地完成剪枝,减少运行时间。多数情况能提供最优解
我还给了最优解检测:记录每次的路程,取最小
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

 楼主| 发表于 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[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)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

发表于 2019-10-23 17:28:49 | 显示全部楼层
LXMARCO 发表于 2019-10-23 17:11
嗯嗯,是的,我明白你得意思,相当于在DFS上优化了。  谢谢你的分享,哈哈,我在DFS和你的基础上又写了个 ...

这就是右>下>左>上的DFS顺序鸭
我的是相当于给了他一个类函数来分析DFS顺序
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 12:42

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表