ข้อถัดมา Shopping Plan

ข้อนี้เค้าจะให้ตำแหน่งร้านต่างๆ มา

ซึ่งแต่ละร้านจะขายของราคาต่างๆ กัน

การไปร้านต่างๆ ก็ต้องจ่ายค่าเดินทาง

และของบางอย่างเป็นของสดมาก

ซื้อเสร็จต้องรีบเอากลับบ้าน ห้ามแวะที่อื่น

โจทย์ให้หาราคาที่ถูกที่สุดที่สามารถซื้อของทุกอย่างได้

อ่านเพิ่มเติม ที่นี่



*** คำเตือน: บทนี้อาจจะเข้าใจยากหน่อย แต่ถ้าลองทำไปด้วย น่าจะเข้าใจมากขึ้น ***



ข้อนี้ก็ยังเป็นแบบ Dynamic Programming สูตรคือ



findMinCost(ของที่ยังไม่รู้ราคา, สถานที่) = min { ค่าของ + ค่าเดินทาง + findMinCost(ของที่ยังไม่รู้ราคา - ของที่ซื้อไป, ร้านที่ซื้อ) }



วิธีคิด ให้คิดถอยหลัง

เริ่มจากเราอยู่ที่บ้าน และมีของครบทุกอย่าง (แต่ไม่รู้ราคาสักชิ้น)

ทีนี้ตัวเลือกเราจะมีเพียบ คือ ก่อนเราอยู่บ้าน เราไปร้านไหนมาก็ไม่รู้ และซื้อของอะไรมาก็ไม่รู้

สมมติ ร้านมี Top, BigC, Lotus และของมี Lay, Pocky, Pepsi

เนื่องจากเราไม่รู้อะไรเลย เราจึงต้องลองทุกๆ แบบ เช่น เราอาจจะมาจาก Top และซื้อ Lay

พอเราย้อนไปที่ Top เราก็จะรู้ราคาของ Lay รู้ค่าเดินทาง และจาก Top เราก็ findMinCost อีกครั้ง

โดยคราวนี้ของที่ยังไม่รู้ราคามีแค่ Pocky และ Pepsi พอเรา findMinCost ย้อนไปเรื่อยๆ จนรู้ราคาของจนหมด

เราก็กลับมาลองแบบอื่น เช่น ไป BigC และซื้อ Lay แทน

พอเราย้อนไปย้อนมาจนครบทุกรูปแบบ เราก็จะรู้ว่าแบบไหนถูกที่สุด



เริ่มแรกมารู้จัก class ของร้านขายของก่อน

type Store = { id:int; position:float*float; items:Map<int,float>; costToHome:float }
let homeStore = { id=0; position=0.0,0.0; items=Map.empty; costToHome=0.0 }

แบบนี้ f# เค้าเรียกว่า record

บรรทัดถัดมา homeStore คือบ้านเราเอง

id คือ id ของร้าน เลข 0 คือบ้านเรา ร้านต่างๆ จะเริ่มที่ 1,2,3,... ไปเรื่อยๆ

position คือ ตำแหน่ง บ้านเราจะเป็นตำแหน่ง 0,0

items คือ ของต่างๆ ที่ขาย เป็น map (คล้ายๆ dictionary) บ้านเราจะไม่มีของขาย (Map.empty)

key ของ map คือ itemId ซึ่งเป็น flag ซึ่ง itemId จะเริ่มที่ 1,2,4,8,... ไปเรื่อยๆ ทีละ 2 เท่า

ส่วน value ของ map คือ ราคาของ

สุดท้าย costToHome ค่าเดินทางกลับมาบ้าน



ถัดมามารู้จัก function หาระยะทาง

let (<->) (x1, y1) (x2, y2) =
    let deltaX = x1 - x2
    let deltaY = y1 - y2
    sqrt (deltaX*deltaX + deltaY*deltaY)

การประกาศแบบนี้เรียกว่า operator overload

