Giới thiệu về thuật toán tham lam - Greedy Algorithm(Phần 1)

Tham ăn hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ...

Tham ăn hiểu một cách dân gian là: trong một mâm có nhiều món ăn, món nào ngon nhất ta sẽ ăn trước và ăn cho hết món đó thì chuyển sang món ngon thứ hai, lại ăn hết món ngon thứ hai này và chuyển sang món ngon thứ ba…

Phương pháp tham ăn (greedy method) là một chến lược thiết kế thuật toán thường được sử dụng để giải quyết các bài toán tối ưu.

Có rất nhiều vấn đề cần giải quyết, có thể quy về vấn đề chính sau đây: Cho trước một tập A các đối tượng nào đó, đòi hỏi phải chọn ra một tập con S các đối tượng thỏa mãn một số điều kiện nào đó. Bất kỳ một tập con S nào của A thỏa mãn các yêu cầu đặt ra được gọi lànghiệm chấp nhận được của bài toán. Một hàm mục tiêu gắn mỗi nghiệm chấp nhận được với một giá trị nào đó. Một nghiệm chấp nhận được mà tại đó hàm mục tiêu có giá trị lớn nhất (hoặc nhỏ nhất) được gọi là nghiệm tối ưu.

Ý tưởng:
Ta xây dựng tập S dần dần từng bước, bắt đầu từ tập rỗng. Tại mỗi bước, ta sẽ chọn một phần tử “tốt nhất” trong các phần tử còn lại của A để đưa vào S. Việc lựa chọn một phần tử như thế ở mỗi bước được hướng dẫn bởi hàm chọn. Phần tử được chọn sẽ bị loại khỏi tập A. Nếu khi thêm phần tử được chọn vào tập S mà S vẫn còn thỏa mãn các điều kiện của bài toán thì ta mở rộng S bằng cách thêm vào phần tử được chọn.

Đặc điểm:
Mục đích xây dựng bài toán giải nhiều lớp bài toán khác nhau, đưa ra quyết định dựa ngay vào thuật toán đang có, và trong tương lai sẽ không xem xét lại quyết định trong quá khứ. Vì vậy thuật toán dễ đề xuất, thời gian tính nhanh nhưng thường không cho kết quả đúng.

Lời giải cần tìm có thể mô tả như là bộ gồm hữu hạn các thành phần thoả mãn điều kiện nhất định, ta phải giải quyết bài toán một cách tối ưu.

Để xây dựng lời giải ta có một tập các ứng cử viên
Xuất phát từ lời giải rỗng, thực hiện việc xây dựng lời giải từng bước, mỗi bước sẽ lựa chọn trong tập ứng cử viên để bổ sung vào lời giải hiện có.

Xây dựng một hàm nhận biết tính chấp nhận được của lời giải hiện có -> Hàm Solution(S) -> Kiểm tra thoả mãn điều kiện chưa.

Một hàm quan trọng nữa: Select(A) cho phép tại mỗi bước của thuật toán lựa chọn ứng cử viên có triển vọng nhất để bổ xung vào lời giải hiện có -> dựa trên căn cứ vào ảnh hưởng của nó vào hàm mục tiêu, thực tế là ứng cử viên đó phải giúp chúng ta phát triển tiếp tục bài toán.

Lược đồ tổng quát:

Click image for larger version  Name: Untitled.png Views: 1 Size: 11,4 KB ID: 59863



Trong lược đồ tổng quát trên. Select là hàm chọn, nó cho phép ta chọn ra từ tập A một phần tử được xem là tốt nhất, nhiều hứa hẹn nhất là thành viên của nghiệm.

Ta có thể dễ dàng thấy tại sao các thuật toán như thế được gọi là “ tham ăn”. Tại mỗi bước, nó chọn “miếng ngon nhất” (được xác định bởi hàm chọn), nếu thấy có thể nuốt được (có thể đưa vào nghiệm) nó sẽ xơi ngay, nếu không nó sẽ bỏ đi, sau này không bao giờ xem xét lại.
Cần nhấn mạnh rằng, thuật toán tham ăn trong một số bài toán, nếu xây dựng được hàm chọn thích hợp có thể cho nghiệm tối ưu. Trong nhiều bài toán, thuật toán tham ăn chỉ tìm được nghiệm gần đúng với nghiệm tối ưu.

