ขั้นตอนวิธีของควิน-แม็กคลัสกีย์

จากวิกิพีเดีย สารานุกรมเสรี

ขั้นตอนวิธีของควิน-แม็กคลัสกีย์ (อังกฤษ: Quine-McCluskey algorithm) เป็นหนึ่งในขั้นตอนวิธีที่ใช้สำหรับการลดรูปนิพจน์ตรรกศาสตร์ให้อยู่ในรูปอย่างง่ายที่มีประสิทธิภาพสูง พัฒนาโดย ดับเบิลยู.วี. ควิน (W.V.Quine) และเอ็ดเวิด เจ. แมกคลัสกีย์ (Edward J. McCluskey)

ขั้นตอนวิธีของควิน-แม็กคลัสกีย์เป็นขั้นตอนวิธีที่ช่วยในการลดรูปนิพจน์ตรรกะได้เมื่อข้อมูลขาเข้าที่มีปริมาณตัวแปรจำนวนมาก แต่ในการทำงานยังมีข้อจำกัดในเรื่องของเวลาอยู่ จึงควรดูขนาดของข้อมูลขาเข้า ว่ามีขนาดเท่าไหร่ และสมควรที่จะใช้วิธีการนี้หรือไม่ หากไม่สมควรควรจะเลือกใช้วิธีการอื่นที่สามารถลดนิพจน์ตรรกะได้ เช่น วิธีการเอกเพรซโซ่ ซึ่งเป็นวิธีการที่จะใช้ผ่านโปรแกรม[ต้องการอ้างอิง]

วิธีการทำงาน[แก้]

วิธีการนี้มีขั้นตอนการทำงานเหมือนกับการทำแผนผังคาร์โนห์ (Karnaugh map หรือ K-map) แต่มีความยืดหยุ่นมากกว่า ในด้านการนำไปประยุกต์เพื่อสร้างโปรแกรมคอมพิวเตอร์อย่างมีประสิทธิภาพ และด้านการใช้งานกับนิพจน์ตรรกศาสตร์ที่มีตัวแปรเป็นจำนวนมาก
ขั้นตอนการทำงาน แบ่งออกเป็นสองขั้นตอน ดังนี้:

  1. รวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอม
  2. สร้างตารางเพื่อหานิพจน์ตรรกศาสตร์ในรูปอย่างง่าย

รหัสเทียม[แก้]

ตัวอย่างรหัสเทียม[แก้]

ตัวอย่างรหัสเทียมสำหรับการทำงานของขั้นตอนวิธีควิน-แมกคลัสกีย์
Function QM1 ( levels ) returns primes
put { } (empty set) into primes
for each level level do
	irredundant level (remove duplicates from level)
	put { } (empty set) into nonprimes	for every term term in level from 1 to the size of level –1 do
		for every term compterm in level from term + 1 to the size of level do
			put –1 into differentLiteral as a flag
			for every literal literal from 1 to NUMINPUTS do
				if literal literal of term  ?  literal literal of compterm then
					if differentLiteral =1 then
						(there was no previous difference)
						put literal into differentLiteral
					else (there was a previous difference)
						put –1 into differentLiteral as a flag
						break (get out of this comparison loop)
					end if
				end if
			end for of literal
			if differentLiteral  ?1 then (there was exactly one difference)
				add term to nonprimes
				add compterm to nonprimes
				add term with 2 in literal differentLiteral to level level + 1
		end for of compterm
	end for of term
	if the size of nonprimes > 0 then
		add all terms not in nonprimes to primes
	else
		break (get out of loop for levels)
	end if
end for of level
return primes

ข้อจำกัด[แก้]

ถึงแม้วิธีการนี้จะได้ผลดีกว่ากว่าแผนผังคาร์โนห์เมื่อใช้ลดนิพจน์ตรรกศาสตร์ที่มีตัวแปรมากกว่าสี่ตัวก็ตาม แต่เวลาที่ใช้ในการทำงานจะเพิ่มมากขึ้นอย่างรวดเร็วตามจำนวนของตัวแปร (เพิ่มขึ้นในอัตราส่วนแบบฟังก์ชันเลขชี้กำลัง) โดยสามารถแสดงในรูปแบบของฟังก์ชันขอบเขตสูงสุดของตัวแปร n ตัว ได้เป็น \frac{3^{n}}{n} ซึ่งหากนิพจน์ตรรกศาสตร์มีจำนวนตัวแปรเท่ากับ 32 ตัว หรือ n=32 อาจจะมีเทอมที่ไม่สามารถจับคู่ได้มากกว่า 6.5\times1015 เทอม ดังนั้นหากต้องการลดนิพจน์ตรรกศาสตร์ที่มีจำนวนตัวแปรมากๆ ควรใช้วิธีการอื่นแทน เช่น การใช้โปรแกรมเอสเปรสโซ่ เป็นต้น
ขั้นตอนวิธีนี้ เป็นขั้นตอนวิธีปัญหา เอ็นพี-แบบยาก เพราะมีอัตราการทำงานเติบโตในรูปของฟังก์ชันเอกซ์โพเน็นเชียล

