เร็วกว่าเบราว์เซอร์!
6 ความสัมพันธ์: การหาค่าเหมาะที่สุดแบบเฟ้นสุ่มรายการสาขาวิชาวิยุตคณิตขั้นตอนวิธีการประมาณขั้นตอนวิธีฮังกาเรียนขั้นตอนวิธีซิมเพล็กซ์
การหาค่าเหมาะที่สุดแบบเฟ้นสุ่ม
การหาค่าเหมาะที่สุดแบบเฟ้นสุ่ม (อังกฤษ:Stochastic Optimization) เป็นวิธีการหาค่าเหมาะที่สุดโดยการสร้างและใช้ตัวแปรสุ่ม สำหรับปัญหาในกลุ่มนี้ จะใช้ตัวแปรสุ่มในขั้นตอนการคำนวณหาค่าเหมาะที่สุดสำหรับปัญหานั้นๆ การแก้ปัญหาโดยวิธิการเฟ้นสุ่มนั้นได้ถูกใช้กันอย่างแพร่หลายในหลายวงการ อาทิเช่น ทางด้านอากาศยาน ทางการแพทย์ การขนส่ง และทางด้านการเงิน เป็นต้น เพื่อใช้ช่วยในการออกแบบจรวจมิสไซล์และอากาศยาน การคำนวณกำหนดประสิทธิภาพของยาตัวใหม่ ช่วยในการพัฒนาประสิทธิภาพของการควบคุมสัญญาณจราจร หรือแม้กระทั่งใช้เป็นเครื่องมือในการช่วยตัดสินใจเพื่อผลประโยชน์สูงสุดในการลงทุน โดยวิธีการแบบเฟ้นสุ่มนี้เป็นขั้นตอนวิธีที่จะช่วยให้สามารถตัดสินใจเลือกหนทางที่เหมาะที่สุดในการลดทอนปัญหาต่างๆในโลกความเป็นจริงลง.
ใหม่!!: กำหนดการเชิงเส้นและการหาค่าเหมาะที่สุดแบบเฟ้นสุ่ม · ดูเพิ่มเติม »
รายการสาขาวิชา
รายชื่อสาขาวิชา หรือ สาขาการศึกษา (Field of study) หมายถึงสาขาความรู้ หรือ การวิจัยที่เปิดสอนในวิทยาลัยหรือมหาวิทยาลัย คำว่า สาขาวิชา ได้รับการนิยามและยอมรับโดย วารสารวิชาการที่ตีพิมพ์ผลงานวิจัย และโดยสมาคมผู้รู้ (learned societies) และโดยภาควิชาหรือคณะวิชาที่บุคคลผู้อยู่ในสาขาวิชานั้นๆ สังกัด โดยปกติ สาขาการศึกษาต่างๆ มักมีสาขาย่อยหรือแขนงวิชาแตกออกไป เส้นแบ่งระหว่างสาขาย่อยมักยังมีความคลุมเครือและมีกฎเกณฑ์ที่ไม่ชัดเจน ในยุโรปสมัยกลางซึ่งขณะนั้นยังมีการแบ่งคณะวิชาออกเป็น 4 คณะหรือสายวิชา ได้แก่เทววิทยา การแพทย์ ธรรมศาสตร์ นิติศาสตร์ และศิลปะ โดยคณะวิชาหลังมีสถานะไม่สูงเท่า 3 สาขาแรก การแบ่งสาขาวิชาในมหาวิทยาลัยสมัยนั้นมีรากสืบทอดมาจากขบวนการแยกอาณาจักรออกจากศาสนจักร (Secularization) ของมหาวิทยาลัยซึ่งเกิดขึ้นราวสมัยกลาง-ปลายคริสต์ศตวรรษที่ 19 (ประมาณ พ.ศ. 2390 - พ.ศ. 2440) โดยได้เพิ่มวิชาภาษาศาสตร์ที่ไม่ใช่คลาสสิก วรรณคดี และวิชาสายวิทยาศาสตร์และเทคโนโลยี เช่น ฟิสิกส์ เคมี ชีววิทยาและวิศวกรรมศาสตร์เสริมเข้าไปในหลักสูตรแบบประเพณีโบราณ ในต้นคริสต์ศตวรรษ ที่ 20 (ประมาณ พ.ศ. 2440 - พ.ศ. 2475) ได้มีการเพิ่มสาขาวิชาใหม่ๆ เช่น การศึกษา สังคมวิทยา และจิตวิทยา ในมหาวิทยาลัยต่างๆ และในช่วงประมาณ พ.ศ. 2513 - พ.ศ. 2523) ได้เกิดปรากฏการณ์ "การระเบิด" ของสาขาวิชาใหม่ๆ ที่เน้นเนื้อหาเฉพาะเจาะจง เช่น สื่อศึกษา สตรีศึกษา และชนผิวดำศึกษา สาขาใหม่ๆ เหล่านี้จัดขึ้นในมหาวิทยาลัยเพื่อรองรับอาชีพและวิชาชีพต่างๆ เช่น การพยาบาล การจัดการโรงพยาบาล การราชทัณฑ์ และหลังสุดก็ได้เห็นสาขาวิชาที่เป็นลักษณะ "สหสาขาวิชา" เช่น ชีวเคมี และ ธรณีฟิสิกส์เกิดเพิ่มขึ้นและได้รับการยอมรับว่าสาขาวิชาใหม่ๆ ที่เกิดขึ้นเหล่านี้ได้ช่วยเพิ่มพูนความรู้ให้กว้างขวางขึ้น เครื่องหมายดอกจัน * แสดงเป็นหมายเหตุว่าสาขาวิชานั้นยังเป็นที่ถกเถียงถึงสถานภาพว่าควรนับไว้ในสายวิชาใด เช่น วิชามานุษยวิทยา และวิชาภาษาศาสตร์ควรจัดไว้ในกลุ่มสังคมศาสตร์ หรือ มนุษยศาสตร์ เป็นที่สังเกตได้ว่าบางท่าน โดยเฉพาะนักทฤษฎีวิจารณ์มักให้ความสำคัญในการบ่งชี้การจัดกลุ่มที่เข้มงวดในทุกสายวิชา รวมทั้งความชัดเจนของโครงสร้างของแนวคิดโดยรวมของแต่ละวิชาซึ่งยังเป็นถกเถียงได้มากสำหรับบางคน.
ใหม่!!: กำหนดการเชิงเส้นและรายการสาขาวิชา · ดูเพิ่มเติม »
วิยุตคณิต
วิยุตคณิต ภินทนคณิตศาสตร์ หรือ คณิตศาสตร์ไม่ต่อเนื่อง (discrete mathematics) หรือบางครั้งเรียกว่า คณิตศาสตร์จำกัด (finite mathematics) เป็นการศึกษาโครงสร้างทางคณิตศาสตร์ซึ่งมีลักษณะเป็นค่าเฉพาะเจาะจง และไม่ต่อเนื่อง ซึ่งไม่ต้องใช้แนวคิดเกี่ยวกับความต่อเนื่อง วัตถุที่ศึกษาส่วนมากในสาขานี้มักเป็นเซตนับได้ เช่น เซตของจำนวนเต็ม วิยุตคณิตได้รับความสนใจมากขึ้นในปัจจุบันเนื่องจากการประยุกต์ใช้ในวิทยาการคอมพิวเตอร์ แนวคิดและสัญกรณ์จากวิยุตคณิตนั้นมีประโยชน์ในการศึกษา หรืออธิบายวัตถุหรือปัญหาในขั้นตอนวิธี และภาษาโปรแกรม ในหลาย ๆ หลักสูตรทางคณิตศาสตร์วิชาด้านคณิตศาสตร์จำกัด จะเน้นเนื้อหาที่เกี่ยวข้องกับด้านธุรกิจ ส่วนวิยุตคณิตเน้นแนวคิดสำหรับวิทยาการคอมพิวเตอร์ เพื่อการเปรียบเทียบ ดู ภาวะต่อเนื่อง ทอพอลอยี และ คณิตวิเคราะห.
ใหม่!!: กำหนดการเชิงเส้นและวิยุตคณิต · ดูเพิ่มเติม »
ขั้นตอนวิธีการประมาณ
ั้นตอนวิธีการประมาณ ในศาสตร์ด้านวิทยาการคอมพิวเตอร์นั้น เป็นวิธีการหนึ่งที่ใช้สำหรับจัดการกับปัญหาการหาค่าเหมาะที่สุดประเภทเอ็นพี-ฮาร์ด เนื่องจากเป็นที่เชื่อกันว่าไม่มีขั้นตอนวิธีใดที่มีประสิทธิภาพ (ทำงานได้รวดเร็ว) ที่สามารถแก้ไขปัญหาเอ็นพี-ฮาร์ดได้คำตอบที่เที่ยงตรง จึงได้เกิดความพยายามที่จะหาคำตอบที่อาจจะไม่ถูกต้องที่สุด แต่สามารถหาได้ในเวลาโพลิโนเมียล ข้อแตกต่างของขั้นตอนวิธีประเภทนี้กับฮิวริสติก (ซึ่งมักเป็นการหาคำตอบที่ดีในระดับหนึ่งโดยใช้เวลาไม่มากนัก) ก็คือ ขั้นตอนวิธีประมาณต้องการคำตอบที่สามารถพิสูจน์ได้ว่าดีเพียงใด และพิสูจน์ได้ว่ามีขอบเขตการใช้เวลาไม่เกินเท่าใด ขั้นตอนวิธีในอุดมคติมักจะต้องผิดไปจากคำตอบจริงไม่เกินค่าคงที่ค่าหนึ่ง (เช่น คลาดเคลื่อนไม่เกิน 5%) ปัญหาเอ็นพี-ฮาร์ดมีความหลากหลายอย่างมากในแง่ของการประมาณค่า บางปัญหาสามารถประมาณได้เป็นอัตราส่วนขนาดหนึ่ง (ขั้นตอนวิธีสำหรับประมาณปัญหาเหล่านี้มักเรียกกันว่า แบบแผนการประมาณในเวลาโพลิโนเมียล (polynomial time approximation scheme) หรือ PTAS) ส่วนบางปัญหานั้นก็ไม่สามารถที่จะประมาณได้เลย ตัวอย่างของขั้นตอนวิธีประมาณที่มักกล่าวถึงกัน ได้แก่ ขั้นตอนวิธีสำหรับการคลุมจุดยอดในกราฟ โจทย์คือเลือกจุดยอดจำนวนน้อยที่สุด ให้ทุก ๆ ด้านมีปลายอย่างน้อยข้างหนึ่งถูกเลือก ขั้นตอนวิธีสำหรับประมาณปัญหานี้คือ หาด้านที่ยังไม่ถูกคลุม (ยังไม่มีปลายข้างใดถูกเลือก) มา แล้วเลือกปลายทั้งคู่ของด้านนี้ ขั้นตอนวิธีนี้ให้ผลลัพธ์ที่มีขนาดไม่เกินสองเท่าของคำตอบที่ดีที่สุด วิธีหนึ่งที่ใช้ได้ผลบ่อยในการหาขั้นตอนวิธีประมาณคือ การพิจารณาการผ่อน (relax) กำหนดการเชิงเส้น ใช่ว่าขั้นตอนวิธีประมาณทุกอันจะเหมาะสมกับงานในทางปฏิบัติ ตัวอย่างเช่น คนส่วนใหญ่คงไม่ค่อยประทับใจนัก กับขั้นตอนวิธีที่ช่วยให้พวกเขาจ่ายเงินไม่เกิน 20 เท่าของค่าใช้จ่ายที่ถูกที่สุด และเช่นกัน บางขั้นตอนวิธีอาจมีเวลาในการทำงานที่ไม่ค่อยดีนัก (ถึงแม้จะเป็นเวลาโพลิโนเมียลก็ตาม) เช่น O (n^) ข้อจำกัดอีกอย่างหนึ่งของวิธีการนี้ก็คือ มันใช้ได้กับปัญหาการหาค่าเหมาะที่สุด (optimization problem) เท่านั้น ไม่สามารถใช้กับปัญหาการตัดสินใจ“แท้ ๆ” เช่น ปัญหาความสอดคล้องแบบบูล ได้.
ใหม่!!: กำหนดการเชิงเส้นและขั้นตอนวิธีการประมาณ · ดูเพิ่มเติม »
ขั้นตอนวิธีฮังกาเรียน
ั้นตอนวิธีชาวฮังกาเรียน (Hungarian Algorithm) คือ ขั้นตอนวิธีการหาค่าเหมาะสมที่สุดเชิงการจัด ซึ่งใช้ในการแก้ ปัญหาการกำหนดงาน ถูกคิดค้นและตั้งชื่อโดย แฮโรลด์ วิลเลียม คุห์น ในปี ค.ศ. 1955 ที่ตั้งชื่อนี้เพราะว่าขั้นตอนวิธีนี้มีพื้นฐานส่วนใหญ่จากการคิดของนักคณิตศาสตร์ชาวฮังกาเรียน 2 คน คือ Dénes Kőnig และ Jenő Egerváry ต่อมาเจมส์ มุนเครสได้นำขั้นตอนวิธีนี้มาตรวจสอบในปี ค.ศ. 1957 และได้พบว่ามีประสิทธิภาพเชิงเวลาเป็นแบบ strongly polynomial ตั้งแต่นั้นมาขั้นตอนวิธีนี้จึงเป็นที่รู้จักในชือว่า ขั้นตอนวิธีคุห์น-มุนเครส หรือ ขั้นตอนวิธีการกำหนดงานมุนเครส โดยมีประสิทธิภาพเชิงเวลาของขั้นตอนวิธีดั้งเดิมเป็น O(n^4) แต่อย่างไรก็ตามขั้นตอนวิธีนี้ แจ็ค เอดมันด์ และ ริชาร์ด แมนนิ่งคาร์ป ได้สามารถปรับปรุงให้มีประสิทธิภาพเชิงเวลาเป็น O(n^3) ได้ และในปี ค.ศ. 2006 มีการค้นพบว่า คาร์ล กุสตาฟ จาโคบี (Carl Gustav Jacobi) สามารถแก้ปัญหาการกำหนดงานได้ในคริสต์ศตวรรษที่ 19 และได้เผยแพร่ในปี ค.ศ. 1890 ในภาษาละติน.
ใหม่!!: กำหนดการเชิงเส้นและขั้นตอนวิธีฮังกาเรียน · ดูเพิ่มเติม »
ขั้นตอนวิธีซิมเพล็กซ์
ั้นตอนวิธีซิมเพล็กซ์ (simplex algorithm) หรือ วิธีซิมเพล็กซ์ (simplex method) จะอาศัยหลักการของเมทริกซ์เข้าช่วยในการหาผลลัพธ์ที่เหมาะสมที่สุด ซึ่งจะทำให้เห็นถึงการเปลี่ยนแปลงของตัวแปรในแต่ละขั้นตอนอย่างมีเหตุผล และเปลี่ยนแปลงไปในทางที่จะนำมาซึ่งผลลัพธ์ที่โมเดลทางคณิตศาสตร์ต้องการ.
ใหม่!!: กำหนดการเชิงเส้นและขั้นตอนวิธีซิมเพล็กซ์ · ดูเพิ่มเติม »
