AI - อัลกอริทึมการค้นหายอดนิยม

การค้นหาเป็นเทคนิคสากลในการแก้ปัญหาใน AI มีเกมสำหรับผู้เล่นคนเดียวบางเกมเช่นเกมเรียงไพ่ซูโดกุคำไขว้ ฯลฯ อัลกอริทึมการค้นหาช่วยให้คุณค้นหาตำแหน่งเฉพาะในเกมดังกล่าว

ปัญหาการค้นหาตัวแทนเดี่ยว

เกมเช่น 3X3 แปดไทล์ 4X4 สิบห้าไทล์และ 5X5 ยี่สิบสี่ไทล์เป็นความท้าทายในการค้นหาเส้นทางตัวแทนเดียว ประกอบด้วยเมทริกซ์ของกระเบื้องกับกระเบื้องเปล่า ผู้เล่นจะต้องจัดเรียงกระเบื้องโดยการเลื่อนกระเบื้องในแนวตั้งหรือแนวนอนลงในพื้นที่ว่างโดยมีจุดประสงค์เพื่อบรรลุวัตถุประสงค์บางประการ

ตัวอย่างอื่น ๆ ของปัญหาการค้นหาเส้นทางตัวแทนรายเดียว ได้แก่ ปัญหาพนักงานขายการเดินทางลูกบาศก์ของรูบิคและการพิสูจน์ทฤษฎีบท

คำศัพท์การค้นหา

• Problem Space- เป็นสภาพแวดล้อมที่การค้นหาเกิดขึ้น (ชุดของสถานะและชุดตัวดำเนินการเพื่อเปลี่ยนสถานะเหล่านั้น)

• Problem Instance - เป็นสถานะเริ่มต้น + สถานะเป้าหมาย

• Problem Space Graph- แสดงถึงสถานะปัญหา สถานะจะแสดงโดยโหนดและตัวดำเนินการจะแสดงตามขอบ

• Depth of a problem - ความยาวของเส้นทางที่สั้นที่สุดหรือลำดับที่สั้นที่สุดของตัวดำเนินการจากสถานะเริ่มต้นไปยังสถานะเป้าหมาย

• Space Complexity - จำนวนโหนดสูงสุดที่เก็บไว้ในหน่วยความจำ

• Time Complexity - จำนวนโหนดสูงสุดที่สร้างขึ้น

• Admissibility - คุณสมบัติของอัลกอริทึมเพื่อค้นหาโซลูชันที่เหมาะสมที่สุดเสมอ

• Branching Factor - จำนวนโหนดลูกโดยเฉลี่ยในกราฟพื้นที่ปัญหา

• Depth - ความยาวของเส้นทางที่สั้นที่สุดจากสถานะเริ่มต้นไปยังสถานะเป้าหมาย

กลยุทธ์การค้นหา Brute-Force

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

ข้อกำหนด -

• คำอธิบายสถานะ
• ชุดของตัวดำเนินการที่ถูกต้อง
• สถานะเริ่มต้น
• คำอธิบายสถานะเป้าหมาย

การค้นหาแบบกว้าง - แรก

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

ถ้า branching factor(ค่าเฉลี่ยของจำนวนโหนดลูกสำหรับโหนดที่กำหนด) = b และความลึก = d แล้วจำนวนโหนดในระดับ d = b d

ไม่มีโหนดทั้งหมดที่สร้างขึ้นในกรณีที่เลวร้ายที่สุดคือ B + B ² b + ³ + ... + B d

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

ความซับซ้อนขึ้นอยู่กับจำนวนโหนด สามารถตรวจสอบโหนดที่ซ้ำกันได้

การค้นหาเชิงลึก - แรก

มันถูกนำไปใช้ในการเรียกซ้ำด้วยโครงสร้างข้อมูล LIFO stack มันสร้างชุดของโหนดเดียวกันกับวิธี Breadth-First เฉพาะในลำดับที่ต่างกัน

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

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

ความซับซ้อนของมันขึ้นอยู่กับจำนวนเส้นทาง ไม่สามารถตรวจสอบโหนดที่ซ้ำกันได้

การค้นหาแบบสองทิศทาง

ค้นหาจากสถานะเริ่มต้นและย้อนกลับจากสถานะเป้าหมายจนกว่าทั้งสองจะพบกันเพื่อระบุสถานะทั่วไป

เส้นทางจากสถานะเริ่มต้นเชื่อมต่อกับเส้นทางผกผันจากสถานะเป้าหมาย การค้นหาแต่ละครั้งทำได้ไม่เกินครึ่งหนึ่งของเส้นทางทั้งหมด

การค้นหาต้นทุนสม่ำเสมอ

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

สำรวจเส้นทางตามลำดับต้นทุนที่เพิ่มขึ้น

Disadvantage- สามารถมีเส้นทางยาวได้หลายเส้นทางโดยมีค่าใช้จ่าย≤ C * การค้นหา Uniform Cost ต้องสำรวจทั้งหมด

การค้นหาเชิงลึกแบบวนซ้ำ - การค้นหาครั้งแรก

ทำการค้นหาเชิงลึกก่อนถึงระดับ 1 เริ่มต้นใหม่ดำเนินการค้นหาเชิงลึกก่อนถึงระดับ 2 และดำเนินการต่อไปในลักษณะดังกล่าวจนกว่าจะพบโซลูชัน

