實驗3 知識表示與推理

一、實驗目的
（1）掌握知識和知識表示的基本概念，理解其在AI中的深刻含義與意義；
（2）熟悉AI中常用的知識表示方法的優缺點及其應用場景；
（3）掌握產生式系統知識表示的方法及其構成要素；
（4）掌握狀態空間法的基本構成及其特點，能用其表示實際AI問題；
（5）深入理解圖的深度、寬度搜索方法，并能應用于實際問題；
（6）根據自身情況，能選擇合適的編程語言，解決實際AI問題。
二、實驗內容
借助產生式系統和狀態空間法，選擇一種編程語言（最好為python或java），完成題目要求。
1、八數碼難題
在3×3的棋盤上，擺有八個棋子，每個棋子上標有1至8的某一數字。棋盤中留有一個空格，空格可用0來表示。空格周圍的棋子可以移到空格中。要求解的問題是：給出一種初始布局（初始狀態）和目標布局，找到一種移動方法，實現從初始布局到目標布局的轉變。

1.需求分析
在一個3×3的棋盤格中，擺有1-8數字的八個棋子，剩余的空格用0表示。給出一種初始布局和目標布局，找到一種移動方法，實現從初始布局到目標布局的轉變，規則是移動空格，并且空格不能移出棋盤外。

2.數據結構、功能模塊設計與說明
采用廣度優先搜索算法，從初始狀態開始，每次進行可行操作（與0所在位置相鄰數字交換），得到新的狀態，并將其加入隊列中，直到找到目標狀態為止。

在搜索之前需要判斷一下目標狀態是否可達，根據八數碼問題的特性，合法的移動操作只涉及兩個數字的交換，空格左右移動不會改變任何兩對數字之間的逆序對數量，因為整個序列的相對順序保持不變。空格上下移動會改變兩對數字之間的逆序對數量。當初始狀態的空白格和目標狀態的空白格在不同行時，只有通過上下移動才有可能改變逆序對的數量，從而實現初始狀態到目標狀態的轉換。故當初始狀態和結果狀態逆序數奇偶性相同的時候才可達，否則不進行搜索。

當目標狀態可達的時候，又因為有很多狀態會重復出現，所以判斷移動之后的狀態是否出現過？這里用哈希表來去重，如果出現過則丟棄；否則，將它加入隊列，并將它對應的步數設為前一個狀態的步數+1，直到找到目標狀態為止。

3.核心代碼與測試結果說明

# 在 A* 算法 中的一個節點。代表了搜索空間中的一個狀態
class Node:def __init__(self, state, parent=None, move=0, depth=0):self.state = stateself.parent = parentself.move = moveself.depth = depthself.cost = 0  # g(n) + h(n)def __lt__(self, other):return self.cost < other.cost# A* 算法
# 結合實際成本（g(n)）和估計成本（h(n)）來選擇最有希望的路徑
# g(n) 是從起始節點到當前節點的移動次數（或稱為深度），
# 而 h(n) 是當前狀態與目標狀態之間的曼哈頓距離
def a_star(initial, goal):open_list = []closed_set = set()root = Node(initial)heapq.heappush(open_list, (manhattan_distance(initial, goal), root))while open_list:_, current = heapq.heappop(open_list)closed_set.add(tuple(current.state))if current.state == goal:path = []while current:path.append(current.state)current = current.parentreturn path[::-1]zero_pos = current.state.index(0)x, y = divmod(zero_pos, 3)moves = [(-1, 0), (1, 0), (0, -1), (0, 1)]for dx, dy in moves:new_x, new_y = x + dx, y + dyif 0 <= new_x < 3 and 0 <= new_y < 3:new_state = current.state[:]new_pos = new_x * 3 + new_ynew_state[zero_pos], new_state[new_pos] = new_state[new_pos], new_state[zero_pos]if tuple(new_state) not in closed_set:new_node = Node(new_state, current, move=current.move + 1, depth=current.depth + 1)new_node.cost = new_node.depth + manhattan_distance(new_state, goal)heapq.heappush(open_list, (new_node.cost, new_node))return None

結果：

4.存在的問題與體會
4.1 存在的問題
這種解法空間復雜度較高。使用廣度優先搜索算法時，需要存儲所有的狀態和路徑信息。通過哈希表來存儲狀態路徑信息，可能會占用較大內存空間，特別是當搜索空間非常龐大時。所以可以考慮使用其他數據結構或優化算法，以減少空間復雜度。

4.2 體會
雖然代碼存在一些問題和可以改進的地方，但我深入理解了廣度優先搜索算法，并在實踐中獲得了關于數據結構和代碼設計的經驗。

2、設有3個傳教士和3個野人來到河邊，打算乘一只船從右岸渡到左岸去。該船每一次只能裝載2人。在任何時候，如果野人人數超過傳教士人數，那么野人就會把傳教士吃掉。請你設計一個方案怎樣才能用這條船安全地把所有人都渡過河去？編程實現你的方案。

1.需求分析
有3個傳教士和3個野人從河右岸乘一只船到左岸，且該船每次只能裝載2人。必須保證在任何時候，野人人數不能超過傳教士人數，否則野人就會把傳教士吃掉。設計一個方案怎樣才能用這條船安全地把所有人都渡過河去？并且推廣到有n個傳教士和n個野人，河邊的船每次至多可供k個人渡河的解決方案。

2.數據結構、功能模塊設計與說明
使用深度優先搜索算法，尋找所有可能的移動方案。其中，每個狀態包括左岸傳教士和野人的數量，以及船的位置（左岸或右岸）。通過不斷嘗試不同的移動方案，最終找到一種能夠使所有人都安全到達右岸的方法。

3.核心代碼：

# 檢查一組傳教士和野人的數量是否符合規則
def is_valid_state(left_missionaries, left_cannibals):if left_missionaries < 0 or left_cannibals < 0:return Falseif (3 - left_missionaries) < 0 or (3 - left_cannibals) < 0:return Falseif (left_missionaries > 0 and left_cannibals > left_missionaries) or ((3 - left_missionaries) > 0 and (3 - left_cannibals) > (3 - left_missionaries)):return False
return True# 接收一個狀態state作為輸入，并返回可能的下一個狀態列表
def next_states(state):left_missionaries, left_cannibals, right_missionaries, right_cannibals, boat_position = statenext_states_list = []if boat_position == 'left':for i in range(3):for j in range(3):if i + j > 0 and i + j <= 2:new_left_missionaries = left_missionaries - inew_left_cannibals = left_cannibals - jnew_right_missionaries = right_missionaries + inew_right_cannibals = right_cannibals + jif is_valid_state(new_left_missionaries, new_left_cannibals):def bfs():initial_state = (3, 3, 0, 0, 'left')goal_state = (0, 0, 3, 3, 'right')visited = set()queue = deque([(initial_state, [])])while queue:state, path = queue.popleft()if state == goal_state:return path + [state]if state not in visited:visited.add(state)for next_state in next_states(state):queue.append((next_state, path + [state]))
return None

結果：