เส้นทางวิกฤติ (Critical Path)

Critical Path

จากกราฟต่อไปนี้

เราเรียกว่า Activity Node Graph เนื่องจากในแต่ละจุดจะบอกระยะเวลาที่ต้องใช้ในกิจกรรมนั้นๆเอา เช่น F (3) หมายถึงถ้าจะทำกิจกรรม F ต้องใช้เวลา 3 หน่วย เป็นต้น
เราสามารถแปลง Activity Node Graph ให้กลายเป็น Event Node Graph ได้ดังนี้

นี่เป็นเพียงขั้นที่ 1 หลังจากนั้น ให้รวมเส้นที่เหมือนกันเข้าด้วยกันโดยเพิ่ม Dummy Node เข้าไป และกำหนดให้เส้นที่พุ่งเข้า Dummy Node มีค่าเป็น 0 ดังนี้

สังเกตโหนด 6’ 8’ และ 10’ เป็น Dummy Node ที่เพิ่มเข้าไปเพื่อรวมเส้นที่ชื่อเดียวกันเข้าด้วยกัน
หลังจากนั้นให้คำนวณหาค่า Max Time แต่ละโหนด ดังนี้

หลังจากนั้นให้คำนวณหาค่า Min Time โดยการคำนวณค่า Min จะต้องไล่จากโหนดสุดท้ายกลับมาหาโหนดแรก ดังนี้

เมื่อคำนวณค่า Min เสร็จจะได้กราฟดังนี้

เมื่อได้ Min กับ Max ครบทุกโหนดแล้ว เราคำนวณ Slack Time ได้โดยนำ Min ของตัวถัดไป – Max ของตัวก่อนหน้า – ระยะเวลาที่ใช้ ดังนี้

เมื่อคำนวณหา Slack Time ครบทุกเส้นแล้วจะได้ค่าดังนี้

สังเกตว่าเส้นทางที่เป็น zero edge slack (มีค่า slack เป็น 0 ตลอดทาง) คือ Critical Path นั่นเอง


ความคิดเห็น

แสดงความคิดเห็น

โพสต์ยอดนิยมจากบล็อกนี้

การจัดเรียงแบบ Quick Sort

รูปภาพ
Quick Sort การจัดเรียงข้อมูลแบบ Quick Sort มีขั้นตอน 4 ขั้นคือ 1.       ถ้าจำนวนตัวเลขมีเพียง 0 หรือ 1 ตัวไม่ต้องทำงาน ให้หยุดทำได้ 2.       เลือกตัวเลขขึ้นมาหนึ่งตัว เรียกเลขตัวนี้ว่า Pivot สมมุติว่าคือ v 3.       แบ่งกลุ่มตัวเลขออกเป็น 2 กลุ่ม โดยกลุ่มที่ 1 จะต้องเป็นเลขที่น้อยกว่า v ทั้งหมด และกลุ่มที่ 2 จะต้องเป็นเลขที่มากกว่า v ทั้งหมด 4.       กลับไปที่ขั้นตอนที่ 1 ใหม่ โดยทำกับเลข กลุ่มที่ 1 และทำกับเลขกลุ่มที่ 2 ทำแบบนี้ไปเรื่อยๆ จนเลขในกลุ่มย่อยๆ ลดเหลือเพียงแค่ 0 หรือ 1 ตัวก็หยุดได้ ตัวอย่างการทำ Quick Sort เช่น ถ้ามีเลขอยู่ 10 ตัวอยู่ในอะเรย์ a ดังนี้ ถ้าจะจัดเรียงแบบ Quick Sort เราจะต้องหา Pivot ก่อนวิธีการหา Pivot ที่ไม่แนะนำคือ o     ใช้เลขตัวแรกสุดเป็น Pivot แบบนี้เสี่ยงในกรณีที่เลขในชุดนั้นจัดเรียงไว้เรียบร้อยแล้วจะได้ O(N 2 ) o     ใช้วิธีสุ่มเลขแบบ Random มีข้อเสียคือ อัลกอริธึมการสร้างเลขสุ่มเสียเวลาค่อนข้างนาน เราจะเลือก Pivot โดยใช้วิธี Median-of-Threee คือเลือกเลขตัวที่ 1 ตัวสุดท้าย และตัวตรงกลางขึ้นมา และหาค่า Median ของเลข 3 ตัวนี้ เช่นใ
อ่านเพิ่มเติม

