Discrete Mathematics

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/ เมื่อเดินผ่านทุกจุดพบว่าจุดเริ่มต้นและสิ้นสุดเป็นจุดเดียวกัน ทั้งสองภาพ Hamil

เราสามารถคำนวณ 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.geeksforg

A* Search Algorithm การประมาณเส้นทางที่สั้นที่สุดในสถานที่ต่างๆในชีวิตประจำวัน ในแผนที่ต่างๆ   หรือในเกมส์ที่มีสิ่งกีดขวางต่างๆมากมาย   หากพิจารณา 2D Grid ที่มีสิ่งกีดขวางหรืออุปสรรคมากมายและพวกเราเริ่มต้นจากจุดกำเนิด ( จุดสีแดง ) เพื่อไปยังจุดมุ่งหมาย ( จุดสีเขียว ) รูปภาพที่ 1. 2D Grid ที่มา : https://www.geeksforgeeks.org/a-search-algorithm/ A* Search Algorithm คืออะไร A* Search algorithm เป็นหลักการที่ได้รับความนิยมที่นำไปใช้ในการค้นหาเส้นทางต่างๆและการนำไปใช้ในเส้นทางผ่านต่างๆในกราฟ ทำไมต้องเป็น A* Search Algorithm เพราะว่า A* Search Algorithm ไม่เหมือนกับหลักการเดินทางผ่านอื่นๆ มันเป็นอัลกอลิทึมที่ดี  มีรายละเอียดที่ชัดเจน และมีประโยชน์ในเกมส์มากมายและในเว็บแผนที่ต่างๆใช้อัลกอลิทึมนี้เพื่อค้นหาเส้นทางที่สั้นที่สุดได้อย่างมีประสิทธิภาพ ( การประมาณ ) คำอธิบาย พิจารณาตารางสี่เหลี่ยมที่มีสิ่งกีดขวางต่างๆมากมายและพวกเราจะเริ่มจากจุดเริ่มต้นเพื่อไปยังจุดเป้าหมายอย่างรวดเร็วที่สุดถ้าเป็นไปได้ เราจึงใช้ A* Search Algorithm มาเป็นตัวช่ว

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