Cardcaptor เมื่อ 16:04, 28 สิงหาคม 2552

2009-08-28T16:04:54Z

Cardcaptor: หน้าที่ถูกสร้างด้วย '* อินพุต ** ราคาของของแต่ละชิ้น $w_1, w_2, \ldots, w_n$ '

2009-08-28T15:20:12Z

หน้าที่ถูกสร้างด้วย '* อินพุต ** ราคาของของแต่ละชิ้น <math>w_1, w_2, \ldots, w_n</math>'

หน้าใหม่

* อินพุต
** ราคาของของแต่ละชิ้น <math>w_1, w_2, \ldots, w_n</math>

←รุ่นแก้ไขก่อนหน้า		รุ่นแก้ไขเมื่อ 16:04, 28 สิงหาคม 2552
แถว 1:		แถว 1:
		+	== ปัญหา ==
	* อินพุต		* อินพุต
−	** ~~ราคาของของแต่ละชิ้น~~ <math>w_1, w_2, \ldots, w_n</math>	+	** ราคาของอุปกรณ์แต่ละชิ้น <math>w_1, w_2, \ldots, w_n</math>
		+	** ค่า <math>p(i,j) \,</math> สำหรับ <math>1 \leq i \leq n</math> และ <math>1 \leq j \leq k</math>
		+	* เอาต์พุต
		+	** ซับเซต <math>E \subseteq \{1, 2, \ldots, k\}</math>
		+	* เงื่อนไข
		+	*# สำหรับงาน <math>j \,</math> ทุกงานมีอุปกรณ์ <math>i \in E</math> ที่ทำให้ <math>p(i,j) = 1 \,</math>
		+	*# ค่า <math>\sum_{i \in E} w_i</math> มีค่าต่ำที่สุดในซับเซต <math>E \,</math> ใดๆ ที่สอดคล้องกับเงื่อนไขข้อที่ 1
		+
		+	== อัลกอริทึม ==
		+	เราสามารถมองวัตถุที่เราต้องการค้นหาเป็นซับเซตของเซตที่มีสมาชิก <math>n \,</math> ตัว ซึ่งเราสามารถแทนซับเซตนี้ได้ด้วยอะเรย์ <math>g[]</math> ขนาด n ช่อง โดยที่ <math>g[i] = 1 \,</math> ถ้า <math>i \in E \,</math> และ <math>g[i] = 2 \,</math> ถ้า <math>i \not\in E</math>
		+
		+	เราสามารถตรวจสอบว่าซับเซตที่กำหนดให้อันหนังสือเป็นซับเซตที่สอดคล้องกับเงื่อนไขข้อที่ 1 ได้ด้วยฟังก์ชัน <code>check></code> ซึ่งจะคืนค่า <code>true</code> ถ้าซับเซตสอดคล้องกับเงื่อนไขข้อ 1 และคิืนค่า <code>false</code> หากซับเซตไม่สอดคล้องกับเงื่อนไข
		+
		+	check(g,p,n)
		+	{
		+	for j = 1 to k do
		+	{
		+	found = false
		+	for i = 1 to n do
		+	{
		+	if g[i] = 1 and p(i,j) = 1 then
		+	found = true
		+	}
		+	if found = false then
		+	return false
		+	}
		+	return true
		+	}
		+
		+	เราเห็นได้อย่างชัดเจนว่าฟังก์ชัน <code>check</code> มีเวลาการทำงานเท่ากับ <math>O(nk) \,</math>
		+
		+	เมื่อเราได้ซับเซตที่ตรงกับสมบัติข้อที่ 1 แล้ว เราจะต้องหาราคารวมของอุปกรณ์ทั้งหมดในเซต <math>E \,</math> ซึ่งสามารถทำได้อย่างง่ายดายในเวลา <math>O(n) \,</math> ด้วยฟังก์ชัน <code>total</code> ข้างล่างนี้
		+
		+	total(g,w,n)
		+	{
		+	result = 0
		+	for i = 1 to n do
		+	if g[i] = 1 then
		+	result = result + w[i]
		+	return result
		+	}
		+
		+	จากนั้น เราจึงสามารถใช้ฟังก์ชันสองฟังก์ชันข้างบนมาประกอบเป็นอัลกอริทึมสำหรับแก้โจทย์ปัญหาข้อนี้ได้ โดยการหยิบซับเซตขึ้นมาดูทีละซับเซต สำหรับแต่ละซับเซต เราจะเช็คว่ามันสอดคล้องกับเงื่อนไขข้อ 1 หรือไม่ ถ้าใช้ เราจะหาราคารวมของอุปกรณ์ในซับเซต แล้วนำไปเปรียบเทียบกับราคาที่ถูกที่สุดที่เราเคยเจอมา และถ้าราคาใหม่น้อยกว่า เราก็จะจำราคาใหม่เอาไว้พร้อมทั้งซับเซตที่ทำให้ได้ราคาไหมนั้นไว้ด้วย
		+
		+	ตัวแปร min_g[1..n] = อะเรย์ที่แทนซับเซตที่ให้ราคาอุปกรณ์รวมต่ำสุดเท่าที่เคยเจอมา
		+	ตัวแปร min = ราคารวมต่ำสุดที่เคยเจอมา ตอนแรกเซ็ตให้มีค่าสูงๆ เช่น INFINITY
		+
		+	generate(k)
		+	{
		+	if k = 0 then
		+	{
		+	if check(g,p,n) then
		+	{
		+	value = total(g,w,n)
		+	if value < min then
		+	{
		+	min_g = g
		+	min = value
		+	}
		+	}
		+	}
		+	else
		+	{
		+	for g[k] = 1 to 2 do
		+	generate(k-1)
		+	}
		+	}
		+
		+	เนื่องจากมีจำนวนซับเซตที่เป็นไปได้ทั้งหมด <math>2^n \,</math> ซับเซต และสำหรับแต่ละซับเซตเราใช้เวลาเช็คว่ามันตรงกับเงื่อนไข 1 หรือไม่ในเวลา <math>O(nk) \,</math> และใช้เวลาในการหาราคาอุปกรณ์รวมเท่ากับ <math>O(n) \,</math> ฉะนั้นเวลาการทำงานของอัลกอริทึมนี้มีค่าเท่ากับ <math>O(2^n(nk + n)) = O(nk2^n) \,</math>

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

Cardcaptor เมื่อ 16:04, 28 สิงหาคม 2552

Cardcaptor: หน้าที่ถูกสร้างด้วย '* อินพุต ** ราคาของของแต่ละชิ้น w_1, w_2, \ldots, w_n'

Cardcaptor: หน้าที่ถูกสร้างด้วย '* อินพุต ** ราคาของของแต่ละชิ้น $w_1, w_2, \ldots, w_n$ '