如何用Python實現(xiàn)八數(shù)碼問題

更新時間：2023年10月28日 14:32:54 作者：jinzhou742

這篇文章主要給大家介紹了關(guān)于如何用Python實現(xiàn)八數(shù)碼問題的相關(guān)資料,八數(shù)碼問題是一種經(jīng)典的搜索問題,它的目標是將一個亂序的八數(shù)碼序列變成一個有序的八數(shù)碼序列,通常使用 A* 算法來解決,需要的朋友可以參考下

1. 題目介紹

八數(shù)碼問題描述為：在 3×3 組成的九宮格棋盤上，擺有 8 張牌，每張牌都刻有 1-8 中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某張牌向空格移動，這樣通過移動牌就可以不斷改變棋盤布局。這種游戲求解的問題是：給定一種初始的棋盤布局或結(jié)構(gòu)（初始狀態(tài)）和一個目標的布局（稱目標狀態(tài)），問如何移動牌，實現(xiàn)從初始狀態(tài)到目標狀態(tài)的轉(zhuǎn)變。

例如如下的棋盤要求將初始狀態(tài)移動到目標狀態(tài)：

傳統(tǒng)的解題方法包含深度優(yōu)先搜索和廣度優(yōu)先搜索。但這會帶來一個問題，即搜索是盲目的，沒有根據(jù)當前棋盤的布局來動態(tài)地調(diào)整下一步搜索的策略。為此我們定義了啟發(fā)式搜索算法（A* 算法），它會提取出當前棋盤的一些特征，來最優(yōu)地選擇下一次要搜索的方向。

對于八數(shù)碼問題，其啟發(fā)式方法為當前棋盤與目標棋盤的差異度，而差異度又可以通過兩種方法來進行計算。

記當前棋盤為 source，目標棋盤為 target。第一種計算方法為：如果 source[i][j] != target[i][j]，則差異度 += 1；第二種計算方法為：如果 source[i][j] == target[m][n]，則差異度 += (abs(m - i) + abs(n - j))。

例如，對于上面的初始狀態(tài)和目標狀態(tài)，使用第一種計算方法，其差異度矩陣為（1 表示該位置兩狀態(tài)矩陣的元素不同，0 表示相同）：

最終可以計算出兩個矩陣的差異度為 4。

使用第二種計算方法，其差異度矩陣為（值表示 source[i][j] 的元素移動到目標位置所需的最短步數(shù)）：

最終可以計算出兩個矩陣的差異度為 5。

不管使用哪種辦法，都能得出一個差異度，暫且記為 g。并且，解題的辦法要么采用 DFS，要么采用 BFS，兩種辦法的搜索時間都會隨著深度的增加而增加，我們的目標是盡量減少搜索的時間，也就是要想辦法減少搜索深度。為了解決這個問題，記當前的搜索深度為 d，那么 d 越小越好。同時，我們又希望 g 越小越好，所以我們整體的目標就可以轉(zhuǎn)化為 d + g 越小越好，這綜合了 d 和 g 各自有的優(yōu)勢，是一個良好的 tradeoff。

因此，我們的整體目標也就轉(zhuǎn)化成了：在 DFS 或 BFS 的函數(shù)中，對每一個狀態(tài)都計算 f = d + g，選取 f 最小的那個結(jié)點，讓它作為下次迭代的首選結(jié)點。

2. 代碼演示

下面使用三種方式來評估啟發(fā)式算法的性能，第一種是不使用啟發(fā)式算法，第二種是使用前文提到的策略 1，第三種是使用前文提到的策略 2。

2.1 不使用啟發(fā)式算法

在代碼中，將變量 use_A_star 設(shè)定為 False 即指定不使用啟發(fā)式算法，運行結(jié)果為：

運行 50 次求得所耗平均時間為：0.022931413650512697 s

2.2 使用啟發(fā)式策略 1

在代碼中，將變量 use_A_star 設(shè)定為 True，strategy 設(shè)定為 1，即指定使用啟發(fā)式算法 1，運行結(jié)果為：

運行 50 次求得所耗平均時間為：0.0021903276443481444 s

2.3 使用啟發(fā)式策略 2

在代碼中，將變量 use_A_star 設(shè)定為 True，strategy 設(shè)定為 2，即指定使用啟發(fā)式算法 2，運行結(jié)果為：

運行 50 次求得所耗平均時間為：0.002417140007019043 s

3. 結(jié)論分析

從三種方法的運行結(jié)果可以得出下列結(jié)論：使用啟發(fā)式算法可以大幅度節(jié)省程序運行時間（是純 BFS 的 1/10），啟發(fā)式算法 1 比啟發(fā)式算法 2 效率更高，這可能是因為算法 1 在計算矩陣差異度時只需要遍歷一遍矩陣，而算法 2 需要遍歷兩遍矩陣。

4. 源碼

import numpy as np
import time