วิธีใช้ เช่น store1.position <-> store2.position

ซึ่งบางครั้งการใช้ operator อ่านง่ายกว่า การใช้ function

วิธีการหาตำแหน่ง ก็ใช้ ทฤษฎีบทพีทาโกรัส



เรามาเริ่มคำนวนกันเลย!

let solve gas allItems freshMask stores = 

gas คือ ค่า gas

allItems เป็น sequence เก็บ itemId ของสินค้าทุกตัว เช่น [1;2;4;8;16;32;...] (อย่าลืมว่า itemId เป็น flag ต้องเพิ่มทีละ 2 เท่า)

freshMask คือ mask ของสินค้าที่เป็นของสด เช่น itemId 2,4,16 เป็นของสด freshMask จะได้ 22 (ง่ายๆ ก็เอา id มาบวกกัน)

ส่วน stores เป็น array ที่เก็บ type Store ที่ประกาศไว้ด้านบน โดย array ที่ 0 คือบ้านเราเอง array ที่ 1 คือ ร้าน id=1 ไปเรื่อยๆ



วิธีการ build input ผมว่าไม่ยากมาก ลองหัดทำเองแล้วส่งค่าเข้ามานะครับ



ก่อนจะเริ่มทำ อาจต้องคำนวน search space ก่อน

ร้านมีได้ 50 ร้าน และของมีได้ 15 ชนิด

หมายความว่า ต่อ 1 รอบ เราต้องหาค่า min ของ 750 ทางเลือก (50 x 15)

แล้วจำนวนครั้งที่เรา call findMinCost คือ จำนวนรูปแบบของ ของที่ยังไม่รู้ราคา และจำนวนร้าน

ของที่ยังไม่รู้ราคามี 2 สถานะ รู้แล้ว และยังไม่รู้ ของมี 15 ชนิด ดังนั้นมี input 32,768 แบบ (2¹⁵)

สถานที่มี 50 แห่ง รวมบ้านของเราเป็นจุดเริ่มต้นอีก เป็น 51 แห่ง

เอาตัวเลขทุกตัวมาคูณกันได้กว่า 1 พันล้านแบบ (750 x 32,768 x 51)

นี่ยังไม่รวมที่ต้องจัดการกับของสดอีก



วิธีการลดจำนวนการคำนวนที่ดีคือ การลดตัวเลือก

1. เนื่องจากบางร้านขายของราคาแพงมาก เราสามารถตัดของชิ้นนั้นออกจากตัวเลือกได้เลย

2. ถ้าเราอยู่ร้าน A ซึ่งขายของชิ้นนึง 20 บาท เราสามารถตัดตัวเลือกที่จะซื้อของชิ้นเดียวกัน แต่แพงกว่า 20 บาทได้เลย

3. ถ้าอยู่บ้าน แปลว่าจะต้องซื้อของสดแล้วกลับเข้ามาเสมอ

4. ถ้าอยู่ร้าน แล้วไม่ได้กลับบ้านแปลว่าซื้อของแห้งเสมอ



เริ่มข้อ 1 ตัดของราคาแพงออกไป

let storeMap =
    let storeMapX itemId =
        let itemPrices =
            seq {
                for store in stores do
                let item = store.items.TryFind(itemId)
                if item.IsSome then
                yield store,item.Value
            } |> Seq.cache

storeMap มี input คือ itemId เพื่อต้องการหาว่า itemId นี้ มีร้านไหนขายบ้าง (และต้องขายไม่แพง)

itemPrices ก็แค่ loop ทุกร้าน เพื่อหาว่าร้านไหนขาย itemId นี้บ้าง และราคาเท่าไหร่


function ไม่จบ มีต่อ

        let filterFn (store1,price1) =
            let forallFn =
                if itemId &&& freshMask > 0 then
                    fun (store2,price2) -> price1 <= price2 + (store1.position <-> store2.position)*gas 
                                                            + store2.costToHome 
                                                            + store1.costToHome
                else
                    fun (store2,price2) -> price1 <= price2 + (store1.position <-> store2.position)*gas*2.0
            itemPrices |> Seq.forall forallFn

