แนวคิดพื้นฐานของอัลกอริทึมโลภ
1. สร้างแบบจำลองทางคณิตศาสตร์เพื่ออธิบายปัญหา
2. แบ่งปัญหาที่แก้ไขออกเป็นปัญหาย่อยหลายประการ
3. แก้ปัญหาย่อยแต่ละข้อและรับโซลูชันที่ดีที่สุดในท้องถิ่นไปยังปัญหาย่อย
4. สังเคราะห์วิธีแก้ปัญหาที่ดีที่สุดในท้องถิ่นของปัญหาย่อยลงในการแก้ปัญหาการแก้ปัญหาดั้งเดิมของปัญหา
กระบวนการใช้อัลกอริทึมนี้:
เริ่มต้นจากการแก้ปัญหาเบื้องต้นไปจนถึงปัญหา
ในขณะที่สามารถก้าวไปข้างหน้าไปยังเป้าหมายโดยรวมที่กำหนด
ค้นหาองค์ประกอบการแก้ปัญหาของสารละลายที่เป็นไปได้
ทางออกที่เป็นไปได้สำหรับปัญหาประกอบด้วยองค์ประกอบโซลูชันทั้งหมด
ธรรมชาติที่เลือกสรร
ลักษณะการเลือกโลภที่เรียกว่าหมายถึงวิธีการแก้ปัญหาที่ดีที่สุดโดยรวมของปัญหาที่คุณกำลังมองหาสามารถทำได้ผ่านชุดของตัวเลือกที่ดีที่สุดในท้องถิ่น ปัญหาในปัจจุบันโดยไม่ต้องพิจารณา นี่เป็นองค์ประกอบพื้นฐานแรกของความเป็นไปได้ของอัลกอริทึมโลภ
อัลกอริทึมโลภทำให้ตัวเลือกโลภอย่างซ้ำซากและทุกครั้งที่มีการเลือกโลภปัญหาที่คุณกำลังมองหาจะลดลงเป็นปัญหาย่อยที่เล็กลง
สำหรับปัญหาเฉพาะเพื่อตรวจสอบว่ามีลักษณะทางเลือกโลภหรือไม่จำเป็นต้องพิสูจน์ว่าตัวเลือกโลภในแต่ละขั้นตอนในที่สุดนำไปสู่การแก้ปัญหาโดยรวมที่ดีที่สุดสำหรับปัญหา
2. คุณสมบัติโครงสร้างย่อยที่ดีที่สุด <br /> เมื่อวิธีการแก้ปัญหาที่ดีที่สุดของปัญหามีวิธีการแก้ปัญหาที่ดีที่สุดของปัญหาย่อยปัญหานี้กล่าวกันว่ามีคุณสมบัติโครงสร้างย่อยที่ดีที่สุด ลักษณะโครงสร้างพื้นฐานที่ดีที่สุดของปัญหาคือคุณสมบัติสำคัญที่สามารถแก้ไขได้โดยอัลกอริทึมโลภ
กระบวนการทั่วไปของความโลภ
การคัดลอกรหัสมีดังนี้:
โลภ (c) // c เป็นชุดอินพุตของปัญหานั่นคือชุดผู้สมัคร
-
s = {};
ในขณะที่ (ไม่ใช่วิธีแก้ปัญหา) // set s ไม่ถือเป็นวิธีแก้ปัญหา
-
x = select (c);
ถ้าเป็นไปได้ (s, x) // ตัดสินว่าการแก้ปัญหาหลังจากเพิ่ม x ในชุด s เป็นไปได้
s = s+{x};
c = c- {x};
-
กลับ s;
คำอธิบายปัญหา:
ปัจจุบันมีเหรียญที่มีค่าใบหน้า 2 jiao 5 เซนต์, 1 jiao 5 เซนต์, 5 เซนต์และ 1 เซนต์
การวิเคราะห์ปัญหา:
ตามสามัญสำนึกเมื่อเราไปที่ร้านค้าเพื่อซื้อสิ่งของและหาเงินเจ้านายจะให้เงินสูงสุดแก่เราก่อน หากเจ้านายขอให้คุณทำคะแนนหรือไม่กี่เซ็นต์คุณจะไม่ทำอย่างแน่นอน ในความเป็นจริงนี่เป็นปัญหาทั่วไปของการเลือกโลภ
การออกแบบอัลกอริทึมและการดำเนินการตามปัญหา :
ให้ฉันยกตัวอย่างให้คุณก่อน เขามองหาสิ่งนี้? 'ไม่ทำเช่นนั้นเจ้านายสามารถให้ฉันได้ฉันได้ 3 25 คะแนนและฉันได้รับ 24 น้อยลงดังนั้นฉันต้องให้ฉัน 2 10 คะแนนและ 4 1 คะแนน
การคัดลอกรหัสมีดังนี้:
// เลขคณิตสำหรับการค้นหาการเปลี่ยนแปลง
// อินพุต: อาร์เรย์ m เก็บจำนวนค่าใบหน้าที่จัดเรียงจากขนาดใหญ่ถึงเล็กในลำดับ
// เอาท์พุท: อาร์เรย์จำนวนเปรียบเทียบจำนวนเหรียญที่มีค่านิกายต่าง ๆ ในอาร์เรย์ M และค้นหาแผนเงิน
สาธารณะคงที่ int [] Zhaoqian (int m [], int n)
-
int k = m.length;
int [] num = new int [k];
สำหรับ (int i = 0; i <k; i ++)
-
num <i> = n/m <i>;
n = n%m <i>;
-
กลับมา;
-
การคัดลอกรหัสมีดังนี้:
ชั้นเรียนสาธารณะ Zhaoqian
-
โมฆะคงที่สาธารณะหลัก (สตริง [] args)
-
int m [] = {25,10,5,1};
int n = 99;
int [] num = new int [m.length];
num = zhaoqian (m, n);
System.out.println (n+"แผนการค้นหาเงิน:");
สำหรับ (int i = 0; i <m.length; i ++)
System.out.println (num <i>+"zip"+m <i>+"ค่าใบหน้า");
-
สาธารณะคงที่ int [] Zhaoqian (int m [], int n)
-
int k = m.length;
int [] num = new int [k];
สำหรับ (int i = 0; i <k; i ++)
-
num <i> = n/m <i>;
n = n%m <i>;
-
กลับมา;
-
-
ข้างต้นเป็นเนื้อหาทั้งหมดของบทความนี้ฉันหวังว่าคุณจะชอบมัน