Combination

Wednesday, September 08, 2010
8:49 AM

การเลือกของปกติ กับการเลือกของแล้วคืนกลับไป(เลือกซ้ำได้)

เช่นโจทย์การแก้ Combination ของรหัสแม่กุญแจ โดยสร้างเลขทั้งหมดที่เป็นไปได้
วิธีปกติคือ for(i=0;i<10000;i++)
แต่ General Solution คือการวิ่งตรวจสอบทุกแบบที่เป็นไปได้ เช่นมีตัวเลข ABCD สามารถแยกได้เป็น
AAAA
AAAB
…
AAAD
AABA
….
AADD
…
ABAA
…
DDDD

โดย Framework ทั่วไปคือการกำหนด Initial Step แล้วใส่เข้าไปใน Data Structure จากนั้นวนลูปนำของออกมาจาก Data Structure ถ้าตรวจสอบแล้วว่าขั้นนั้นไม่ใช่คำตอบ แล้วใส่ขั้นต่อไปทั้งหมดที่เป็นไปได้เข้าไปใน Data Structure


Backtracking

Wednesday, September 08, 2010
9:01 AM

เป็นกระบวนการสร้าง state ทีละขั้นๆ ไปเรื่อยๆ โดย Data Structure ที่ใช้นั้นปกติจะมี Stack กับ Queue ซึ่งการใช้ Stack มักจะเขียนแทนด้วย Recursive

ในตัวอย่างเรื่อง Padlock นั้นใช้การ recursive แก้ปัญหาดังนี้

void backtracking(int step,int *sol){
	If(step<num_step){
		for(int i=0;i<num_symbol;i++){
			sol[step]=i;
			backtracking(step+1,sol);
	}else{
		check(sol);
	}

}


Search Tree

Wednesday, September 08, 2010
9:23 AM

จากตัวอย่าง Pad Lock
0
00
000
0000 <-- Check
000
0001 <-- Check
000
0002 <-- Check
000
0003 <-- Check
000
00
001
0010 <-- Check



8-Queen Problem

Wednesday, September 08, 2010
9:30 AM

กำหนดตารางหมากรุกมี queen 8 ตัว 
ให้หาวิธีวาง Queen ทั้งหมดที่วาง Queen แล้วไม่ให้กินกันเองได้
(กินได้ 8 ทิศ จนสุดกระดาน)

1st Attempt
ตารางหมากรุกมี 64 ช่อง Queen 8 ตัว ขนาด 648
ตัวแปรที่ใช้เก็บคำตอบเป็นอาเรย์ความยาว 8 สองอัน เก็บ แกน x แกน y

2nd Attempt
ลองเอาครั้งที่ซ้ำกันออก โดยใช้การเลือกช่องว่าจะให้ Queen วางหรือไม่วาง จำนวนแบบทั้งหมดจึงเป็น 264
ปัญหาคือมีการวาง Queen เกินหรือขาดจาก 8 ตัวได้
แก้ได้โดย เพิ่มตัวแปรตอนเรียก Function ที่คอยตรวจสอบว่ามีการเลือก Queen ไปแล้วกี่ช่อง
หรือสะดวกกว่านั้น เพิ่มตัวแปร 2 ตัวชื่อ one กับ zero ที่ระบุว่าจะต้องเลือก 1 กับ 0 อีกกี่ตัว วิธีนี้มีจำนวนแบบทั้งหมด 64C8

3rd Attempt
การวาง Queen ในแต่ละแถวจะต้องมี Queen 1 ตัวเท่านั้น วิธีนี้จะทำให้เหลือเพียง 88 วิธี

4th Attempt
Queen ต้องไม่วางใน Column เดียวกันด้วย วิธีนี้ลงจำนวนวิธีทั้งหมดเหลือเพียง 8!



Permutation

Wednesday, September 08, 2010
9:57 AM

การเรียงสับเปลี่ยน โดยไม่มีการเรียงซ้ำๆกัน

Permutation by Backtracking
ต้องมี Special Condition คือการจำว่าเคยใช้อะไรไปบ้างแล้ว โดยการตรวจสอบจากอาร์เรย์ sol ว่าใช้อะไรไปบ้างแล้ว

วิธีที่ดีกว่าคือมีอาร์เรย์ของ boolean ว่าสัญลักษณ์ตัวนั้นถูกใช้ไปแล้วหรือยัง