อัลกอริทึม, กราฟ และการวางแผนเชิงเส้น
แนะนำใหม่| English | ความหมาย |
|---|---|
| minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/ | ต้นไม้ครอบคลุมที่มีน้ำหนักน้อยที่สุด |
เครือข่ายที่ถูกที่สุดหรือเส้นทางสั้นที่สุด?
- โรงเรียนต้องเชื่อมต่อบนอาคารด้วยสายเคเบิล เส้นทางสั้นที่สุดระหว่างอาคารสองแห่งและเครือข่ายทั้งหมดที่ถูกที่สุดเป็นปัญหาคนละอย่างกัน
- บทเรียนนี้ศึกษา ต้นไม้ขยายตัวน้อยสุด (minimum spanning tree): เครือข่ายที่เชื่อมต่อไม่มีวงจร ซึ่งเชื่อมทุกจุดยอดด้วยน้ำหนักรวมของเส้นขอบที่น้อยที่สุดเท่าที่จะเป็นไปได้
เลือกโครงสร้างทางคณิตศาสตร์
- Kruskal เลือกเส้นขอบตามลำดับน้ำหนักที่เพิ่มขึ้นโดยหลีกเลี่ยงวงจรร Dijkstra อัปเดตระยะทางคร่าวๆ สั้นที่สุดจากจุดเริ่มต้น การวางแผนเชิงเส้นหาจุดสูงสุดของฟังก์ชันวัตถุประสงค์เชิงเส้นเหนือพื้นที่ที่เป็นไปได้; ตรวจสอบจุดยอดและข้อจำกัดจำนวนเต็มเมื่อจำเป็น
- ระบุอินพุตที่อนุญาตและหน่วยก่อนทำการคำนวณ สมการควรแสดงความสัมพันธ์ ไม่ใช่แค่บันทึกการกดเครื่องคิดเลข
อัลกอริทึมของครุสคาลและเส้นทางสั้นที่สุดให้ผลรวม 6 เท่ากันในตัวอย่างเครือข่าย แต่ทำไมจึงไม่สามารถใช้แทนกันได้?
Difficulty 1/5 · 100 coins + a small bonus on first completion today
วัตถุประสงค์ต่างกัน: ต้นไม้ครอบคลุมจุดยอดทั้งหมด (n-1 ขอบ ไม่มีวงจร) ในขณะที่เส้นทางสั้นที่สุดเป็นการปรับปรุงเส้นทางการเดินทางระหว่างต้นทางถึงปลายทางเพียงเส้นทางเดียว การได้คำตอบเท่ากันในที่นี้เป็นเรื่องบังเอิญเท่านั้น
ทำตัวอย่างที่ผ่านการตรวจสอบ
- ตรวจสอบผลลัพธ์เทียบกับปริมาณเริ่มต้น แทนค่าลงในความสัมพันธ์เดิม หรือเปรียบเทียบกราฟกับคำตอบเชิงตัวเลขเมื่อเหมาะสม
สำหรับจุดยอด A,B,C,D และเส้นขอบ AB=2, BC=3, AC=4, CD=1, BD=5, Kruskal เลือก CD, AB, BC รวม 6 เส้นทางสั้นสุดจาก A ไป D คือ A-B-C-D รวม 6 เช่นกัน แต่ความเท่าเทียมนี้อาจเกิดขึ้นโดยบังเอิญ เพิ่มค่า 3x+2y โดย x+y≤4, x≤2, x,y≥0: จุดยอดที่ดีที่สุดคือ (2,2), ค่า 10
อัลกอริทึม, กราฟ และการวางแผนเชิงเส้น
Kruskal เลือกขอบตามลำดับน้ำหนักเพิ่มขึ้นโดยไม่เกิดวงจร
เปรียบเทียบแบบจำลองกับกรณีที่มีตัวอย่างวิธีทำ และอธิบายการเปลี่ยนแปลงหนึ่งอย่าง
หาค่ารวมน้ำหนักของต้นไม้ขยายตัวน้อยสุดสำหรับตัวอย่างกราฟนี้
Difficulty 2/5 · 140 coins + a small bonus on first completion today
Kruskal เลือกน้ำหนักขอบ 1,2,3 โดยไม่มีวงจร เชื่อมทุกจุดยอด: รวม 6
ทดสอบทางลัดที่ดูน่าเชื่อถือ
- ต้นไม้ขยายตัวไม่มีวงจรและเชื่อมทุกจุดยอด เส้นขอบที่มีน้ำหนักมากที่สุดไม่ได้ถูกตัดออกอัตโนมัติจากทุกคำตอบที่ดีที่สุด อัลกอริทึมหาเส้นทางสั้นที่สุดไม่สามารถแทนที่อัลกอริทึมต้นไม้ขยายตัวน้อยสุดได้
- เมื่อทางลัดล้มเหลว ให้ระบุสมมติฐานที่มันทำลายรักษาค่าที่แม่นยำจนถึงการทศนิยมตามโจทย์กำหนดเท่านั้น
เส้นทางสั้นที่สุดระหว่างจุดยอดสองจุดต้องเป็นต้นไม้ขยายตัวน้อยสุดของเครือข่ายทั้งหมด ข้ออ้างนี้ไม่ถูกต้อง อธิบายว่าข้อนี้ละเมิดนิยามหรือสมมติฐานใด
หาค่าสูงสุดของ 3x+2y สำหรับพื้นที่ที่เป็นไปได้ของตัวอย่างนี้
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ตรวจสอบจุดยอดที่เป็นไปได้: (2,2) ให้ 3×2+2×2=10 ซึ่งเป็นค่าฟังก์ชันเป้าหมายมากที่สุด
เส้นทางสั้นที่สุดระหว่างสองจุดยอด还必须เป็นต้นไม้ขยายตัวน้อยสุดของทั้งเครือข่ายด้วย
Difficulty 1/5 · 100 coins + a small bonus on first completion today
ต้นไม้ขยายตัวไม่มีวงจรและเชื่อมทุกจุดยอด ขอบที่มีน้ำหนักมากที่สุดในหนึ่งเส้นไม่ถูกตัดออกโดยอัตโนมัติจากทุกคำตอบที่ดีที่สุด อัลกอริทึมหาเส้นทางสั้นที่สุดไม่สามารถแทนที่อัลกอริทึมหาต้นไม้ขยายตัวน้อยสุดได้
ตีความสถานการณ์ใหม่
- สำหรับเส้นทางวิกฤต ให้คำนวณเวลาเหตุการณ์ที่เร็วที่สุดและช้าที่สุดที่สุด และระบุกิจกรรมที่ไม่มีเวลาสำรอง (zero-float) ระบุหน่วยและตีความค่าที่เหมาะสม บัญชีเก็บข้อมูลเดิมไม่มีคู่ D1 ดังนั้นงานดั้งเดิมเหล่านี้จึงไม่สร้างธนาคารข้อสอบย้อนหลัง D1 ที่ผ่านการทบทวน
- คำตอบที่สมบูรณ์ต้องให้ผลลัพธ์ทางคณิตศาสตร์และอธิบายความหมายของมัน ตรวจสอบว่ามันเป็นไปได้ในบริบทที่กำหนดหรือไม่
ต้นไม้ขยายตัวบน 4 จุดยอด มีขอบกี่เส้น?
Difficulty 2/5 · 140 coins + a small bonus on first completion today
ต้นไม้บน n จุดยอด มี n-1 เส้นขอบ ดังนั้นสี่จุดยอดต้องใช้สามเส้น
จับคู่แต่ละอัลกอริทึมกับกฎของมัน
Difficulty 2/5 · 140 coins + a small bonus on first completion today
แต่ละอัลกอริทึมมีความแม่นยำสำหรับกลุ่มปัญหาของตนเอง การติดตามกฎที่กำหนดให้ครบถ้วน รวมถึงการจัดการกรณีที่มีค่าเท่ากัน คือสิ่งที่ได้รับคะแนน
ใช้สิ่งนี้ในหลักสูตรของคุณ
- edexcel IAL คณิตศาสตร์เพิ่มเติม; หน่วย__)D1__) เป็นทางการ การเสริมเนื้อหาจากหน่วยอื่นระบุไว้ในทบทวนขอบเขต; ไม่ใช่ข้อกำหนดการเพิ่มคะแนนพิเศษ
- ให้วิธีการก่อนคำตอบสุดท้าย และใช้กฎเครื่องคิดเลขและสูตรของใบคำถาม ทบทวนคำตอบที่ผิดโดยการหาขั้นตอนที่ไม่ถูกต้องเป็นครั้งแรก
เครือข่ายที่เชื่อมต่อไม่มีวงจรซึ่งเชื่อมทุกจุดยอดด้วยน้ำหนักรวมของเส้นขอบที่น้อยที่สุดเท่าที่จะเป็นไปได้ เลือกความสัมพันธ์ แสดงวิธีทำ ตรวจสอบสมมติฐานและตีความผลลัพธ์