พื้นฐาน AI 🤖: EP 5 ปัญหาความพึงพอใจภายใต้ข้อจำกัด

หัวข้อใน ep นี้ได้แก่

1. นิยามของปัญหาความพึงพอใจภายใต้ข้อจำกัด

2. Backtracking Search สำหรับ CSPs

3. Local Search สำหรับ CSPs

1. นิยามของปัญหาความพึงพอใจภายใต้ข้อจำกัด

ปัญหาความพึงพอใจภายใต้ข้อจำกัด (Constraint Satisfaction Problems หรือ CSPs) มีส่วนประกอบ 3 อย่างคือ X, D และ C โดย

X: set ของตัวแปร {X₁, X₂, …, Xₙ}

D: set ของ domain หรือ ค่าที่เป็นไปได้ของ X

C: set ของเงื่อนไขที่จะต้องให้เป็นจริง

ตัวอย่างองค์ประกอบของ CSPs

N Queen Problem

จากกติกาของ N Queen Problem ที่ระบุใน EP3 สามารถระบุองค์ประกอบของ CSP ได้ว่า

X: พิกัดช่อง Xᵢⱼ บนตาราง

D: ค่า {0, 1} ที่ระบุว่าบนช่อง Xᵢⱼ มีราชินีหรือไม่

C: เพราะในแต่ละ row, column และ diagonal มีราชินีได้ 1 พระองค์ ดังนั้นได้

∀i, j, k (Xᵢⱼ, Xᵢₖ) ∈ {(0, 0), (0, 1), (1, 0)} ∧

(Xᵢⱼ, Xₖⱼ) ∈ {(0, 0), (0, 1), (1, 0)} ∧

(Xᵢⱼ, Xᵢ₊ₖ, ⱼ₊ₖ) ∈ {(0, 0), (0, 1), (1, 0)} ∧

(Xᵢⱼ, Xᵢ₊ₖ, ⱼ₋ₖ) ∈ {(0, 0), (0, 1), (1, 0)}

Map Coloring Problem

จากแผนที่จังหวัดตรัง กำหนดให้

X: คือ อำเภอของจังหวัดตรัง = {R, Hu, W, M, S, N, K, Y, Ha, P}

D: คือ สีที่จะระบายลงบนแต่ละอำเภอ = {Red, Blue, Yellow}

C: อำเภอที่อยู่ติดกันต้องมีสีที่ต่างกัน คือ {R≠Hu, Hu≠W, Hu≠M, …}

สามารถเขียนออกมาในรูปแบบกราฟ(ซ้าย) และตัวอย่าง solution (ขวา) ตามภาพด้านล่าง

solution ของปัญหาคือ set ของ คู่ Xᵢ กับ domain ของ Xᵢ แต่ละตัว โดยจะต้องตรงตามเงื่อนไขทั้งหมดของ C, solution ถูกเก็บไว้ในสิ่งที่เรียกว่า “assignment”

Weight Assignment

ใช้ในการหาว่า assignment ไหนมี solution ที่ต้องการ โดยการหา weight assignment สูงสุด มีสูตรคือ

โดย

• x: assignment
• f(x): factor ที่ระบุว่าค่า domain ของ X แต่ละตัวที่ระบุใน assignment ดีมาก-น้อยแค่ไหน โดย fⱼ(x) ≥ 0
• m: จำนวน factor

ตัวอย่าง Weight Assignment

ในกรณีปัญหา map coloring กำหนด factor แต่ละตัวออกมาได้เช่น

โดยในที่นี้ ค่าของ f(x) = 1 เมื่อทั้ง 2 node สีต่างกัน และ f(x) = 0 เมื่อทั้ง 2 node สีเหมือนกัน

สมมติกำหนดให้ assignment แต่ละตัวมีค่า

x₁ = {R : Blue, Hu : Yellow, W : Red, M : Yellow, S : Yellow, N : Red, K : Red, Y : Yellow, Ha : Yellow, P : Blue}

ได้ว่า Weight(x₁) = f₁(x₁) × f₂(x₁) × f₃(x₁) × f₄(x₁) × f₅(x₁) × f₆(x₁) × f₇(x₁) × f₈(x₁) × f₉(x₁) × f₁₀(x₁) × f₁₁(x₁) × f₁₂(x₁) × f₁₃(x₁) × f₁₄(x₁) × f₁₅(x₁) × f₁₆(x₁) = 1 × 1 × 1 × 1 × 0 × 0 × 1 × 1 × 1 × 0 × 1 × 1 × 1 × 1 × 1 × 1 = 0