จะไม่สร้างโหนดจนกว่าจะสร้างโหนดที่ต่ำกว่าทั้งหมด บันทึกเฉพาะสแต็กของโหนดเท่านั้น อัลกอริทึมปลายเมื่อพบวิธีการแก้ปัญหาที่ระดับความลึกd จำนวนโหนดที่สร้างขึ้นที่ความลึกdคือ b ^dและที่ความลึกd-1คือ b ^d-1

การเปรียบเทียบความซับซ้อนของอัลกอริทึมต่างๆ

ให้เราดูประสิทธิภาพของอัลกอริทึมตามเกณฑ์ต่างๆ -

เกณฑ์	ความกว้างก่อน	ความลึกก่อน	แบบสองทิศทาง	ต้นทุนสม่ำเสมอ	Interactive Deepening
เวลา	ขง	ขเมตร	ขง / 2	ขง	ขง
พื้นที่	ขง	ขเมตร	ขง / 2	ขง	ขง
การเพิ่มประสิทธิภาพ	ใช่	ไม่	ใช่	ใช่	ใช่
ความสมบูรณ์	ใช่	ไม่	ใช่	ใช่	ใช่

กลยุทธ์การค้นหาข้อมูล (Heuristic)

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

ฟังก์ชั่นการประเมินฮิวริสติก

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

การค้นหา Heuristic บริสุทธิ์

ขยายโหนดตามลำดับของค่าฮิวริสติก สร้างสองรายการรายการปิดสำหรับโหนดที่ขยายแล้วและรายการเปิดสำหรับโหนดที่สร้างขึ้น แต่ยังไม่ขยาย

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

ก * ค้นหา

เป็นรูปแบบการค้นหาที่ดีที่สุดที่รู้จักกันดีที่สุด หลีกเลี่ยงการขยายเส้นทางที่มีราคาแพงอยู่แล้ว แต่จะขยายเส้นทางที่มีแนวโน้มมากที่สุดก่อน

f (n) = g (n) + h (n) โดยที่

• g (n) ค่าใช้จ่าย (จนถึงปัจจุบัน) ในการเข้าถึงโหนด
• h (n) ต้นทุนโดยประมาณที่จะได้รับจากโหนดไปยังเป้าหมาย
• f (n) ต้นทุนทั้งหมดโดยประมาณของเส้นทางผ่าน n ไปยังเป้าหมาย ดำเนินการโดยใช้ลำดับความสำคัญโดยการเพิ่ม f (n)

การค้นหาครั้งแรกที่ดีที่สุดโลภ

ขยายโหนดที่คาดว่าใกล้เคียงกับเป้าหมายมากที่สุด ขยายโหนดตาม f (n) = h (n) ดำเนินการโดยใช้ลำดับความสำคัญคิว

Disadvantage- อาจติดอยู่ในลูป มันไม่เหมาะสม

อัลกอริทึมการค้นหาในท้องถิ่น

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

ค้นหา Hill-Climbing

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

ฟังก์ชัน Hill-Climbing (ปัญหา) ส่งคืนสถานะที่เป็นค่าสูงสุดในท้องถิ่น

inputs: problem, a problem
local variables: current, a node
                 neighbor, a node
current <-Make_Node(Initial-State[problem])
loop
   do neighbor <- a highest_valued successor of current
      if Value[neighbor] ≤ Value[current] then
      return State[current]
      current <- neighbor				  
	
end

Disadvantage - อัลกอริทึมนี้ไม่สมบูรณ์หรือเหมาะสมที่สุด

ค้นหา Beam ในท้องถิ่น

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

มิฉะนั้นสถานะ (k เริ่มต้นและจำนวน k ของตัวตายตัวแทนของสถานะ = 2k) จะถูกวางไว้ในพูล จากนั้นพูลจะเรียงตามตัวเลข สถานะ k สูงสุดจะถูกเลือกเป็นสถานะเริ่มต้นใหม่ กระบวนการนี้จะดำเนินต่อไปจนกว่าจะถึงค่าสูงสุด

ฟังก์ชัน BeamSearch ( ปัญหา k ) ส่งกลับสถานะโซลูชัน

start with k randomly generated states
loop
   generate all successors of all k states
   if any of the states = solution, then return the state
   else select the k best successors
end

การหลอมจำลอง

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

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

เริ่ม

• เริ่มต้น k = 0; L = จำนวนเต็มของตัวแปร;
• จาก i → j ค้นหาความแตกต่างของประสิทธิภาพΔ
• ถ้าΔ <= 0 ให้ยอมรับ else ถ้า exp (-Δ / T (k))> สุ่ม (0,1) แล้วยอมรับ;
• ทำซ้ำขั้นตอนที่ 1 และ 2 สำหรับขั้นตอน L (k)
• k = k + 1;

ทำซ้ำขั้นตอนที่ 1 ถึง 4 จนครบตามเกณฑ์

สิ้นสุด

ปัญหาพนักงานขายในการเดินทาง

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

Start
   Find out all (n -1)! Possible solutions, where n is the total number of cities.
   Determine the minimum cost by finding out the cost of each of these (n -1)! solutions.
   Finally, keep the one with the minimum cost.
end