ปัญหาที่เกี่ยวข้อง[แก้]

  • วิธีการของแพททริก

ตัวอย่างขั้นตอนการทำงาน[แก้]

ลดรูปนิพจน์ตรรกศาสตร์ต่อไปนี้:

f (A,B,C,D) =\sum m (4,5,6,8,9,10,13) + d (0,7,15) \,

รวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอม[แก้]

เนื่องจากนิพจน์ตรรกศาสตร์ดังกล่าว มีตัวแปรจำนวน 4 ตัว ได้แก่ A, B, C และ D ดังนั้นจึงสามารถสร้างตารางค่าความจริงได้ทั้งหมด 16 กรณี ดังนี้
A B C D - f
m0 0 0 0 0 - x
m1 0 0 0 1 - 0
m2 0 0 1 0 - 0
m3 0 0 1 1 - 0
m4 0 1 0 0 - 1
m5 0 1 0 1 - 1
m6 0 1 1 0 - 1
m7 0 1 1 1 - x
m8 1 0 0 0 - 1
m9 1 0 0 1 - 1
m10 1 0 1 0 - 1
m11 1 0 1 1 - 0
m12 1 1 0 0 - 0
m13 1 1 0 1 - 1
m14 1 1 1 0 - 0
m15 1 1 1 1 - x


ในการรวมเทอมเข้าด้วยกันเพื่อลดจำนวนเทอมนั้น จะพิจารณาจากเทอมที่มีค่าของ A,B,C และ D ต่างกันเพียง 1 บิต ตัวอย่างเช่น 0000 กับ 0100 (ต่างกันที่บิตที่สอง) หรือ 0000 กับ 1000 (ต่างกันที่บิตที่หนึ่ง) เป็นต้น ดังนั้นเพื่อให้ง่ายต่อการพิจารณา จะทำการแบ่งกลุ่มที่มีค่าของ A,B,C และ D ต่างกันเพียง 1 บิตโดยแบ่งตามจำนวนของเลข 1 ในค่า A,B,C และ D ดังนี้

จำนวนเลข 1 ใน A,B,C,D m ค่าของ A,B,C,D
0 m0 0000
1 m4 0100
m8 1000
2 m5 0101
m6 0110
m9 1001
m10 1010
3 m7 0111
m13 1101
4 m15 1111


จากตารางด้านบน จะเห็นว่าเราสามารถแบ่งกลุ่มที่มีค่าของ A,B,C,D ต่างกันเพียง 1 บิทได้เป็น 5 กลุ่ม ดังนั้นในการรวมเทอมที่มีรูปแบบคล้ายกัน เราจะพิจารณาแต่ละกลุ่มเทียบกันโดยใช้วิธีการเขียนตาราง ดังนี้

  1. เขียนค่าของ ABCD ที่ต้องการพิจารณาลงในคอลัมน์เริ่มต้นของตาราง (คอลัมน์ที่ 1)
  2. เปรียบเทียบค่า ABCD ที่ต่างกันเพียง 1 บิต (ค่าของกลุ่มติดกันที่แบ่งไว้ข้างต้น) เพื่อยุบรวมเป็นตัวเดียว โดยแทนตัวที่ต่างกันด้วย "-" และแทนตัวที่เหมือนกันด้วยตัวเลขนั้นๆ เขียนผลลัพธ์ลงในคอลัมน์ถัดไป (คอลัมน์ที่ 2) ตัวอย่างเช่น เปรียบเทียบ 0000 กับ 0100 แล้วรวมเป็น 0-00, เปรียบเทียบ 0000 กับ 1000 แล้วรวมเป็น -000 เป็นต้น
  3. เมื่อยุบรวมพจน์เรียบร้อยแล้ว ให้ทำการเขียนเครื่องหมายถูก "/" หากยุบไม่ได้ก็ใส่เครื่องหมายดอกจัน "*" ไว้ด้านหลังพจน์ที่ถูกยุบรวมแล้ว
  4. ทำการเปรียบเทียบค่า ABCD ไปเรื่อยๆ เพื่อยุบรวมพจน์จนกระทั่งไม่สามารถยุบรวมได้อีก
