PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 棋盤走路的問題

看板Prob_Solve (計算數學 Problem Solving)作者Leon (Achilles)時間10年前 (2014/03/14 13:57)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/2 (看更多)

※ 引述《soheadsome (師大狗鼻哥)》之銘言： : 不好意思這算半個作業文 : 題目的內容大概是 : 一個棋盤會給定起點和終點 : 然後棋盤上每一格都會有值 : 求起點到終點的所經過的最小值 : 我大概知道要用BFS來解決 : 但我想到說起點和終點會不固定 : 如果我剛好這次的iterate有兩個以上相同的值 : 我應該是依貪婪的方式選擇離終點最近的 : 但我想是該直接去量兩者之間的距離 : 還是應該直接選方位呢? : (若終點在左上我應當選這次可走的最左或最上方為主) : 這邊卡了滿久 : 希望有大大能幫忙解惑謝謝 Here are some quick ideas.. 1. You need to assume the weights in each grid are all positive. Otherwise you may have a 'negative' loop and the result will not be reasonable. 2. Then, the chess board can be represented as a graph. More preceisely, it will be a grid. 3. It will become a classical problem of Dynamic programming (DP).. Read Dijkstra algorithm.. -- 趙客縵胡纓，吾鉤霜雪明。銀鞍照白馬，颯沓如流星。十步殺一人，千里不留行。是了拂衣去，深藏身與名。閑過信陵飲，脫劍膝前橫。將炙啖朱亥，持觴勸侯贏。三杯吐然諾，五嶽倒為輕。眼花耳熱後，意氣素霓生。就趙揮金錘，邯鄲先震驚。千秋二壯士，烜赫大梁城。 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 66.214.174.109