ปัญหาการเดินของม้า (Knight's Tour Problem) และการประยุกต์ใช้อัลกอริธึมด้วยภาษา C

 

 

อัลกอริธึม Knight's Tour คืออะไร?

Knight's Tour เป็นหนึ่งในปัญหาคลาสสิกของทฤษฎีกราฟและหมากรุกที่ศึกษาการเดินของม้า (Knight) บนกระดานหมากรุก ตามกฎของหมากรุกม้าสามารถเดินไปในช่องที่ห่างออกไปสองช่องในแนวตั้งและหนึ่งช่องในแนวนอน หรือหนึ่งช่องในแนวตั้งและสองช่องในแนวนอน เป้าหมายคือการเดินชิ้นม้าผ่านทุกช่องบนกระดานให้ครบโดยไม่ซ้ำช่องใดช่องหนึ่ง ซึ่งเราเรียกการเดินที่สำเร็จแบบนี้ว่า "Knight's Tour".

 

ประโยชน์ของ Knight's Tour

ปัญหาการเดินของม้ามีไม่เพียงแค่เป็นปัญหาทางคณิตศาสตร์หรือสันทนาการ เท่านั้น แต่ยังใช้ประยุกต์ในด้านอื่นๆ เช่น การวางแผนเส้นทางในหุ่นยนต์ หรือปัญหาการเดินทางของผู้ขายหนังสือ (Travelling Salesman Problem) ที่มีการค้นหาเส้นทางที่มีต้นทุนต่ำที่สุด และใช้แนวคิดนี้ในการพัฒนาอัลกอริธึมเสริมในการค้นหาเส้นทางที่มีประสิทธิภาพในหลากหลายด้านของวิทยาการคอมพิวเตอร์

 

ตัวอย่างโค้ดภาษา C สำหรับ Knight's Tour

#include
#define N 8

int solveKTUtil(int x, int y, int movei, int sol[N][N],
                int xMove[],  int yMove[]);

/* ฟังก์ชั่นที่ตรวจสอบ index ที่เราเดินไปว่ามีความถูกต้องหรือไม่ */
int isSafe(int x, int y, int sol[N][N])
{
  return ( x >= 0 && x < N && y >= 0 &&
           y < N && sol[x][y] == -1);
}

/* ฟังก์ชั่นที่ตั้งค่าบนกระดานหมากรุกด้วยการเดิน Tour ของ Knight */
void printSolution(int sol[N][N])
{
  for (int x = 0; x < N; x++)
  {
    for (int y = 0; y < N; y++)
      printf(" %2d ", sol[x][y]);
    printf("\n");
  }
}

/* ฟังก์ชั่นสำหรับการแก้ปัญหา Knight's Tour โดยใช้ Backtracking */
int solveKT()
{
  int sol[N][N];

  /* Initialization of solution matrix */
  for (int x = 0; x < N; x++)
    for (int y = 0; y < N; y++)
      sol[x][y] = -1;

  /* xMove[] และ yMove[] กำหนดการเคลื่อนไหวของ Knight  */
  /* xMove[] สำหรับถัดไป x และ yMove[] สำหรับถัดไป y */
  int xMove[8] = {2, 1, -1, -2, -2, -1, 1, 2};
  int yMove[8] = {1, 2, 2, 1, -1, -2, -2, -1};

  // ตำแหน่งเริ่มต้น
  sol[0][0]  = 0;

  /* หากหาทำให้เกิดการเดินของ Knight ครั้งที่ 1 */
  if(solveKTUtil(0, 0, 1, sol, xMove, yMove) == 0)
  {
    printf("Solution does not exist");
    return 0;
  }
  else
    printSolution(sol);

  return 1;
}

/* ฟังก์ชั่นสำหรับหาการเดิน */
int solveKTUtil(int x, int y, int movei, int sol[N][N], int xMove[N],
                int yMove[N])
{
  int k, next_x, next_y;
  if (movei == N*N)
    return 1;

  /* ทดลองการเดินทั้งหมดของ Knight ต่อไปจากตำแหน่งปัจจุบัน x, y */
  for (k = 0; k < 8; k++)
  {
    next_x = x + xMove[k];
    next_y = y + yMove[k];
    if (isSafe(next_x, next_y, sol))
    {
      sol[next_x][next_y] = movei;
      if (solveKTUtil(next_x, next_y, movei+1, sol,
                      xMove, yMove) == 1)
        return 1;
      else
        // Backtracking
        sol[next_x][next_y] = -1;
    }
  }

  return 0;
}

/* Main Function */
int main()
{
  solveKT();
  return 0;
}

 

Usecase ในโลกจริง

ในโลกจริง Knight's Tour อาจใช้เพื่อเป็นการเรียนรู้และฝึกฝนในการโปรแกรมคอมพิวเตอร์ สำหรับการหาเส้นทางในเกม AI หรือหุ่นยนต์ที่ต้องการวิเคราะห์และคำนวณเส้นทางเดินที่ซับซ้อน

 

วิเคราะห์ Complexity และข้อดีข้อเสีย

Complexity

: อัลกอริธึมนี้โดยทั่วไปมีความซับซ้อนในระดับ O(n^2)โดยที่ n คือจำนวนช่องที่ม้าต้องเดินผ่าน ในกรณีที่เลวร้ายที่สุด ความซับซ้อนในการคำนวณสามารถเพิ่มขึ้นอย่างมากเนื่องจากมีความเป็นไปได้ในการเดินถึง 8 ทิศทาง และการหาทางออกที่ถูกต้องต้องทำการ backtrack หลายครั้ง

ข้อดี

: ช่วยฝึกฝนความสามารถในการแก้ปัญหาแบบรีเคอร์ซีฟและปัญหากราฟ

ข้อเสีย

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

 

สรุป

Knight's Tour เป็นอัลกอริธึมที่น่าสนใจซึ่งทำให้เราเข้าใจถึงการใช้และข้อจำกัดของการค้นหาแบบ Backtracking และเหมาะแก่การศึกษาและฝึกฝนทางด้านการค้นหา. หากคุณสนใจที่จะเรียนรู้เกี่ยวกับอัลกอริธึมต่างๆ หรือการประยุกต์ใช้ในการหาเส้นทาง ที่ EPT (Expert-Programming-Tutor) เรามีคอร์สโดยเฉพาะเกี่ยวกับเรื่องนี้ที่จะช่วยให้คุณเข้าใจการทำงานและการประยุกต์ใช้อัลกอริธึมในโลกจริง พร้อมด้วยบทเรียนที่ออกแบบมาเพื่อเสริมสร้างทักษะการแก้ปัญหาและการคิดเชิงตรรกะของคุณ!

 

 

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