คอลัมน์ที่ 1 คอลัมน์ที่ 2 คอลัมน์ที่ 3
0000 / 0-00 * 01-- *
- -000 *
0100 / -1-1 *
1000 / 010- /
- 01-0 /
0101 / 100- *
0110 / 10-0 *
1001 /
1010 / 01-1 /
- -101 /
0111 / 011- /
1101 / 1-01 *
-
1111 / -111 /
11-1 /

จากตารางด้านบน แสดงให้เห็นว่าพจน์ที่ไม่สามารถยุบรวมได้อีก มีทั้งหมด 7 พจน์ ได้แก่ 0-00, -000, 100-, 10-0, 1-01, 01-- และ -1-1

สร้างตารางเพื่อหานิพจน์ตรรกศาสตร์ในรูปอย่างง่าย[แก้]

การสร้างตาราง[แก้]

การสร้างตารางในเบื้องต้น มีขั้นตอนดังนี้

  • สำหรับแต่ละแถว คือ พจน์ที่ไม่สามารถยุบรวมได้อีก ที่ได้หามาแล้วในขั้นตอนที่ 1
  • สำหรับแต่ละคอลัมน์ คือ พจน์ที่มีค่าฟังก์ชันเป็น 1
  • ทำเครื่องหมายกากบาท "X" ในตารางตามช่องที่มีตัวเลขในแถวและคอลัมน์เหมือนกัน


ขั้นตอนที่ 1
4 5 6 8 9 10 13
0,4 (0-00) X
0,8 (-000) X
8,9 (100-) X X
8,10 (10-0) X X
9,13 (1-01) X X
4,5,6,7 (01--) X X X
5,7,13,15 (-1-1) X X

การหารูปอย่างง่ายของนิพจน์ตรรกศาสตร์[แก้]

หลังจากสร้างตารางเสร็จเรียบร้อยแล้ว หลักการในการหารูปอย่างง่ายของนิพจน์ตรรกศาสตร์ คือการเลือกแถวให้น้อยที่สุด โดยเลือกให้ครอบคลุมทุกคอลัมน์

  • ในการเลือกแถวเบื้องต้นนั้น จะทำการตรวจสอบคอลัมน์ที่มีเครื่องหมาย "X" เพียงแถวเดียว แล้วทำการเลือกแถวนั้นๆ เนื่องจากเป็นแถวที่จำเป็นต้องเลือก หากไม่เลือกจะทำให้ไม่ครอบคลุมครบทุกคอลัมน์
  • ทำเครื่องหมายทั้งในแนวแถวและคอลัมน์ที่เลือก
ขั้นตอนที่ 2
4 5 6 8 9 10 13
0,4 (0-00) X
0,8 (-000) X
8,9 (100-) X X
8,10 (10-0) X X
9,13 (1-01) X X
4,5,6,7 (01--) X X X
5,7,13,15 (-1-1) X X
  • จากนั้นให้ทำเครื่องหมายให้กับ "X" ที่อยู่ในคอลัมน์เดียวกันทั้งหมด เพื่อแสดงว่าคอลัมน์นั้นๆ ได้ถูกครอบคลุมโดยแถวที่เลือกไปแล้ว
ขั้นตอนที่ 3
4 5 6 8 9 10 13
0,4 (0-00) X
0,8 (-000) X
8,9 (100-) X X
8,10 (10-0) X X
9,13 (1-01) X X
4,5,6,7 (01--) X X X
5,7,13,15 (-1-1) X X
  • เลือกแถวที่ครอบคลุม "X" ในคอลัมน์ที่เหลืออยู่ แล้วทำเครื่องหมายสำหรับแถวนั้น (หากมีหลายแถวจะต้องเลือกแถวที่ครอบคลุมคอลัมน์ได้มากที่สุด)
  • ผลที่ได้จะมีจำนวนแถวที่เลือกน้อยที่สุด และครอบคลุมส่วนที่เหลือทั้งหมดได้
ขั้นตอนที่ 4
4 5 6 8 9 10 13
0,4 (0-00) X
0,8 (-000) X
8,9 (100-) X X
8,10 (10-0) X X
9,13 (1-01) X X
4,5,6,7 (01--) X X X
5,7,13,15 (-1-1) X X

ดังนั้น นิพจน์ตรรกศาสตร์ในรูปอย่างง่าย คือ : f_{A,B,C,D} = AB'D' + AC'D + A'B


ดูเพิ่ม[แก้]

อ้างอิง[แก้]

เชื่อมต่อภายนอก[แก้]