ทั้งหมดเกี่ยวกับการค้นหาข้อมูลในปัญญาประดิษฐ์

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

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

ลงทะเบียนเรียน หลักสูตร Machine Learning จากมหาวิทยาลัยชั้นนำของโลก รับหลักสูตร Master, Executive PGP หรือ Advanced Certificate เพื่อความก้าวหน้าในอาชีพของคุณ

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

ฟังก์ชันฮิวริสติกส์

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

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

ตัวอย่างฟังก์ชันฮิวริสติกในชีวิตจริง

เพื่อทำความเข้าใจฟังก์ชันฮิวริสติกให้ดียิ่งขึ้น ต่อไปนี้คือตัวอย่างในชีวิตจริงบางส่วน:

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

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

ตัวอย่างของอัลกอริทึมการค้นหาที่มีข้อมูล

อัลกอริทึมการค้นหาที่มีข้อมูลที่ใช้บ่อยที่สุด 2 รายการ ได้แก่ การค้นหาอันดับแรกที่ดีที่สุด และการค้นหา A* มาทำความเข้าใจอัลกอริทึมทั้งสองนี้พร้อมกับตัวอย่าง ข้อดี ข้อเสีย และการนำ Python ไปใช้:

1. การค้นหาครั้งแรกที่ดีที่สุด

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

การค้นหาครั้งแรกที่ดีที่สุด – ตัวอย่างที่มีภาพประกอบ

ต่อไปนี้คือตัวอย่างง่ายๆ เพื่ออธิบายการค้นหาครั้งแรกที่ดีที่สุด:

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

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

การค้นหาครั้งแรกที่ดีที่สุด – การใช้งาน Python

นี่คือวิธีที่คุณสามารถใช้อัลกอริธึมการค้นหาแรกที่ดีที่สุดใน Python:

กองนำเข้า

def best_first_search (start_state, goal_state, heuristic_func, actions_func, cost_func):

# เริ่มต้นชายแดนและชุดสำรวจ

ชายแดน = [(heuristic_func(start_state, goal_state), start_state)]

สำรวจ = ชุด ()

# เริ่มต้นเส้นทางและค่าใช้จ่าย

เส้นทาง = {}

ค่าใช้จ่าย = {}

เส้นทาง[start_state] = ไม่มี

ค่าใช้จ่าย[start_state] = 0

ในขณะที่ชายแดน:

# รับโหนดที่มีค่าฮิวริสติกต่ำสุดจากชายแดน

(h, current_state) = heapq.heappop (ชายแดน)

ถ้า current_state == goal_state:

# ย้อนกลับเส้นทางหากบรรลุเป้าหมาย

เส้นทางกลับ

explored.add (current_state)

# สร้างการกระทำที่เป็นไปได้จากสถานะปัจจุบัน

สำหรับการกระทำใน actions_func(current_state):

next_state = การดำเนินการ (current_state)

#คำนวณค่าใช้จ่ายของเส้นทางใหม่

new_cost = ต้นทุน[current_state] + cost_func(current_state, action, next_state)

ถ้า next_state ไม่ได้อยู่ในการสำรวจ และ next_state ไม่ได้อยู่ใน [state for (h, state) in frontier]:

# เพิ่มสถานะใหม่ให้กับชายแดน

heapq.heappush(ชายแดน, (heuristic_func(next_state, goal_state), next_state))

เส้นทาง[next_state] = current_state

ค่าใช้จ่าย[next_state] = new_cost

# ส่งคืนไม่มีหากไม่สามารถเข้าถึงสถานะเป้าหมายได้

กลับไม่มี

อย่างที่คุณเห็น คุณจะต้องกำหนดฟังก์ชันต่อไปนี้:

• heuristic_func(current_state, goal_state): ฟังก์ชันนี้ใช้สถานะปัจจุบันและสถานะเป้าหมายเป็นอินพุตและส่งกลับค่าประมาณของค่าใช้จ่ายในการไปถึงสถานะเป้าหมายจากสถานะปัจจุบัน
• actions_func(current_state): ฟังก์ชันนี้ใช้สถานะปัจจุบันเป็นอินพุตและส่งกลับรายการของการกระทำที่สามารถนำมาจากสถานะปัจจุบัน
• cost_func(current_state, action, next_state): ฟังก์ชันนี้ใช้สถานะปัจจุบัน การดำเนินการ และสถานะถัดไปเป็นอินพุตและส่งกลับต้นทุนของการดำเนินการจากสถานะปัจจุบันไปยังสถานะถัดไป

