演算法作業09

第1題: 最短路徑

請使用Branch-and-Bound找出下圖中，S到T的最短路徑。請畫出Branch-and-Bound圖，並標示各點的cost，以及被bound住的地方。(可參考ppt20頁)

hill climbing

如果Bound會更新的話

如果Bound不會更新的話

GIF太大傳不上來QQ

第2題: Personnel Assignment Problem

• 已知5個工作(
  $j_1,\dots ,j_5$)，其先後關係為：
  $j_1\to j_3,j_3\to j_4,j_2\to j_5$，分配給5個人員(
  $p_1,\dots ,p_5$)
• 每人分配一個工作，且當
  $j_a<j_b$ ，須要
  $p_a<p_b$。
• 請使用Branch-and-Bound找出最少費用的人員工作分配。

提煉cost matrix

原始矩陣

$\left[\begin{array}{ccccc}17& 13& 4& 23& 12\\ 32& 30& 45& 19& 31\\ 7& 11& 12& 3& 15\\ 10& 17& 13& 9& 11\\ 8& 19& 9& 6& 7\end{array}\right]$

橫排提煉後

$\left[\begin{array}{ccccc}13& 9& 0& 19& 8\\ 13& 11& 26& 0& 12\\ 4& 8& 9& 0& 12\\ 1& 8& 4& 0& 2\\ 2& 13& 3& 0& 1\end{array}\right]$

4+19+3+9+6 = 41

直排提煉後

$\left[\begin{array}{ccccc}12& 1& 0& 19& 7\\ 12& 3& 26& 0& 11\\ 3& 0& 9& 0& 11\\ 0& 0& 4& 0& 1\\ 1& 5& 3& 0& 0\end{array}\right]$

41 + (1+8+1) = 51

基本成本就是51

稍微畫個拓樸排序 等等可以對照

B&B結果

第3題: Traveling Salesperson Optimization Problem

• 在ppt34頁中，該例首先以4-6將所有feasible solution分為兩集合。
• 現在，將原例的4-6改以6-7來作區分，接著再以3-5作區分，如下圖所示：

• 請計算出圖中每個紅框的lower bound，並列出reduced matrix。

原始reduced matrix

lower bound = 96

lower bound = 96 + 0 = 96

把7-6改成無限、把第7欄刪掉
因為第6列有一個0了，所以不用縮減

lower bound = 96 + 0 + 5 = 101

lower bound = 96 + 0 = 96

把5-3改成無限、把第5欄刪掉
因為第5列有一個0了，所以不用縮減

lower bound = 96 + 1 + 17 = 114

每個的lower bound

第4題: 左右反轉二元樹

解題思路

左右子樹的結點都翻一次
整棵樹就翻過來了
寫個遞迴給他左右翻轉
蠻簡單的

程式碼

class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root == NULL)
        {
            return NULL;
        }
        TreeNode* L = new TreeNode();
        L = root->left;
        TreeNode* R = new TreeNode();
        R = root->right;
        if(L!=NULL)
        {
            invertTree(L);
        }
        if(R!=NULL)
        {
            invertTree(R);
        }
        root->left=R;
        root->right=L;
        return root;
    }
};

測試輸出輸入的畫面截圖

花費時間

9分鐘

完成程度

完全自己解出

第5題:

解題思路

因為二元搜尋樹的中序就是從小排到大
中序跑一次就好，全域變數紀錄跑到第幾個這樣

程式碼

class Solution {
public:
    int num = 0,ans = 0;
    int kthSmallest(TreeNode* root, int k) {
        num = 0;
        ans = 0;
        f(root,k);
        return ans;
    }
    void f(TreeNode* root, int k) {
        if(root == NULL)
        {
            return;
        }
        f(root->left,k);
        num++;
        if(num == k)
        {
            ans = root->val;
            return;
        }
        if(num > k)
        {
            return;
        }
        f(root->right,k);
    }
};

測試輸出輸入的畫面截圖

花費時間

5分鐘

完成程度

完全自己解出

第6題:

解題思路

紀錄目前遇到的最深的節點
如果遇到更深的，就把LD更新、把sum歸零，並把點的數值加到sum
如果遇到跟最深的一樣深，就把點的數值加到sum

程式碼

class Solution {
public:
    int LD = -1;
    int sum = 0;
    int deepestLeavesSum(TreeNode* root) {
        LD = -1;
        sum = 0;
        f(root , 0);
        return sum;
    }
    void f(TreeNode* root,int d)
    {
        if(root == NULL)
        {
            return;
        }
        if(d > LD)
        {
            sum = root->val;
            LD = d;
        }
        else if( d == LD )
        {
            sum += root->val;
        }
        f(root->left,d+1);
        f(root->right,d+1);
    }
};

測試輸出輸入的畫面截圖

花費時間

10分鐘

完成程度

完全自己解出

心得:

已填