D1 · Decision Mathematics 1 — Edexcel International A-Level Mathematics หมายเหตุทบทวนความรู้

1.1.1

คณิตศาสตร์สำหรับการตัดสินใจ 1: อัลกอริทึม, กราฟ และการวางแผนเชิงเส้น

การตัดสินใจทางคณิตศาสตร์ 1 (D1, ข้อสอบ WDM01/01, 1 ชั่วโมง 30 นาที, 75 คะแนน, การประเมินครั้งแรก เดือนมิถุนายน 2019) เป็นตัวเลือกแบบไม่ต่อเนื่องของ IAL: P1–P2 จะถูกกำหนดให้, และทุกวิธีคือ อัลกอริทึม — รายการคำสั่งที่แม่นยำจำนวนจำกัด ไม่มีรายการในคู่มือสูตรนอกเหนือจาก พื้นฐาน: คะแนนมาจากการดำเนินการตามขั้นตอนอย่างแม่นยำและการระบุผลลัพธ์ในรูปแบบที่กำหนด รูปแบบ การอ้างอิงนี้ครอบคลุมอัลกอริทึมการเรียงลำดับและการบรรจุในกล่อง, ต้นไม้Resultadoที่น้อยที่สุด, เส้นทางสั้นที่สุด, ปัญหาผู้ส่งไปรษณีย์จีนและปัญหาผู้เดินทางขายของ, การวิเคราะห์เส้นทางสำคัญ และการโปรแกรมเชิงเส้น

กฎสำหรับคำตอบอัลกอริทึม:

งาน	รูปแบบที่ต้องการ
เรียงลำดับ	แสดงรายการหลังแต่ละรอบ (หรือตัวเลือกพิวต์สำหรับการเรียงแบบควิก)
บรรจุในกล่อง	ระบุชื่ออัลกอริทึม (ฟิสต์-ฟิต, ฟิสต์-ฟิตเดครีซิ่ง, ฟูล-บิน) และแสดงการวางแต่ละครั้ง
อัลกอริทึมกราฟ	ระบุลำดับการเลือกเส้น/โหนด; แสดงค่าสุดท้าย (ฉลาก, น้ำหนักรวม)
route inspection	list the odd nodes, the pairings and their weights, before totalling
โปรแกรมเชิงเส้น	นิยามตัวแปร, วัตถุประสงค์ และข้อจำกัดทุกอย่างพร้อมทั้งความไม่เป็นลบ

1.1.1 1.1.2

อัลกอริทึมการเรียงลำดับและการบรรจุในกล่อง

การเรียงแบบบับเบิล เปรียบเทียบไอเท็มที่อยู่ติดกัน สลับคู่ที่ไม่เป็นไปตามลำดับ, รอบละหนึ่งรอบ ต่อครั้ง; รอบที่ไม่มีการสลับจะสิ้นสุดกระบวนการ การเรียงแบบควิก เลือกไอเท็มตรงกลางของรายการเป็นพิวต์, แบ่งไอเท็มที่เหลือออกเป็น "น้อยกว่าพิวต์" และ "มากกว่าพิวต์" รายการย่อย (รักษาลำดับเดิม) แล้วเรียกซ้ำ — ต้องระบุพิวต์และรายการหลังแต่ละการแบ่งเสมอ ของรายการเป็นแกนหมุน, แบ่งส่วนที่เหลือออกเป็น "น้อยกว่าแกน", "เท่ากับแกน" และ "มากกว่า แกน" กลุ่ม (รักษาทุกสำเนาไว้); เรียงลำดับกลุ่มที่เล็กกว่าและใหญ่กว่าแบบ.saved; ต้องระบุแกนและ รายการหลังจากการแบ่งส่วนแต่ละครั้ง สเปกกำหนดการเลือก ITEM กลางไปที่วิธีการที่นิยามไว้ใน กล่องแรกที่มีพื้นที่เหลือ; ฟิสต์-ฟิตเดครีซิ่ง เรียงไอเท็มจากใหญ่ไปเล็กก่อนแล้วใช้ ตำแหน่ง $\tfrac{n+1}2$. บรรจุถุง: First-fit วางแต่ละ ITEM ลงในถุงแรกที่มีพื้นที่เหลือ; first-fit decreasing เรียงลำดับ ITEM จากใหญ่ไปเล็กก่อนแล้วใช้ first-fit; การบรรจุเต็มถุงมองหาชุดที่เติมถุงให้เต็มพอดี การบรรจุแบบเต็มช่องแรก; การบรรจุแบบเต็มช่องมองหาชุดที่เติมช่องให้พอดี