ตัวอย่าง Best First Search

start_state = (0, 0)

goal_state = (4, 4)

def heuristic_func (current_state, goal_state):

ส่งคืน abs(current_state[0] – goal_state[0]) + abs(current_state[1] – goal_state[1])

def actions_func (current_state):

การกระทำ = []

ถ้า current_state[0] > 0:

actions.append(สถานะแลมบ์ดา: (สถานะ[0]-1, สถานะ[1]))

ถ้า current_state[0] < 4:

actions.append(สถานะแลมบ์ดา: (สถานะ[0]+1, สถานะ[1]))

ถ้า current_state[1] > 0:

actions.append(สถานะแลมบ์ดา: (สถานะ[0], สถานะ[1]-1))

ถ้า current_state[1] < 4:

actions.append(สถานะแลมบ์ดา: (สถานะ[0], สถานะ[1]+1))

กลับการกระทำ

def cost_func (current_state, การดำเนินการ, next_state):

กลับ 1

เส้นทาง = best_first_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

ถ้าเส้นทาง:

# สร้างเส้นทางจากสถานะเริ่มต้นไปยังสถานะเป้าหมาย

current_state = เป้าหมาย_สถานะ

ในขณะที่ current_state != start_state:

พิมพ์ (current_state)

current_state = เส้นทาง [current_state]

พิมพ์ (start_state)

อื่น:

พิมพ์ (“ไม่สามารถเข้าถึงสถานะเป้าหมายได้”)

ข้อดีของ Best First Search

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

ข้อเสียของ Best First Search

• บางครั้งอาจครอบคลุมระยะทางมากกว่าที่คิดไว้
• โอกาสที่จะติดอยู่ในลูปมีโอกาสสูง

* ค้นหา

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

การค้นหา A* – ตัวอย่างที่แสดง

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

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

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

การค้นหา A* – การใช้งาน Python

นี่คือวิธีที่คุณสามารถใช้อัลกอริทึมการค้นหา A* โดยใช้การเขียนโปรแกรม Python:

กองนำเข้า

def astar_search (start_state, goal_state, heuristic_func, actions_func, cost_func):

# เริ่มต้นชายแดนและชุดสำรวจ

ชายแดน = [(heuristic_func(start_state, goal_state), start_state)]

สำรวจ = ชุด ()

# เริ่มต้นเส้นทางและค่าใช้จ่าย

เส้นทาง = {}

ค่าใช้จ่าย = {}

เส้นทาง[start_state] = ไม่มี

ค่าใช้จ่าย[start_state] = 0

ในขณะที่ชายแดน:

# รับโหนดที่มีค่า f ต่ำสุดจากชายแดน

(f, current_state) = heapq.heappop (ชายแดน)

ถ้า current_state == goal_state:

# ย้อนกลับเส้นทางหากบรรลุเป้าหมาย

เส้นทางกลับ

explored.add (current_state)

# สร้างการกระทำที่เป็นไปได้จากสถานะปัจจุบัน

สำหรับการกระทำใน actions_func(current_state):

next_state = การดำเนินการ (current_state)

#คำนวณค่าใช้จ่ายของเส้นทางใหม่

new_cost = ต้นทุน[current_state] + cost_func(current_state, action, next_state)

ถ้า next_state ไม่ได้อยู่ในการสำรวจ และ next_state ไม่ได้อยู่ใน [state for (f, state) in frontier]:

# เพิ่มสถานะใหม่ให้กับชายแดน

heapq.heappush(ชายแดน, (new_cost + heuristic_func(next_state, goal_state), next_state))

เส้นทาง[next_state] = current_state

ค่าใช้จ่าย[next_state] = new_cost

elif next_state ใน [state for (f, state) in frontier] และ new_cost < cost[next_state]:

# อัปเดตค่าใช้จ่ายของรัฐที่มีอยู่ในชายแดน

ดัชนี = [i สำหรับ (i, (f, state)) ในการแจกแจง (ชายแดน) ถ้า state == next_state][0]

ชายแดน[ดัชนี] = (new_cost + heuristic_func(next_state, goal_state), next_state)

เส้นทาง[next_state] = current_state

ค่าใช้จ่าย[next_state] = new_cost

