CỔNG ÔN TẬP THI & PHẦN MỀM MÔ PHỎNG GIẢI THUẬT AI

from collections import deque

graph = {
    'S': ['A', 'B'],
    'A': ['C', 'D'],
    'B': ['D'],
    'C': ['G'],
    'D': ['G'],
    'G': []
}

# BFS: Hàng đợi FIFO (Queue)
def bfs(graph, start, goal):
    queue = deque([[start]])
    visited = set()
    explored = []

    while queue:
        path = queue.popleft()
        node = path[-1]
        if node not in visited:
            visited.add(node)
            explored.append(node)
            if node == goal:
                return explored, path
            for neighbor in graph.get(node, []):
                if neighbor not in visited:
                    queue.append(path + [neighbor])
    return explored, None

# DFS: Ngăn xếp LIFO (Stack)
def dfs(graph, start, goal):
    stack = [[start]]
    visited = set()
    explored = []

    while stack:
        path = stack.pop()
        node = path[-1]
        if node not in visited:
            visited.add(node)
            explored.append(node)
            if node == goal:
                return explored, path
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(path + [neighbor])
    return explored, None

# IDS: Iterative Deepening Search
def dls(graph, node, goal, depth, path):
    if depth == 0 and node == goal:
        return path
    if depth > 0:
        for neighbor in graph.get(node, []):
            if neighbor not in path:
                res = dls(graph, neighbor, goal, depth - 1, path + [neighbor])
                if res: return res
    return None

def ids(graph, start, goal, max_depth=10):
    for d in range(max_depth):
        found = dls(graph, start, goal, d, [start])
        if found: return found, d
    return None, -1

print("BFS Path:", bfs(graph, 'S', 'G')[1])
print("DFS Path:", dfs(graph, 'S', 'G')[1])
print("IDS Path:", ids(graph, 'S', 'G')[0])

import heapq

graph = {
    'S': {'A': 4, 'B': 2},
    'A': {'C': 5, 'D': 12},
    'B': {'A': 1, 'D': 7},
    'C': {'G': 16},
    'D': {'G': 3},
    'G': {}
}

heuristics = {'S': 10, 'A': 7, 'B': 8, 'C': 12, 'D': 3, 'G': 0}

def a_star(graph, heuristics, start, goal):
    # pq: (f_score, g_cost, [path])
    pq = []
    heapq.heappush(pq, (heuristics[start], 0, [start]))
    visited_cost = {}

    while pq:
        f, g, path = heapq.heappop(pq)
        current = path[-1]

        if current == goal:
            return path, g

        if current in visited_cost and visited_cost[current] <= g:
            continue
        visited_cost[current] = g

        for neighbor, weight in graph.get(current, {}).items():
            new_g = g + weight
            new_f = new_g + heuristics.get(neighbor, 0)
            heapq.heappush(pq, (new_f, new_g, path + [neighbor]))

    return None, float('inf')

path, cost = a_star(graph, heuristics, 'S', 'G')
print(f"A* Path: {' -> '.join(path)} | Optimal Cost = {cost}")

import math

def alpha_beta_pruning(depth, node_index, is_max, values, alpha, beta, path="Root"):
    # Nếu đến tầng lá
    if depth == 3:
        return values[node_index]

    if is_max:
        max_eval = -math.inf
        for i in range(2):
            val = alpha_beta_pruning(depth + 1, node_index * 2 + i, False, values, alpha, beta, path + f"->{i}")
            max_eval = max(max_eval, val)
            alpha = max(alpha, val)
            if beta <= alpha:
                print(f"[CẮT NHÁNH BETA] Tại độ sâu {depth}: alpha={alpha} >= beta={beta}. Bỏ qua nhánh còn lại!")
                break
        return max_eval
    else:
        min_eval = math.inf
        for i in range(2):
            val = alpha_beta_pruning(depth + 1, node_index * 2 + i, True, values, alpha, beta, path + f"->{i}")
            min_eval = min(min_eval, val)
            beta = min(beta, val)
            if beta <= alpha:
                print(f"[CẮT NHÁNH ALPHA] Tại độ sâu {depth}: alpha={alpha} >= beta={beta}. Bỏ qua nhánh còn lại!")
                break
        return min_eval

leaves = [3, 5, 6, 9, 1, 2, 0, -1]
root_val = alpha_beta_pruning(0, 0, True, leaves, -math.inf, math.inf)
print(f"Giá trị tối ưu tại nút gốc MAX = {root_val}")