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

ปัญหา ​

• อินพุต
  • ราคาของอุปกรณ์แต่ละชิ้น $w_{1},w_{2},\ldots ,w_{n}$
  • ค่า ​$p(i,j)\,$ สำหรับ $1\leq i\leq n$ และ $1\leq j\leq k$
• เอาต์พุต
  • ซับเซต $E\subseteq \{1,2,\ldots ,k\}$
• เงื่อนไข
  1. สำหรับงาน $j\,$ ทุกงานมีอุปกรณ์ $i\in E$ ที่ทำให้ $p(i,j)=1\,$
  2. ค่า $\sum _{i\in E}w_{i}$ มีค่าต่ำที่สุดในซับเซต $E\,$ ใดๆ ที่สอดคล้องกับเงื่อนไขข้อที่ 1

อัลกอริทึม

เราสามารถมองวัตถุที่เราต้องการค้นหาเป็นซับเซตของเซตที่มีสมาชิก $n\,$ ตัว ซึ่งเราสามารถแทนซับเซตนี้ได้ด้วยอะเรย์ $g[]$ ขนาด n ช่อง โดยที่ $g[i]=1\,$ ถ้า $i\in E\,$ และ $g[i]=2\,$ ถ้า $i\not \in E$

เราสามารถตรวจสอบว่าซับเซตที่กำหนดให้อันหนังสือเป็นซับเซตที่สอดคล้องกับเงื่อนไขข้อที่ 1 ได้ด้วยฟังก์ชัน check> ซึ่งจะคืนค่า true ถ้าซับเซตสอดคล้องกับเงื่อนไขข้อ 1 และคิืนค่า false หากซับเซตไม่สอดคล้องกับเงื่อนไข

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            
}

เราเห็นได้อย่างชัดเจนว่าฟังก์ชัน check มีเวลาการทำงานเท่ากับ ​$O(nk)\,$

เมื่อเราได้ซับเซตที่ตรงกับสมบัติข้อที่ 1 แล้ว เราจะต้องหาราคารวมของอุปกรณ์ทั้งหมดในเซต $E\,$ ซึ่งสามารถทำได้อย่างง่ายดายในเวลา $O(n)\,$ ด้วยฟังก์ชัน total ข้างล่างนี้

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)
    }
}

เนื่องจากมีจำนวนซับเซตที่เป็นไปได้ทั้งหมด $2^{n}\,$ ซับเซต และสำหรับแต่ละซับเซตเราใช้เวลาเช็คว่ามันตรงกับเงื่อนไข 1 หรือไม่ในเวลา $O(nk)\,$ และใช้เวลาในการหาราคาอุปกรณ์รวมเท่ากับ $O(n)\,$ ฉะนั้นเวลาการทำงานของอัลกอริทึมนี้มีค่าเท่ากับ $O(2^{n}(nk+n))=O(nk2^{n})\,$