//
you're reading...
Bài tập huấn luyện, Dùng cho thi học sinh giỏi

Nội dung huấn luyện: Duyệt nhánh cận

[Một số vấn đề đáng chú ý trong môn Tin học]


Chuyên đề Duyệt nhánh cận – Giới thiệu


Lý thuyết


VN ðỀ: DUYT NHÁNH CN.
Duyt nhánh cn là phương pháp phbiến sdng ðể gii quyết mt slượng ln các bài toán tin, ðặc bit là các bài toán thc tế. Cu trúc ca chương trình duyt nhánh cn ðược mô tsơ lược như sau:

Chn mt nghim ca bài toán làm cn (c).

Thc hin bước duyt thi:
– N
ếu i là bước sau bước cui cùng thì kim tra nghim mi tìm ðược và cp nht cn (c), ghi nhn mt nghim tt hơn ca bài toán.
– Sau b
ước duyt thi, kim tra nghim stìm ðược có khnăng tt hơn cn (c) hay không – gi là ðiu kin nhánh cn. Nếu có gi thc hin bước thi+1. còn không thì quay li bước i-1.

Hai yếu tquan trng ca chương trình là cn (c) khi to ban ðầu và ðiu kin nhánh cn. Vic chn mt cn (c) và ðiu kin kim tra nhánh cn tt sgiúp bước duyt tránh ði vào nhng hướng mà chc chn không tìm ra ðược kết qutt hơn. ðiu có nh nh hưởng trc tiếp ðến ðộ hiu quca chương trình.

Dưới ðây ta xét mt scách kim tra nhánh cn hay dùng thông qua các bài toán cth.


Ví dụ


Bài toán: Chu trình Hamilton nhỏ nhất.

Cho ðồ thị vô hướng G. Mỗi cạnh ðược gán một trọng số nhất ðịnh (lớn hơn 0), tìm một chu trình ði qua tất cả các ðỉnh, mỗi ðỉnh một lần và có tổng trọng số nhỏ nhất.

Gợi ý: Duyệt nhánh cận là phương pháp duy nhất ðể giải quyết bài toán nêu trên.

Chu trình ði qua N ðỉnh sẽ bao gồm N cạnh. Giả sử tại bước thứ i, ðã ði qua k cạnh và còn n-k cạnh nữa cần phải ði qua thì ðiều kiện ðể ði tiếp bước thứ i+1 là s(k) + (n-k)*minc < smin.

Trong ðó:

– s(k) là tổng chi phí của k cạnh ðã ði qua.

– minc là trọng số của cạnh nhỏ nhất trong số các cạnh còn lại chưa ðược ði qua
của ðồ thị.

– smin là tổng trọng số của một chu trình ðã tìm ðược nhưng chưa tối ưu. Có thể
khởi tạo smin ban ðầu là một số vô cùng lớn.


Danh mục bài luyện tập


  1. Bài tập huấn luyện: Xếp ba lô
  2. b
  3. c

About pascalteacher

Trang thông tin Toán học và Tin học

Thảo luận

Chưa có phản hồi.

Gửi phản hồi

Mời bạn điền thông tin vào ô dưới đây hoặc kích vào một biểu tượng để đăng nhập:

WordPress.com Logo

Bạn đang bình luận bằng tài khoản WordPress.com Log Out / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Log Out / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Log Out / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Log Out / Thay đổi )

Connecting to %s

Các tác giả

Danh mục

Tháng Mười Hai 2016
M T W T F S S
« Nov   Jan »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

sunset

Detroit Night

White-winged Scoter | Macreuse à ailes blanches

More Photos

Thống kê

  • 95,281 lượt xem

%d bloggers like this: