【精品】交大资工系 fll 解题程式技巧精品ppt课件.ppt

《【精品】交大资工系 fll 解题程式技巧精品ppt课件.ppt》由会员分享，可在线阅读，更多相关《【精品】交大资工系 fll 解题程式技巧精品ppt课件.ppt（16页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、交大资工系2005 fll 解题程式技巧p2.Course Objectives1.To review specific data structures such as linear lists,stacks,queues,hash tables,binary trees,heaps,tournament trees,binary search trees,and graphs.2.To study heuristic search strategies including game search.p3.Course Objectives3.To study specific algorith

2、m design methods such as the greedy method,divide and conquer,dynamic programming,backtracking,and branch and bound.4.To study algorithms for special topics including numerical number theory,data compression,optimization 5.To gain experience writing programs in C+.p4.Course Resources Course Homepage

3、:http:/www.csie.nctu.edu.tw/probsol/p5.References 1“Data Structures,Algorithms,and Applications in Java”,by Sartaj Sahni,McGraw Hill,2000.(Part of power point files of this book will be used.)2Notes will be given in“couse notes”of course page:loginname and password:ps2002p6.p7.p8.Text ContentsTradit

4、ional Search Techniques1.搜索求解搜索求解1.1 寬度優先搜索寬度優先搜索 量杯問題量杯問題(*)換棋問題換棋問題 魔術方塊問題魔術方塊問題1.2 深度優先搜索深度優先搜索 連環鎖問題連環鎖問題 智慧盤問題智慧盤問題 二叉樹的遍歷二叉樹的遍歷p9.Text Contents1.3 等代價搜索等代價搜索 旅行者問題旅行者問題1.4 A*算法算法 炸迷宮問題炸迷宮問題 滑動積木遊戲滑動積木遊戲p10.Text Contents2.回溯法回溯法 八皇后問題八皇后問題 填數字問題填數字問題 取數組合問題取數組合問題 加減號填寫問題加減號填寫問題 一筆劃問題一筆劃問題 擺馬賽克問

5、題擺馬賽克問題 撕郵票問題撕郵票問題p11.Text Contents3.問題歸約問題歸約 3.1 與或樹與或樹 3.2 遞歸遞歸 排序問題排序問題 遞歸函數問題遞歸函數問題 河內塔問題河內塔問題 3.3 博弈樹博弈樹 Nim-like遊戲遊戲(三角棋三角棋)3.4 alpha-beta過程過程p12.Text ContentsAlgorithm-Design MethodsThe Greedy MethodDivide and ConquerDynamic ProgrammingBacktrackingBranch and BoundLinear program and Integer pr

6、ogram(use Lindo package)p13.Algorithm Designn動態規劃動態規劃(Dynamic Programming)n矩陣連乘積矩陣連乘積Matrix chain multiplicationn 是是 n 個矩陣個矩陣,找出最有效的乘法計算方式來計算找出最有效的乘法計算方式來計算A1A2An.nA1A2A3 A4 n 有五種方式有五種方式:(A1(A2(A3A4)(A1(A2A3)A4)(A1A2)(A3A4)(A1(A2A3)A4)(A1A2)A3)A4).p14.Algorithm Designn貪婪演算數法貪婪演算數法The Greedy MethodnHuffman 編碼編碼A:0B:101C:100D:111E:1101F:1100p15.Algorithm Designn分治演算法分治演算法Divide-and-Conquer n矩陣相乘矩陣相乘Matrix multiplicationStrassens Algorithm 可由可由7個個SIZE為一半的小為一半的小矩陣相乘合成矩陣相乘合成complexityp16.Algorithm Designn反溯法反溯法Backtracking n八后問題八后問題The 8-queen problem12345678