Just algorithm!
Random Route



ข้อถัดมา Random Route

ข้อนี้จะให้รายการถนนมา และเวลาในการผ่านถนนเส้นนี้

โดยคุณก็ไม่รู้จุดหมาย คุณเลยสุ่มเลือกให้ทุกจุดหมายมีโอกาสเท่ากัน

และคุณก็ไม่รู้จะใช้ถนนเส้นไหน คุณก็สุ่มเลือกถนนที่สั้นที่สุด ถ้ามีหลายเส้น ทุกเส้นมีโอกาสเท่ากัน

อ่านเพิ่มเติมได้ ที่นี่



ข้อนี้อาจจะต้องใช้ทักษะในการใช้ Sequence ของ F# อยู่สักหน่อย



เริ่มจาก type ของถนน
type Road = { id:int; origin:string; dest:string; distant:int }

id คือหมายเลขถนน

origin กับ dest คือ ชื่อเมืองต้นทาง ปลายทาง

และ distant คือ ระยะทาง



เริ่มกันเลย
let solve start roads =

start ชื่อชื่อเมืองเริ่มต้น

roads ชื่อ sequence ของถนน (Road)
let rec explore ways =
    let newWays = 
        seq {
            for way in ways do
            for road in roads do
            let head::tails = way
            if road.origin = head.dest then
            if Seq.forall (fun it -> it.origin <> road.dest) way then
            yield road::way
        } |> Seq.cache
    if Seq.isEmpty newWays
    then ways
    else explore newWays |> Seq.append ways 
                         |> Seq.cache

คำสั่ง explore คำสั่งนี้จะต่อถนนไปเรื่อยๆ เช่น

เริ่มแรกอาจเป็น { กรุงเทพฯ-สมุทรสาคร }

พอ explore ครั้งนึงก็จะเป็น { กรุงเทพฯ-สมุทรสาคร; กรุงเทพฯ-สมุทรสาคร-เพชรบุรี }

คือ มันจะเติมเส้นทางไปเรื่อยๆ จนไม่เจอทางใหม่ๆ ถึงจะหยุด
let destinations = roads |> Seq.filter (fun it -> it.origin = start)
                         |> Seq.map (List.replicate 1)
                         |> explore
                         |> Seq.groupBy (fun (head::tails) -> head.dest)

ถัดมาก็จัดกลุ่มตามจุดหมาย
let destScore = 1.0 / float (Seq.length destinations)

และเนื่องจากเราจะสุ่มให้ทุกจุดหมายมีโอกาสเท่ากัน

เราก็แค่หารตามจำนวนจุดหมาย
let collectFn ways =
    let shortestWays = ways |> Seq.groupBy (List.sumBy (fun it -> it.distant))
                            |> Seq.minBy fst
                            |> snd
                            |> Seq.cache
    let wayScore = 1.0 / float (Seq.length shortestWays)
    shortestWays |> Seq.collect id
                 |> Seq.map (fun it -> it.id, destScore * wayScore)

ถัดมาเป็นคำสั่งหาโอกาสของถนนต่างๆ

เริ่มจากหาถนนที่สั้นที่สุด

และถ้าเส้นทางที่สั้นที่สุดมีหลายเส้น เราให้โอกาสเท่าๆ กัน

เราเลยหาโอกาสการใช้ถนน ด้วยการหารด้วยจำนวนเส้นทางที่สั้นที่สุด

เสร็จแล้วก็เอาโอกาสของจุดหมาย คูณกันโอกาสของเส้นทาง กลายเป็นโอกาสการใช้ถนน
let probs = query {
                for _, ways in destinations do
                for id, score in collectFn ways do
                groupValBy score id into g
                select (g.Key, g.Sum())
            } |> Map.ofSeq

สุดท้ายแล้วกันการหาโอกาสของการใช้ถนนแต่ละเส้น

เราเอาเส้นทางต่างๆ ของแต่ละจุดหมายไปโยนใส่ collectFn ด้านบน

แล้วจัดกลุ่มตามเลขถนน และรวมโอกาสเข้าด้วยกัน

ด้านบนใช้ feature ของ F# เรียกว่า query expression

ซึ่งทำอะไรได้มากกว่า linq มาก



สุดท้าย คืนค่า
let ans = roads |> Seq.map (fun road -> probs.TryFind(road.id))
                |> Seq.map (fun prob -> if prob.IsNone then 0.0 else prob.Value)
                |> Seq.map (fun prob -> sprintf "%.7f" prob)
String.Join(" ", ans)

โดยการ loop ทุกๆ ถนน แล้วไปหาใน probs ด้านบน

หากไม่เจอก็เป็น 0



จบ



Create Date : 07 มิถุนายน 2557
Last Update : 7 มิถุนายน 2557 9:20:06 น. 1 comments
Counter : 546 Pageviews.

 
happy birthday

ขอให้มีความสุขนะคะ ขอบคุณค่ะที่เอา code มาแบ่งปัน


โดย: cyberlifenlearn วันที่: 23 กรกฎาคม 2557 เวลา:17:20:17 น.  

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

Valentine's Month


 
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.