人工智能实验报告

姓名: 徐国超
班级: 计算机2305
学号:
本报告分别从实验目的与内容、算法设计、核心代码实现、运行结果以及实验结论五个方面展示了两个实验的内容,并在报告最后附上了完整代码。

实验一:状态空间搜索算法编程实现(重排九宫问题)

实验目的与内容

实验中要求通过状态空间搜索算法编程实现一个具体问题,本报告选取经典的重排九宫问题,分别实现盲目搜索算法(BFS)与启发式搜索算法(A*)。并对两种算法在搜索节点数和耗时上的差异进行对比,理解启发式搜索在缩小搜索空间中的作用。

算法设计

核心代码实现

def heuristic(self, state):  
    distance = 0  
    for i, val in enumerate(state):  
        if val == 0: continue  
        target_idx = val - 1  
        curr_row, curr_col = i // 3, i % 3  
        target_row, target_col = target_idx // 3, target_idx % 3  
        distance += abs(curr_row - target_row) + abs(curr_col - target_col)  
    return distance  
  
def solve_astar(self):  
    print("\nA*:")  
    start_time = time.time()  
    initial_h = self.heuristic(self.initial_state)  
    pq = [(initial_h, 0, self.initial_state, [])]  
    visited = {self.initial_state: 0}#记录到达该状态的最小g值  
  
    nodes_explored = 0  
    while pq:  
        f, g, current_state, path = heapq.heappop(pq)  
        nodes_explored += 1  
  
        if current_state == GOAL_STATE:  
            print(f"A*耗时: {time.time() - start_time:.4f}秒, 共搜索节点数: {nodes_explored}")  
            return path  
  
        for next_state, move in self.get_next(current_state):  
            new_g = g + 1  
            if next_state not in visited or new_g < visited[next_state]:  
                visited[next_state] = new_g  
                h = self.heuristic(next_state)  
                heapq.heappush(pq, (new_g + h, new_g, next_state, path + [move]))  
    return None

这段代码实现了基于曼哈顿距离的 A* 启发式搜索算法。其核心在于 heuristic 函数通过计算每个非零数字滑块当前位置与目标位置的行列坐标绝对差之和,为搜索提供了估计代价 h(n),每次优先扩展h(n)更小的节点,这样会使扩展到最优路径上的节点的几率增大。在 solve_astar 执行过程中,算法利用优先队列动态维护评价函数 f(n)=g(n)+h(n) 最小的节点进行扩展,并结合 visited 字典实时记录并更新到达各状态的最小路径代价 g(n),这保证算法能搜寻到最短路径,并尽量避免了对冗余节点的重复探索。

运行结果

file-20251226014722189.png
从图中可以看出,对于相同的重排九宫初始状态,广度优先搜索与 A* 算法均成功找到了步数为 4 的最短解路径。但在搜索效率的对比上,属于盲目搜索的广搜为了得到最优路径共搜索了 26 个节点,而属于启发式搜索的 A* 算法仅搜索了 16 个节点便找到了最优路径,节点搜索量减少了约 38.5%。这一结果直观地证明了启发式搜索在处理复杂状态空间问题时,能够通过收窄搜索范围、降低资源开销,展现出远高于盲目搜索的效率。

实验结论

通过对相同初始状态进行测试,结果表明:

实验二:神经网络分类器编程实现(BP算法)

实验目的与内容

