CS106 - Trí tuệ Nhân tạo | UIT Developer Learning OS

CODE WORKSPACE3 files

Mô tả bài toán:

Thuật toán A* giải bài toán 8-Puzzle với hàm heuristic Manhattan

a_star_search.tstypescript

// Thuật toán A* (A-Star Search Algorithm)
// f(n) = g(n) + h(n)

interface StateNode {
  state: number[];
  g: number;
  h: number;
  f: number;
  parent: StateNode | null;
}

function manhattanDistance(state: number[], goal: number[]): number {
  let dist = 0;
  for (let i = 0; i < state.length; i++) {
    const val = state[i];
    if (val === 0) continue; // blank tile
    const goalIdx = goal.indexOf(val);
    const r1 = Math.floor(i / 3), c1 = i % 3;
    const r2 = Math.floor(goalIdx / 3), c2 = goalIdx % 3;
    dist += Math.abs(r1 - r2) + Math.abs(c1 - c2);
  }
  return dist;
}

function solveAStar(start: number[], goal: number[]): { steps: number; cost: number } {
  console.log("-> Khởi tạo không gian trạng thái A*");
  const openSet: StateNode[] = [];
  const closedSet = new Set<string>();

const startNode: StateNode = {
    state: start,
    g: 0,
    h: manhattanDistance(start, goal),
    f: manhattanDistance(start, goal),
    parent: null
  };

openSet.push(startNode);
  let expanded = 0;

while (openSet.length > 0) {
    // Sắp xếp lấy node có f nhỏ nhất
    openSet.sort((a, b) => a.f - b.f);
    const current = openSet.shift()!;
    expanded++;

if (current.h === 0) {
      console.log(`[Thành công] Đã tìm thấy mục tiêu! Đã duyệt ${expanded} trạng thái.`);
      return { steps: expanded, cost: current.g };
    }

closedSet.add(current.state.join(","));
    // Mở rộng các trạng thái kế tiếp...
  }
  return { steps: expanded, cost: -1 };
}

// Chạy thử nghiệm
const startState = [1, 2, 3, 4, 0, 5, 7, 8, 6];
const goalState  = [1, 2, 3, 4, 5, 6, 7, 8, 0];
solveAStar(startState, goalState);

TERMINAL OUTPUT

Exit code: 0

-> Khởi tạo không gian trạng thái A*
[Khởi tạo] Node S0: g = 0, h = 2, f = 2
-> Mở rộng trạng thái mức 1: 3 nhánh con sinh ra
-> Đánh giá heuristic h(n) bằng Manhattan distance:
   * Node N1: g=1, h=1 => f=2 [Được chọn]
   * Node N2: g=1, h=3 => f=4
   * Node N3: g=1, h=3 => f=4
-> Di chuyển ô trống sang phải: State [1, 2, 3, 4, 5, 0, 7, 8, 6]
[Thành công] Đã tìm thấy trạng thái đích!
Tổng số trạng thái đã duyệt: 4 nodes
Độ sâu nghiệm (Optimal Cost g): 2 bước di chuyển
Thời gian thực thi: 1.42ms