[理工] 關於Transitive closure的疑問 jojoboy0115 PTT批踢踢實業坊

[理工] 關於Transitive closure的疑問

作者: jojoboy0115 (jojo) 2019-01-23 14:48:19

https://i.imgur.com/QRxie58.jpg
https://i.imgur.com/y4hIJMG.jpg
為什麼這兩題的第0次矩陣定義不一樣？
一個是離散的，一個是演算法/資結的，
神奇的是兩個都是用Floyd-Warshall
來求transitive closure。
我以為如果用離散的定義，應該先求出矩陣各個次方後，再聯集起來...
還是有什麼方法來分辨要用那個定義？

作者: destiny3952 (戴斯泰尼3952) 2019-01-23 16:16:00

演算法好像定義對角項是1？

作者: sdfg014025xx (隨便就好) 2019-01-23 17:17:00

定義的問題演算法對角線定義1 離散0

作者: cvn21 (你是中國人) 2019-01-23 17:30:00

是因為A+還有A*的差異嗎？

作者: sooge (老衲) 2019-01-23 17:35:00

求矩陣各次方再加起來不就是在求演算法的Floyd Warshall嗎你要問的是對角線的問題吧? 不然只是做法不同考演算法對角線就設1，考數學就照adjacency matrix算

作者: jojoboy0115 (jojo) 2019-01-23 19:30:00

是的演算法定義對角項都是1感謝 cvn 大提醒所以應該是當題目有特別提到A+就用離散的定義因為成大這題是考在資料結構@@

作者: sooge (老衲) 2019-01-23 19:51:00

竟然是考在資結....

繼續閱讀

[理工] 作業系統 deadlock avoidance題目susukila [理工] 演算法 flow、NPsdfg014025xx [理工] 106中央線代bmpss92196 [理工] 計組 CPI計算jojoboy0115 [理工] 計組 pipeline 問題matt530 [理工] 台大資工102 資演kaidi620 103中興計組winson910343 [理工] 102台大電機丙計系paralyzation [理工] 中興104 資概o5739201 [理工] 時間複雜度一題OwTaingJune