八數碼問題 python實作 BFS寬度優先搜索 極大優化速度版

上一年的人工智能課就已經把八數碼的BFS DFS A* 遺傳演算法都試了一遍.昨天上傳舊的時候覺得實作的不是很優雅,現在想重新用python來一遍.這次我實作了一個很大的突破,起碼比原來的演算法實作的速度提高了幾十倍~

題目如圖,首先我們先建立一個棋盤類來進行八數碼問題的操作.

class board:
    def __init__(self):
        # self.groud = [1,0,2,3,4,5,6,7,8]
        # 棋盤,0代表空
        self.groud = [7, 2, 4, 5, 0, 6, 8, 3, 1]
        #移動的路徑
        self.route = []
# 是否到達正確狀態
    def guiwei(self):
        flag = True
        for i in range(9):
            if self.groud[i] != i:
                flag = False
                break
        return flag
# 兩個位置數字進行交換
    def exchange(self, index1, index2):
        temp = self.groud[index1]
        self.groud[index1] = self.groud[index2]
        self.groud[index2] = temp
# 空格向左移動
    def left(self):
        index = self.groud.index(0)
        if index % 3 != 0:
            self.exchange(index, index-1)
# 空格向右移動
    def right(self):
        index = self.groud.index(0)
        if index % 3 != 2:
            self.exchange(index, index+1)
# 空格向上移動
    def up(self):
        index = self.groud.index(0)
        if int(index/3) != 0:
            self.exchange(index, index-3)
# 空格向下移動
    def down(self):
        index = self.groud.index(0)
        if int(index/3) != 2:
            self.exchange(index, index+3)
# 回傳空格能移動的方位的串列,比如[0,1,2,3]代表空格能向左右上下進行移動
    def can_move(self):
        index = self.groud.index(0)
        can = []
        if index % 3 != 0:
            can.append(0)
        if index % 3 != 2:
            can.append(1)
        if int(index/3) != 0:
            can.append(2)
        if int(index/3) != 2:
            can.append(3)
        return can
# 展示棋盤
    def show_board(self):
        print(self.groud)
# 路徑
    def show_route(self):
        print(self.route)
        print(len(self.route))
# 通過route路徑進行移動,route是路徑串列
    def move(self, route):
        for i in route:
            if i == 0:
                self.left()
            elif i == 1:
                self.right()
            elif i == 2:
                self.up()
            else:
                self.down()
# 僅移動一步
    def move_one(self, i):
        if i == 0:
            self.left()
        elif i == 1:
            self.right()
        elif i == 2:
            self.up()
        else:
            self.down()
# 測驗如果向目標方向移動,棋盤的變化,回傳變化的棋盤
    def test(self, i):
        groud = []
        if i == 0:
            self.left()
            groud = self.groud[:]
            self.right()
        elif i == 1:
            self.right()
            groud = self.groud[:]
            self.left()
        elif i == 2:
            self.up()
            groud = self.groud[:]
            self.down()
        else:
            self.down()
            groud = self.groud[:]
            self.up()
        return groud

然后我先寫出來了一個沒有任何優化的極簡BFS

from board import board
def BFS_waste_time():
    deq = []
    b = board()
    for x in b.can_move():
        deq.append([x])
    flag = 0
    while True:
        flag+=1
        temp = deq.pop(0)
        if flag%10000==0:
            flag=0
            print(temp)
            print(len(temp)) 
        b_temp = board()
        b_temp.move(temp)
        if  b_temp.guiwei():
            print(temp)
            break
        for x in b_temp.can_move():
            new_temp=temp[:]
            new_temp.append(x)
            deq.append(new_temp)   

很簡單通過佇列,先進后出就能實作.這個演算法是沒有問題的,實作也沒有問題,就是這么個暴力計算的話需要算很久才能算出來.接下來這個是經過我優化的.

import copy
def list2str(li):
    s = ""
    for x in li:
        s+=str(x)
    return s
def BFS():
    deq = []
    appear = set()#使用set進行檢索極快,hash檢索
    temp = board()
    appear.add(list2str(temp.groud))
    for x in temp.can_move():
        b = board()
        b.move_one(x)
        b.route.append(x)
        appear.add(list2str(b.groud))
        deq.append(b)
    flag = 0
    while True:
        flag+=1
        temp = deq.pop(0)
        if flag%10000==0:
            flag=0
            temp.show_board() 
            temp.show_route()

        if  temp.guiwei():
            temp.show_board() 
            temp.show_route()
            break
        for x in temp.can_move():
            # 篩選掉重復的棋盤情況,加快搜索速度
            if list2str(temp.test(x)) not in appear:
                new_temp=copy.deepcopy(temp)
                new_temp.move_one(x)
                new_temp.route.append(x)
                deq.append(new_temp)
                appear.add(list2str(new_temp.groud)) 

提高的速度比簡單的BFS提升速度少說幾千倍~比優化過的JAVA版快了幾十倍.優化重點:

• 重復的棋盤就不要入隊了.在移動程序中大概率會出現這種情況,移動了幾步回到了原來的棋盤的情況.我們將出現過的棋盤情況全部記錄下來放在appear,移動后如果是新棋盤就入隊,如果不是就不再入隊進行搜索.
• 由于每次都需要進行appear的檢索,如果單純地使用路徑串列進行檢索的話很慢很慢.我搜索了一下知道一件事情,set()集合的搜索是可以使用哈希值進行搜索的,復雜度為O(1),所以,將路徑轉化為字串(字串才是可哈希的),然后使用字串進行檢索,速度直接起飛~

其它嘗試了的優化,這些優化可能影響不大

• 嘗試過使用cython提高效率,但是不是很明顯
• test函式的出現是因為覺得復制可能比較耗時,所以就使用test函式進行.

說明:JAVA的路徑是指0的位置(設計的不是很優雅,前面兩個4就是0一開始就在4的位置) python的路徑是移動的方向

總結:在BFS中嘗試了很多方法進行速度優化,從演算法層面來講,剪枝應該就是BFS中比較好用的優化方法了,后面的哈希表以及cython個人覺得屬于代碼方面的優化了.不過哈希也是演算法,第一次切身體會到資料結構上的優化帶來的巨大提升.