สมมติอยู่ร้านแรก เพื่อเปรียบเทียบราคา เราต้องเดินทางไปร้าน 2 เพื่อซื้อของ และกลับมาร้านแรกใหม่

ถ้าค่าใช้จ่ายทั้งหมด ยังถูกกว่าการซื้อของที่ร้านแรก

แปลว่าของร้านแรกแพงมากถึงขนาดเดินไปซื้อที่ร้าน 2 แล้วยังคุ้มกว่า เราสามารถตัดของชิ้นนั้นออกจากร้านแรกได้เลย

function ไม่จบ มาต่อส่วนสุดท้าย

        itemPrices |> Seq.filter filterFn
                   |> Seq.map (fun (store,price) -> store.id,(store,price))
                   |> Map.ofSeq
    memoize storeMapX

เมื่อเอา itemPrices ผ่าน filterFn จะเหลือแค่ของที่ไม่แพงมากเท่านั้น

บรรทัดสุดท้ายมีการเรียก memoize (ดูวิธีการประกาศบทที่แล้ว) เพื่อเมื่อเรียกซ้ำจะได้ไม่ต้องคำนวนใหม่



ถัดมาข้อ 2 หาร้านที่จะซื้อของชิ้นถัดไป โดยร้านที่จะซื้อต้องขายของถูกว่าร้านที่เรายืนอยู่

let rec findStores =
    let findStoresX (storeId, itemId) =
        seq {
            let store1 = Array.get stores storeId
            let map = storeMap itemId
            let item1 = Map.tryFind storeId map
            for kvp in map do
            let store2,price2 = kvp.Value
            if storeId = store2.id || item1.IsNone || snd item1.Value > price2 then
            let travel = (store1.position <-> store2.position)*gas
            yield store2.id, itemId, price2 + travel
        } |> Seq.cache
    let cached = memoize findStoresX
    fun storeId itemId -> cached (storeId, itemId)

findStores มี input 2 ตัว คือ storeId และ itemId

storeId คือ ปัจจุบันเราอยู่ที่ร้านไหน

itemId คือ ปัจจุบันเราอยากรู้ราคาของของชิ้นไหน

เป้าหมายของ findStores คือ บอกว่าเราควรไปซื้อ itemId นี้ที่ร้านไหนบ้าง



ใน code จะมี for in อยู่ คือเราก็ไปทุกๆ ร้าน (ที่ขายของไม่แพงมากจาก function storeMap ด้านบน)

และก็มีการเช็คนิดหน่อยว่า ถ้าร้านที่เรายืนอยู่ขายของชิ้นเดียวกันถูกกว่า เราจะไม่ไปร้านอื่น

แล้วก็คืนค่า storeId ร้านใหม่ (store2.id), itemId, และราคาของบวกค่าเดินทาง

function นี้ก็มีการเรียก memoize เพราะ function นี้มีการเรียก input เดิมๆ ซ้ำหลายครั้ง



ถัดมาข้อ 3 และข้อ 4 เรามีการแยกของแห้งและของสด

ถ้าอยู่บ้าน เราก็เลือกที่จะซื้อของสด และกลับบ้าน

ถ้าอยู่ร้าน ยังไงก็ต้องซื้อของแห้ง

let isFresh itemId = itemId &&& freshMask > 0
let dryItems = allItems |> Seq.filter (not << isFresh)
                        |> Seq.cache
let freshItems = allItems |> Seq.filter isFresh
                          |> Seq.cache

ไม่มีอะไรมาก dryItems คือ รายการของแห้ง freshItems คือ รายการของสด



และ function สุดท้าย ยาวนิดนึงแต่เป็น logic ทั้งหมดของ program

