เราสามารถคำนวณ g ได้ แต่เราจะคำนวณ h ได้อย่างไร
1. คำนวณค่าที่แน่นอนและถูกต้องของ  h ซึ่งต้องใช้เวลานาน
2. ประมาณค่าของ h ซึ่งใช้เวลาน้อยกว่า

การหาค่าที่แน่นอนของ h (ใช้เวลานาน)
1. คำนวณระยะทางระหว่างจุด 2 จุดก่อน
2. ถ้าไม่มีสิ่งกีดขวางต่างๆให้ใช้วิธีการคำนวณค่าที่แน่นอนของ h ด้วยวิธีการ Distance formula/Euclidean distance
สามารถเข้าไปศึกษาได้ตามเว็บไซต์นี้ https://en.wikipedia.org/wiki/Euclidean_distance

การประมาณค่าของ h (ใช้เวลาน้อยกว่า) มี  3 วิธีดังนี้

1.  Manhattan Distance
ค่าสัมบูรณ์ที่เกิดจากการนำระยะพิกัดของจุดเป้าหมาย x ลบกับระยะพิกัดที่จุด x ในตำแหน่งปัจจุบัน รวมกับ ค่าสัมบูรณ์ที่เกิดจากการนำระยะพิกัดของจุดเป้าหมาย y ลบกับระยะพิกัดที่จุด y ในตำแหน่งปัจจุบัน ตามสูตรด้านล่างนี้  เราจะใช้สูตรนี้คำนวณเมื่อเคลื่อนที่แค่ 4 ทิศทางเท่านั้น คือ ซ้าย ขวา บน ล่าง

h = abs (current_cell.x – goal.x) + abs (current_cell.y – goal.y)



รูปภาพที่ 3. ตัวอย่างที่สามารถคำนวณด้วยวิธี Manhattan Distance ได้
ที่มา : https://www.geeksforgeeks.org/a-search-algorithm/


 2. Diagonal Distance
