街口冰淇淋車

延伸學習

自己設計一個地圖, 使用六個地圖區塊，每個區塊中間使用一台冰淇淋車，然後將區塊間外部點連結，形成一個自己的地圖，請同學來解題。

冰淇淋車問題正式的名稱是最小支配集(Minimum dominating set)

活動的意義

什麼是演算法？演算法是用以解決特定問題的有限個步驟和敘述。

單向函數（one-way function)：除了製作謎題的人，其他人沒有辦法輕易解題，這對密碼學是非常重要的。

暴力演算法(Brute-fore)：用嘗試錯誤法(try and error)，利用電腦快速計算的速度，找出答案。但是隨著地圖變大所需的時間會指數爆增。（時間複雜度：2^n)

貪婪法(greedy method): 是一種在每一步選擇中都採取在當前狀態下最好選擇，從而希望導致最好的結果，如泥濘城市的最小生成樹問題。最小支配集問題可以用貪婪法來解嗎？答案是不可以。

多項式時間演算法(Polynomial-time algorithm): 只要地圖夠大，也比暴力法更快。 (時間複雜度：n^17) 在n>117, 多項式法就會比暴力法還要快。

NP完全問題（Non-deterministic Polynomial Complete)：這個問題沒有辦法在確定的合理時間內解決。例如：最小生成樹問題、著色問題、最小支配集問題。

Complete完全的意思是如果其中一個問題找到一個有效率的解答，那麼這個方法也可以隨用於解決同組中的任何問題。

NP完全問題是否有多項式時間演算法可以解？目前的答案是沒有。

啟發式演算法(Heuristic algorithm): 這類演算法不保證找到最佳解，但可以找到最佳解的一部分，因為速度快所耗費成本相對少。

找不到問題的答案有三種可能：