กำหนดการเชิงเส้นและขั้นตอนวิธีการประมาณ

ทางลัด: ความแตกต่างความคล้ายคลึงกันค่าสัมประสิทธิ์การเปรียบเทียบ Jaccardการอ้างอิง

ความแตกต่างระหว่าง กำหนดการเชิงเส้นและขั้นตอนวิธีการประมาณ

กำหนดการเชิงเส้น vs. ขั้นตอนวิธีการประมาณ

กำหนดการเชิงเส้น เป็นคณิตศาสตร์ประยุกต์แขนงหนึ่งที่คิดค้นขึ้น เพื่อแก้ปัญหาให้เป็นไปตามจุดประสงค์ของมนุษย์ โดยมีแนวคิดที่ว่า ให้เพียงพออย่างสูงสุดในทรัพยากรที่มีจำกัด สามารถใช้คำนวณเพื่อแก้ปัญหาได้หลายอย่าง เช่น คำนวณการผลิตสินค้าให้ได้มากที่สุด แต่เสียค่าใช้จ่ายน้อยที่สุด, หาวิธีการเคลื่อนย้ายทหารให้มากที่สุดโดยที่เสียค่าใช้จ่ายน้อยที่สุด, ผลิตสินค้าจำนวนน้อยที่สุด แต่ทำกำไรได้มากที่สุด หรือหาว่า หากบริษัทหนึ่งผลิตสินค้า 2 ประเภท ต้องผลิตอย่างละกี่ชิ้นจึงจะได้กำไรสูงสุด เป็นต้น กำหนดการเชิงเส้น จะอยู่ในรูปแบบทางคณิตศาสตร์ของสมการเชิงเส้นและอสมการเชิงเส้น แล้วหาค่าสูงสุด ต่ำสุดของฟังก์ชันที่สอดคล้องกับสมการ (และอสมการ) ที่กำหนด ตัวแบบคณิตศาสตร์ประกอบด้ว. ั้นตอนวิธีการประมาณ ในศาสตร์ด้านวิทยาการคอมพิวเตอร์นั้น เป็นวิธีการหนึ่งที่ใช้สำหรับจัดการกับปัญหาการหาค่าเหมาะที่สุดประเภทเอ็นพี-ฮาร์ด เนื่องจากเป็นที่เชื่อกันว่าไม่มีขั้นตอนวิธีใดที่มีประสิทธิภาพ (ทำงานได้รวดเร็ว) ที่สามารถแก้ไขปัญหาเอ็นพี-ฮาร์ดได้คำตอบที่เที่ยงตรง จึงได้เกิดความพยายามที่จะหาคำตอบที่อาจจะไม่ถูกต้องที่สุด แต่สามารถหาได้ในเวลาโพลิโนเมียล ข้อแตกต่างของขั้นตอนวิธีประเภทนี้กับฮิวริสติก (ซึ่งมักเป็นการหาคำตอบที่ดีในระดับหนึ่งโดยใช้เวลาไม่มากนัก) ก็คือ ขั้นตอนวิธีประมาณต้องการคำตอบที่สามารถพิสูจน์ได้ว่าดีเพียงใด และพิสูจน์ได้ว่ามีขอบเขตการใช้เวลาไม่เกินเท่าใด ขั้นตอนวิธีในอุดมคติมักจะต้องผิดไปจากคำตอบจริงไม่เกินค่าคงที่ค่าหนึ่ง (เช่น คลาดเคลื่อนไม่เกิน 5%) ปัญหาเอ็นพี-ฮาร์ดมีความหลากหลายอย่างมากในแง่ของการประมาณค่า บางปัญหาสามารถประมาณได้เป็นอัตราส่วนขนาดหนึ่ง (ขั้นตอนวิธีสำหรับประมาณปัญหาเหล่านี้มักเรียกกันว่า แบบแผนการประมาณในเวลาโพลิโนเมียล (polynomial time approximation scheme) หรือ PTAS) ส่วนบางปัญหานั้นก็ไม่สามารถที่จะประมาณได้เลย ตัวอย่างของขั้นตอนวิธีประมาณที่มักกล่าวถึงกัน ได้แก่ ขั้นตอนวิธีสำหรับการคลุมจุดยอดในกราฟ โจทย์คือเลือกจุดยอดจำนวนน้อยที่สุด ให้ทุก ๆ ด้านมีปลายอย่างน้อยข้างหนึ่งถูกเลือก ขั้นตอนวิธีสำหรับประมาณปัญหานี้คือ หาด้านที่ยังไม่ถูกคลุม (ยังไม่มีปลายข้างใดถูกเลือก) มา แล้วเลือกปลายทั้งคู่ของด้านนี้ ขั้นตอนวิธีนี้ให้ผลลัพธ์ที่มีขนาดไม่เกินสองเท่าของคำตอบที่ดีที่สุด วิธีหนึ่งที่ใช้ได้ผลบ่อยในการหาขั้นตอนวิธีประมาณคือ การพิจารณาการผ่อน (relax) กำหนดการเชิงเส้น ใช่ว่าขั้นตอนวิธีประมาณทุกอันจะเหมาะสมกับงานในทางปฏิบัติ ตัวอย่างเช่น คนส่วนใหญ่คงไม่ค่อยประทับใจนัก กับขั้นตอนวิธีที่ช่วยให้พวกเขาจ่ายเงินไม่เกิน 20 เท่าของค่าใช้จ่ายที่ถูกที่สุด และเช่นกัน บางขั้นตอนวิธีอาจมีเวลาในการทำงานที่ไม่ค่อยดีนัก (ถึงแม้จะเป็นเวลาโพลิโนเมียลก็ตาม) เช่น O (n^) ข้อจำกัดอีกอย่างหนึ่งของวิธีการนี้ก็คือ มันใช้ได้กับปัญหาการหาค่าเหมาะที่สุด (optimization problem) เท่านั้น ไม่สามารถใช้กับปัญหาการตัดสินใจ“แท้ ๆ” เช่น ปัญหาความสอดคล้องแบบบูล ได้.