x₂ = {R : Blue, Hu : Yellow, W : Red, M : Blue, S : Yellow, N : Red, K : Red, Y : Yellow, Ha : Yellow, P : Blue}

ได้ว่า Weight(x₂) = 1 × 1 × 1 × 1 × 1× 1× 1 × 1 × 1 × 1× 1 × 1 × 1 × 1 × 1 × 1 = 1

2. Backtracking Search สำหรับ CSPs

backtracking search เปรียบเหมือนการสร้างวัดเพราะเริ่มจากไม่มีอะไรเลย แล้วค่อยสร้างต่อเติมขึ้นไป

ซูโดโค้ด algorithm ของ backtracking search คือ

// csp เก็บข้อมูลองค์ประกอบทุกอย่างของ CSP
// assignment เก็บ X และ domain ของ X แต่ละตัว (ใช้เป็น solution)
function BACKTRACKING-SEARCH(csp) returns a solution, or failure
    return BACKTRACK({ }, csp)

// ตัวแปรด้านล่างต่อไปนี้กำหนด var คือ X และ value คือค่าใน domain
function BACKTRACK(assignment, csp) returns a solution, or failure
    if assignment is complete then return assignment
    // เลือก X ที่ยังไม่ได้ถูกกำหนด domain
    var ← SELECT-UNASSIGNED-VARIABLE(csp)
    // จากแต่ละค่าใน domain ที่เป็นไปได้ของ X ตัวนี้
    for each value in ORDER-DOMAIN-VALUES(var, assignment, csp) do
        // เมื่อเทียบกับข้อมูลใน assignemnt ถ้า X มีค่าเท่ากับ domain ตัวนี้แล้ว ยังตรงตามเงื่อนไขที่กำหนด
        if value is consistent with assignment then
            // กำหนดให้ X เท่ากับ domain ตัวนี้ แล้วเพิ่มข้อมูลของ X ตัวนี้เก็บใน assignemnt
            add {var = value} to assignment
            // อัปเดตค่า domain ที่เป็นไปได้ของ X ตัวอื่นที่ยังไม่ถูกกำหนด domain
            inferences ← INFERENCE(csp, var, value)
            // ถ้า X ที่ยังไม่ถูกกำหนด domain ยังมีค่า domain ให้เลือกอยู่
            if inferences ≠ failure then
                // เพิ่มข้อมูล X ที่ยังไม่ถูกกำหนด domain ใน assignment
                add inferences to assignment
                // เรียกใช้ function BACKTRACK ซ้ำ เพื่อกำหนด domain ให้ X ที่ยังไม่ถูกกำหนด domain ต่อไป
                result ← BACKTRACK(assignment, csp)
                if result ≠ failure then
                    return result
        // ถ้ามี X ที่ยังไม่ถูกกำหนด domain ตัวในตัวหนึ่งไม่มี domain ให้เลือกแล้ว ลบค่า X ทั้งหมดจาก assignment
        remove {var = value} and inferences from assignment
    return failure

ตัวอย่างการทำ backtracking search ในปัญหา map coloring

1) กำหนดค่าเริ่มต้นที่เป็นองค์ประกอบของ CSP

• X = {R, Hu, W, M, S, N, K, Y, Ha, P}
• D = {R, B, Y} (หมายถึง แดง, น้ำเงิน, เหลือง)
• C = {R≠Hu, Hu≠W, Hu≠M, …}

โดยในที่นี้มีการกำหนด inference เพื่อระบุค่า domain ที่เป็นไปได้ของ X แต่ละตัว (ทำ filtering) ได้ว่า

2) เลือก X มา 1 ค่า ในที่นี้จะเลือก X โดยเรียงจากซ้ายไปขวา ดังนั้นตัวแรกคือ R, เลือก domain ที่เป็นไปได้ของ R ในที่นี้จะเลือก domain โดยเรียงจากซ้ายไปขวา ดังนั้นได้ R

อัปเดตค่าในตารางโดยเอาสีแดงออกจาก domain ของอำเภอที่อยู่ติดกับ R ที่ยังไม่ได้ถูกกำหนด domain ซึ่งก็คือ Hu

3) X ตัวต่อมาคือ Hu, domain ตัวแรกที่เลือกได้คือ B

อัปเดตค่าในตารางโดยเอาสีน้ำเงินออกจาก domain ของอำเภอที่อยู่ติดกับ Hu ที่ยังไม่ได้ถูกกำหนด domain ซึ่งก็คือ W และ M

