โลโก้
ยูเนี่ยนพีเดีย
การสื่อสาร
ดาวน์โหลดได้จาก Google Play
ใหม่! ดาวน์โหลด ยูเนี่ยนพีเดีย บน Android ™ของคุณ!
ฟรี
เร็วกว่าเบราว์เซอร์!
 

ขั้นตอนวิธีการประมาณ

ดัชนี ขั้นตอนวิธีการประมาณ

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

7 ความสัมพันธ์: กำหนดการเชิงเส้นวิทยาการคอมพิวเตอร์ศึกษาสำนึกจุดยอดขั้นตอนวิธีปัญหาการตัดสินใจปัญหาความสอดคล้องแบบบูล

กำหนดการเชิงเส้น

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

ใหม่!!: ขั้นตอนวิธีการประมาณและกำหนดการเชิงเส้น · ดูเพิ่มเติม »

วิทยาการคอมพิวเตอร์

วิทยาการคอมพิวเตอร์ หรือ วิทยาศาสตร์คอมพิวเตอร์ (Computer science) เป็นศาสตร์เกี่ยวกับการศึกษาค้นคว้าทฤษฎีการคำนวณสำหรับคอมพิวเตอร์ และทฤษฎีการประมวลผลสารสนเทศ ทั้งด้านซอฟต์แวร์ ฮาร์ดแวร์ และ เครือข่าย ซึ่งวิทยาการคอมพิวเตอร์นั้นประกอบด้วยหลายหัวข้อที่เกี่ยวข้องกับคอมพิวเตอร์ ตั้งแต่ระดับนามธรรม หรือความคิดเชิงทฤษฎี เช่น การวิเคราะห์และสังเคราะห์ขั้นตอนวิธี ไปจนถึงระดับรูปธรรม เช่น ทฤษฎีภาษาโปรแกรม ทฤษฎีการพัฒนาซอฟต์แวร์ ทฤษฎีฮาร์ดแวร์คอมพิวเตอร์ และ ทฤษฎีเครือข่าย ในแง่ของศาสตร์เกี่ยวกับคอมพิวเตอร์นั้น วิทยาการคอมพิวเตอร์เป็นหนึ่งในห้าสาขาวิชาคอมพิวเตอร์ ซึ่งประกอบด้วย สาขาวิทยาการคอมพิวเตอร์ หรือวิทยาศาสตรคอมพิวเตอร์ สาขาวิศวกรรมคอมพิวเตอร์ สาขาวิศวกรรมซอฟต์แวร์ สาขาเทคโนโลยีสารสนเทศ หรือเทคโนโลยีสารสนเทศและการสือสาร และ สาขาคอมพิวเตอร์ธุรกิจ หรือ ระบบสารสนเทศทางธุรก.

ใหม่!!: ขั้นตอนวิธีการประมาณและวิทยาการคอมพิวเตอร์ · ดูเพิ่มเติม »

ศึกษาสำนึก

ปกติการออกแบบหรือค้นหาขั้นตอนวิธี หรือขั้นตอนวิธี ที่ดีเพื่อการหาผลลัพธ์หรือแก้ปัญหาด้วยคอมพิวเตอร์นั้นมีเป้าหมายพื้นฐานอยู่ 2 ประการ คือ.

ใหม่!!: ขั้นตอนวิธีการประมาณและศึกษาสำนึก · ดูเพิ่มเติม »

จุดยอด

อด (vertex) อาจหมายถึง; คณิตศาสตร.

ใหม่!!: ขั้นตอนวิธีการประมาณและจุดยอด · ดูเพิ่มเติม »

ขั้นตอนวิธี

ั้นตอนวิธี หรือ อัลกอริทึม (algorithm) หมายถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic) โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน ในการทำงานอย่างเดียวกัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time), และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง หนึ่งในขั้นตอนวิธีอย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้.

ใหม่!!: ขั้นตอนวิธีการประมาณและขั้นตอนวิธี · ดูเพิ่มเติม »

ปัญหาการตัดสินใจ

ปัญหาการตัดสินใจ เป็นปัญหาในทฤษฎีการคำนวณได้และทฤษฎีความซับซ้อนในการคำนวณ ซึ่งพิจารณาค่าอินพุตและตอบเพียงว่า "ใช่" หรือ "ไม่ใช่" เท่านั้น เช่นปัญหาที่ถามว่าจำนวนเต็ม x เป็นจำนวนเฉพาะใช่หรือไม.

ใหม่!!: ขั้นตอนวิธีการประมาณและปัญหาการตัดสินใจ · ดูเพิ่มเติม »

ปัญหาความสอดคล้องแบบบูล

ปัญหาความสอดคล้องแบบบูล หรือ SAT (Boolean satisfiability) เป็นปัญหาการตัดสินใจอย่างหนึ่งที่ถูกกล่าวถึงบ่อย ๆ ในศาสตร์ทางด้านทฤษฎีความซับซ้อนในการคำนวณ ตัวอย่างของปัญหา (instance) สำหรับปัญหานี้ก็คือ นิพจน์บูลีน (boolean expression) ที่ประกอบด้วยตัวแปร ตัวเชื่อมต่าง ๆ และวงเล็บ ปัญหานี้ถามคำถามที่ว่า สำหรับนิพจน์บูลีนที่กำหนด เราสามารถทำให้นิพจน์เป็นจริงโดยการกำหนดค่าให้กับตัวแปรได้หรือไม่ ในกรณีที่เราสามารถกำหนดค่าความจริงให้กับตัวแปรแล้วทำให้นิพจน์เป็นจริงได้ เราจะกล่าวว่านิพจน์นั้น สามารถทำให้เป็นจริงได้ (satisfiable) ปัญหา SAT จัดอยู่ในกลุ่มของปัญหาเอ็นพีบริบูรณ์ (NP-complete) ในบางครั้งเราอาจจะสนใจศึกษาความซับซ้อนของรูปแบบที่ต่างกันออกไปของปัญหา SAT ยกตัวอย่างเช่นปัญหา SAT แบบที่นิพจน์บูลีนอยู่ในรูปมาตรฐานแบบเชื่อม (หรือ Conjunctive Normal Form---CNF) ในกรณีนี้ถ้าแต่ละประพจน์เลือก (disjunct) ประกอบด้วยตัวแปรไม่เกิน 3 ตัวแปรเราจะเรียกปัญหาว่า 3-SAT ซึ่งเป็นปัญหาเอ็นพีบริบูรณ์เช่นเดียวกัน อย่างไรก็ตาม ในกรณีที่ตัวแปรในแต่ละประพจน์เลือกมีไม่เกิน 2 ตัวแปร (เรียกว่าปัญหา 2-SAT) นั้น เรามีอัลกอริธึมที่มีประสิทธิภาพในการแก้ปัญหาได้ นั่นก็คือ 2SAT \in P หรือหากจะพูดให้ชัดเจนกว่านั้น 2SAT \in NL \subseteq P (ทั้งนี้เนื่องจากขั้นตอนวิธีที่ใช้แก้ปัญหา 2-SAT เป็นขั้นตอนวิธีที่ทำงานโดยใช้เนื้อที่เป็นลอการิธึมบนเครื่องจักรทัวริงเชิงไม่กำหนดเท่านั้น).

ใหม่!!: ขั้นตอนวิธีการประมาณและปัญหาความสอดคล้องแบบบูล · ดูเพิ่มเติม »

เปลี่ยนเส้นทางที่นี่:

Approximation algorithmอัลกอริทึมประมาณอัลกอริทึมแบบประมาณ

ขาออกขาเข้า
Hey! เราอยู่ใน Facebook ตอนนี้! »