Thuật toán quay lui trong Pascal

Thuật toán quay lui (backtracking) là một kỹ thuật giải quyết các bài toán liên quan đến tìm kiếm tất cả các giải pháp có thể của một bài toán. Thường được sử dụng trong các bài toán về tối ưu hoặc những bài toán có thể phân loại bằng cách duyệt toàn bộ tập hợp các giải pháp có thể.

Dưới đây là một ví dụ về thuật toán quay lui trong Pascal để tìm kiếm tất cả các cách sắp xếp một tập hợp gồm n phần tử:

program Backtracking;
const
  n=3; { số phần tử cần sắp xếp }
var
  a: array[1..n] of integer;
  b: array[1..n] of boolean;
procedure Try(i: integer);
var
  j: integer;
begin
  for j:=1 to n do
    if not b[j] then
    begin
      a[i]:=j;
      b[j]:=true;
      if i=n then
      begin
        { in ra cách sắp xếp }
        for j:=1 to n do write(a[j],' ');
        writeln;
      end
      else Try(i+1);
      b[j]:=false;
    end;
end;
begin
  Try(1);
end.

Trong ví dụ trên, chúng ta duyệt tất cả các cách sắp xếp có thể của tập hợp gồm n phần tử. Tuy nhiên, trong một số bài toán, chúng ta có thể thực hiện một số kiểm tra để cắt tỉa những nhánh không cần thiết của cây tìm kiếm, giúp tăng tốc độ thực hiện thuật toán. Chẳng hạn, trong bài toán TSP (Traveling Salesman Problem), chúng ta có thể kiểm tra số lượng các đỉnh đã duyệt, nếu đã duyệt tất cả các đỉnh nhưng đường đi hiện tại chưa tối ưu hơn đường đi tốt nhất đã tìm được, chúng ta có thể dừng quá trình duyệt tại nhánh hiện tại.

Ngoài ra, thuật toán quay lui còn được áp dụng trong nhiều lĩnh vực khác nhau như: tìm kiếm từ điển, xếp hình, giải Sudoku, giải cờ vua, … Tuy nhiên, việc sử dụng thuật toán quay lui đòi hỏi phải tìm ra được phương pháp cắt tỉa phù hợp để giảm thiểu số lượng trường hợp phải duyệt.

Dưới đây là một ví dụ cụ thể về thuật toán quay lui để giải bài toán Sudoku. Bài toán này yêu cầu điền các số từ 1 đến 9 vào các ô trống trên một bảng 9×9 sao cho mỗi hàng, mỗi cột và mỗi khối 3×3 đều chứa đủ các số từ 1 đến 9.

program SudokuSolver;

const
  N = 9;

type
  TBoard = array[1..N, 1..N] of Integer;

var
  Board: TBoard;

function IsValid(Board: TBoard; Row, Col, Num: Integer): Boolean;
var
  i, j, Row0, Col0: Integer;
begin
  { kiểm tra hàng và cột }
  for i := 1 to N do
    if (Board[Row, i] = Num) or (Board[i, Col] = Num) then
      Exit(False);
  { kiểm tra khối 3x3 }
  Row0 := 3 * ((Row - 1) div 3) + 1;
  Col0 := 3 * ((Col - 1) div 3) + 1;
  for i := Row0 to Row0 + 2 do
    for j := Col0 to Col0 + 2 do
      if Board[i, j] = Num then
        Exit(False);
  Result := True;
end;

procedure PrintBoard(Board: TBoard);
var
  i, j: Integer;
begin
  for i := 1 to N do
  begin
    for j := 1 to N do
      Write(Board[i, j], ' ');
    Writeln;
  end;
end;

procedure SolveSudoku(Board: TBoard; Row, Col: Integer; var Found: Boolean);
var
  i, j, Num: Integer;
begin
  if Row > N then
  begin
    { tìm được một giải pháp }
    PrintBoard(Board);
    Found := True;
    Exit;
  end;
  if Board[Row, Col] <> 0 then
  begin
    { ô này đã được điền số }
    if Col = N then
      SolveSudoku(Board, Row + 1, 1, Found)
    else
      SolveSudoku(Board, Row, Col + 1, Found);
    Exit;
  end;
  { duyệt các số từ 1 đến 9 }
  for Num := 1 to N do
  begin
    if IsValid(Board, Row, Col, Num) then
    begin
      Board[Row, Col] := Num;
      if Col = N then
        SolveSudoku(Board, Row + 1, 1, Found)
      else
        SolveSudoku(Board, Row, Col + 1, Found);
      if Found then
        Exit;
      Board[Row, Col] := 0;
    end;
  end;
end;

begin
  { đọc bảng Sudoku từ file }
  { ... }
  { giải bài toán }
  SolveSudoku(Board, 1, 1, Found);
end.

Lập trình Pascal

Thuật toán quay lui trong Pascal

Trả lời Hủy