ตัวอย่างวิธีทำ — เรียงลำดับแบบเร็ว (ต้นฉบับ). เรียบ 9, 2, 7, 5, 3, 4, 6. รายการตรงกลาง (ตำแหน่ง 4 ของ 7) คือ 5: น้อยกว่า = 2, 3, 4; มากกว่า = 9, 7, 6, ให้ 2, 3, 4, 5, 9, 7, 6. sublist 2, 3, 4 (pivot 3): 2, 3, 4 — เรียบแล้ว. Sublist 9, 7, 6 (pivot 7): 6, 7, 9 — เรียงแล้ว. รายการสุดท้าย: 2, 3, 4, 5, 6, 7, 9.

ตัวอย่างวิธีทำ — การบรรจุในกล่อง (ต้นฉบับ). กล่องมีความจุ 10; รายการ 7, 5, 4, 3, 6, 2 (รวม 27, ดังนั้นอย่างน้อยต้อง 3 กล่อง). First-fit: 7→b1, 5→b2 (7+5 > 10), 4→b2 (9), 3→b1 (10), 6→b3, 2→b3 (8): กล่อง (7,3), (5,4), (6,2). First-fit decreasing: 7, 6, 5, 4, 3, 2: 7→b1, 6→b2, 5→b3 (6+5 > 10), 4→b2 (10), 3→b1 (10), 2→b3 (7): bins (7,3), (6,4), (5,2) — และยังได้ 3 กล่อง.

1.2.1 1.2.2

ต้นไม้หาค่าต่ำสุด

ซ้าย: กราฟที่มีน้ำหนักบน A, B, C, D โดยเส้นขอบ MST AC 2, CD 1, CB 3 ถูกเน้นและฉลาก Dijkstra 0, 2, 3, 8 อยู่ที่จุดยอด ขวา: พื้นที่ที่เป็นไปได้ของโปรแกรมเชิงเส้นที่มีจุดยอด (0,0), (7,0), (4,6), (0,10) และเส้นวัตถุประสงค์สัมผัสจุดสูงสุดที่ (4,6) — Left: a weighted network on A, B, C, D with the MST edges AC 2, CD 1, CB 3 highlighted and Dijkstra labels 0, 2, 3, 8 at the vertices. Right: the feasible region of a linear program with vertices (0,0), (7,0), (4,6), (0,10) and the objective line touching the optimum at (4,6).

A minimum spanning tree (MST) เชื่อมต่อทุกจุดยอดด้วยน้ำหนักรวมต่ำที่สุด. อัลกอริทึมของ Kruskal: เรียบขอบตามน้ำหนัก เพิ่มขอบที่เล็กที่สุดที่ไม่ NOT สร้างวงจร (ปฏิเสธและข้ามไปเมื่อจะสร้างวงจร). Prim's algorithm: ขยาย ต้นไม้จากจุดเริ่มต้นใดๆ โดยเพิ่มขอบที่ประหยัดที่สุดจากต้นไม้ไปยังจุดใหม่ ซ้ำๆ. รูปแบบเมทริกซ์ของ Prim: ตัดแถวเริ่มต้นออก, วงกลมค่าที่เหลือที่น้อยที่สุดใน คอลัมน์ของจุดที่เลือกไว้, และดำเนินการต่อไป. Kruskal เป็นแบบขับเคลื่อนด้วยขอบ (ดีสำหรับกราฟที่วาด), Prim เป็นแบบขับเคลื่อนด้วยจุดยอด (ดีสำหรับเมทริกซ์). ทั้งสองให้ผลรวมเดียวกัน; ขอบอาจต่างกันเฉพาะเมื่อมีน้ำหนักเท่ากันเท่านั้น. เครือข่าย); Prim เป็นแบบขับเคลื่อนจากจุดยอด (เหมาะสำหรับเมทริกซ์) ทั้งสองให้ผลรวมเท่ากัน; เส้นขอบอาจ แตกต่างกันเฉพาะเมื่อค่าน้ำหนักเท่ากัน

