418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 10 - ประวัติรุ่นแก้ไข

Aoy เมื่อ 10:04, 4 กันยายน 2552

2009-09-04T10:04:42Z

Aoy เมื่อ 05:02, 24 สิงหาคม 2552

2009-08-24T05:02:51Z

Aoy เมื่อ 04:53, 24 สิงหาคม 2552

2009-08-24T04:53:46Z

Aoy เมื่อ 04:48, 24 สิงหาคม 2552

2009-08-24T04:48:03Z

Aoy เมื่อ 05:31, 20 สิงหาคม 2552

2009-08-20T05:31:55Z

Aoy เมื่อ 05:30, 20 สิงหาคม 2552

2009-08-20T05:30:41Z

Aoy เมื่อ 05:24, 20 สิงหาคม 2552

2009-08-20T05:24:58Z

Aoy: หน้าที่ถูกสร้างด้วย 'อินพุต: จุด $n \,$ จุดในระนาบสองมิติ เอาพุต: Hamiltonian Cycle…'

2009-08-20T05:23:55Z

หน้าที่ถูกสร้างด้วย 'อินพุต: จุด <math>n \,</math> จุดในระนาบสองมิติ เอาพุต: Hamiltonian Cycle…'

หน้าใหม่

อินพุต: จุด <math>n \,</math> จุดในระนาบสองมิติ

เอาพุต: Hamiltonian Cycle ที่มีระยะทางสั้นที่สุด

แนวคิด วัตถุที่เราสนใจคือ Hamiltonian Cycle ทั้งหมด พิจาณา Hamiltonian Cycle หนึ่งที่อาจเป็นไปได้ เช่น <math>(x_1,y_1) \rightarrow (x_2,y_2)\rightarrow ... \rightarrow (x_n,y_n) \rightarrow (x_1,y_1)</math> สังเกตว่าถ้าไม่พิจารณาจุดแรกกับจุดสุดท้าย นั่นคือ <math>(x_1,y_1)</math> จุดที่อยู่ระหว่างจุดแรกกับจุดสุดท้ายนี้ เมื่อนำมาเรียงสับเปลี่ยนกันก็จะเกิด Hamiltonian Cycle ใหม่ขึ้นอีก ดังนั้นการหยิบวัตถุที่สนใจขึ้นมาดู คือการสร้าง Hamiltonian Cycle ทั้งหมดที่เป็นไปได้จากกราฟนั่นเอง จากแนวคิดข้างต้น ก็คือการสร้าง permutation นั่นเอง ซึ่ง ถ้าไม่นับจุดแรกและจุดสุดท้าย จะมีจุดตรงกลางให้เรียงสับเปลี่ยนทั้งหมด <math>n-1 \,</math> จุด ก็จะได้การเรียงสับเปลี่ยนทั้งหมด <math>(n-1)! \,</math>และเราสามารถเลือกจุดแรก (เลือกจุดสุดท้ายด้วยในขณะเดียวกัน) ได้อีกทั้งหมด <math>n \,</math> จุด ดังนั้นจำนวน Hamiltonian Cycle ทั้งหมด จะได้ <math>n! \,</math> ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน

@@ แถว 7: / แถว 7: @@
 จากแนวคิดข้างต้น สามารถนำมาเขียนเป็น pseudocode ได้ดังนี้
 GENERATE(k)
-: if k=0
-:: c=COST(p,n) // COST เป็น subroutine ที่ใช้ในการคำนวณระยะทางของ Hamiltonian Cycle ตามสูตรในโจทย์
+     if k=0
-:: if c < min  // ถ้า ระยะทางของ Hamiltonian cycle ที่พิจารณาขณะนี้มีค่าน้อยกว่า ระยะทางของ cycle ที่เคยจำไว้
-::: min <-- c // ให้เปลี่ยนมาจำระยะทางที่สั้นที่สุดของ cycle นี้แทน
+         c=COST(p,n) // COST เป็น subroutine ที่ใช้ในการคำนวณระยะทางของ Hamiltonian Cycle ตามสูตรในโจทย์
-::: for i= 0 to i< n
+                  if c < min  // ถ้า ระยะทางของ Hamiltonian cycle ที่พิจารณาขณะนี้มีค่าน้อยกว่า ระยะทางของ cycle ที่เคยจำไว้
-:::: p_min[i] <-- p[i] // จำว่า cycle นั้นคือ cycle ไหน (วิ่งจากจุดไหน ไปจุดไหน)
-:else
+             min <-- c // ให้เปลี่ยนมาจำระยะทางที่สั้นที่สุดของ cycle นี้แทน
-:: for i=1 to i<= n // จุด <math>(x_i,y_i) \,</math> เป็นจุดเริ่มต้นของ cycle
+                          for i= 0 to i< n
-::: for j=1 to j<=n
+                 p_min[i] <-- p[i] // จำว่า cycle นั้นคือ cycle ไหน (วิ่งจากจุดไหน ไปจุดไหน)
-:::: if j != i  // จะทำการหา permutation โดยการสลับจุดต่าง ๆ ที่ไม่ใช่จุดเริ่มต้น
+         } // end if  c < min
-::::: if used[j] != 1
+     }else{
-:::::: used[j] <-- 1
+             for i=1 to i<= n // จุด <math>(x_i,y_i) \,</math> เป็นจุดเริ่มต้นของ cycle
-:::::: p[k-1] <-- j
-:::::: GENERATE(k-1)
+                 for j=1 to j<=n
-:::::: used[j]<-- 0

@@ แถว 17: / แถว 17: @@
 :: for i=1 to i<= n // จุด <math>(x_i,y_i) \,</math> เป็นจุดเริ่มต้นของ cycle
 ::: for j=1 to j<=n
-:::: if i != j  // จะทำการหา permutation โดยการสลับจุดต่าง ๆ ที่ไม่ใช่จุดเริ่มต้น
+:::: if j != i  // จะทำการหา permutation โดยการสลับจุดต่าง ๆ ที่ไม่ใช่จุดเริ่มต้น
-::::: if used[i] != 1
+::::: if used[j] != 1
-:::::: used[i] <-- 1
+:::::: used[j] <-- 1
-:::::: p[k-1] <-- i
+:::::: p[k-1] <-- j
 :::::: GENERATE(k-1)
-:::::: used[i]<-- 0
+:::::: used[j]<-- 0

@@ แถว 9: / แถว 9: @@
 GENERATE(k)
 : if k=0
-:: c=COST(p,n)
+:: c=COST(p,n) // COST เป็น subroutine ที่ใช้ในการคำนวณระยะทางของ Hamiltonian Cycle ตามสูตรในโจทย์
-:: if c < min
+:: if c < min  // ถ้า ระยะทางของ Hamiltonian cycle ที่พิจารณาขณะนี้มีค่าน้อยกว่า ระยะทางของ cycle ที่เคยจำไว้
-::: min <-- c
+::: min <-- c // ให้เปลี่ยนมาจำระยะทางที่สั้นที่สุดของ cycle นี้แทน
 ::: for i= 0 to i< n
-:::: p_min[i] <-- p[i]
+:::: p_min[i] <-- p[i] // จำว่า cycle นั้นคือ cycle ไหน (วิ่งจากจุดไหน ไปจุดไหน)
 :else
-:: for i=1 to i<= n
+:: for i=1 to i<= n // จุด <math>(x_i,y_i) \,</math> เป็นจุดเริ่มต้นของ cycle
 ::: for j=1 to j<=n
-:::: if i != j
+:::: if i != j  // จะทำการหา permutation โดยการสลับจุดต่าง ๆ ที่ไม่ใช่จุดเริ่มต้น
 ::::: if used[i] != 1
 :::::: used[i] <-- 1

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 04:48, 24 สิงหาคม 2552
แถว 6:		แถว 6:

	จากแนวคิดข้างต้น สามารถนำมาเขียนเป็น pseudocode ได้ดังนี้		จากแนวคิดข้างต้น สามารถนำมาเขียนเป็น pseudocode ได้ดังนี้
		+
		+	GENERATE(k)
		+	: if k=0
		+	:: c=COST(p,n)
		+	:: if c < min
		+	::: min <-- c
		+	::: for i= 0 to i< n
		+	:::: p_min[i] <-- p[i]
		+	:else
		+	:: for i=1 to i<= n
		+	::: for j=1 to j<=n
		+	:::: if i != j
		+	::::: if used[i] != 1
		+	:::::: used[i] <-- 1
		+	:::::: p[k-1] <-- i
		+	:::::: GENERATE(k-1)
		+	:::::: used[i]<-- 0

@@ แถว 3: / แถว 3: @@
 เอาพุต: Hamiltonian Cycle ที่มีระยะทางสั้นที่สุด
-แนวคิด วัตถุที่เราสนใจคือ Hamiltonian Cycle ทั้งหมด พิจาณา Hamiltonian Cycle หนึ่งที่อาจเป็นไปได้ เช่น <math>(x_1,y_1) \rightarrow (x_2,y_2)\rightarrow ... \rightarrow (x_n,y_n) \rightarrow (x_1,y_1)\,</math> สังเกตว่าถ้าไม่พิจารณาจุดแรกกับจุดสุดท้าย นั่นคือ <math>(x_1,y_1)</math> จุดที่อยู่ระหว่างจุดแรกกับจุดสุดท้ายนี้ เมื่อนำมาเรียงสับเปลี่ยนกันก็จะเกิด Hamiltonian Cycle ใหม่ขึ้นอีก ดังนั้นการหยิบวัตถุที่สนใจขึ้นมาดู ก็คือการสร้าง permutation นั่นเอง ซึ่ง ถ้าไม่นับจุดแรกและจุดสุดท้าย จะมีจุดตรงกลางให้เรียงสับเปลี่ยนทั้งหมด <math>n-1 \,</math> จุด ก็จะได้การเรียงสับเปลี่ยนทั้งหมด <math>(n-1)! \,</math>และเราสามารถเลือกจุดแรก (เลือกจุดสุดท้ายด้วยในขณะเดียวกัน) ได้อีกทั้งหมด <math>n \,</math> จุด ดังนั้นจำนวน Hamiltonian Cycle ทั้งหมด จะได้ <math>n! \,</math> ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน
+แนวคิด วัตถุที่เราสนใจคือ Hamiltonian Cycle ทั้งหมด พิจาณา Hamiltonian Cycle หนึ่งที่อาจเป็นไปได้ เช่น <math>(x_1,y_1) \rightarrow (x_2,y_2)\rightarrow ... \rightarrow (x_n,y_n) \rightarrow (x_1,y_1) \,</math> สังเกตว่าถ้าไม่พิจารณาจุดแรกกับจุดสุดท้าย นั่นคือ <math>(x_1,y_1)</math> จุดที่อยู่ระหว่างจุดแรกกับจุดสุดท้ายนี้ เมื่อนำมาเรียงสับเปลี่ยนกันก็จะเกิด Hamiltonian Cycle ใหม่ขึ้นอีก ดังนั้นการหยิบวัตถุที่สนใจขึ้นมาดู ก็คือการสร้าง permutation นั่นเอง ซึ่ง ถ้าไม่นับจุดแรกและจุดสุดท้าย จะมีจุดตรงกลางให้เรียงสับเปลี่ยนทั้งหมด <math>n-1 \,</math> จุด ก็จะได้การเรียงสับเปลี่ยนทั้งหมด <math>(n-1)! \,</math>แบบ และเราสามารถเลือกจุดแรก (เลือกจุดสุดท้ายด้วยในขณะเดียวกัน) ได้อีกทั้งหมด <math>n \,</math> จุด ดังนั้นจำนวน Hamiltonian Cycle ทั้งหมด จะได้ <math>n(n-1)!=n! \,</math> ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน
 จากแนวคิดข้างต้น สามารถนำมาเขียนเป็น pseudocode ได้ดังนี้

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 05:24, 20 สิงหาคม 2552
แถว 4:		แถว 4:

	แนวคิด วัตถุที่เราสนใจคือ Hamiltonian Cycle ทั้งหมด พิจาณา Hamiltonian Cycle หนึ่งที่อาจเป็นไปได้ เช่น <math>(x_1,y_1) \rightarrow (x_2,y_2)\rightarrow ... \rightarrow (x_n,y_n) \rightarrow (x_1,y_1)</math> สังเกตว่าถ้าไม่พิจารณาจุดแรกกับจุดสุดท้าย นั่นคือ <math>(x_1,y_1)</math> จุดที่อยู่ระหว่างจุดแรกกับจุดสุดท้ายนี้ เมื่อนำมาเรียงสับเปลี่ยนกันก็จะเกิด Hamiltonian Cycle ใหม่ขึ้นอีก ดังนั้นการหยิบวัตถุที่สนใจขึ้นมาดู คือการสร้าง Hamiltonian Cycle ทั้งหมดที่เป็นไปได้จากกราฟนั่นเอง จากแนวคิดข้างต้น ก็คือการสร้าง permutation นั่นเอง ซึ่ง ถ้าไม่นับจุดแรกและจุดสุดท้าย จะมีจุดตรงกลางให้เรียงสับเปลี่ยนทั้งหมด <math>n-1 \,</math> จุด ก็จะได้การเรียงสับเปลี่ยนทั้งหมด <math>(n-1)! \,</math>และเราสามารถเลือกจุดแรก (เลือกจุดสุดท้ายด้วยในขณะเดียวกัน) ได้อีกทั้งหมด <math>n \,</math> จุด ดังนั้นจำนวน Hamiltonian Cycle ทั้งหมด จะได้ <math>n! \,</math> ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน		แนวคิด วัตถุที่เราสนใจคือ Hamiltonian Cycle ทั้งหมด พิจาณา Hamiltonian Cycle หนึ่งที่อาจเป็นไปได้ เช่น <math>(x_1,y_1) \rightarrow (x_2,y_2)\rightarrow ... \rightarrow (x_n,y_n) \rightarrow (x_1,y_1)</math> สังเกตว่าถ้าไม่พิจารณาจุดแรกกับจุดสุดท้าย นั่นคือ <math>(x_1,y_1)</math> จุดที่อยู่ระหว่างจุดแรกกับจุดสุดท้ายนี้ เมื่อนำมาเรียงสับเปลี่ยนกันก็จะเกิด Hamiltonian Cycle ใหม่ขึ้นอีก ดังนั้นการหยิบวัตถุที่สนใจขึ้นมาดู คือการสร้าง Hamiltonian Cycle ทั้งหมดที่เป็นไปได้จากกราฟนั่นเอง จากแนวคิดข้างต้น ก็คือการสร้าง permutation นั่นเอง ซึ่ง ถ้าไม่นับจุดแรกและจุดสุดท้าย จะมีจุดตรงกลางให้เรียงสับเปลี่ยนทั้งหมด <math>n-1 \,</math> จุด ก็จะได้การเรียงสับเปลี่ยนทั้งหมด <math>(n-1)! \,</math>และเราสามารถเลือกจุดแรก (เลือกจุดสุดท้ายด้วยในขณะเดียวกัน) ได้อีกทั้งหมด <math>n \,</math> จุด ดังนั้นจำนวน Hamiltonian Cycle ทั้งหมด จะได้ <math>n! \,</math> ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน
		+
		+	จากแนวคิดข้างต้น สามารถนำมาเขียนเป็น pseudocode ได้ดังนี้