กราฟอัลกอริธึม

รูปภาพ
กราฟอัลกอริธึม กราฟประกอบด้วยเซ็ตของจุดและด้าน จุดคือ Vertice และด้านคือ Edge เขียนในลักษณะเซ็ตของคณิตศาสตร์ได้เป็น G = (V, E) โดยสมมุติว่า G คือกราฟ 1 ตัว และ V คือ เซ็ตของ Vertice ส่วน E คือเซ็ตของ Edge รูปภาพ 1 ตัวอย่างของ Set G ที่ใช้แทนกราฟ สังเกตว่าเซ็ต E จะเป็นคู่อันดับ (Ordered Pair) ของ Vectice 2 ตัว เช่น (a, b) หมายถึงเส้นที่เชื่อมระหว่าง a ไป b ดังนั้นกล่าวได้ว่าคู่อันดับ (v, w) โดย v และ w ทุกตัวต้องเป็นสมาชิกของ V หรือเขียนแบบคณิตศาสตร์ได้เป็น (v, w) Î V บางครั้งเราจะเรียก edge ว่าเป็น arc ถ้าคู่อันดับมีการจัดเรียงกันมาตามลำดับและมีทิศทาง (directed) กราฟแบบที่แต่ละเส้นมีทิศทางกำกับไว้ เราจะเรียกว่า Directed Graph หรือย่อๆคือ digraphs สมมุติว่ามีจุดมุม Vertex อยู่จุดหนึ่ง ชื่อว่า w เราบอกว่าจุด w นี้ต่อติด (adjacent) กับจุด v ก็ต่อเมื่อ (w, v) Î E แต่ถ้ากราฟนี้เป็นแบบไม่มีทิศทาง เส้น (w, v) ย่อมเทียบเท่ากับเส้น (v, w) ดังนั้นถ้า w adjacent to v ดังนั้น v ก็ย่อมจะ adjacent to w ด้วย หรือพูดง่ายๆก็คือมันต่อติดกันทั้งขาไปและขากลับเพราะไม่สนใ
อ่านเพิ่มเติม

Huffman's Code

รูปภาพ
Huffman’s Code สมมุติว่าเราต้องการบีบอัดไฟล์ข้อมูล (compression) เช่นพวก zip ไฟล์ ปกติแล้วเราจะเปลี่ยนตัวอักษรที่อยู่ในไฟล์ให้กลายเป็นบิตข้อมูล (bit) ที่มีขนาดเล็กกว่าบิตข้อมูลธรรมดา เช่น ปกต ิเลข 5 อาจจะเป็นตัวเลข 0000 0101 ถ้าเก็บแบบ 8 บิต แต่ถ้าเราบีบอัดแล้วอาจจะใช้ที่เก็บจริงๆแค่ 3 บิตคือ 101 เท่านั้น เช่นถ้าในไฟล์เรามีข้อมูลตัวอักษร a, e, i, s, t, space bar, new line (สำหรับ space bar ก็คือช่องไฟ และ new line คือ ขึ้นบรรทัดใหม่ พวกนี้เป็นตัวอักษรล่องหน มองไม่เห็น แต่กินพื้นที่ไฟล์ด้วยเช่นกัน) เราต้องการบีบอัดไฟล์นี้ให้มีขนาดเล็กเราอาจจะเปลี่ยนตัวอักษรเหล่านี้ให้กลายเป็นรหัสขนาด 3 บิต ดังตารางต่อไปนี้ จากตารางข้างต้น สมมุติว่าในไฟล์มีข้อมูลดังนี้ aaeeiiissttt  a  ti เราสามารถแปลงให้กลายเป็นรหัสตามที่กำหนดไว้ได้ดังนี้ 000 000 001 001 010 010 010 011 011 100 100 100 110 000 101 101 100 010 เมื่อนับจำนวนบิตดูจะพบว่ามีขนาดทั้งหมด เท่ากับ 18 x 3 = 54 บิต สมมุติว่าถ้าในไฟล์มีตัว a อยู่ 10 ตัว ตัว e อยู่ 15 ตัว ตัว i อยู่ 12 ตัว ตัว s อยู่ 3 ตัว ตัว t อยู่ 4 ตั
อ่านเพิ่มเติม