bài giảng các chuyên đề phần 2

Tham khảo tài liệu bài giảng các chuyên đề phần 2, công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả
Nội dung trích xuất từ tài liệu:
bài giảng các chuyên đề phần 2Bài toán liệt kê 24 TOURISM.INP TOURISM.OUT 46 1->3->2->4->1 123 Cost: 6 132 3 1 2 2 141 231 242 2 1 1 344 4 3 4 PROG04_1.PAS * Kỹ thuật nhánh cận dùng cho bài toán người du lịchprogram TravellingSalesman;const max = 20; {+∞} maxC = 20 * 100 + 1;var {Ma trận chi phí} C: array[1..max, 1..max] of Integer; X, BestWay: array[1..max + 1] of Integer; {X để thử các khả năng, BestWay để ghi nhận nghiệm} {Ti để lưu chi phí đi từ X1 đến Xi} T: array[1..max + 1] of Integer; {Free để đánh dấu, Freei= True nếu chưa đi qua tp i} Free: array[1..max] of Boolean; m, n: Integer; {Chi phí hành trình tối ưu} MinSpending: Integer;procedure Enter;var i, j, k: Integer;begin ReadLn(n, m); {Khởi tạo bảng chi phí ban đầu} for i := 1 to n do for j := 1 to n do if i = j then C[i, j] := 0 else C[i, j] := maxC; for k := 1 to m do begin ReadLn(i, j, C[i, j]); {Chi phí như nhau trên 2 chiều} C[j, i] := C[i, j]; end;end;procedure Init; {Khởi tạo}begin FillChar(Free, n, True); {Các thành phố là chưa đi qua ngoại trừ thành phố 1} Free[1] := False; {Xuất phát từ thành phố 1} X[1] := 1; {Chi phí tại thành phố xuất phát là 0} T[1] := 0; MinSpending := maxC;end;procedure Try(i: Integer); {Thử các cách chọn xi}var j: Integer;begin {Thử các thành phố từ 2 đến n} for j := 2 to n do {Nếu gặp thành phố chưa đi qua} if Free[j] then―― begin {Thử đi} X[i] := j; {Chi phí := Chi phí bước trước + chi phí đường đi trực tiếp} T[i] := T[i - 1] + C[x[i - 1], j]; {Hiển nhiên nếu có điều này thì C[x[i - 1], j] < +∞ rồi} if T[i] < MinSpending then if i < n then―{Nếu chưa đến được xn}―――――――― beginLê Minh HoàngBài toán liệt kê 25 Free[j] := False;― {Đánh dấu thành phố vừa thử} {Tìm các khả năng chọn xi+1}―――――――― Try(i + 1); Free[j] := True;― {Bỏ đánh dấu}―――――――――――――― end else if T[n] + C[x[n], 1] < MinSpending then {Từ xn quay lại 1 vẫn tốn chi phí ít hơn trước} begin {Cập nhật BestConfig}―――― BestWay := X; MinSpending := T[n] + C[x[n], 1]; end; end;end;procedure PrintResult;var i: Integer;begin if MinSpending = maxC then WriteLn(NO SOLUTION) else for i := 1 to n do Write(BestWay[i], ->); WriteLn(1); WriteLn(Cost: , MinSpending);end;begin Assign(Input, TOURISM.INP); Reset(Input); Assign(Output, TOURISM.OUT); Rewrite(Output); Enter; Init; Try(2); PrintResult; Close(Input); Close(Output);end.Trên đây là một giải pháp nhánh cận còn rất thô sơ giải bài toán người du lịch, trên thực tế người tacòn có nhiều cách đánh giá nhánh cận chặt hơn nữa. Hãy tham khảo các tài liệu khác để tìm hiểu vềnhững phương pháp đó.V. DÃY ABCCho trước một số nguyên dương N (N ≤ 100), hãy tìm một xâu chỉ gồm các ký tự A, B, C thoả mãn3 điều kiện: • Có độ dài N • Hai đoạn con bất kỳ liền nhau đều khác nhau (đoạn con là một dãy ký tự liên tiếp của xâu) • Có ít ký tự C nhất.Cách giải:Không trình bày, đề nghị tự xem chương trình để hiểu, chỉ chú thích kỹ thuật nhánh cận như sau:Nếu dãy X1X2...Xn thoả mãn 2 đoạn con bất kỳ liền nhau đều khác nhau, thì trong 4 ký tự liên tiếpbất kỳ bao giờ cũng phải có 1 ký tự C. Như vậy với một dãy con gồm k ký tự liên ti ...