4) X ตัวต่อมาคือ W, domain ตัวแรกที่เลือกได้คือ R

อัปเดตค่าในตารางได้

5) ทำแบบเดิมไปเรื่อยๆ จนกว่า X ทุกตัวจะถูกกำหนด domain (ถ้าระหว่างทำพบว่า X ที่ตัวใดตัวหนึ่งไม่มี domain ให้เลือกแล้ว reset ตารางทั้งหมด แล้วกำหนดให้ R คือสีน้ำเงินแทน ถ้า R เปลี่ยนครบทุก 3 สีแล้วยังไม่มีคำตอบ แสดงว่าปัญหานี้ไม่มีคำตอบ)

3. Local Search สำหรับ CSPs

local search เปรียบเหมือนการซ่อมวัดเพราะมีโครงสร้างเดิมอยู่แล้ว แต่มีบางส่วนที่มีปัญหาต้องแก้ไข ซึ่งมีความยืดหยุ่นมากกว่า backtracking search

ซูโดโค้ด algorithm ของ local search คือ

function MIN-CONFLICTS(csp, max steps) returns a solution or failure
    inputs: csp, a constraint satisfaction problem
        // max steps คือค่าที่เรากำหนดขึ้นมาเอง คือจำนวน loop สูงสุดที่ใช้ในการหา solution
        max steps, the number of steps allowed before giving up

  // เริ่มต้น X ทุกตัวถูกกำหนด domain แต่ค่าของ X แต่ละตัวอาจไม่ตรงตามเงื่อนไขที่กำหนด
  current ← an initial complete assignment for csp
    for i = 1 to max steps do
        if current is a solution for csp then return current
        // สุ่มเลือก X ที่มีค่าไม่ตรงตามเงื่อนไขมาแก้ไขค่า
        var ← a randomly chosen conflicted variable from csp.VARIABLES
        // เลือกค่า domain ของ X ตัวนี้ที่ทำให้มีความขัดแย้งน้อยที่สุด
        value ← the value v for var that minimizes CONFLICTS(var, v, current, csp)
        // กำหนดให้ X มีค่าเท่ากับ domain ค่านั้น
        set var =value in current
    return failure

ในการณีที่ค่า domain ของ X ไม่ตรงตามเงื่อไข หรือเกิดความขัดแย้ง (conflict) กับเงื่อนไข วิธีเช็คว่ามีความขัดแย้งมากหรือน้อยมีได้หลายวิธี ขึ้นอยู่กับปัญหา ในกรณีปัญหา map coloring conflict มาก-น้อย ดูที่จำนวนคู่ node ที่อยู่ติดกัน แต่มีสีเหมือนกัน

ตัวอย่างการทำ local search ในปัญหา map coloring

1) กำหนดให้ state เริ่มต้นเป็นไปตามภาพด้านล่าง

ได้ว่า X ที่ conflict ได้แก่ {Hu, W, S, K, Ha}, ค่าความขัดแย้ง (จำนวนคู่ที่ node ที่อยู่ติดกัน แต่มีสีเหมือนกัน) คือ 3

2) สุ่ม X มา สมมติสุ่มได้ Hu พบว่าเมื่อแก้ไข Hu เป็นสีอื่น ค่าความขัดแย้งก็ยังเท่ากับ 3 ดังนั้นค่าความขัดแย้งต่ำสุดเมื่อลองเปลี่ยนค่าของ Hu ก็ยังคงเท่ากับ 3 เท่าเดิม (Hu สีเหลืองเหมือนเดิม)

3) สุ่ม X มา สมมติสุ่มได้ W พบว่าเมื่อแก้ไข W เป็นสีแดง ได้ค่าความขัดแย้งต่ำที่สุด ซึ่งก็คือ 1 ดังนั้นแก้ไข W เป็นสีแดง และได้ X ที่ conflict คือ {K, Ha}

4) สุ่ม X มา สมมติสุ่มได้ Ha พบว่าเมื่อแก้ไข Ha เป็นสีเหลือง ได้ค่าความขัดแย้งต่ำที่สุด ซึ่งก็คือ 0 ดังนั้นแก้ไข Ha เป็นสีเหลือง เนื่องจากไม่มี X ตัวไหนที่มีค่า domain ไม่ตรงตามเงื่อนไขแล้ว จึงได้ solution ตามภาพด้านล่าง

อ้างอิง

หนังสือ Artificial Intelligence: A Modern Approach (4th edition)