สมัครเรียนโทร. 085-350-7540 , 084-88-00-255 , ntprintf@gmail.com
# 5 อัลกอริทึมการค้นหาที่สำคัญพร้อมยกตัวอย่าง
เมื่อพูดถึงการเขียนโปรแกรมและอัลกอริทึม การค้นหา (Search Algorithms) คือหัวใจสำคัญหนึ่งที่ทุกโปรแกรมเมอร์ควรศึกษา อัลกอริทึมเหล่านี้ช่วยให้สามารถค้นหาข้อมูลจากชุดข้อมูลมหาศาลได้อย่างเร็วและมีประสิทธิภาพ ในบทความนี้ เราจะมาสำรวจ 5 อัลกอริทึมการค้นหาที่สำคัญ พร้อมยกตัวอย่างการใช้งานในชีวิตจริงเพื่อให้เข้าใจอัลกอริทึมเหล่านี้อย่างลึกซึ้ง
การค้นหาแบบเชิงเส้นเป็นอัลกอริทึมที่พื้นฐานที่สุด เป็นการค้นหาแบบหนึ่งต่อหนึ่ง (One-by-one) ตามลำดับ แม้ว่าจะไม่มีประสิทธิภาพที่สุด แต่ก็เป็นการเริ่มต้นที่ดีสำหรับการเรียนรู้เกี่ยวกับคอนเซ็ปต์การค้นหา
ตัวอย่างการใช้งาน:
สมมติว่าเรามีรายการชื่อสินค้าในคลัง และเราต้องการหาสินค้าชิ้นหนึ่ง การค้นหาแบบเชิงเส้นจะทำการตรวจสอบทุกรายการตั้งแต่ต้นจนกระทั่งพบสินค้าที่ต้องการ
def linear_search(items, target):
for index, item in enumerate(items):
if item == target:
return index
return -1
# ตัวอย่างการใช้งาน linear_search ใน Python
inventory = ['แอปเปิ้ล', 'กล้วย', 'เชอร์รี่', 'มะม่วง']
target = 'เชอร์รี่'
found_index = linear_search(inventory, target)
if found_index != -1:
print(f"พบสินค้า {target} ที่ตำแหน่ง {found_index}")
else:
print("ไม่พบสินค้า")
การค้นหาแบบไบนารีเป็นการค้นหาที่มีประสิทธิภาพมากกว่า เนื่องจากการทำงานของมันคือการหารองค์ประกอบของชุดข้อมูลออกเป็นครึ่ง ๆ เพื่อลดขอบเขตการค้นหาในแต่ละขั้นตอน อย่างไรก็ตาม การใช้งานอัลกอริทึมนี้ต้องการให้ชุดข้อมูลนั้นมีการเรียงลำดับไว้อย่างถูกต้องเสียก่อน
ตัวอย่างการใช้งาน:
หากเราต้องการหาหนังสือจากห้องสมุดที่มีการเรียงลำดับแล้ว การค้นหาแบบไบนารีจะช่วยลดจำนวนขั้นตอนในการค้นหาได้มาก
def binary_search(sorted_items, target):
left, right = 0, len(sorted_items) - 1
while left <= right:
middle = (left + right) // 2
if sorted_items[middle] == target:
return middle
elif sorted_items[middle] < target:
left = middle + 1
else:
right = middle - 1
return -1
# ตัวอย่างการใช้งาน binary_search ใน Python
books = ["Harry Potter", "The Hobbit", "1984", "The Great Gatsby"]
books.sort() # การเรียงลำดับก่อนการค้นหา
target_book = "1984"
found_index = binary_search(books, target_book)
if found_index != -1:
print(f"พบหนังสือ {target_book} ในห้องสมุด")
else:
print("ไม่พบหนังสือ")
การค้นหาแบบ Depth-First Search เป็นอัลกอริทึมที่ใช้ในการค้นหาหรือเรียกดูโครงสร้างข้อมูลแบบกราฟหรือต้นไม้ โดยการลงไปในความลึกของแต่ละจุดยอดก่อน แล้วจึงย้อนกลับเมื่อถึงทางตัน มีประโยชน์อย่างมากในหลายๆ สถานการณ์ เช่น การค้นหาเส้นทางในเกม หรือปัญหาการแก้ไข Maze
ตัวอย่างการใช้งาน:
เช่น การหาเส้นทางในแผนที่ โดยเริ่มจากจุดเริ่มต้นและทำการเดินทางไปยังทุกสาขาที่เป็นไปได้จนกว่าจะพบเป้าหมาย
def depth_first_search(graph, start, target, path=[], visited=set()):
path.append(start)
visited.add(start)
if start == target:
return path
for neighbour in graph[start]:
if neighbour not in visited:
result_path = depth_first_search(graph, neighbour, target, path, visited)
if result_path:
return result_path
path.pop()
return None
# ตัวอย่างกราฟในรูปแบบของ dictionary ใน Python
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
start_node = 'A'
end_node = 'F'
dfs_path = depth_first_search(graph, start_node, end_node)
if dfs_path:
print(f"พบเส้นทางจากจุด {start_node} ถึง {end_node}: {dfs_path}")
else:
print(f"ไม่พบเส้นทางจากจุด {start_node} ถึง {end_node}")
Breadth-First Search คล้ายคลึงกับ DFS แต่มีแนวทางการค้นหาที่ตรงกันข้าม เริ่มจากจุดรากและเลื่อนไปยังจุดยอดที่ใกล้ที่สุดเรื่อยๆ จนกว่าจะพบเป้าหมาย การค้นหาแบบ BFS มักให้เส้นทางที่สั้นที่สุดหากทุกขั้นตอนมีระยะทางเท่ากัน
ตัวอย่างการใช้งาน:
การใช้ BFS ในการหาเพื่อนในระดับที่ใกล้ที่สุดบนโซเชียลเน็ตเวิร์ก หรือการหาเส้นทางสั้นที่สุดในเกมกระดาน
from collections import deque
def breadth_first_search(graph, start, target):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
if vertex == target:
return True
for neighbour in graph[vertex]:
if neighbour not in visited:
queue.append(neighbour)
return False
graph = {
'1': ['2', '3'],
'2': ['4', '5'],
'3': ['5'],
'4': ['6'],
'5': ['6'],
'6': []
}
start_node = '1'
end_node = '6'
if breadth_first_search(graph, start_node, end_node):
print(f"พบทางจากจุด {start_node} ไปยัง {end_node}")
else:
print(f"ไม่พบทางจากจุด {start_node} ไปยัง {end_node}")
Jump Search คือการรวมข้อดีของ Linear Search และ Binary Search เข้าด้วยกัน โดยอัลกอริทึมนี้จะกระโดดในชุดข้อมูลที่มีการเรียงลำดับด้วยขนาดก้าวที่คงที่ จากนั้นจึงทำการค้นหาเชิงเส้นในช่วงที่มีความเป็นไปได้
ตัวอย่างการใช้งาน:
การใช้ Jump Search ในการหาหมายเลขหน้าของหนังสือจากรายการชื่อหนังสือที่ถูกจัดเรียง
import math
def jump_search(sorted_list, target):
length = len(sorted_list)
jump = int(math.sqrt(length))
left, right = 0, 0
while left < length and sorted_list[left] <= target:
right = min(length - 1, left + jump)
if sorted_list[left] <= target <= sorted_list[right]:
break
left += jump
if left >= length or sorted_list[left] > target:
return -1
right = min(length - 1, right)
for i in range(left, right+1):
if sorted_list[i] == target:
return i
return -1
page_list = [1, 13, 24, 36, 47, 58, 69, 80, 92]
page_number = 36
found_index = jump_search(page_list, page_number)
if found_index != -1:
print(f"พบหน้าหมายเลข {page_number} ที่ตำแหน่ง {found_index}")
else:
print("ไม่พบหน้าหมายเลข")
ในการเริ่มต้นด้านการเรียนรู้เกี่ยวกับอัลกอริทึม การทดลองและเข้าใจการทำงานของแต่ละอัลกอริทึมนั้นมีความสำคัญอย่างยิ่ง และการปฏิบัติจริงเป็นก้าวสำคัญในการพัฒนาฝีมือ จึงอยากชวนคุณมาลองค้นหาและฝึกการเขียนโค้ดกับอัลกอริทึมเหล่านี้เพื่อเสริมสร้างทักษะการเขียนโปรแกรมของคุณให้แข็งแกร่งยิ่งขึ้น อย่าลืมว่าการฝึกฝนต่อเนื่องนำไปสู่การประสบความสำเร็จ และหากคุณอยากเริ่มต้นเรียนรู้การเขียนโปรแกรมด้วยการฝึกปฏิบัติจริง ที่ EPT (Expert-Programming-Tutor) พร้อมเปิดประตูสู่โลกแห่งการเรียนรู้การเขียนโค้ดให้กับคุณ!
หมายเหตุ: ข้อมูลในบทความนี้อาจจะผิด โปรดตรวจสอบความถูกต้องของบทความอีกครั้งหนึ่ง บทความนี้ไม่สามารถนำไปใช้อ้างอิงใด ๆ ได้ ทาง EPT ไม่ขอยืนยันความถูกต้อง และไม่ขอรับผิดชอบต่อความเสียหายใดที่เกิดจากบทความชุดนี้ทั้งทางทรัพย์สิน ร่างกาย หรือจิตใจของผู้อ่านและผู้เกี่ยวข้อง
หากเจอข้อผิดพลาด หรือต้องการพูดคุย ติดต่อได้ที่ https://m.me/expert.Programming.Tutor/
Tag ที่น่าสนใจ: search_algorithms linear_search binary_search depth-first_search breadth-first_search jump_search algorithm programming python data_structures learning efficiency
หากมีข้อผิดพลาด/ต้องการพูดคุยเพิ่มเติมเกี่ยวกับบทความนี้ กรุณาแจ้งที่ http://m.me/Expert.Programming.Tutor
085-350-7540 (DTAC)
084-88-00-255 (AIS)
026-111-618
หรือทาง EMAIL: NTPRINTF@GMAIL.COM
Copyright (c) 2013 expert-programming-tutor.com. All rights reserved. | 085-350-7540 | 084-88-00-255 | ntprintf@gmail.com