Board logo

标题: [问题求助] 没学好算法写的Python盲搜程序,高手给看看怎么能让0更快找到1 [打印本页]

作者: 普大喜奔    时间: 2014-9-29 20:24     标题: 没学好算法写的Python盲搜程序,高手给看看怎么能让0更快找到1

  1. import os
  2. import time
  3. import random
  4. global FIND
  5. global SCREEN
  6. FIND=0
  7. cols=22
  8. rows=22
  9. waypoint=[]
  10. target=(10,13)
  11. start=(1,1)
  12. SCREEN=[['' for x in range(cols)] for y in range(rows)]
  13. grid=[[0 for x in range(cols)] for y in range(rows)]
  14. for x in range(cols):
  15.     grid[0][x]=1
  16.     grid[rows-1][x]=1
  17. for y in range(rows):
  18.     grid[y][0]=1
  19.     grid[y][cols-1]=1
  20. grid[target[0]][target[1]]=2
  21. def show(sy,sx):
  22.     for y in range(rows):
  23.         for x in range(cols):
  24.             if grid[y][x]==0:SCREEN[y][x]=' '
  25.             if grid[y][x]==1:SCREEN[y][x]='*'
  26.             if grid[y][x]==2:SCREEN[y][x]='1'
  27.             if grid[y][x]==3:SCREEN[y][x]='x'
  28.     SCREEN[sy][sx]='0'
  29.     os.system('cls')
  30.     for y in SCREEN:print(' '.join(y))
  31.     time.sleep(0.1)
  32. def search(y,x):
  33.     global FIND
  34.     global SCREEN
  35.     direct=random.randint(0,3)
  36.     grid[y][x]=3
  37.     waypoint.append((y,x))
  38.     show(y,x)
  39.     if grid[y][x+1]==2 or grid[y+1][x]==2 or grid[y-1][x]==2 or grid[y][x-1]==2:
  40.         FIND=1
  41.         return
  42.     if direct==0:#向右顺时针搜索
  43.         if grid[y][x+1]==0 and FIND==0:search(y,x+1)
  44.         if grid[y+1][x]==0 and FIND==0:search(y+1,x)
  45.         if grid[y][x-1]==0 and FIND==0:search(y,x-1)
  46.         if grid[y-1][x]==0 and FIND==0:search(y-1,x)
  47.     if direct==1:#向下顺时针
  48.         if grid[y+1][x]==0 and FIND==0:search(y+1,x)
  49.         if grid[y][x-1]==0 and FIND==0:search(y,x-1)
  50.         if grid[y-1][x]==0 and FIND==0:search(y-1,x)
  51.         if grid[y][x+1]==0 and FIND==0:search(y,x+1)
  52.     if direct==2:#向左顺时针
  53.         if grid[y][x-1]==0 and FIND==0:search(y,x-1)
  54.         if grid[y-1][x]==0 and FIND==0:search(y-1,x)
  55.         if grid[y][x+1]==0 and FIND==0:search(y,x+1)
  56.         if grid[y+1][x]==0 and FIND==0:search(y+1,x)
  57.     if direct==3:#向上顺时针
  58.         if grid[y-1][x]==0 and FIND==0:search(y-1,x)
  59.         if grid[y][x+1]==0 and FIND==0:search(y,x+1)
  60.         if grid[y+1][x]==0 and FIND==0:search(y+1,x)
  61.         if grid[y][x-1]==0 and FIND==0:search(y,x-1)
  62.     if FIND==0:
  63.         del waypoint[-1]
  64.         show(waypoint[-1][0],waypoint[-1][1])
  65.     else:
  66.         print('blind 0 found 1!')
  67.         os.system('pause >nul')
  68.         os.system('cls')
  69.         print("0's way of duplicate removal:")
  70.         SCREEN=[['   'for x in range(cols)] for y in range(rows)]
  71.         i=1
  72.         for point in waypoint:
  73.             SCREEN[point[0]][point[1]]=('%3s'%(str(i)))
  74.             i+=1
  75.         for y in SCREEN:print(' '.join(y))
  76.         os.system('pause >nul')
  77.         exit()
  78. show(start[0],start[1])
  79. print("blind 0 want to find 1,press key to go...")
  80. os.system('pause >nul')
  81. search(start[0],start[1])
复制代码

作者: CrLf    时间: 2014-9-29 21:11

没看懂
如果 1 的位置是随机的,怎么搜不是都一样的概率吗?
而如果 1 的位置是固定的,那好像就不是“盲搜”了吧?
作者: 523066680    时间: 2014-9-29 21:20

本帖最后由 523066680 于 2014-9-29 21:23 编辑

回复 2# CrLf


    同没看懂,可能nerobin比较了解。
作者: 普大喜奔    时间: 2014-9-29 21:33

回复 2# CrLf
1是随机的 我为方便观察搞成固定的了
意思就是说怎么搜都一样啊
作者: 普大喜奔    时间: 2014-9-29 22:55

回复 3# 523066680
写这个东东的目的其实是为了随机生成迷宫 版主有没有好点的办法




欢迎光临 批处理之家 (http://bbs.bathome.net/) Powered by Discuz! 7.2