Just algorithm!
Hexagon Game




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

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

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


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

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

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


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

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

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







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

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

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

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

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 ให้มันหาคะแนนที่น้อยที่สุดออกมา



จบ





Create Date : 29 มิถุนายน 2557
Last Update : 29 มิถุนายน 2557 9:37:00 น. 0 comments
Counter : 563 Pageviews.

ชื่อ :
Comment :
  *ใช้ code html ตกแต่งข้อความได้เฉพาะสมาชิก
 
รหัสส่งข้อความ
กรุณายืนยันรหัสส่งข้อความ

chaowman
Location :
กรุงเทพฯ Thailand

[Profile ทั้งหมด]

ให้ทิปเจ้าของ Blog [?]
ฝากข้อความหลังไมค์
Rss Feed
Smember
ผู้ติดตามบล็อก : 8 คน [?]









New Comments
Group Blog
 
All Blogs
 
Friends' blogs
[Add chaowman's blog to your web]
Links
 

 Pantip.com | PantipMarket.com | Pantown.com | © 2004 BlogGang.com allrights reserved.