[理工] 關於Transitive closure的疑問

看板Grad-ProbAsk作者 (その血の運命~Jo~Jo~)時間7年前 (2019/01/23 14:48), 編輯推噓6(6推 0噓 6→)
留言12則, 5人參與, 7年前最新討論串1/1
https://i.imgur.com/QRxie58.jpg
https://i.imgur.com/y4hIJMG.jpg
為什麼這兩題的第0次矩陣定義不一樣？ 一個是離散的，一個是演算法/資結的， 神奇的是兩個都是用Floyd-Warshall 來求transitive closure。 我以為如果用離散的定義，應該先求出矩陣各個次方後，再聯集起來... 還是有什麼方法來分辨要用那個定義？ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.24.51 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1548226102.A.801.html
推
01/23 16:16, 7年前 , 1F
演算法好像定義對角項是1？
01/23 16:16, 1F
推
01/23 17:17, 7年前 , 2F
定義的問題 演算法對角線定義1 離散0
01/23 17:17, 2F
推
01/23 17:30, 7年前 , 3F
是因為A+還有A*的差異嗎？
01/23 17:30, 3F
推
01/23 17:35, 7年前 , 4F
求矩陣各次方再加起來不就是在求演算法的Floyd Warshall嗎
01/23 17:35, 4F
→
01/23 17:37, 7年前 , 5F
你要問的是對角線的問題吧? 不然只是做法不同
01/23 17:37, 5F
推
01/23 17:50, 7年前 , 6F
考演算法對角線就設1，考數學就照adjacency matrix算
01/23 17:50, 6F
→
01/23 19:30, 7年前 , 7F
是的 演算法定義對角項都是1
01/23 19:30, 7F
→
01/23 19:30, 7年前 , 8F
感謝 cvn 大 提醒
01/23 19:30, 8F
→
01/23 19:30, 7年前 , 9F
所以應該是當題目有特別提到A+
01/23 19:30, 9F
→
01/23 19:30, 7年前 , 10F
就用 離散的定義
01/23 19:30, 10F
→
01/23 19:30, 7年前 , 11F
因為成大這題是考在資料結構@@
01/23 19:30, 11F
推
01/23 19:51, 7年前 , 12F
竟然是考在資結....
01/23 19:51, 12F
‣ 更多 jojoboy0115 的文章
文章代碼(AID): #1SI0usW1 (Grad-ProbAsk)