# ส่งคืนไม่มีหากไม่สามารถเข้าถึงสถานะเป้าหมายได้

กลับไม่มี

หลักสูตรการเรียนรู้ของเครื่องและหลักสูตร AI ออนไลน์ชั้นนำ

ตัวอย่างการค้นหา A*

ต่อไปนี้เป็นตัวอย่างของวิธีใช้ฟังก์ชัน astar_search กับฟังก์ชันเหล่านี้:

start_state = (0, 0)

goal_state = (4, 4)

def heuristic_func (current_state, goal_state):

ส่งคืน abs(current_state[0] – goal_state[0]) + abs(current_state[1] – goal_state[1])

def actions_func (current_state):

การกระทำ = []

ถ้า current_state[0] > 0:

actions.append(สถานะแลมบ์ดา: (สถานะ[0]-1, สถานะ[1]))

ถ้า current_state[0] < 4:

actions.append(สถานะแลมบ์ดา: (สถานะ[0]+1, สถานะ[1]))

ถ้า current_state[1] > 0:

actions.append(สถานะแลมบ์ดา: (สถานะ[0], สถานะ[1]-1))

ถ้า current_state[1] < 4:

actions.append(สถานะแลมบ์ดา: (สถานะ[0], สถานะ[1]+1))

กลับการกระทำ

def cost_func (current_state, การดำเนินการ, next_state):

กลับ 1

เส้นทาง = astar_search(start_state, goal_state, heuristic_func, actions_func, cost_func)

ถ้าเส้นทาง:

# สร้างเส้นทางจากสถานะเริ่มต้นไปยังสถานะเป้าหมาย

current_state = เป้าหมาย_สถานะ

ในขณะที่ current_state != start_state:

พิมพ์ (current_state)

current_state = เส้นทาง [current_state]

พิมพ์ (start_state)

อื่น:

พิมพ์ (“ไม่สามารถเข้าถึงสถานะเป้าหมายได้”)

ข้อดีของการค้นหา A*

• เป็นหนึ่งในเทคนิคฮิวริสติกชั้นนำ
• สามารถใช้การค้นหา A* เพื่อแก้ปัญหาการค้นหาที่ซับซ้อนได้

ทักษะการเรียนรู้ของเครื่องที่ได้รับความนิยม

ข้อเสียของ A* Search

• ประสิทธิภาพการค้นหา A* อาศัยความแม่นยำของอัลกอริทึมการวิเคราะห์พฤติกรรมเป็นอย่างมาก
• มีประสิทธิภาพการค้นหาต่ำ

บล็อก AI และ ML ยอดนิยม & หลักสูตรฟรี

เอาไป

อัลกอริทึมการค้นหาที่ได้รับข้อมูลมีความสำคัญในปัญญาประดิษฐ์ เนื่องจากช่วยให้คอมพิวเตอร์สามารถค้นหาสถานะเป้าหมายได้อย่างมีประสิทธิภาพและประสิทธิผล อัลกอริธึมเหล่านี้ใช้ฟังก์ชันฮิวริสติกเพื่อประเมินต้นทุนของการเคลื่อนไหวที่เป็นไปได้แต่ละครั้ง และแนะนำกระบวนการค้นหาไปสู่สถานะเป้าหมาย Best First Search และ A* Search เป็นตัวอย่างของอัลกอริทึมการค้นหาที่ได้รับข้อมูลซึ่งใช้กันอย่างแพร่หลายในสาขาต่างๆ อย่างไรก็ตาม ฟังก์ชันฮิวริสติกที่กำหนดไว้อย่างดีมีความสำคัญต่อความสำเร็จของอัลกอริทึมการค้นหาที่มีข้อมูลครบถ้วน

หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับปัญญาประดิษฐ์และการเรียนรู้ของเครื่อง ลองดูโปรแกรมปริญญาโทสาขาการเรียนรู้ของเครื่องและปัญญาประดิษฐ์ของ upGrad ที่ เสนอโดย Liverpool John Moores University โปรแกรมนี้ครอบคลุมหัวข้อแมชชีนเลิร์นนิงและ AI ต่างๆ รวมถึงอัลกอริทึม เช่น การค้นหาข้อมูล เมื่อเข้าร่วมโปรแกรมนี้ คุณจะได้รับทักษะและความรู้ที่จำเป็นต่อการประสบความสำเร็จในอาชีพที่เกี่ยวข้องกับ AI ที่หลากหลาย

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