ตัวอย่างที่คำนวณแล้ว (ต้นฉบับ). ขอบ AB 4, AC 2, BC 3, BD 5, CD 1: Kruskal เลือก CD 1, AC 2, BC 3 (B เชื่อมต่อ — ไม่มีวงจร), จากนั้นปฏิเสธ AB 4 และ BD 5 (เกิดวงจร): ผลรวม MST 6. Prim จาก A: AC 2, CD 1 (ขอบที่มีค่าน้อยที่สุดจาก {A,C} ไปยังจุดยอดใหม่), CB 3: ได้ต้นไม้เดียวกัน และ ผลรวม 6 ✓. ต้องระบุลำดับขอบที่เลือกและให้ผลรวมเสมอ.

คำศัพท์ ฝึกฝน

English	ไทย
Prim's algorithm/prɪmz ˈælɡərɪθəm/	อัลกอริทึมของพรีม
activity-on-arc network/ækˈtɪvɪti ɒn ɑːk ˈnetwɜːk/	เครือข่ายกิจกรรมบนส่วนโค้ง
bin packing/bɪn ˈpækɪŋ/	ปัญหาการจัดกล่อง
minimum spanning tree/ˈmɪnɪməm ˈspænɪŋ triː/	ต้นไม้สร้างน้อยที่สุด
nearest neighbour algorithm/ˈnɪərɪst ˈneɪbə ˈælɡərɪθəm/	อัลกอริทึมเพื่อนบ้านใกล้สุด

1.2.2

เส้นทางสั้นที่สุด

สำหรับน้ำหนักขอบที่ไม่เป็นลบ อัลกอริทึมของไดสตรา จะติดฉลากจุดยอดด้วยระยะทางรวมที่น้อยที่สุด ที่พบจนถึงปัจจุบัน: ป้ายจุดเริ่มต้น 0; ซ้ำๆ เลือกจุดยอดที่ยังไม่มีป้ายที่มีค่า ชั่วคราวน้อยที่สุด เปลี่ยนเป็นถาวร และอัปเดตเพื่อนบ้านของมัน (ใหม่ = ถาวร + น้ำหนัก, เฉพาะถ้าค่าน้อยกว่า) บันทึกลำดับการทำให้เป็นถาวรและค่าสุดท้าย ป้าย; สามารถกู้คืนเส้นทางได้โดยการย้อนกลับผ่านจุดยอดwhose label equals the final label minus the connecting weight. final label minus the connecting weight.

ตัวอย่างวิธีทำ (ต้นฉบับ). ขอบ AB 4, AC 2, BC 1, BD 5, CD 8. ป้าย: A = 0 ถาวร; C = 2 ถาวร; B = min(4, 2+1) = 3 ถาวร; D = min(3+5, 2+8) = 8 ถาวร. เส้นทาง สั้นที่สุดจาก A ไป D มีความยาว 8: A–C–B–D (ย้อนกลับ: 8 = 3 + 5 ที่ B, 3 = 2 + 1 ที่ C).

1.3.1

ปัญหาผู้ส่งจดหมายจีน

