【從搬磚問題看為什麼要學演算法】

這幾個月因為授課的關係又把 Introduction to Algorithms 這本演算法大學教科書讀過，想想真慚愧以前修課讀書都沒有那麼認真XDDD

但因為這本書有將近 1400 頁，而資料結構、演算法普遍都是一學期 3 學分的課程，整學期通常有20~25學分，對一般學生而言是不可能在一學期內讀完的。

讀完一部分之後，才體會到「經典之所以是經典，在於每次閱讀都能夠有不同的體悟」，比方來說，我之前有嘗試寫過虛擬貨幣的搬磚，雖然後來失敗了(詳：https://bit.ly/3bb52Ge)，但那時候並沒有體認或使用到演算法，單純使用暴力解，直到看到書上的例題，才發現其實搬磚問題是可以用演算法中的最短路徑、檢查負環來解答的。

Introduction to Algorithms 上的習題

首先，若有 i 個貨幣，先把幣幣之間的匯率轉換成一個 i × i 的矩陣如下。

這時候我們想要找到是否有套利的空間，就相當於我想找到一條路徑，經過不斷換匯後最後換回來的幣值會大於1

為了方便後續運算，首先把這個不等式都取倒數變成：

因為最短路徑問題處理的是加法，也就是該路徑中的權重總和，為了把乘法變成加法，再對上面這段不等式取 ln

就變成是圖論中的負環！透過一些簡單的數學轉換，就可以把找尋是否有套利空間的問題轉成檢查負環存在與否的問題，後續就可以使用 Bellman-Ford 演算法來實作，複雜度為 O(n³)。