DAA - อัลกอริทึมการปีนเขา

อัลกอริทึมที่กล่าวถึงในบทก่อนหน้านี้ทำงานอย่างเป็นระบบ เพื่อให้บรรลุเป้าหมายต้องจัดเก็บเส้นทางที่สำรวจก่อนหน้านี้อย่างน้อยหนึ่งเส้นทางไปยังโซลูชันเพื่อค้นหาโซลูชันที่เหมาะสมที่สุด

สำหรับปัญหาหลาย ๆ อย่างเส้นทางไปสู่เป้าหมายไม่เกี่ยวข้อง ตัวอย่างเช่นในปัญหา N-Queens เราไม่จำเป็นต้องสนใจเกี่ยวกับการกำหนดค่าสุดท้ายของราชินีรวมถึงลำดับการเพิ่มราชินี

ปีนเขา

Hill Climbing เป็นเทคนิคในการแก้ปัญหาการเพิ่มประสิทธิภาพบางอย่าง ในเทคนิคนี้เราเริ่มต้นด้วยโซลูชันย่อยที่เหมาะสมและมีการปรับปรุงโซลูชันซ้ำ ๆ จนกว่าเงื่อนไขบางอย่างจะขยายใหญ่สุด

แนวคิดในการเริ่มต้นด้วยวิธีการแก้ปัญหาย่อยที่เหมาะสมจะเปรียบเทียบกับการเริ่มต้นจากฐานของเนินเขาการปรับปรุงวิธีการแก้ปัญหานั้นเปรียบได้กับการเดินขึ้นเขาและในที่สุดการเพิ่มเงื่อนไขบางอย่างจะเปรียบเทียบกับการไปถึงยอดเขา

ดังนั้นเทคนิคการปีนเขาจึงถือได้ว่าเป็นขั้นตอนต่อไปนี้ -

• การสร้างโซลูชันย่อยที่เหมาะสมซึ่งเป็นไปตามข้อ จำกัด ของปัญหา
• การปรับปรุงโซลูชันทีละขั้นตอน
• การปรับปรุงโซลูชันจนกว่าจะไม่สามารถปรับปรุงได้อีก

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

Algorithm: Hill Climbing 
Evaluate the initial state. 
Loop until a solution is found or there are no new operators left to be applied: 
   - Select and apply a new operator 
   - Evaluate the new state: 
      goal -→ quit 
      better than current state -→ new current state

การปรับปรุงซ้ำ

ในวิธีการปรับปรุงแบบวนซ้ำวิธีแก้ปัญหาที่ดีที่สุดสามารถทำได้โดยการก้าวไปสู่โซลูชันที่เหมาะสมที่สุดในการทำซ้ำทุกครั้ง อย่างไรก็ตามเทคนิคนี้อาจพบกับ maxima ในท้องถิ่น ในสถานการณ์เช่นนี้ไม่มีสถานะใกล้เคียงสำหรับทางออกที่ดีกว่า

ปัญหานี้สามารถหลีกเลี่ยงได้ด้วยวิธีการต่างๆ หนึ่งในวิธีการเหล่านี้คือการจำลองการอบอ่อน

รีสตาร์ทแบบสุ่ม

นี่เป็นอีกวิธีหนึ่งในการแก้ปัญหาของ optima ในท้องถิ่น เทคนิคนี้ดำเนินการค้นหาหลายชุด ทุกครั้งจะเริ่มจากสถานะเริ่มต้นที่สร้างขึ้นแบบสุ่ม ดังนั้นจึงสามารถหาโซลูชันที่เหมาะสมหรือเกือบจะดีที่สุดโดยเปรียบเทียบวิธีแก้ปัญหาของการค้นหาที่ดำเนินการ

ปัญหาของเทคนิคการปีนเขา

Maxima ท้องถิ่น

หากฮิวริสติกไม่นูน Hill Climbing อาจมาบรรจบกับแม็กซิมาในพื้นที่แทนที่จะเป็นแม็กซิมาระดับโลก

สะพานและตรอกซอกซอย

หากฟังก์ชันเป้าหมายสร้างสันเขาแคบ ๆ นักปีนเขาจะสามารถขึ้นสันเขาหรือลงซอยได้โดยการซิกแซกเท่านั้น ในสถานการณ์นี้นักปีนเขาต้องทำตามขั้นตอนเล็ก ๆ น้อย ๆ ซึ่งต้องใช้เวลามากขึ้นในการบรรลุเป้าหมาย

ที่ราบสูง

พบที่ราบสูงเมื่อพื้นที่การค้นหาแบนหรือแบนเพียงพอที่ค่าที่ส่งคืนโดยฟังก์ชันเป้าหมายจะแยกไม่ออกจากค่าที่ส่งคืนสำหรับพื้นที่ใกล้เคียงเนื่องจากความแม่นยำที่ใช้โดยเครื่องเพื่อแสดงค่า

ความซับซ้อนของเทคนิคการปีนเขา

เทคนิคนี้ไม่ได้รับผลกระทบจากปัญหาเกี่ยวกับพื้นที่เนื่องจากดูเฉพาะสถานะปัจจุบันเท่านั้น เส้นทางที่สำรวจก่อนหน้านี้จะไม่ถูกเก็บไว้

สำหรับปัญหาส่วนใหญ่ในเทคนิค Random-restart Hill Climbing วิธีแก้ปัญหาที่ดีที่สุดสามารถทำได้ในรูปแบบพหุนาม อย่างไรก็ตามสำหรับปัญหา NP-Complete เวลาในการคำนวณอาจเป็นเลขชี้กำลังตามจำนวนสูงสุดในพื้นที่

การประยุกต์ใช้เทคนิคการปีนเขา

เทคนิคการปีนเขาสามารถใช้เพื่อแก้ปัญหาต่างๆได้โดยที่สถานะปัจจุบันอนุญาตให้ใช้ฟังก์ชันการประเมินที่แม่นยำเช่นปัญหาเครือข่ายโฟลว์ปัญหาพนักงานขายในการเดินทางปัญหา 8 ควีนส์การออกแบบวงจรรวมเป็นต้น

Hill Climbing ใช้ในวิธีการเรียนรู้แบบอุปนัยด้วย เทคนิคนี้ใช้ในวิทยาการหุ่นยนต์เพื่อประสานงานระหว่างหุ่นยนต์หลายตัวในทีม มีปัญหาอื่น ๆ อีกมากมายที่ใช้เทคนิคนี้

ตัวอย่าง

เทคนิคนี้สามารถนำไปใช้เพื่อแก้ปัญหาพนักงานขายที่เดินทางได้ อันดับแรกการแก้ปัญหาเบื้องต้นจะถูกกำหนดว่าจะไปเยี่ยมเมืองทั้งหมดในครั้งเดียว ดังนั้นวิธีแก้ปัญหาเบื้องต้นนี้จึงไม่เหมาะสมที่สุดในกรณีส่วนใหญ่ แม้แต่วิธีการแก้ปัญหานี้ก็ทำได้แย่มาก อัลกอริธึม Hill Climbing เริ่มต้นด้วยวิธีการแก้ปัญหาเบื้องต้นดังกล่าวและทำการปรับปรุงในลักษณะซ้ำ ๆ ในที่สุดก็น่าจะได้เส้นทางที่สั้นกว่ามาก