ปัญหา ตรวจสอบเส้นทาง (ผู้ส่งจดหมายจีน) เดินทุก EDGE อย่างน้อย ครั้งและกลับไปยังจุดเริ่มต้น. ความยาวรวม = ผลรวมของทุกขอบ + วิธีสั้นที่สุดในการ ทำซ้ำขอบเพื่อให้ทุกจุดยอดมีดีกรีคู่. หาจุดยอดที่มีดีกรีคี่ (สูงสุดสี่จุด) รายการ จับคู่ของพวกมัน, เลือกการจับคู่ที่มีน้ำหนักรวมต่ำสุด, และทำซ้ำเส้นขอบเหล่านั้น. ระบุ การจับคู่ก่อนผลลัพธ์สุดท้าย

ตัวอย่างวิธีทำ (ต้นฉบับ). ขอบ AB 4, AC 2, BC 3, BD 5, CD 1 (รวม 15). ดีกรี: A 2, B 3, C 3, D 2 — โหนดที่มีดีกรีคี่คือ B และ C ดังนั้นเพิ่มขอบ BC (น้ำหนัก 3): เส้นทางปิดที่สั้นที่สุด ที่เดินผ่านทุกขอบอย่างน้อยหนึ่งครั้งมีความยาว 15 + 3 = 18.

1.3.2 1.3.3 1.3.4

The travelling salesman problem

The classical travelling salesman problem tours every VERTEX exactly once และกลับคืนมาบนกราฟที่สมบูรณ์ด้วยอสมการสามเหลี่ยม ขอบเขต: ค่า MST ของเครือข่ายที่คูณสองให้เส้นทางขอบเขตบน (เดินแต่ละขอบ MST สองครั้ง); การที่ดีกว่า สร้างเส้นทาง: จากโหนดเริ่มต้น ไปยังโหนดที่ยังไม่ได้เยี่ยมที่ใกล้ที่สุดซ้ำๆ แล้วกลับ. แปลงเป็นเครือข่ายสมบูรณ์ของระยะทางสั้นที่สุดก่อน เมื่อกราฟไม่สมบูรณ์ (ผ่าน Dijkstra หรือการสังเกต). เริ่มก่อนหน้าพร้อม float เป็นช่องว่างตามท้าย; การจัดตารางงานจัดสรรพนักงานวันต่อวัน. จุดที่ไม่ได้ไป-visita แล้ว กลับมา แปลงเป็นเครือข่ายสมบูรณ์ด้วยระยะทางสั้นที่สุดก่อน เมื่อกราฟไม่สมบูรณ์ (ผ่าน Dijkstra หรือการสังเกต)