本实验要求手动编程实现人工神经网络中的反向传播算法,即构建一个 BP 神经网络,并解决一个实际分类问题。因此本报告在Kaggle上选取了一个数据集用于本次实验(https://www.kaggle.com/datasets/parulpandey/palmer-archipelago-antarctica-penguin-data)。该数据集是一份来自Palmer Archipelago (Antarctica)的企鹅数据,共有species、culmen_length_mm、culmen_depth_mm、flipper_length_mm、body_mass_g、island和sex共七个变量,本报告实现了通过其余六个变量该企鹅的species进行分类。
file-20251226023847679.png

算法设计

核心代码实现

	def backward(self, X, y, output):  
	    # 反向传播  
	    m = y.shape[0]  
	  
	    # 输出层梯度  
	    dz3 = output  
	    dz3[range(m), y] -= 1  
	    dz3 /= m  
	  
	    # 第二隐藏层梯度  
	    dW3 = np.dot(self.a2.T, dz3)  
	    db3 = np.sum(dz3, axis=0, keepdims=True)  
	    da2 = np.dot(dz3, self.W3.T)  
	  
	    # ReLU梯度  
	    da2[self.z2 <= 0] = 0  
	  
	    # 第一隐藏层梯度  
	    dW2 = np.dot(self.a1.T, da2)  
	    db2 = np.sum(da2, axis=0, keepdims=True)  
	    da1 = np.dot(da2, self.W2.T)  
	    da1[self.z1 <= 0] = 0  
	  
	    # 输入层梯度  
	    dW1 = np.dot(X.T, da1)  
	    db1 = np.sum(da1, axis=0, keepdims=True)  
	  
	    return dW1, db1, dW2, db2, dW3, db3
    
    def update_params(self, grads, learning_rate=0.01):  
	    dW1, db1, dW2, db2, dW3, db3 = grads  
	    self.W1 -= learning_rate * dW1  
	    self.b1 -= learning_rate * db1  
	    self.W2 -= learning_rate * dW2  
	    self.b2 -= learning_rate * db2  
	    self.W3 -= learning_rate * dW3  
	    self.b3 -= learning_rate * db3
	    
for epoch in range(epochs):  
    output = nn.forward(X_train)  
    loss = nn.compute_loss(output, y_train)  
    grads = nn.backward(X_train, y_train, output)  
    nn.update_params(grads, learning_rate=0.02)

这段核心代码主要展现了 BP 神经网络的核心学习机制:反向传播与参数优化。backward 函数基于链式法则,从输出层开始逐层向输入层计算损失函数对各个权重和偏置的梯度,其中包含了对 ReLU 激活函数梯度的处理;随后,update_params 函数利用计算出的梯度,通过梯度下降法按学习率更新网络参数。在主循环中,模型通过不断重复前向预测—计算损失—反向传播—更新权重的迭代过程,使得损失函数逐步减小,从而持续优化网络的分类性能。

运行结果

实验结论

在学习率为 0.01 时,Loss 曲线下降较为平缓,准确率在大约 2200 个 Epoch 后趋于稳定;学习率提升至 0.1 时,模型在 500 个 Epoch 内便实现了损失函数近乎归零,且训练集与测试集的准确率均迅速达到 几乎100%,表明在合理范围内增大学习率能有效缩短训练时间,提高效率。同时,两组实验在测试集上的准确率曲线均能紧跟训练集,未出现明显的过拟合现象,证明了该 BP 神经网络分类器在当前数据集上具有极佳的泛化能力和鲁棒性。

完整代码

lab1:状态空间搜索算法编程实现

import heapq  
from collections import deque  
import time  
  
GOAL_STATE = (1, 2, 3, 8, 0, 4, 7, 6, 5)  
MOVES = {  
    '左': (0, -1), '上': (-1, 0), '右': (0, 1),'下': (1, 0),  
}  
  
  
class Solve:  
    def __init__(self, initial_state):  
        self.initial_state = tuple(initial_state)  
  
    def get_next(self, state):  
        state_list = list(state)  
        idx = state_list.index(0)  
        row, col = idx // 3, idx % 3  
        neighbors = []  
  
        for move_name, (dr, dc) in MOVES.items():  
            new_row, new_col = row + dr, col + dc  
            if 0 <= new_row < 3 and 0 <= new_col < 3:  
                new_idx = new_row * 3 + new_col  
                new_state = list(state_list)  
                new_state[idx], new_state[new_idx] = new_state[new_idx], new_state[idx]  
                neighbors.append((tuple(new_state), move_name))  
        return neighbors  
  
    def print_path(self, path):  
        print(f"解法路径: {' -> '.join(path)}")  
        print(f"总步数: {len(path)}")  
  
    def solve_bfs(self):  
        print("\nBFS:")  
        start_time = time.time()  
        queue = deque([(self.initial_state, [])])  
        visited = set([self.initial_state])  
  
        explored = 0  
        while queue:  
            current_state, path = queue.popleft()  
            explored += 1  
  
            if current_state == GOAL_STATE:  
                print(f"BFS耗时: {time.time() - start_time:.4f}秒, 共搜索节点数: {explored}")  
                return path  
  
            for next_state, move in self.get_next(current_state):  
                if next_state not in visited:  
                    visited.add(next_state)  
                    queue.append((next_state, path + [move]))  
        return None  
  
    def heuristic(self, state):  
        distance = 0  
        for i, val in enumerate(state):  
            if val == 0: continue  
            target_idx = val - 1  
            curr_row, curr_col = i // 3, i % 3  
            target_row, target_col = target_idx // 3, target_idx % 3  
            distance += abs(curr_row - target_row) + abs(curr_col - target_col)  
        return distance  
  
    def solve_astar(self):  
        print("\nA*:")  
        start_time = time.time()  
        initial_h = self.heuristic(self.initial_state)  
        pq = [(initial_h, 0, self.initial_state, [])]  
        visited = {self.initial_state: 0}  # 记录到达该状态的最小g值  
  
        nodes_explored = 0  
        while pq:  
            f, g, current_state, path = heapq.heappop(pq)  
            nodes_explored += 1  
  
            if current_state == GOAL_STATE:  
                print(f"A*耗时: {time.time() - start_time:.4f}秒, 共搜索节点数: {nodes_explored}")  
                return path  
  
            for next_state, move in self.get_next(current_state):  
                new_g = g + 1  
                if next_state not in visited or new_g < visited[next_state]:  
                    visited[next_state] = new_g  
                    h = self.heuristic(next_state)  
                    heapq.heappush(pq, (new_g + h, new_g, next_state, path + [move]))  
        return None  
  
    def is_solvable(self):  
        def get_inversions(state):  
            flat = [x for x in state if x != 0]  
            count = 0  
            for i in range(len(flat)):  
                for j in range(i + 1, len(flat)):  
                    if flat[i] > flat[j]:  
                        count += 1  
            return count % 2  
  
        return get_inversions(self.initial_state) == get_inversions(GOAL_STATE)  
  
if __name__ == "__main__":  
    #初始状态  
    #2 8 3  
    #1 0 4    #7 6 5    start = (2, 8, 3, 1, 0, 4, 7, 6, 5)  
    solver = Solve(start)  
  
    # 检测是否有解  
    if not solver.is_solvable():  
        print("该初始状态无解")  
    else:  
        bfs_path = solver.solve_bfs()  
        if bfs_path: solver.print_path(bfs_path)  
  
        astar_path = solver.solve_astar()  
        if astar_path: solver.print_path(astar_path)

lab2:神经网络分类器编程实现

import numpy as np  
import pandas as pd  
import matplotlib.pyplot as plt  
from sklearn.model_selection import train_test_split  
from sklearn.preprocessing import StandardScaler, LabelEncoder  
  
  
class BP:  
    def __init__(self, input_size, hidden1_size, hidden2_size, output_size):  
        #初始化权重  
        np.random.seed(40)  
        self.W1 = np.random.randn(input_size, hidden1_size) * 0.1  
        self.b1 = np.zeros((1, hidden1_size))  
        self.W2 = np.random.randn(hidden1_size, hidden2_size) * 0.1  
        self.b2 = np.zeros((1, hidden2_size))  
        self.W3 = np.random.randn(hidden2_size, output_size) * 0.1  
        self.b3 = np.zeros((1, output_size))  
  
    def relu(self, x):  
        return np.maximum(0, x)  
  
    def softmax(self, x):  
        exp_x = np.exp(x - np.max(x, axis=1, keepdims=True))  
        return exp_x / np.sum(exp_x, axis=1, keepdims=True)  
  
    def forward(self, X):  
        # 前向传播  
        self.z1 = np.dot(X, self.W1) + self.b1  
        self.a1 = self.relu(self.z1)  
  
        self.z2 = np.dot(self.a1, self.W2) + self.b2  
        self.a2 = self.relu(self.z2)  
  
        self.z3 = np.dot(self.a2, self.W3) + self.b3  
        self.a3 = self.softmax(self.z3)  # 输出概率  
  
        return self.a3  
  
    def compute_loss(self, y_pred, y_true):  
        #交叉熵损失  
        m = y_true.shape[0]  
        log_probs = -np.log(y_pred[range(m), y_true])  
        loss = np.sum(log_probs) / m  
        return loss  
  
    def backward(self, X, y, output):  
        # 反向传播  
        m = y.shape[0]  
  
        # 输出层梯度  
        dz3 = output  
        dz3[range(m), y] -= 1  
        dz3 /= m  
  
        # 第二隐藏层梯度  
        dW3 = np.dot(self.a2.T, dz3)  
        db3 = np.sum(dz3, axis=0, keepdims=True)  
        da2 = np.dot(dz3, self.W3.T)  
  
        # ReLU梯度  
        da2[self.z2 <= 0] = 0  
  
        # 第一隐藏层梯度  
        dW2 = np.dot(self.a1.T, da2)  
        db2 = np.sum(da2, axis=0, keepdims=True)  
        da1 = np.dot(da2, self.W2.T)  
        da1[self.z1 <= 0] = 0  
  
        # 输入层梯度  
        dW1 = np.dot(X.T, da1)  
        db1 = np.sum(da1, axis=0, keepdims=True)  
  
        return dW1, db1, dW2, db2, dW3, db3  
  
    def update_params(self, grads, learning_rate=0.01):  
        dW1, db1, dW2, db2, dW3, db3 = grads  
        self.W1 -= learning_rate * dW1  
        self.b1 -= learning_rate * db1  
        self.W2 -= learning_rate * dW2  
        self.b2 -= learning_rate * db2  
        self.W3 -= learning_rate * dW3  
        self.b3 -= learning_rate * db3  
  
def get_accuracy(X_data, y_true):  
    #前向传播  
    predictions = nn.forward(X_data)  
    pred_labels = np.argmax(predictions, axis=1)  
    accuracy = np.mean(pred_labels == y_true)  
    return accuracy  
  
  
df = pd.read_csv('dataset/penguins_size.csv')  
df = df.ffill()  
le_species = LabelEncoder()  
df['species_encoded'] = le_species.fit_transform(df['species'])  
df['sex'] = df['sex'].map({'MALE': 1, 'FEMALE': 0, 'nan': 0}).fillna(0)  
island_dummies = pd.get_dummies(df['island'], prefix='island')  
df = pd.concat([df, island_dummies], axis=1)  
features = ['culmen_length_mm', 'culmen_depth_mm',  
            'flipper_length_mm', 'body_mass_g', 'sex',  
            'island_Biscoe', 'island_Dream']  
X = df[features].values  
y = df['species_encoded'].values  
scaler = StandardScaler()  
X = scaler.fit_transform(X)  
  
X_train, X_test, y_train, y_test = train_test_split(  
    X, y, test_size=0.2, random_state=42  
)  
  
nn = BP(input_size=7, hidden1_size=16,  
        hidden2_size=8, output_size=3)  
  
history = {'loss': [], 'train_acc': [], 'test_acc': []}  
  
epochs = 4000  
for epoch in range(epochs):  
    # 前向传播  
    output = nn.forward(X_train)  
    loss = nn.compute_loss(output, y_train)  
    grads = nn.backward(X_train, y_train, output)  
    nn.update_params(grads, learning_rate=0.02)  
    history['loss'].append(loss)  
    history['train_acc'].append(get_accuracy(X_train, y_train))  
    history['test_acc'].append(get_accuracy(X_test, y_test))  
  
  
plt.figure(figsize=(12, 5))  
  
plt.subplot(1, 2, 1)  
plt.plot(history['loss'], color='red')  
plt.title('Training Loss')  
plt.xlabel('Epochs')  
  
plt.subplot(1, 2, 2)  
plt.plot(history['train_acc'], label='Train Accuracy')  
plt.plot(history['test_acc'], label='Test Accuracy', linestyle='--')  
plt.title('Accuracy Comparison')  
plt.xlabel('Epochs')  
plt.legend()  
  
plt.tight_layout()  
plt.show()