class Node(object):
    def __init__(self, source, target, strategy, cost=0, depth=0):
        self.directions = ['left', 'up', 'right', 'down']
        self.source = source
        self.target = target
        self.cost = cost
        self.depth = depth
        self.strategy = strategy

    # 打印原始矩陣
    def print_source(self):
        for i in range(3):
            [print(self.source[i][j], end=' ') for j in range(3)]
            print()
        print()

    # 計算不在位的棋子個數(shù)
    def num_misposition(self):
        # 比較source和target，不同的地方標記為1，相同的地方標記為0
        flag = np.where(self.source == self.target, 0, 1)
        # 返回source與target之間不相同的數(shù)的個數(shù)
        return np.sum(np.reshape(flag, (flag.size,)))

    # 計算耗散值
    def get_cost(self):
        if self.strategy == 1:
            return self.depth + self.num_misposition()
        elif self.strategy == 2:
            flag = np.where(self.source == self.target, 0, 1)
            sum_cost = 0
            for i in range(3):
                for j in range(3):
                    if flag[i][j]:
                        for m in range(3):
                            for n in range(3):
                                if self.target[m][n] == self.source[i][j]:
                                    dif_row, dif_col = abs(m - i), abs(n - j)
                                    sum_cost += (dif_row + dif_col)
            return sum_cost

    # 將棋子0分別往四個方向移動
    def move(self):
        # 記錄棋子0所在的行號和列號
        row, col = np.where(self.source == 0)
        row, col = row[0], col[0]
        moved_nodes = []
        for direction in self.directions:
            if direction == 'left' and col > 0:
                source_copy = self.source.copy()
                source_copy[row, col], source_copy[row, col - 1] = source_copy[row, col - 1], source_copy[row, col]
                moved_nodes.append(
                    Node(source_copy, target=self.target, cost=self.get_cost(), depth=self.depth + 1, strategy=self.strategy))
            elif direction == 'up' and row > 0:
                source_copy = self.source.copy()
                source_copy[row, col], source_copy[row - 1, col] = source_copy[row - 1, col], source_copy[row, col]
                moved_nodes.append(
                    Node(source_copy, target=self.target, cost=self.get_cost(), depth=self.depth + 1, strategy=self.strategy))
            elif direction == 'right' and col < len(self.source) - 1:
                source_copy = self.source.copy()
                source_copy[row, col], source_copy[row, col + 1] = source_copy[row, col + 1], source_copy[row, col]
                moved_nodes.append(
                    Node(source_copy, target=self.target, cost=self.get_cost(), depth=self.depth + 1, strategy=self.strategy))
            elif direction == 'down' and row < len(self.source) - 1:
                source_copy = self.source.copy()
                source_copy[row, col], source_copy[row + 1, col] = source_copy[row + 1, col], source_copy[row, col]
                moved_nodes.append(
                    Node(source_copy, target=self.target, cost=self.get_cost(), depth=self.depth + 1, strategy=self.strategy))
        return moved_nodes

class EightPuzzle(object):
    def __init__(self, init_node, use_A_star, strategy):
        self.use_A_star = use_A_star
        self.queue = []
        self.closed_nodes = []
        self.count = 0
        self.init_node = init_node
        self.time_start = 0
        self.time_end = 0
        self.strategy = strategy

    # 判斷傳入的結(jié)點是否在self.closed_nodes中
    def is_in_closed_nodes(self, node):
        for closed_node in self.closed_nodes:
            # 比較closed_node和node，不同的地方標記為1，相同的地方標記為0
            flag = np.where(closed_node.source == node.source, 0, 1)
            if np.sum(np.reshape(flag, (flag.size,))) == 0:
                return True
        return False
    
    # 獲取最小耗散值的那個結(jié)點
    def get_min_cost_index(self):
        min_cost = self.queue[0].cost
        index = 0
        for i in range(len(self.queue)):
            if self.queue[i].cost < min_cost:
                index = i
                min_cost = self.queue[i].cost
        return index

    # bfs求解問題
    def bfs(self):
        self.time_start = time.time()
        self.queue.append(self.init_node)
        min_cost = self.init_node.cost
        while self.queue:
            if self.use_A_star:
                current_node_index = self.get_min_cost_index()
                current_node = self.queue.pop(current_node_index)
            else:
                current_node = self.queue.pop(0)
            self.closed_nodes.append(current_node)
            # 不在位棋子個數(shù)為0，到達終點
            if current_node.num_misposition() == 0:
                self.time_end = time.time()
                return True, self.time_end - self.time_start, current_node
            moved_nodes = current_node.move()
            for next_node in moved_nodes:
                if self.is_in_closed_nodes(next_node):
                    continue
                self.queue.append(next_node)
            self.count += 1
        self.time_end = time.time()
        return False, self.time_end - self.time_start, None

def main():
    source = np.array([[2, 8, 3], [1, 6, 4], [7, 0, 5]])
    target = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
    print('The source matrix is:\n', source)
    print('The target matrix is:\n', target)
    use_A_star = True
    strategy = 2
    init_node = Node(source, target, strategy, cost=0)

    solution = EightPuzzle(init_node, use_A_star, strategy)
    has_solved, time_used, result_node = solution.bfs()

    if has_solved:
        print('\nThis problem has been solved, using', time_used, 's.')
        print('The result matrix is:')
        result_node.print_source()
        
    return time_used

if __name__ == '__main__':
    main()