Bài 4: Nhánh cận

Kỹ thuật nhánh cận thêm vào cho thuật toán quay lui khả năng đánh giá theo từng bước, nếu tại bước thứ i, giá trị x[i] không còn hy vọng tìm thấy cấu hình tốt hơn x[i] thì thử giá trị khác ngay mà không cần đệ quy tiếp và ghi nhận giá trị làm gì. Nghiệm của bài toán sẽ được tốt dần , bởi khi tìm thấy một cấu hình mới ( tốt hơn BESTCONFIG) ta không in kết quả ngay mà tiến hành cập nhật BESTCONFIG bằng cấu hình mới vừa tìm được






Mô hình kỹ thuật nhánh cận:

                   Mo hinh ky thuat nhanh can
                   
procedure Init;
begin
        < Khoi tao mot cau hinh bat ky BESTCONFIG >;
end;

{Thu tuc nay thu chon cho x[i] tat ca cac gia tri}
          {no co the nhan}
          
procedure Attempt ( i: Integer);
begin
       for < Moi gia tri V co the gan cho x[i] > do
          begin
             <Thu cho x[i] := V>;
          if < Viec thu tren van con hy vong >
             < tim thay cau hinh tot hon BESTCONFIG> then
             
             if< x[i] la phan tu cuoi cung trong cau hinh> then
               <Cap nhat BESTCONFIG>
             else
                begin
                  <Ghi nhan viec thu x[i] = V neu can>
                  
                  {Goi de quy, chon tiep x[i+1]}
                  Attempt(i+1); 
                  <Bo ghi nhan viec thu x[i] = V (neu can)>;
                end;
          end;
end;

begin

Init;
Attempt(1);
<thong bao cau hinh toi uu BESTCONFIG>;

end;