ค่ามากที่สุดของค่าสัมบูรณ์ที่เกิดจากการนำระยะพิกัดของจุดเป้าหมาย x  ลบกับระยะพิกัดที่จุด x ในตำแหน่งปัจจุบัน หรือค่ามากที่สุดของค่าสัมบูรณ์ที่เกิดจากการนำระยะพิกัดของจุดเป้าหมาย y  ลบกับระยะพิกัดที่จุด y ในตำแหน่งปัจจุบัน ตามสูตรด้านล่างนี้ 
( เราจะใช้สูตรนี้คำนวณเมื่อเคลื่อนที่แค่ 8 ทิศทาง (คล้ายกับการเคลื่อนย้าย King  in  Chess )


h = max { abs(current_cell.x – goal.x),  abs(current_cell.y – goal.y) }


รูปภาพที่ 4. ตัวอย่างที่สามารถคำนวณด้วยวิธี Diagonal Distance ได้
ที่มา : https://www.geeksforgeeks.org/a-search-algorithm/

 3.  Euclidean Distance
    ใช้สูตรระยะทางในการคำนวณ ตามข้างล่างนี้
     เราใช้สูตรนี้คำนวณเมื่อเราเคลื่อนที่ไปทิศทางใดก็ได้

h = sqrt ( (current_cell.x – goal.x)2 + (current_cell.y – goal.y)2 )



รูปภาพที่ 5. ตัวอย่างที่สามารถคำนวณด้วยวิธี Euclidean Distance ได้
ที่มา : https://www.geeksforgeeks.org/a-search-algorithm/

เราสามารถใช้ Fibonacci heap เพื่อนำไปเปิดรายการแทนการใช้ binary heap/self-balancing tree และมันจะมีประสิทธิภาพที่ดีกว่า  เพื่อเป็นการลดระยะเวลาในการคำนวณ g  เราจะใช้การเขียนโปรแกรมแบบ dynamic ดังตัวอย่างข้างล่างนี้ (โค้ดแค่บางส่วนเท่านั้น) สามารถเข้าไปดูโค้ดที่สมบูรณ์ได้ที่เว็บไซต์ด้านล่าง 
https://www.geeksforgeeks.org/a-search-algorithm/

// A C++ Program to implement A* Search Algorithm
#include<bits/stdc++.h>
using namespace std;
  
#define ROW 9
#define COL 10
  
// Creating a shortcut for int, int pair type
typedef pair<int, int> Pair;
  
// Creating a shortcut for pair<int, pair<int, int>> type
typedef pair<double, pair<int, int>> pPair;
  
// A structure to hold the neccesary parameters
struct cell
{
    // Row and Column index of its parent
    // Note that 0 <= i <= ROW-1 & 0 <= j <= COL-1
    int parent_i, parent_j;
    // f = g + h
    double f, g, h;
};

A* Search Algorithm สามารถนำไปใช้ในเกมต่างๆได้ เช่น
เกม Tower Defense Games เป็นประเภทของวิดีโอเกมที่มีเป้าหมายคือ เพื่อปกป้องดินแดนและหรือทรัพย์สมบัติของผู้เล่น โดยขัดขวางการโจมตีจากฝ่ายตรงข้าม ทำได้โดยวางโครงสร้างการป้องกันบนหรือตามแนวเส้นทางการโจมตี
A* Search Algorithm จะถูกนำมาใช้ในการหาเส้นทางที่สั้นที่จุดจากจุดหนึ่งไปยังอีกจุดหนึ่ง เราสามารถใช้ A* Search Algorithm เพื่อหาเส้นทางไปยังจุดเป้าหมาย 

ความซับซ้อนของเวลา
พิจารณาจากกราฟ มันจะพาเราเดินทางไปทุกจุดเพื่อไปยังจุดเป้าหมาย เช่น พิจารณากราฟที่จุดเริ่มต้นและจุดเป้าหมายเชื่อมต่อกันเป็นชุดของด้าน คือ  – 0(source) –>1 –> 2 –> 3 (target)
ความซับซ้อนของเวลาในกรณีที่แย่ๆ คือ O(E) เมื่อ E คือ จำนวนด้านในกราฟ

Auxiliary Space
Auxiliary space ในกรณีที่แย่ คือ  O(V) เมื่อ V คือ จำนวนจุดทั้งหมด

บทสรุป
1. มีจุดกำเนิดหนึ่งจุดและจุดเป้าหมายอีกหนึ่งจุด
→ ใช้ A* Search Algorithm  เมื่อเป็นการไม่ถ่วงน้ำหนักและกราฟถ่วงน้ำหนัก
2. มีจุดกำเนิดหนึ่งจุด และมีจุดเป้าหมายหลายจุด
→ ใช้  BFS  เมื่อเป็นกราฟไม่ถ่วงน้ำหนัก
→ใช้ Dijkstra เมื่อเป็นกราฟถ่วงน้ำหนักที่ไม่มีตัวเลขติดลบ
→ ใช้ Bellman Ford เมื่อเป็นกราฟถ่วงน้ำหนักที่มีตัวเลขติดลบ
3) ระหว่างทุกคู่ของจุด
→ ใช้ Floyd-Warshall และ Johnson’s Algorithm

วิดีโออธิบาย A* Search Algorithm






ขอบคุณแหล่งข้อมูลจาก 
https://www.geeksforgeeks.org/a-search-algorithm/
https://www.youtube.com/watch?v=KNXfSOx4eEE&t=4s
https://www.youtube.com/watch?v=eSOJ3ARN5FM&t=208s




.


ความคิดเห็น

แสดงความคิดเห็น

โพสต์ยอดนิยมจากบล็อกนี้

ทฤษฎีกราฟ 4

