//
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
Advertisements

About pascalteacher

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

Thảo luận

Không có bình luận

Trả lờ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 Đăng xuất / Thay đổi )

Twitter picture

Bạn đang bình luận bằng tài khoản Twitter Đăng xuất / Thay đổi )

Facebook photo

Bạn đang bình luận bằng tài khoản Facebook Đăng xuất / Thay đổi )

Google+ photo

Bạn đang bình luận bằng tài khoản Google+ Đăng xuất / Thay đổi )

Connecting to %s

Các tác giả

Categories

Tháng Mười Hai 2016
H B T N S B C
« Th11   Th1 »
 1234
567891011
12131415161718
19202122232425
262728293031  

NCT Computer

Flickr Photos

Thống kê

  • 148,992 lượt xem

pascalteacher.nct@gmail.com


Trang huấn luyện học sinh giỏi Tin học

%d bloggers like this: