Try   HackMD

演算法作業 HW10

  • 本週進入到第5章後半，樹搜尋延伸至A*演算法。

觀念題
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

第1題: 01背包問題

  • 已知有六個物品，其價值和重量如下，背包重量限制為34。
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • 仿照課本以tree search來解。
  • 請將下圖中的框框中，填入其upper bound與lower bound
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

第2題: A* 解multi-stage shortest path problem

  • 請使用A* 找出S到T的最短路徑。請畫出樹狀圖，並標示各點的cost，並註明哪裏分枝不用再繼續尋找了。
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

第3題: Channel Routing Problem

  • 請使用A* 解Channel Routing Problem。
  • 本題將原本題目的net 7移除，只剩下7個nets，請找出最少track的安排方式。
    Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

程式題:
Image Not Showing Possible Reasons
  • The image file may be corrupted
  • The server hosting the image is unavailable
  • The image path is incorrect
  • The image format is not supported
Learn More →

第4題: 合併二元樹

第5題: 最深葉子的最低共同祖先

  • Lowest Common Ancestor of Deepest Leaves - LeetCode
  • 所謂Lowest Common Ancestor(最低共同祖先)，舉例來說，下圖中xy的最低共同祖先就是深綠色的點。
    • 若當只有一個點時，該點的LCA就是自己。
    • 例如x的最低共同祖先就是x。
  • Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →
  • 題目：給定一個二元樹，找出該二元樹最深的葉子之最低共同祖先
    • 建議以BFS來作。
  • 例如下圖中，最深的葉子為7,4,而LCA就是2。
  • Image Not Showing Possible Reasons
    • The image file may be corrupted
    • The server hosting the image is unavailable
    • The image path is incorrect
    • The image format is not supported
    Learn More →

第6題:

  • Binary Tree Pruning - LeetCode
  • 題目：給定一個二元樹，刪除不含1的子樹
    Image Not Showing Possible Reasons
    • The image was uploaded to a note which you don't have access to
    • The note which the image was originally uploaded to has been deleted
    Learn More →

第7題 : 心得

Last changed by 
 
王皓立
0
1275
Published on HackMD