ตัวอย่างที่คำนวณแล้ว (ต้นฉบับ). เครือข่ายสมบูรณ์: AB 4, AC 2, AD 7, BC 3, BD 5, CD 6 (ซึ่ง อสมการสามเหลี่ยมเป็นจริงตลอดทั้ง network. เพื่อนที่ใกล้ที่สุดจาก A: A–C (2), C–B (3), B–D (5), D–A (7): ความยาวเส้นทาง 17 — เป็นขอบเขตบน การหา MST คือ AC + BC + BD = 10 ดังนั้นการทำสองเท่า จะได้ขอบเขตบนแบบหยาบ 20, ปรับเป็น 17 ด้วยการตัดทอน; ขอบเขตล่างจากการลบ A (MST of B, C, D is 3 + 5 = 8, plus A's two cheapest edges AC + AB = 2 + 4 = 6) is 14. The เส้นทางที่ดีที่สุดอยู่ระหว่าง 14 และ 17.

คำศัพท์ ฝึกฝน

English	ไทย
classical travelling salesman problem/ˈklæsɪkl ˈtrævəlɪŋ ˈseɪlzmən ˈprɒbləm/	ปัญหาผู้ขายของเดินทางแบบคลาสสิก

1.4.1 1.4.2 1.4.3 1.4.4

การวิเคราะห์เส้นทางวิกฤต

จำลองโครงการเป็น เครือข่ายกิจกรรมบนขอบ จากตารางลำดับความสำคัญ; activity-on-arc (dummies) (ขอบน้ำหนักศูนย์) แก้ไขการพึ่งพาที่จุดปลายร่วมกันไม่สามารถจัดการได้ เส้นทางการวิกฤต (critical path) คือเส้นทางที่ยาวที่สุดผ่านเครือข่าย: ซึ่ง ระยะเวลาโครงการ คำนวณ เวลาเหตุการณ์เริ่มต้นก่อนสุด (forward pass: ค่าสูงสุดของ การมาถึง) และ เวลาเหตุการณ์ล่าสุด (backward pass: ค่าต่ำสุดของการออก) ความลอยตัวรวม (total float) ของกิจกรรม = เวลาสิ้นสุดล่าสุด − เวลาเริ่มต้นก่อนสุด − ระยะเวลา; กิจกรรมที่มีเส้นทางการวิกฤตมีความลอยตัวเป็นศูนย์ แผนภูมิกานต์ (Gantt chart) แสดงแต่ละกิจกรรมด้วยแท่งจากเวลาเริ่มต้นก่อนสุดพร้อมพื้นที่ว่างตามหลังแทนความลอยตัว; การวางแผนจัดสรรแรงงานวันต่อวัน สำหรับฐานบวก, กฎของเลขชี้กำลัง ใช้ได้กับเลขชี้กำลังเป็นจำนวนตรรกยะ. ฐานศูนย์และลบจำเป็นต้องมีข้อจำกัดในโดเมนจริง:

ตัวอย่างที่คำนวณแล้ว (ต้นฉบับ). กิจกรรม A (3 วัน), B (4), C (4 หลัง A), D (1 หลัง B), E (5 หลัง C และ D). เส้นทาง A–C–E = 12 วัน; เส้นทาง B–D–E = 10 วัน: เส้นทางวิกฤตคือ A–C–E และโครงการใช้เวลา 12 วัน; Total float ของ D = 12 − (4 + 1 + 5) = 2 วัน.

ซ้าย: ช่อง first-fit จำนวนสามช่องที่มีความจุ 10 เก็บไอเท็ม (7,3), (5,4), (6,2) ขวา: กราฟกิจกรรมบนลูกศรที่มีเหตุการณ์ 1-5, กิจกรรม A 3, B 4, C 4, D 1 และ E 5, ลูกศรวิกฤตถูกเน้น และเวลาเหตุการณ์ 0, 3/4, 7, 12 — ซ้าย: กล่อง first-fit สามกล่องมีความจุ 10 ใส่ไอเทม (7,3), (5,4), (6,2). ขวา: เครือข่าย activity-on-arc มีเหตุการณ์ 1-5, กิจกรรม A 3, B 4, C 4, D 1 และ E 5, ขอบวิกฤตถูกเน้น, และเวลาเหตุการณ์ 0, 3/4, 7, 12.

คำศัพท์ ฝึกฝน

English	ไทย
Dijkstra's algorithm/ˈdeɪkstrəz ˈælɡərɪθəm/	อัลกอริทึมของดิจกสตรา
Gantt chart/ɡænt tʃɑːt/	แผนภูมิแกลต์
Kruskal's algorithm/ˈkrʌsklz ˈælɡərɪθəm/	อัลกอริทึมของครุสคาล
critical path/ˈkrɪtɪkl pæθ/	เส้นทางสำคัญ
dummy/ˈdʌmi/	กิจกรรมเทียม
earliest event times/ˈɜːlɪɪst ɪˈvent taɪmz/	เวลาเกิดเหตุเร็วที่สุด
latest event times/ˈleɪtɪst ɪˈvent taɪmz/	เวลาเกิดเหตุช้าสุด
total float/ˈtəʊtl fləʊt/	total float
vertex method/ˈvɜːteks ˈmeθəd/	วิธีจุดยอด
route inspection (Chinese postman) problem/ruːt ɪnˈspekʃn ˈprɒbləm/	ปัญหาการตรวจสอบเส้นทาง (ผู้ส่งจดหมายจีน)

1.5.1 1.5.2 1.5.3

การวางแผนเชิงเส้น

แรเงาพื้นที่ที่เป็นไปได้ แล้วใช้ วิธีไม้บรรทัด (เลื่อนไม้บรรทัดไปตามความชันของฟังก์ชันวัตถุประสงค์) หรือ วิธีจุดยอด (คำนวณค่าฟังก์ชันวัตถุประสงค์ที่จุดยอดแต่ละจุดของพื้นที่ที่เป็นไปได้) คำตอบจำนวนเต็ม: ตรวจสอบจุดจำนวนเต็มใกล้จุดยอดที่เหมาะสมภายในพื้นที่ ข้อจำกัดในรูปอสมการ รวมถึง $x, y \ge 0$. แก้โจทย์ตัวแปรสองตัวโดยวิธีกราฟ: ทาสีพื้นที่ที่เป็นไปได้ แล้วใช้ วิธีไม้บรรทัด (เลื่อนไม้บรรทัดไปตาม ความชันของฟังก์ชันเป้าหมาย) หรือ วิธีจุดยอด (แทนค่าฟังก์ชันเป้าหมายที่จุดยอด ของแต่ละจุดของพื้นที่ที่เป็นไปได้) คำตอบจำนวนเต็ม: ทดสอบจุดจำนวนเต็มใกล้จุดยอดที่ อยู่ในพื้นที่

1.5.1 1.5.2 1.5.3

รายการตรวจสอบก่อนจะถือว่าหน่วยนี้จบแล้ว

ทำ Bubble Sort และ Quick Sort โดยแสดงทุกรอบและจุดแบ่ง; จัดกล่องแบบ First-fit, First-fit decreasing และ Full-bin พร้อมแสดงการจัดวาง
หาค่า MST โดยใช้ Kruskal และ Prim (รูปแบบโหนดและรูปแบบเมทริกซ์); วาดเครือข่ายจากเมทริกซ์และกลับคืนมา
ใช้ดิจสตราพร้อมฉลากตามลำดับความคงที่; ฟื้นคืนเส้นทาง ไม่ใช่เพียงระยะทาง
แก้ปัญหาการตรวจสอบเส้นทาง: โหนดคี่, การจับคู่ทั้งหมดที่มีน้ำหนัก, การซ้ำน้อยที่สุด, ความยาวรอบเดินทั้งหมด
ขอบเขตของ TSP แบบคลาสสิก: ต้นไม้ออกแบบต่ำสุดสองเท่าและตัดทอนเพื่อขอบบน, การลบต้นไม้ออกแบบต่ำสุดเพื่อขอบล่าง; ใช้วิธีเพื่อนใกล้สุดบนเครือข่ายระยะสั้นที่สุดที่สมบูรณ์
สร้างเครือข่ายกิจกรรมด้วยตัวกลาง; การส่งผ่านไปข้างหน้าและย้อนกลับสำหรับเวลาเหตุการณ์; ค่าลอยรวม; ระบุเส้นทางวิกฤต; วาดแผนภูมิแกนต์และตารางเวลา

ตัวอย่างทำ — แล็กซาร์โปรแกรม (ต้นฉบับ). หาค่าสูงสุด $P = 3x + 2y$ ภายใต้ข้อจำกัด $x + y \le 10$, $2x + y \le 14$, $x, y \ge 0$. จุดยอดของพื้นที่ที่เป็นไปได้คือ $(0,0)$, $(7,0)$, $(4,6)$, $(0,10)$; ประเมิน $P$: 0, 21, 24, 20 — ค่าสูงสุดคือ $P = 24$ ที่ $(4,6)$, ซึ่งข้อจำกัดทั้งสองเป็นค่าแน่น

ตั้งสมการแล็กซาร์โปรแกรมให้ครบถ้วน; แก้ด้วยกราฟโดยใช้ไม้บรรทัดหรือวิธีจุดยอด; หาคำตอบจำนวนเต็มที่ดีที่สุด

คำศัพท์ ฝึกฝน

English	ไทย
bubble sort/ˈbʌbl sɔːt/	การเรียงลำดับแบบฟองอากาศ
quick sort/kwɪk sɔːt/	การเรียงลำดับแบบควิก
ruler method/ˈruːlə ˈmeθəd/	วิธีไม้บรรทัด