รูปภาพ
Euler Circuit คือ กราฟที่ต้องเดินผ่านทุกด้าน ไม่มีการซ้ำด้าน เริ่มตรงไหนจบตรงนั้น โดยจุดยอดทุกจุดจะมีดีกรีคู่ ภาพประกอบจาก https://www.geeksforgeeks.org/wp-content/uploads/Euler 2. png จากภาพจะพบว่าทุกจุดยอดมีดีกรีคู่ เมื่อมีการเดินผ่านทุกด้านโดยไม่ซ้ำจุดเริ่มต้นและสิ้นสุดจะเป็นจุดเดียวกัน Euler Path คือ กราฟที่ต้องเดินผ่านทุกด้าน ไม่มีการซ้ำด้าน แต่ เริ่มต้นกับสิ้นสุดต้องเป็นคนละจุด สามารถสังเกตได้จากกราฟว่าจะมีสองจุดยอดเท่านั้นที่มีดีกรีเป็นเลขคี่ ภาพประกอบจาก https://www.geeksforgeeks.org/eulerian-path-and-circuit/ จากภาพพบว่ามีสองจุดเท่านั้นที่มีดีกรีคี่ คือ จุด 0 และ จุด 4 เมื่อมีการเดินผ่านทุกด้านพบว่าจุดเริ่มต้นและสิ้นสุดเป็นคนละจุดกัน   Hamilton Circuit คือ กราฟที่ไม่จำเป็นต้องเดินผ่านทุกด้าน จุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ไม่ซ้ำจุด ภาพประกอบจาก https://slideplayer.com/slide/ 7549367/ เมื่อเดินผ่านทุกจุดพบว่าจุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ทั้งสองภาพ H...
อ่านเพิ่มเติม

ทฤษฎีกราฟ 3

รูปภาพ
Bipartite graph คือ กราฟที่สามารถแบ่งออกเป็นสองส่วน โดยทั้งสองส่วนนั้นจะมีเส้นเชื่อมเชื่อมกันแต่จะไม่มีเส้นเชื่อมภายในส่วนเดียวกัน ภาพประกอบจาก https://study.com/cimages/multimages/ 16/ bipartite 4. jpg จากภาพจะพบว่าสามารถแบ่งกราฟออกเป็นสองส่วน โดยแต่ละจุดยอดของกลุ่ม 1 จะมีเส้นเชื่อมไปยังกลุ่ม 2 ทุกเส้นแต่ไม่มีเส้นใดเลยที่เชื่อมกันเองภายในกลุ่ม การแทนที่กราฟและการสมสัณฐานของกราฟ (Representing graph and graph Isomorphism) การแทนที่กราฟด้วย Adjacency matrix แบ่งเป็น แบบไม่มีทิศทางและแบบมีทิศทาง ภาพประกอบจาก https://bournetocode.com/projects/AQA_A_Theory/pages/graph.html จากภาพเป็นการแทนที่กราฟด้วย Adjacency Matrix กราฟเป็นแบบไม่มีทิศทาง จุดยอดที่มีเส้นเชื่อมไปยังอีกจุดยอดหนึ่งจะแทนด้วย เลข 1 แต่ถ้าไม่มีจะแทนด้วย เลข 0 ในกรณีที่กราฟนั้นเป็นกราฟเชิงเดียวหรือ simple graph โดยอันดับแรกจะเขียนจุดยอดที่หลักและแถว จากนั้นให้สังเกตแต่ละจุดยอดว่ามีเส้นเชื่อมไปยังจุดใดบ้างให้ทำแบบนี้ไปเรื่อยๆจนถึงจุดยอดสุดท้าย ภาพประกอบจาก https://bournetocode.com...
อ่านเพิ่มเติม

ทฤษฎีกราฟ

รูปภาพ
ทฤษฎีกราฟ กราฟมีบทบาทสำคัญกับชีวิตของเราอย่างไร ? ถนนที่เราใช้ในการสัญจรเป็นตัวอย่างหนึ่งที่มีการนำทฤษฎีกราฟมาใช้รวมทั้งการวางระบบท่อประปา และวงจรไฟฟ้า ชีวิตประจำวันของเราล้วนเกี่ยวข้องกับคณิตศาสตร์ในเรื่องต่างๆรวมถึงเรื่องทฤษฎีกราฟ กราฟ G ประกอบด้วยคู่ลำดับของเซต คือ 1.          เซตของจุดยอด (Vertex) ที่ไม่เป็นเซตว่าง V(G) 2.          เซตของเส้นเชื่อม (Edge) ระหว่างคู่ที่เชื่อมจุดยอด E(G) ภาพที่ 1 ภาพประกอบจาก https://www 3. nd.edu/~dgalvin 1/40210/40210 _F 12/ CGT_early.pdf จากภาพ   เซตของจุดยอด หรือ V(G) คือ { a, b, c, d, e, f, g, h}   เซตของเส้นเชื่อมที่เชื่อมจุดยอด หรือ E(G) คือ {{a, e},{a, d},{b, e},{b, g},{b, c},{c, f},{d, f},                                                                     ...
อ่านเพิ่มเติม