Link tải luận văn miễn phí cho ae Kết Nối
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
LỜI NÓI ĐẦU
Bài toán tìm kiếm được xem là bài toán được nhiều người quan tâm, đặc
biệt là tìm kiếm tối ưu toàn cục. Có nhiều phương pháp để giải các bài toán tìm
kiếm tối ưu toàn cục như : phương pháp trực tiếp (áp dụng các công thức, định lý,
thuật giải đã có sẵn ), các phương pháp gián tiếp hay tìm kiếm lời giải thông dụng
(phương pháp thử sai, phương pháp vét cạn, phương pháp quay lui). Ngoài các
phương pháp nêu trên thì trong học phần “ Thuật toán và phương pháp giải quyết
vấn đề em còn được tiếp cận với các phương pháp hueristic và meta hueristic.
Và sau đây là bài thu hoạch của em : “Tìm hiểu về hueristic -
metahueristic - Giải pháp hueristic theo nguyên lý tham lam giải bài toán người
đưa thư ”.
Em xin gửi lời Thank chân thành đến trường Đại học Công Nghệ Thông
Tin TP.HCM đã tạo điều kiện cho em được tiếp cận với môn học “Thuật toán và
phương pháp giải quyết vấn đề ”
Em xin Thank Thầy PGS.TS. Đỗ Văn Nhơn đã tận tình truyền đạt kiến
thức và có những định hướng giúp em hoàn thành bài thu hoạch.
Mặc dù đã rất cố gắng nhưng bài thu hoạch của em khó tránh khỏi thiếu
sót em mong Thầy góp ý nhận xét để bài thu hoạch hoàn thiện hơn.
SVTH : CH1301074 – Nguyễn Hải Yến 2
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
MỤC LỤC
LỜI NÓI ĐẦU 2
Chương 1 4
TÌM HIỂU VỀ HUERISTIC VÀ META HUERISTIC TRONG GIẢI
QUYẾT VẤN ĐỀ NP 4
Xác suất lai ghép cho biết tính thường xuyên của việc lai ghép tạo ra thế hệ mới
được thực hiện như thế nào. Nếu xác suất lai ghép là pc , khi đó khả năng để một cá
thể được lai ghép là pc. Nếu không thực hiện lai ghép, con sinh ra sẽ giống hoàn
toàn bố mẹ. Nếu được lai ghép, con sinh ra sẽ có một phần giống bố và một phần
giống mẹ 15
Xác suất đột biến cho biết tính thường xuyên của việc các gen của NST thay đổi
như thế nào. Nếu xác suất đột biến là pm, khi đó khả năng để mỗi gen của một NST
bất kỳ bị đột biến là pm. Tác dụng của toán tử đột biến là ngăn ngừa giải thuật di
truyền rơi vào tình trạng cực trị địa phương, tuy nhiên nếu thực hiện đột biến với xác
suất quá cao sẽ biến giải thuật di truyền thành giải thuật tìm kiếm ngẫu nhiên 15
LocalSearch() là hàm tìm kiếm địa phương, giúp tìm ra tối ưu cục bộ 22
22
Sơ đồ thuật toán bầy kiến 22
Chương 2: 23
ỨNG DỤNG HUERISTIC GIẢI QUYẾT BÀI TOÁN NGƯỜI ĐƯA THƯ. .23
TÀI LIỆU THAM KHẢO 32
SVTH : CH1301074 – Nguyễn Hải Yến 3
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Chương 1.
TÌM HIỂU VỀ HUERISTIC VÀ META
HUERISTIC TRONG GIẢI QUYẾT VẤN ĐỀ
NP
1.1. Khái niệm về lớp bài toán P và NP
1.1.1. Khái niệm các loại thời gian tính
• Thời gian tính tốt nhất: là thời gian tính tối thiểu cần thiết để thực hiện
thuật toán với mọi bộ dữ liệu đầu vào kích thước n.
• Thời gian tính tồi nhất: là thời gian tính tối đa cần thiết để thực hiện thuật
toán với mọi bộ dữ liệu đầu vào có kích thước n
• Thời gian tính trung bình: là thời gian tính cần thiết để thực hiện thuật toán
trên một tập hữu hạn các bộ dữ liệu đầu vào có kích thước n. Thời gian tính
trung bình được tính theo công thức sau:
• Thời gian tính trung bình=(Tổng thời gian tính tất cả các bộ dữ liệu có thể)/
Số bộ dữ liệu.
Định nghĩa: Bài toán quyết định là bài toán mà đầu ra chỉ có thể là ‘yes’ hoặc
‘no’(đúng/sai, 0/1).
Đối với một bài toán quyết định, có những bộ dữ liệu vào cho ra câu trả lời(đầu ra)
là ‘yes’, chúng ta gọi đây là bộ dữ liệu ‘yes’, nhưng cũng có những bộ dữ liệu vào
cho ra câu trả lời là ‘no’, chúng ta gọi những bộ dữ liệu này là bộ dữ liệu ‘no’.
1.1.2. Bằng chứng ngắn gọn dễ kiểm tra
Rất nhiều các bài toán quyết định có một đặc điểm chung, đó là để xác
nhận câu trả lời ‘yes’ đối với bộ dữ liệu vào ‘yes’ của chúng, chúng ta có thể đưa
ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời ‘yes’ cho bộ dữ liệu vào
‘yes’ đó. Tính ngắn gọn dễ kiểm tra ám chỉ việc thời gian kiểm tra để đưa ra kết
SVTH : CH1301074 – Nguyễn Hải Yến 4
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
quả chỉ mất thời gian đa thức. Ví dụ về những bài toán quyết định kiểu này rất
nhiều, sau đây là một số ví dụ:
• Bài toán kiểm tra tính hợp số: “Có phải số n là hợp số?”, để xác nhận câu
trả lời ‘yes’ cho đầu vào n, chúng ta có thể đưa ra một ước số b (1
phép chia n cho b sau thời gian đa thức. Trong ví dụ này , b là bằng chứng
ngắn gọn (vì b
là ước số của n không).
• Đối với bài toán Hamilton, để xác nhận câu trả lời là ‘yes’ cho đồ thị đã
cho G, chúng ta có thể đưa ra một chu trình Hamilton của đồ thị:
v
1
, v
2
, v
3
v
n
, v
1
Việc kiểm tra dãy đỉnh nói trên có là chu trình Hamilton của đồ thị đã cho
hay không có thể thực hiện sau thời gian đa thức. Khi đó chúng ta nói dãy
đỉnh nói trên là bằng chứng ngắn gọn dễ kiểm tra để xác nhận câu trả lời
‘yes’ của bài toán Hamilton.
Một cách tương tự, có thể đưa ra khái niệm bằng chứng ngắn gọn dễ kiểm
tra để xác nhận câu trả lời ‘no’. Đối với một số bài toán, việc đưa ra bằng chứng
ngắn gọn dễ kiểm tra để xác nhận câu trả lời ‘no’ là dễ hơn so với việc đưa ra bằng
chứng ngắn gọn xác định câu trả lời là ‘yes’.
1.1.3. Khái niệm quy dẫn
Định nghĩa . Giả sử chúng ta có hai bài toán quyết định A và B. Chúng ta nói A
có thể quy dẫn về B nếu như sau một thời gian tính đa thức nếu tồn tại một thuật
toán thời gian đa thức R cho phép biến đổi bộ dữ liệu x của A thành bộ dữ liệu
vào R(x) của B sao cho x là bộ dữ liệu yes của A khi và chỉ khi R(x) là dữ liệu vào
yes của B.
Nếu A quy dẫn về được B sau thời gian đa thức và B có thể giải được sau thời gian
đa thức thì A cũng có thể giải được sau thời gian đa thức.
SVTH : CH1301074 – Nguyễn Hải Yến 5
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
1.1.4. Lớp bài toán P
Định nghĩa. Chúng ta gọi P là lớp các bài toán có thể giải được trong thời gian
đa thức.
Ví dụ: Bài toán cây khung nhỏ nhất giải được nhờ thuật toán Prim với thời gian
0(n
2
) thuộc lớp bài toán P.
1.1.5. Lớp bài toán NP
Định nghĩa. Ta gọi NP là lớp các bài toán quyết định mà để xác nhận câu trả lời
‘yes’ của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ: Bài toán kiểm tra tính hợp số: “Có phải n là hợp số không?”, để xác nhận
câu trả lời ‘yes’ cho đầu vào n ta có thể đưa ra một ước số b (1< b < n) của n. Để
kiểm tra xem b có phải là ước số của n hay không ta có thể thực hiện phép chia n
cho b sau thời gian đa thức. Trong ví dụ này dễ thấy b là bằng chứng ngắn gọn
(b
1.1.6. Lớp bài toán Co- NP
Định nghĩa. Ta gọi Co-NP là lớp các bài toán quyết định mà để xác nhận câu trả
lời ‘no’ của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ: Bài toán kiểm tra tính nguyên tố: “Có phải n là số nguyên tố không?”, để
đưa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời ‘no’ cho đầu vào n ta
có thể đưa ra một ước số b của n.
1.1.7. Lớp bài toán NP- đầy đủ (NP- complete)
Định nghĩa. Một bài toán quyết định A được gọi là NP-đầy đủ (NP-Complete)
nếu như:
• A là một bài toán trong NP.
• Mọi bài toán trong NP đều có thể quy dẫn về A.
Bổ đề. Giả sử bài toán A là NP-đầy đủ, bài toán B thuộc NP, và bài toán A qui dẫn
được về bài toán B. Khi đó bài toán B cũng là NP-đầy đủ
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
LỜI NÓI ĐẦU
Bài toán tìm kiếm được xem là bài toán được nhiều người quan tâm, đặc
biệt là tìm kiếm tối ưu toàn cục. Có nhiều phương pháp để giải các bài toán tìm
kiếm tối ưu toàn cục như : phương pháp trực tiếp (áp dụng các công thức, định lý,
thuật giải đã có sẵn ), các phương pháp gián tiếp hay tìm kiếm lời giải thông dụng
(phương pháp thử sai, phương pháp vét cạn, phương pháp quay lui). Ngoài các
phương pháp nêu trên thì trong học phần “ Thuật toán và phương pháp giải quyết
vấn đề em còn được tiếp cận với các phương pháp hueristic và meta hueristic.
Và sau đây là bài thu hoạch của em : “Tìm hiểu về hueristic -
metahueristic - Giải pháp hueristic theo nguyên lý tham lam giải bài toán người
đưa thư ”.
Em xin gửi lời Thank chân thành đến trường Đại học Công Nghệ Thông
Tin TP.HCM đã tạo điều kiện cho em được tiếp cận với môn học “Thuật toán và
phương pháp giải quyết vấn đề ”
Em xin Thank Thầy PGS.TS. Đỗ Văn Nhơn đã tận tình truyền đạt kiến
thức và có những định hướng giúp em hoàn thành bài thu hoạch.
Mặc dù đã rất cố gắng nhưng bài thu hoạch của em khó tránh khỏi thiếu
sót em mong Thầy góp ý nhận xét để bài thu hoạch hoàn thiện hơn.
SVTH : CH1301074 – Nguyễn Hải Yến 2
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
MỤC LỤC
LỜI NÓI ĐẦU 2
Chương 1 4
TÌM HIỂU VỀ HUERISTIC VÀ META HUERISTIC TRONG GIẢI
QUYẾT VẤN ĐỀ NP 4
Xác suất lai ghép cho biết tính thường xuyên của việc lai ghép tạo ra thế hệ mới
được thực hiện như thế nào. Nếu xác suất lai ghép là pc , khi đó khả năng để một cá
thể được lai ghép là pc. Nếu không thực hiện lai ghép, con sinh ra sẽ giống hoàn
toàn bố mẹ. Nếu được lai ghép, con sinh ra sẽ có một phần giống bố và một phần
giống mẹ 15
Xác suất đột biến cho biết tính thường xuyên của việc các gen của NST thay đổi
như thế nào. Nếu xác suất đột biến là pm, khi đó khả năng để mỗi gen của một NST
bất kỳ bị đột biến là pm. Tác dụng của toán tử đột biến là ngăn ngừa giải thuật di
truyền rơi vào tình trạng cực trị địa phương, tuy nhiên nếu thực hiện đột biến với xác
suất quá cao sẽ biến giải thuật di truyền thành giải thuật tìm kiếm ngẫu nhiên 15
LocalSearch() là hàm tìm kiếm địa phương, giúp tìm ra tối ưu cục bộ 22
22
Sơ đồ thuật toán bầy kiến 22
Chương 2: 23
ỨNG DỤNG HUERISTIC GIẢI QUYẾT BÀI TOÁN NGƯỜI ĐƯA THƯ. .23
TÀI LIỆU THAM KHẢO 32
SVTH : CH1301074 – Nguyễn Hải Yến 3
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
Chương 1.
TÌM HIỂU VỀ HUERISTIC VÀ META
HUERISTIC TRONG GIẢI QUYẾT VẤN ĐỀ
NP
1.1. Khái niệm về lớp bài toán P và NP
1.1.1. Khái niệm các loại thời gian tính
• Thời gian tính tốt nhất: là thời gian tính tối thiểu cần thiết để thực hiện
thuật toán với mọi bộ dữ liệu đầu vào kích thước n.
• Thời gian tính tồi nhất: là thời gian tính tối đa cần thiết để thực hiện thuật
toán với mọi bộ dữ liệu đầu vào có kích thước n
• Thời gian tính trung bình: là thời gian tính cần thiết để thực hiện thuật toán
trên một tập hữu hạn các bộ dữ liệu đầu vào có kích thước n. Thời gian tính
trung bình được tính theo công thức sau:
• Thời gian tính trung bình=(Tổng thời gian tính tất cả các bộ dữ liệu có thể)/
Số bộ dữ liệu.
Định nghĩa: Bài toán quyết định là bài toán mà đầu ra chỉ có thể là ‘yes’ hoặc
‘no’(đúng/sai, 0/1).
Đối với một bài toán quyết định, có những bộ dữ liệu vào cho ra câu trả lời(đầu ra)
là ‘yes’, chúng ta gọi đây là bộ dữ liệu ‘yes’, nhưng cũng có những bộ dữ liệu vào
cho ra câu trả lời là ‘no’, chúng ta gọi những bộ dữ liệu này là bộ dữ liệu ‘no’.
1.1.2. Bằng chứng ngắn gọn dễ kiểm tra
Rất nhiều các bài toán quyết định có một đặc điểm chung, đó là để xác
nhận câu trả lời ‘yes’ đối với bộ dữ liệu vào ‘yes’ của chúng, chúng ta có thể đưa
ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời ‘yes’ cho bộ dữ liệu vào
‘yes’ đó. Tính ngắn gọn dễ kiểm tra ám chỉ việc thời gian kiểm tra để đưa ra kết
SVTH : CH1301074 – Nguyễn Hải Yến 4
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
quả chỉ mất thời gian đa thức. Ví dụ về những bài toán quyết định kiểu này rất
nhiều, sau đây là một số ví dụ:
• Bài toán kiểm tra tính hợp số: “Có phải số n là hợp số?”, để xác nhận câu
trả lời ‘yes’ cho đầu vào n, chúng ta có thể đưa ra một ước số b (1
phép chia n cho b sau thời gian đa thức. Trong ví dụ này , b là bằng chứng
ngắn gọn (vì b
là ước số của n không).
• Đối với bài toán Hamilton, để xác nhận câu trả lời là ‘yes’ cho đồ thị đã
cho G, chúng ta có thể đưa ra một chu trình Hamilton của đồ thị:
v
1
, v
2
, v
3
v
n
, v
1
Việc kiểm tra dãy đỉnh nói trên có là chu trình Hamilton của đồ thị đã cho
hay không có thể thực hiện sau thời gian đa thức. Khi đó chúng ta nói dãy
đỉnh nói trên là bằng chứng ngắn gọn dễ kiểm tra để xác nhận câu trả lời
‘yes’ của bài toán Hamilton.
Một cách tương tự, có thể đưa ra khái niệm bằng chứng ngắn gọn dễ kiểm
tra để xác nhận câu trả lời ‘no’. Đối với một số bài toán, việc đưa ra bằng chứng
ngắn gọn dễ kiểm tra để xác nhận câu trả lời ‘no’ là dễ hơn so với việc đưa ra bằng
chứng ngắn gọn xác định câu trả lời là ‘yes’.
1.1.3. Khái niệm quy dẫn
Định nghĩa . Giả sử chúng ta có hai bài toán quyết định A và B. Chúng ta nói A
có thể quy dẫn về B nếu như sau một thời gian tính đa thức nếu tồn tại một thuật
toán thời gian đa thức R cho phép biến đổi bộ dữ liệu x của A thành bộ dữ liệu
vào R(x) của B sao cho x là bộ dữ liệu yes của A khi và chỉ khi R(x) là dữ liệu vào
yes của B.
Nếu A quy dẫn về được B sau thời gian đa thức và B có thể giải được sau thời gian
đa thức thì A cũng có thể giải được sau thời gian đa thức.
SVTH : CH1301074 – Nguyễn Hải Yến 5
Thuật toán & PP giải quyết vấn đề PGS.TS Đỗ Văn Nhơn
1.1.4. Lớp bài toán P
Định nghĩa. Chúng ta gọi P là lớp các bài toán có thể giải được trong thời gian
đa thức.
Ví dụ: Bài toán cây khung nhỏ nhất giải được nhờ thuật toán Prim với thời gian
0(n
2
) thuộc lớp bài toán P.
1.1.5. Lớp bài toán NP
Định nghĩa. Ta gọi NP là lớp các bài toán quyết định mà để xác nhận câu trả lời
‘yes’ của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ: Bài toán kiểm tra tính hợp số: “Có phải n là hợp số không?”, để xác nhận
câu trả lời ‘yes’ cho đầu vào n ta có thể đưa ra một ước số b (1< b < n) của n. Để
kiểm tra xem b có phải là ước số của n hay không ta có thể thực hiện phép chia n
cho b sau thời gian đa thức. Trong ví dụ này dễ thấy b là bằng chứng ngắn gọn
(b
1.1.6. Lớp bài toán Co- NP
Định nghĩa. Ta gọi Co-NP là lớp các bài toán quyết định mà để xác nhận câu trả
lời ‘no’ của nó ta có thể đưa ra bằng chứng ngắn gọn dễ kiểm tra.
Ví dụ: Bài toán kiểm tra tính nguyên tố: “Có phải n là số nguyên tố không?”, để
đưa ra bằng chứng ngắn gọn dễ kiểm tra xác nhận câu trả lời ‘no’ cho đầu vào n ta
có thể đưa ra một ước số b của n.
1.1.7. Lớp bài toán NP- đầy đủ (NP- complete)
Định nghĩa. Một bài toán quyết định A được gọi là NP-đầy đủ (NP-Complete)
nếu như:
• A là một bài toán trong NP.
• Mọi bài toán trong NP đều có thể quy dẫn về A.
Bổ đề. Giả sử bài toán A là NP-đầy đủ, bài toán B thuộc NP, và bài toán A qui dẫn
được về bài toán B. Khi đó bài toán B cũng là NP-đầy đủ
Do Drive thay đổi chính sách, nên một số link cũ yêu cầu duyệt download. các bạn chỉ cần làm theo hướng dẫn.
Password giải nén nếu cần: ket-noi.com | Bấm trực tiếp vào Link để tải:
You must be registered for see links
Tags: thuat toan nguoi dua thu