Note : Trong phần sau mình đưa ví dụ cụ thể và nói kĩ hơn về thuật toán này.

COMMENTS

Tên

.:: Connect Trojan ::.,111,.htaccess,2,0-day,3,2017,2,Add-on,16,Affiliate,1,Anotador,1,AutoIT,17,BackDoor,1,Bán Sách,13,banhangonline,1,Bảo Mật,173,Bất Động Sản Tại Tiền Giang,5,Bestsellers,13,Binder,1,blog,31,Blogger,4,Blogger Template,1,Botnet,3,Brute,1,Bug Bounty,1,Bypass,10,camera,1,ceh,1,Châu Tinh Trì,2,Checked,6,Chrome,21,Code,5,coin hive,1,Coin-Hive,2,CoinHive,1,Connect Trojan,342,Connect Trojan ::.,1,Cổ Tích,2,Crack,3,Crypto,5,CSRF,5,CSS,2,Cuộc Sống,1,Dau tu,8,DDoS,6,Designer,1,Dich vụ,1,DNS,4,Download,2,du-an,3,DVD LUMION Tiếng Việt của anh Dũng Già Pro,1,Đam Mỹ,1,điện,1,Đồ Họa,215,Đô Thị,16,e11.me,1,ebook,17,ebook free,295,eBook Phệ Hồn Nghịch Thiên,1,eBook Thịnh Thế Địch Phi,1,Encrypt,1,Encryption,1,epub,76,epub [Tiên hiệp],1,ET-Logger,1,exploit,23,Exploitation,1,Extractor,2,facebook,69,FireFox,15,Flood,2,Forensic,7,full prc,2,game,177,Gerador,3,Gerenciador,1,Get Root,3,GHDB,3,Giả Tưởng,1,giaitri,1,Google,15,H&Y Shop,2,Hacker,3,Hacking,16,Hacking and Security,6,Hacking Tools,36,Hành Động,3,He Thong Site Phim,25,Hijacking,6,Hình Sự,1,hivecoin.hive coin,1,Hỏi Xoáy Đáp Xoay Trên VTV3,1,HTML,1,Huyền Ảo,92,Hướng dẫn Internet cơ bản,1,IFTTT,703,Imgur,2,Infographic,1,Information Disclosure,1,Internet Explorer,3,IT News,39,J2TeaM,29,J2TeaM Tools,9,JavaScript,6,Javascript Injection,3,Juno_okyo's Blog,23,Khóa Học,32,Khóa Học kiếm tiền online với accesstrade,5,khoá học miễn phí,16,Khóa học Photoshop,19,Khóa học sử dụng mã độc và phòng chống mã độc,2,Khoa Huyễn,6,khuyến mãi,16,kiemhiep,9,Kiếm Hiệp,20,Kiếm Tiền MMO,34,kiếm tiền rút gọn link,1,KilerRat,1,Kinh Dị,24,Kinh Dị - Ma,4,Kinh Doanh,73,kinhdi,1,kinhdoanh,5,KRACK Attacks,1,Lãng mạn,1,lazada,1,Lập trình,2,Lịch Sử,5,Linux,1,Local Attack,2,Logins/Cadastro,1,Lỗi Web,1,Lược Sử Hacker,2,Mã Giảm Giá,2,Mã Hóa,48,Malware,3,Master-Code,31,Máy Tính,1,Metasploit,2,Microsoft,4,mobile hacking,2,monero,1,Movie,25,MySQL,1,NEW PRODUCTS,19,NGHỆ THUẬT ẨN MÌNH,13,ngontinh,10,Ngôn Tình,151,nhà đất,1,Nhà Đất Gò Công,1,Nhân Vật Lịch Sử,2,Nhật Bản,1,Nhựt Trường Group,1,NjRat,5,Nước,1,open redirect,1,Oracle,1,Path Disclosure,2,pdf,76,Pen-Test,6,Pentest Box,9,Phan mem Internet,1,phanmem,23,phanmemdienthoai,3,phanmemmaytinh,10,phần mềm,11,Phim 18,2,Phim 2012,1,Phim 3D,1,Phim Âm Nhạc,2,Phim Bộ,39,Phim Chiến Tranh,5,Phim Dã Sử - Cổ Trang,6,Phim Đài Loan,6,Phim Đề Cử,4,Phim Hài Hước,26,Phim Hàn Quốc,33,Phim HD Chất Lượng Cao,5,Phim Hoạt Hình,2,Phim Hot,1,Phim Hồng Kông,20,Phim HQ,2,Phim Kinh Dị,8,Phim lẻ,4,Phim Mới 2011,2,Phim Mới 2012,1,Phim Mới 2015,1,Phim Nhật Bản,4,Phim SD,3,Phim Thái Lan,6,Phim Thần Thoại,4,Phim Tình Cảm,35,Phim Trung Quốc,37,Phim Truyền Hình,19,Phim Viễn Tưởng,1,Phim Võ Thuật,36,Phim Xã Hội Đen,1,Phishing,5,PHP,16,Plugin,1,Port,1,post mẫu,1,prc,77,Programming,15,Python,1,Quảng Cáo,1,rat,457,Recovery,3,Remote Code Execution,1,Remote Desktop,1,Reverse Engineering,6,review,3,rút gọn link,1,sach,47,Sách,37,Sách Nghệ Thuật Sống,12,sách nói,1,Sách Tâm Linh,1,Sách Tiếng Anh,2,sachiep,2,Sản Phẩm,1,Sắc Hiệp,16,Scam,1,Scanner,10,Security,66,SEO,5,share,1,Shell,5,shop,1,Social Engineering,4,Software,22,Source Unity,1,SQL injection,21,Sức Khỏe,1,Symlink,3,Tài Chính,1,Tài chính cá nhân,2,Tài Liệu,1,Tản mạn,7,Taudio,2,Tâm lý xã hội,1,tấn công,1,Testador,1,Thái Lan,2,Tham Khảo,3,thamkhao,11,them,1,Thiệp Cưới,1,Thiết Kế Web,30,Thời Trang,2,Thủ Thuật Hacking,53,Thuyết Minh,1,tienhiep,5,Tiên Hiệp,123,Tiểu Thuyết,94,tiki,3,TIL,8,Tin Tức,52,Tips,39,tool,1,Tool Hack,14,Tools,9,Tổng Hợp,1,Tricks,26,Trinh thám,1,trojan original,48,Trọng sinh,11,Trộm mộ,1,Trung Quốc,1,Truyện,1,Trương Định,110,Tu Chân,2,TUTORIALS,124,Twitter,1,Ung_Dung,4,Upload,1,usb,1,vanhoc,11,văn học,6,vBulletin,7,video,16,Vietsub,1,Việt Nam,4,Virus,4,Võ Thuật,3,Võng Du,5,Vulnerability,19,Web Developer,15,webmau,5,WHMCS,3,WiFi,2,wiki lỗi máy tinh,1,wiki lỗi NTG,3,Windows,12,WordPress,43,Write-up,11,XSS,16,Yahoo,1,yeah1offer,1,youtube,11,
ltr
item
NhutTruong.Com - Chia sẻ kiến thức miễn phí: Giới thiệu về thuật toán tham lam - Greedy Algorithm(Phần 1)
Giới thiệu về thuật toán tham lam - Greedy Algorithm(Phần 1)
https://whitehat.vn/filedata/fetch?id=59863&d=1475716744&type=full
NhutTruong.Com - Chia sẻ kiến thức miễn phí
https://www.nhuttruong.com/2016/11/gioi-thieu-ve-thuat-toan-tham-lam_8.html
https://www.nhuttruong.com/
https://www.nhuttruong.com/
https://www.nhuttruong.com/2016/11/gioi-thieu-ve-thuat-toan-tham-lam_8.html
true
7607280272436897486
UTF-8
Loaded All Posts Not found any posts VIEW ALL Readmore Reply Cancel reply Delete By Home PAGES POSTS View All RECOMMENDED FOR YOU LABEL ARCHIVE SEARCH ALL POSTS Not found any post match with your request Back Home Sunday Monday Tuesday Wednesday Thursday Friday Saturday Sun Mon Tue Wed Thu Fri Sat January February March April May June July August September October November December Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec just now 1 minute ago $$1$$ minutes ago 1 hour ago $$1$$ hours ago Yesterday $$1$$ days ago $$1$$ weeks ago more than 5 weeks ago Followers Follow THIS PREMIUM CONTENT IS LOCKED STEP 1: Share to a social network STEP 2: Click the link on your social network Copy All Code Select All Code All codes were copied to your clipboard Can not copy the codes / texts, please press [CTRL]+[C] (or CMD+C with Mac) to copy Table of Content