推 gsrr:老實說,不是很懂 03/11 10:07
推 EntHeEnd:高手 推一個 03/11 11:38
推 rockmanray:這個解答真是太精闢了 01/16 11:23
※ 引述《gsrr (下象棋)》之銘言：
: http://www2.lib.nctu.edu.tw/n_exam/exam96/cslz/cslz1001.pdf
: 第6題要求是否存在一組Index相乘 >1
: 請問應該如何描述該演算法?
: 謝謝!
首先把建立一個矩陣R'[i,j] = -log R[i,j]
如果R[i1,i2] * R[i2, i3] ... R[ik,i1] > 1
那麼R'[i1.i2] + R'[i2, i3] ... + R'[ik, i1] < 0
把R'想像成是adjacency matrix。
問題就轉化成在圖找一個negative cycle，用Bellman-Ford演算法解。
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.162.50