ขั้นตอนวิธีการประมาณ ในศาสตร์ด้านวิทยาการคอมพิวเตอร์นั้น เป็นวิธีการหนึ่งที่ใช้สำหรับจัดการกับปัญหาการหาค่าเหมาะที่สุดประเภทเอ็นพี-ฮาร์ด เนื่องจากเป็นที่เชื่อกันว่าไม่มีขั้นตอนวิธีใดที่มีประสิทธิภาพ (ทำงานได้รวดเร็ว) ที่สามารถแก้ไขปัญหาเอ็นพี-ฮาร์ดได้คำตอบที่เที่ยงตรง จึงได้เกิดความพยายามที่จะหาคำตอบที่อาจจะไม่ถูกต้องที่สุด แต่สามารถหาได้ในเวลาโพลิโนเมียล ข้อแตกต่างของขั้นตอนวิธีประเภทนี้กับฮิวริสติก (ซึ่งมักเป็นการหาคำตอบที่ดีในระดับหนึ่งโดยใช้เวลาไม่มากนัก) ก็คือ ขั้นตอนวิธีประมาณต้องการคำตอบที่สามารถพิสูจน์ได้ว่าดีเพียงใด และพิสูจน์ได้ว่ามีขอบเขตการใช้เวลาไม่เกินเท่าใด ขั้นตอนวิธีในอุดมคติมักจะต้องผิดไปจากคำตอบจริงไม่เกินค่าคงที่ค่าหนึ่ง (เช่น คลาดเคลื่อนไม่เกิน 5%)
ปัญหาเอ็นพี-ฮาร์ดมีความหลากหลายอย่างมากในแง่ของการประมาณค่า บางปัญหาสามารถประมาณได้เป็นอัตราส่วนขนาดหนึ่ง (ขั้นตอนวิธีสำหรับประมาณปัญหาเหล่านี้มักเรียกกันว่า แบบแผนการประมาณในเวลาโพลิโนเมียล (polynomial time approximation scheme) หรือ PTAS) ส่วนบางปัญหานั้นก็ไม่สามารถที่จะประมาณได้เลย
ตัวอย่างของขั้นตอนวิธีประมาณที่มักกล่าวถึงกัน ได้แก่ ขั้นตอนวิธีสำหรับการคลุมจุดยอดในกราฟ โจทย์คือเลือกจุดยอดจำนวนน้อยที่สุด ให้ทุก ๆ ด้านมีปลายอย่างน้อยข้างหนึ่งถูกเลือก ขั้นตอนวิธีสำหรับประมาณปัญหานี้คือ หาด้านที่ยังไม่ถูกคลุม (ยังไม่มีปลายข้างใดถูกเลือก) มา แล้วเลือกปลายทั้งคู่ของด้านนี้ ขั้นตอนวิธีนี้ให้ผลลัพธ์ที่มีขนาดไม่เกินสองเท่าของคำตอบที่ดีที่สุด
วิธีหนึ่งที่ใช้ได้ผลบ่อยในการหาขั้นตอนวิธีประมาณคือ การพิจารณาการผ่อน (relax) กำหนดการเชิงเส้น
ใช่ว่าขั้นตอนวิธีประมาณทุกอันจะเหมาะสมกับงานในทางปฏิบัติ ตัวอย่างเช่น คนส่วนใหญ่คงไม่ค่อยประทับใจนัก กับขั้นตอนวิธีที่ช่วยให้พวกเขาจ่ายเงินไม่เกิน 20 เท่าของค่าใช้จ่ายที่ถูกที่สุด และเช่นกัน บางขั้นตอนวิธีอาจมีเวลาในการทำงานที่ไม่ค่อยดีนัก (ถึงแม้จะเป็นเวลาโพลิโนเมียลก็ตาม) เช่น
ข้อจำกัดอีกอย่างหนึ่งของวิธีการนี้ก็คือ มันใช้ได้กับปัญหาการหาค่าเหมาะที่สุด (optimization problem) เท่านั้น ไม่สามารถใช้กับปัญหาการตัดสินใจ“แท้ ๆ” เช่น ปัญหาความสอดคล้องแบบบูล ได้
แหล่งข้อมูลอื่น - แหล่งรวบรวมหัวข้อของปัญหาการหาค่าเหมาะที่สุดแบบเอ็นพี
นตอนว, การประมาณ, บทความน, ไม, การอ, างอ, งจากแหล, งท, มาใดกร, ณาช, วยปร, บปร, งบทความน, โดยเพ, มการอ, างอ, งแหล, งท, มาท, าเช, อถ, เน, อความท, ไม, แหล, งท, มาอาจถ, กค, ดค, านหร, อลบออก, เร, ยนร, าจะนำสารแม, แบบน, ออกได, อย, างไรและเม, อไร, งก, ามภาษา, ในบทควา. bthkhwamniimmikarxangxingcakaehlngthimaidkrunachwyprbprungbthkhwamni odyephimkarxangxingaehlngthimathinaechuxthux enuxkhwamthiimmiaehlngthimaxacthukkhdkhanhruxlbxxk eriynruwacanasaraemaebbnixxkidxyangiraelaemuxir lingkkhamphasa inbthkhwamni miiwihphuxanaelaphurwmaekikhbthkhwamsuksaephimetimodysadwk enuxngcakwikiphiediyphasaithyyngimmibthkhwamdngklaw krann khwrribsrangepnbthkhwamodyerwthisudkhntxnwithikarpraman insastrdanwithyakarkhxmphiwetxrnn epnwithikarhnungthiichsahrbcdkarkbpyhakarhakhaehmaathisudpraephthexnphi hard enuxngcakepnthiechuxknwaimmikhntxnwithiidthimiprasiththiphaph thanganidrwderw thisamarthaekikhpyhaexnphi hardidkhatxbthiethiyngtrng cungidekidkhwamphyayamthicahakhatxbthixaccaimthuktxngthisud aetsamarthhaidinewlaophlionemiyl khxaetktangkhxngkhntxnwithipraephthnikbhiwristik sungmkepnkarhakhatxbthidiinradbhnungodyichewlaimmaknk kkhux khntxnwithipramantxngkarkhatxbthisamarthphisucnidwadiephiyngid aelaphisucnidwamikhxbekhtkarichewlaimekinethaid khntxnwithiinxudmkhtimkcatxngphidipcakkhatxbcringimekinkhakhngthikhahnung echn khladekhluxnimekin 5 pyhaexnphi hardmikhwamhlakhlayxyangmakinaengkhxngkarpramankha bangpyhasamarthpramanidepnxtraswnkhnadhnung khntxnwithisahrbpramanpyhaehlanimkeriykknwa aebbaephnkarpramaninewlaophlionemiyl polynomial time approximation scheme hrux PTAS swnbangpyhannkimsamarththicapramanidelytwxyangkhxngkhntxnwithipramanthimkklawthungkn idaek khntxnwithisahrbkarkhlumcudyxdinkraf octhykhuxeluxkcudyxdcanwnnxythisud ihthuk danmiplayxyangnxykhanghnungthukeluxk khntxnwithisahrbpramanpyhanikhux hadanthiyngimthukkhlum yngimmiplaykhangidthukeluxk ma aelweluxkplaythngkhukhxngdanni khntxnwithiniihphllphththimikhnadimekinsxngethakhxngkhatxbthidithisudwithihnungthiichidphlbxyinkarhakhntxnwithipramankhux karphicarnakarphxn relax kahndkarechingesnichwakhntxnwithipramanthukxncaehmaasmkbnganinthangptibti twxyangechn khnswnihykhngimkhxyprathbicnk kbkhntxnwithithichwyihphwkekhacayenginimekin 20 ethakhxngkhaichcaythithukthisud aelaechnkn bangkhntxnwithixacmiewlainkarthanganthiimkhxydink thungaemcaepnewlaophlionemiylktam echn O n 2000 displaystyle O n 2000 khxcakdxikxyanghnungkhxngwithikarnikkhux mnichidkbpyhakarhakhaehmaathisud optimization problem ethann imsamarthichkbpyhakartdsinic aeth echn pyhakhwamsxdkhlxngaebbbul idaehlngkhxmulxun aekikhaehlngrwbrwmhwkhxkhxngpyhakarhakhaehmaathisudaebbexnphi bthkhwamekiywkbkhnitsastrniyngepnokhrng khunsamarthchwywikiphiediyidodyephimkhxmul duephimthi sthaniyxy khnitsastr ekhathungcak https th wikipedia org w index php title khntxnwithikarpraman amp oldid 8380181, wikipedia, วิกิ หนังสือ, หนังสือ, ห้องสมุด,
บทความ
, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม
