ผลต่างระหว่างรุ่นของ "418531 ภาคต้น 2552/โจทยปัญหาการค้นหาด้วยพละกำลังเยี่ยงควายถึก/เฉลยข้อ 10"
ไปยังการนำทาง
ไปยังการค้นหา
Aoy (คุย | มีส่วนร่วม) |
Aoy (คุย | มีส่วนร่วม) |
||
| (ไม่แสดง 4 รุ่นระหว่างกลางโดยผู้ใช้คนเดียวกัน) | |||
| แถว 3: | แถว 3: | ||
เอาพุต: Hamiltonian 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! \,</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 ได้ดังนี้ | จากแนวคิดข้างต้น สามารถนำมาเขียนเป็น pseudocode ได้ดังนี้ | ||
| + | |||
| + | <geshi lang="c"> | ||
| + | GENERATE(k) | ||
| + | { | ||
| + | if k=0 | ||
| + | { | ||
| + | c=COST(p,n) // COST เป็น subroutine ที่ใช้ในการคำนวณระยะทางของ Hamiltonian Cycle ตามสูตรในโจทย์ | ||
| + | if c < min // ถ้า ระยะทางของ Hamiltonian cycle ที่พิจารณาขณะนี้มีค่าน้อยกว่า ระยะทางของ cycle ที่เคยจำไว้ | ||
| + | { | ||
| + | min <-- c // ให้เปลี่ยนมาจำระยะทางที่สั้นที่สุดของ cycle นี้แทน | ||
| + | for i= 0 to i< n | ||
| + | p_min[i] <-- p[i] // จำว่า cycle นั้นคือ cycle ไหน (วิ่งจากจุดไหน ไปจุดไหน) | ||
| + | } // end if c < min | ||
| + | }else{ | ||
| + | for i=1 to i<= n // จุด <math>(x_i,y_i) \,</math> เป็นจุดเริ่มต้นของ cycle | ||
| + | { | ||
| + | for j=1 to j<=n | ||
| + | { | ||
| + | if j != i // จะทำการหา permutation โดยการสลับจุดต่าง ๆ ที่ไม่ใช่จุดเริ่มต้น | ||
| + | { | ||
| + | if used[j] != 1 | ||
| + | { | ||
| + | used[j] <-- 1 | ||
| + | p[k-1] <-- j | ||
| + | GENERATE(k-1) | ||
| + | used[j]<-- 0 | ||
| + | } // end if used[j] != 1 | ||
| + | } // end if j!= i | ||
| + | }// end for j | ||
| + | } // end for i | ||
| + | } // end else (k!=0) | ||
| + | } // end pseudocode | ||
| + | </geshi> | ||
รุ่นแก้ไขปัจจุบันเมื่อ 10:04, 4 กันยายน 2552
อินพุต: จุด จุดในระนาบสองมิติ
เอาพุต: Hamiltonian Cycle ที่มีระยะทางสั้นที่สุด
แนวคิด วัตถุที่เราสนใจคือ Hamiltonian Cycle ทั้งหมด พิจาณา Hamiltonian Cycle หนึ่งที่อาจเป็นไปได้ เช่น สังเกตว่าถ้าไม่พิจารณาจุดแรกกับจุดสุดท้าย นั่นคือ จุดที่อยู่ระหว่างจุดแรกกับจุดสุดท้ายนี้ เมื่อนำมาเรียงสับเปลี่ยนกันก็จะเกิด Hamiltonian Cycle ใหม่ขึ้นอีก ดังนั้นการหยิบวัตถุที่สนใจขึ้นมาดู ก็คือการสร้าง permutation นั่นเอง ซึ่ง ถ้าไม่นับจุดแรกและจุดสุดท้าย จะมีจุดตรงกลางให้เรียงสับเปลี่ยนทั้งหมด จุด ก็จะได้การเรียงสับเปลี่ยนทั้งหมด แบบ และเราสามารถเลือกจุดแรก (เลือกจุดสุดท้ายด้วยในขณะเดียวกัน) ได้อีกทั้งหมด จุด ดังนั้นจำนวน Hamiltonian Cycle ทั้งหมด จะได้ ตรงตามเวลาการทำงานที่โจทย์ต้องการ ส่วนเงื่อนไขในข้อนี้คือ Hamiltonian Cycle ที่มี cost ต่ำที่สุด ฉะนั้นเมื่อหยิบ Hamiltonian Cycle ขึ้นมาพิจารณาแล้วก็ดูว่า cost ของมันต่ำกว่า Cycle ที่เคยจำไว้หรือไม่ ถ้าต่ำกว่าก็เปลี่ยนมาจำ Hamiltonian Cycle ใหม่นี้แทน
จากแนวคิดข้างต้น สามารถนำมาเขียนเป็น pseudocode ได้ดังนี้
<geshi lang="c"> GENERATE(k) {
if k=0
{
c=COST(p,n) // COST เป็น subroutine ที่ใช้ในการคำนวณระยะทางของ Hamiltonian Cycle ตามสูตรในโจทย์
if c < min // ถ้า ระยะทางของ Hamiltonian cycle ที่พิจารณาขณะนี้มีค่าน้อยกว่า ระยะทางของ cycle ที่เคยจำไว้
{
min <-- c // ให้เปลี่ยนมาจำระยะทางที่สั้นที่สุดของ cycle นี้แทน
for i= 0 to i< n
p_min[i] <-- p[i] // จำว่า cycle นั้นคือ cycle ไหน (วิ่งจากจุดไหน ไปจุดไหน)
} // end if c < min
}else{
for i=1 to i<= n // จุด เป็นจุดเริ่มต้นของ cycle
{
for j=1 to j<=n
{
if j != i // จะทำการหา permutation โดยการสลับจุดต่าง ๆ ที่ไม่ใช่จุดเริ่มต้น
{
if used[j] != 1
{
used[j] <-- 1
p[k-1] <-- j
GENERATE(k-1)
used[j]<-- 0
} // end if used[j] != 1
} // end if j!= i
}// end for j
} // end for i
} // end else (k!=0)
} // end pseudocode </geshi>
