前言

前一篇文章中，我使用了 Eller’s Algorithm 迷宮生成算法 來生成迷宮，這一篇文章會先介紹 A* Algorithm，並使用 A* Search Algorithm 來攻略迷宮，先偷看一下成果:

Eller’s Algorithm 算法介紹

Eller’s Algorithm 是一種神奇動態迷宮生成算法，可以在線性時間內逐行生成迷宮，用我自己的理解來說，算法的精神就是:

每個格子一開始都是被分隔開的「區域」，隨機打通格子間的牆壁使區域間可以相通。

前言

台北捷運最近推出了一個很瘋狂的集章全制霸活動，集滿5條捷運路線(不含環狀線)，總共109個車站，就可以抽大獎，到底有誰會閒閒沒事想參加這個活動? 啊，我女朋友剛剛問我要不要參加，沒事沒事，真是個好活動! 問題來了，該如何用最短的時間集齊所有車站並回到出發地呢?

本文將使用 Held Karp 算法來計算從台北車站出發，遍歷 109 個車站，並在最後回到台北車站所需花費的最短時間與路徑，不想看過程的人也可以直接到最後面看結果。XD

重點

寫了一個 Hexo 外掛 hexo-hackmd 協助下載 HackMD 筆記到本地端，歡迎大家使用，有問題可以發 issues 給我。

問題說明

如上面所展示的，Sidebar 渲染的速度明顯比其他部分要慢上許多。

Monotonic Stack 本質上就是一個 Stack 而已，只不過在操作 Stack 時需要同時維護其單調的特性，本文會簡單介紹 Monotonic Stack 並附上兩個有一點點難度的 LeetCode 題目做練習：84. Largest Rectangle in Histogram、85. Maximal Rectangle。

Java Stream

Stream 是一個元素形成的隊列，其來源 (Source) 可以是集合或數組，Stream 本身並不會存儲元素，其操作也不會影響到原始來源，單純以數據流的方式來處理數據，依性質可以分為兩類：

• 中間操作 (Intermediate Operations)
  Stream 的中間步驟，一個 Stream 可以有多個中間操作，會返回一個新的 stream，屬於惰性求值 (Lazy Evaluation)，意思是不會馬上計算結果，而是等到終端操作時才一併計算。
• 終端操作 (Terminal Operations)
  Stream 的最後一步，一個 stream 只能有一個終端操作，會產生一個新的集合或值。

前言

因為被旋轉甜甜圈給驚豔到，所以也想要自己來寫寫看，不過甜甜圈的數學看了頭好痛，所以改寫稍微簡單一點的旋轉立方體，不囉嗦先看成果：

在 Java 自學筆記 07 - Concurrent Queue 中我們使用 concurrent queue 來實作 Producer Consumer Problem，將生產者產出的 task 丟給 queue，消費者一有空閒就會去 queue 中拿新的 task 出來，實際上這就是 Thread Pool 的概念，不過過程中我們是自己去創建與管理 thread 和 queue，而 Java 其實提供了許多跟 Thread Pool 有關的介面，讓我們能夠更簡單的實現這些功能。

ExecutorService

內部報酬率 (Internal Rate of Return，IRR)

內部報酬率是一種用來衡量投資效益的指標，其概念是計算出一個折現率，使淨資金流入的現值與淨資金流出的現值加總為 0，也就是淨現值為 0 (NPV=0)。

淨現值的數學公式如下:

${NPV = \displaystyle \sum _{t=0}^{N}{\frac {C_{t}}{\left(1+r\right)^{t}}}}$

其中 ${r}$ 是折現率、${N}$ 為期間、${C_{t}}$ 為第 ${t}$ 年的淨現金流量。
當我們帶入一個 ${r}$ 能使得 NPV=0 時，我們就把這個 ${r}$ 稱 IRR。