let rec findMinCost =
    let findMinCostX (mask, id, home) =
        let filterFn itemId = mask &&& itemId > 0
        let validFreshItems = Seq.filter filterFn freshItems
        let validDryItems = Seq.filter filterFn dryItems
 
        let mapFn (storeId, itemId, itemCost) =
            let newHome = id = 0 || (home && id = storeId)
            itemCost + findMinCost (mask ^^^ itemId, storeId, newHome)

findMinCost เป็น logic ในการหาราคาที่ถูกที่สุด

ถ้ายังจำได้ findMinCost ผมได้ define procedure คร่าวๆ ไว้ว่า



findMinCost(ของที่ยังไม่รู้ราคา, สถานที่) = min { ค่าของ + ค่าเดินทาง + findMinCost(ของที่ยังไม่รู้ราคา - ของที่ซื้อไป, ร้านที่ซื้อ) }



ดังนั้น mask คือ ของที่ยังไม่รู้ราคา เป็น flag

id คือ storeId สถานที่ๆ เรายืนอยู่

parameter อีกตัวคือ home คือบอกว่าเราจะกลับไปบ้านหรือเปล่า (ถ้าใช่จะได้ซื้อของสดติดมือกลับไปได้)



validFreshItems กับ validDryItems ก็คือ freshItems กับ dryItems ที่เรายังไม่รู้ราคา

mapFn คือ ค่าของ + ค่าเดินทาง + ผลลัพธ์จาก findMinCost ที่เป็น subproblem เพื่อเอามาหา mininum cost

function ไม่จบ มีต่อ

        match mask, id, home with
        | 0, id, _ -> stores.[id].costToHome
        | mask, 0, _ ->
            let items = if mask &&& freshMask > 0 
                        then validFreshItems |> Seq.truncate 1
                        else validDryItems
            items |> Seq.collect (findStores id)
                  |> Seq.map mapFn
                  |> Seq.min

เริ่มทำการ match

แบบแรกคือ mask=0 ซึ่งหมายความว่า เรารู้ราคาของครบแล้ว


ซึ่งค่าใช้จ่ายมีแค่ค่าเดินทางจากบ้าน มาร้านที่เราอยู่เท่านั้น



แบบถัดมาคือ id=0 หมายความว่าเราอยู่บ้าน ถ้าเราอยู่บ้าน

และมีของสดที่ยังไม่รู้ราคา เราก็สนใจแค่ของสดเท่านั้น

ของสดต่างจากของแห้ง ตรงที่เราไม่สนใจลำดับการซื้อก่อนหลัง

เพราะยังไงซื้อเสร็จ ต้องกลับบ้านอยู่ดี

ดังนั้น validFreshItems อาจจะมีหลายชิ้น แต่เราสนใจแค่อันแรกเท่านั้น (Seq.truncate 1)

        | mask, id, home -> 
            let freshItemStores =
                seq {
                    if mask &&& freshMask > 0 then
                    let costToHome = stores.[id].costToHome
                    yield 0, 0, costToHome
                    if home then
                    for itemId in validFreshItems do
                    let result = Map.tryFind id (storeMap itemId)
                    if result.IsSome then
                    yield id, itemId, snd result.Value
                }
            validDryItems |> Seq.collect (findStores id)
                          |> Seq.append freshItemStores
                          |> Seq.map mapFn
                          |> Seq.min
    memoize findMinCostX

แบบสุดท้าย คืออยู่ที่ร้าน

ถ้ามีของสดที่ยังไม่รู้ราคา เราอาจจะต้องกลับไปเริ่มที่บ้าน

หรือซื้อของสดในร้านเดียวกัน

มิเช่นนั้น เราจะซื้อแต่ของแห้งเท่านั้น



และเราก็ทำการ memoize อีกครั้ง



วิธีการหาคือสั่งอย่างนี้ครับ

let minCost = findMinCost (Seq.sum allItems, 0, false)
sprintf "%.7f" minCost

จบ