สมมติว่าคุณกำลังเล่นหมากกระดานอยู่

หมากกระดานนี้ไม่ใช่ตาราง 4 เหลี่ยม แต่เป็น 6 เหลี่ยม

คุณมีเบี้ยอยู่จำนวนเท่าขนาดของตาราง เบี้ยแต่ละตัววางมั่วๆ บนกระดาน


เบี้ยสามารถเดินได้เฉพาะช่องที่ติดกัน

และเมื่อไหร่ที่เบี้ยเรียงกันทุกตัวคุณชนะ

ยังไม่จบ เบี้ยแต่ละตัวมีแต้มไม่เท่ากัน


หากเดินเบี้ย 1 ครั้ง คุณจะต้องเสียแต้มตามที่กำหนดบนเบี้ย

คำถามคือ คุณจะสามารถชนะได้โดยเสียแต้มน้อยที่สุดกี่คะแนน

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







ข้อนี้เป็นโจทย์ประเภทกำหนดงาน

คือ ต้องหาว่าเบี้ยตัวไหนจะเดินไปที่ตำแหน่งไหน

หากไม่รู้จัก algorithm เราคงใช้วิธีการ brute force O(n!)

ทีนี้ มันมี algorithm ตัวนึง ที่เพิ่มประสิทธิภาพในการจัดสรรงาน เป็น O(n³)

algorithm ตัวนี้คือ Hungarian Algorithm



เรียนรู้จัก algorithm ตัวนี้ไว้ก็ไม่เสียหาย

เราสามารถเอา algorithm นี้ ไปแก้ปัญหาการจัดสรรทรัพยากรในธุรกิจได้

ทีนี้ตัว code ก็ไม่ต้องเขียนเอง ไป download ที่นี่



มาเริ่มกันเลย เรามาสร้างตารางกันก่อน

วิธีคิดตารางก็ต้องใช้จินตนาการนิดนึง เพราะตารางไม่ใช่สี่เหลี่ยม

สำหรับผม ผมให้ตารางมันเว้นช่องว่าง

|..|..|01|..|02|..|03|..|..|
|..|04|..|05|..|06|..|07|..|
|08|..|09|..|10|..|11|..|12|
|..|13|..|14|..|15|..|16|..|
|..|..|17|..|18|..|19|..|..|

เราไม่ต้องสร้างตารางจริงๆ

เราแค่รู้ว่าเลขต่างๆ อยู่ตำแหน่งไหนก็พอ

เช่น เลข 1 อยู่ตำแหน่งที่ (0,2)

let getBoard =
    let getBoardX size =
        seq {
            let mid = (size + 1) / 2
            let width = (size * 2) - 1
            for row = 1 to size do
            let rowPadding = abs (mid - row)
            for col in { 1+rowPadding .. 2 .. width-rowPadding } do
            yield col,row
        } |> Seq.append [0,0]
          |> Seq.toArray
 
    memoize getBoardX

คำสั่ง getBoard มีไว้หาตำแหน่งของเลขต่างๆ



ทีนี้ การวัดระยะห่างของช่องก็คำนวนง่ายนิดเดียว

let (<->) (x1,y1) (x2,y2) =
    let deltaY = abs (y1 - y2)
    let deltaX = abs (x1 - x2) - deltaY |> max 0
    deltaY + (deltaX / 2)

ถ้ามีการเลื่อนในแนวตั้ง เราสามารถเอามาลบแนวนอนได้ เพราะเวลาเลื่อนในแนวตั้ง เราเลื่อนแนวทแยง

และเวลาเลื่อนแนวนอน เวลาหาระยะห่างเราเอามาหาร 2 เพราะตารางมีการเว้นช่องว่างระหว่างเลข



ถัดมาคือหาตำแหน่งจบ

let finishPos =
    let finishPosX size =
        let board = getBoard size
        let mid = (size + 1) / 2
        let finish1 =
            let col,row = board.[1]
            [|  for i = 0 to size-1 do
                yield col+i,row+i |]
        let finish2 =
            let col,row = board.[mid]
            [|  for i = 0 to size-1 do
                yield col-i,row+i |]
        let finish3 =
            [|  for i = 0 to size-1 do
                yield 1 + (i*2),mid |]
        [| finish1; finish2; finish3 |]
    memoize finishPosX

ตำแหน่งจบมี 3 แบบเสมอ คือ

จบแบบแนวนอน

|..|..|01|..|02|..|03|..|..|
|..|04|..|05|..|06|..|07|..|
|08|..|09|..|10|..|11|..|12|
|..|13|..|14|..|15|..|16|..|
|..|..|17|..|18|..|19|..|..|

และแนวทแยง ซ้ายขวา

|..|..|01|..|02|..|03|..|..|
|..|04|..|05|..|06|..|07|..|
|08|..|09|..|10|..|11|..|12|
|..|13|..|14|..|15|..|16|..|
|..|..|17|..|18|..|19|..|..|

|..|..|01|..|02|..|03|..|..|
|..|04|..|05|..|06|..|07|..|
|08|..|09|..|10|..|11|..|12|
|..|13|..|14|..|15|..|16|..|
|..|..|17|..|18|..|19|..|..|

เริ่มเลย

let solve nums costs =

nums คือ ตำแหน่งเริ่มต้นของเบี้ยแต่ละตัว

costs คือ คะแนนของเบี้ยแต่ละตัว

let size = Array.length nums
let board = getBoard size
let start = nums |> Seq.map (Array.get board)
                 |> Seq.zip costs
                 |> Seq.cache
let finish = finishPos size

size คือขนาดของ board

start คือ คะแนน และ ตำแหน่งเริ่มต้นของเบี้ยแต่ละตัว ซึ่งตำแหน่งเปลี่ยนเป็น (x, y) แทนตัวเลข

finish คือ ตำแหน่งสิ้นสุดของเบี้ย ซึ่งมี 3 แบบ

let minCost finPos =
    let matrix = 
        array2D [|
            for cost, pos in start do
            yield Array.map (fun pos2 -> (pos <-> pos2) * cost) finPos
        |]
    let sol = HungarianAlgorithm.FindAssignments (Array2D.copy matrix)
    sol |> Seq.mapi (Array2D.get matrix)
        |> Seq.sum
 
finish |> Seq.map minCost
       |> Seq.min
       |> string

ทีนี้เวลาหาผลลัพธ์ ก็เอา finish แต่ละแบบมาดูว่าแบบไหนใช้คะแนนน้อยที่สุด

ใน minCost เรามีการสร้าง matrix โดยการใช้ความสามารถของ f# ที่เรียกว่า array comprehension

โดย matrix จะเก็บคะแนนที่ใช้ของเบี้ยแต่ละตัว และตำแหน่งสิ้นสุดแต่ละตำแหน่ง

หลังจากนั้นก็โยนใส่ hangarian algorithm ให้มันหาคะแนนที่น้อยที่สุดออกมา



จบ