การจัดเรียง การบรรจุ และการจัดอัลกอริทึมเครือข่าย
แนะนำใหม่| English | ความหมาย |
|---|---|
| algorithm/ˈælɡərɪθəm/ | อัลกอริทึม |
วิธีการบรรจุที่รวดเร็วเป็นวิธีที่ดีที่สุดเสมอหรือไม่?
- วิธีการบรรจุที่รวดเร็วช่วยเติมกล่องได้อย่างเต็มที่ แต่การจัดวางที่ถูกต้องและรวดเร็วอาจไม่ได้ใช้จำนวนกล่องน้อยที่สุด
- บทเรียนนี้ศึกษาเรื่อง algorithm (อัลกอริทึม): ชุดคำสั่งที่มีลำดับและจำกัดจำนวน ที่แก้ปัญหาประเภทที่กำหนดไว้
เลือกโครงสร้างทางคณิตศาสตร์
- ทำตามชื่ออัลกอริทึมอย่างเคร่งครัด รวมถึงกฎในการจัดการกรณีเท่ากัน ใน first-fit packing วางแต่ละรายการลงใน bin ที่ว่างแรกที่สามารถรับมันได้ First-fit decreasing จะทำการเรียงลำดับก่อนนำไปใช้ first-fit Heuristic อาจถูกต้องแต่ไม่ใช่วิธีที่ดีที่สุด
- ระบุอินพุตที่อนุญาตและหน่วยก่อนทำการคำนวณ สมการควรแสดงความสัมพันธ์ ไม่ใช่แค่บันทึกการกดเครื่องคิดเลข
First-fit ใช้ 2 กล่องสำหรับ 6,5,4,3,2 ที่มีความจุ 10 ซึ่งตรงกับค่าขอบล่าง สรุปได้ว่าอย่างไร?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
การเข้าถึงค่าขอบล่างพิสูจน์ความเหมาะสมในกรณีนี้เท่านั้น ความสำเร็จของ Heuristic ในตัวอย่างเดียวบอกอะไรไม่ได้เกี่ยวกับกรณีแย่ที่สุด - รายการรายการอื่นอาจทำให้ First-fit เกินกว่าค่าขอบล่าง
ทำตัวอย่างที่ผ่านการตรวจสอบ
- ตรวจสอบผลลัพธ์เทียบกับปริมาณเริ่มต้น แทนค่าลงในความสัมพันธ์เดิม หรือเปรียบเทียบกราฟกับคำตอบเชิงตัวเลขเมื่อเหมาะสม
เมื่อความจุของ bin คือ 10 และรายการคือ 6,5,4,3,2 ตามลำดับนั้น first-fit วาง 6 และ 4 ลงใน bin 1 จากนั้นวาง 5,3,2 ลงใน bin 2 ใช้ทั้งหมด 2 bins ขนาดรวมคือ 20 ดังนั้นขอบเขตล่างคือ ceil(20/10)=2; การจัดวางนี้จึงเป็นวิธีที่ดีที่สุดสำหรับกรณีนี้
การจัดเรียง การบรรจุ และการจัดอัลกอริทึมเครือข่าย
ติดตามอัลกอริทึมที่กำหนดชื่ออย่างละเอียด รวมถึงกฎการแก้ empate
เปรียบเทียบแบบจำลองกับกรณีที่มีตัวอย่างวิธีทำ และอธิบายการเปลี่ยนแปลงหนึ่งอย่าง
การจัดแบบ first-fit ในตัวอย่างใช้กล่องจำนวนเท่าไร?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
การจัดแบบ first-fit เติมกล่องสองกล่อง โดยแต่ละกล่องมีขนาดรวม 10
ทดสอบทางลัดที่ดูน่าเชื่อถือ
- ตัวอย่างความสำเร็จไม่ได้พิสูจน์ว่า heuristic เป็นวิธีที่ดีที่สุดเสมอไป รักษารายละเอียดขั้นตอนกลางไว้ในแผนภาพการเรียงลำดับ อย่ากระโดดจากข้อมูลต้นทางไปยังรายการที่เรียงแล้วสุดท้าย หากต้องการเส้นทาง การอัปเดตเส้นทางที่สั้นที่สุดต้องเก็บข้อมูลผู้สำเร็จรูปไว้ด้วย
- เมื่อทางลัดล้มเหลว ให้ระบุสมมติฐานที่มันทำลายรักษาค่าที่แม่นยำจนถึงการทศนิยมตามโจทย์กำหนดเท่านั้น
Heuristic ในการบรรจุที่ทำได้ดีในตัวอย่างหนึ่งต้องเป็นวิธีที่ดีที่สุดเสมอ ข้อความนี้ไม่ถูกต้อง อธิบายว่าข้อความนี้ขัดแย้งกับนิยามหรือสมมติฐานใด
หาค่าขอบล่างของจำนวนกล่องสำหรับขนาดรวม 20 และความจุ 10
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ถังแต่ละใบบรรจุได้ไม่เกิน 10 ดังนั้นจึงต้องใช้ถังอย่างน้อย ceiling(20/10)=2 ถัง
heuristic การบรรจุที่ทำงานได้ดีในตัวอย่างหนึ่ง ต้องเป็นวิธีที่ดีที่สุดเสมอ
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ตัวอย่างความสำเร็จไม่ได้พิสูจน์ว่า heuristic เป็นวิธีที่ดีที่สุดเสมอ ควรเก็บรายการระหว่างขั้นตอนไว้ในตารางติดตามการเรียงลำดับ; อย่ากระโดดจากข้อมูลต้นทางไปยังรายการที่เรียงลำดับเรียบร้อยแล้ว การอัปเดตเส้นทางสั้นที่สุดต้องคงข้อมูลผู้นำทางไว้หากมีการขอเส้นทาง
ตีความสถานการณ์ใหม่
- สำหรับ Dijkstra เลือกฉลากชั่วคราวที่ไม่ได้รับการยืนยันที่มีค่าน้อยที่สุดและอัปเดตเพื่อนบ้านของมัน สำหรับปัญหาการตรวจสอบเส้นทางแยกแยะระหว่างเส้นทางปิดและเส้นทางเปิด และระบุจุดยอดที่มีองศาเป็นเลขคี่ก่อนจับคู่
- คำตอบที่สมบูรณ์ต้องให้ผลลัพธ์ทางคณิตศาสตร์และอธิบายความหมายของมัน ตรวจสอบว่ามันเป็นไปได้ในบริบทที่กำหนดหรือไม่
หาพื้นที่ว่างที่เหลืออยู่ในถังที่มีไอเท็ม 5,3,2 โดยมีความจุ 10
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ความจุที่ไม่ได้ใช้=10-(5+3+2)=0
จับคู่กฎการบรรจุแต่ละข้อกับวิธีการกระทำ
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ติดตามอัลกอริทึมตามนิยามอย่างละเอียด; ค่าขอบล่างตัดสินว่าการจัดบรรจุที่ดีที่สุดในความเป็นไปได้จะเป็นอย่างไร
ใช้สิ่งนี้ในหลักสูตรของคุณ
- edexcel IAL mathematics; official unit D1. การเสริมเนื้อหาจากหน่วยอื่นระบุไว้ในบททบทวนขอบเขต ไม่ใช่ข้อกำหนดในการเพิ่มคะแนนพิเศษ
- ให้วิธีการก่อนคำตอบสุดท้าย และใช้กฎเครื่องคิดเลขและสูตรของใบคำถาม ทบทวนคำตอบที่ผิดโดยการหาขั้นตอนที่ไม่ถูกต้องเป็นครั้งแรก
เซตของคำสั่งที่มีจำนวนจำกัดและเรียงลำดับที่แก้ปัญหา某一ประเภทที่กำหนดได้ เลือกความสัมพันธ์ แสดงวิธีการ ตรวจสอบสมมติฐาน และตีความผลลัพธ์