- 1、本文档共55页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
Dijkstra Algorithm for Single-pair Shortest Path Problem 最短路径
Algorithms (Dr. Shi-Jay Chen, National United University) Course 7貪婪法則Greedy Approach ▓ Outlines 本章重點 Dynamic Programming v.s. Greedy Approach Concepts of Greedy Approach Minimum Spanning Trees The Greedy Approach versus Dynamic Programming: The Knapsack Problem Dijkstra Algorithm for Single-pair Shortest Path Problem ▓ Dynamic Programming v.s. Greedy Approach 對於具有限制的最佳化問題,可以採用 “貪婪法則” 或 “動態規劃” 來設計演算法則。 所謂具有限制條件的最佳化問題,是指可以將這一個問題表示成為具有一個目標函數 (Objective Function)與一些限制函數 (Constraint Function;或稱限制條件)的式子。 對於求解具有限制條件的最佳化問題時所得到的不同答案類型而言: 符合限制函數 (條件) 的所有答案,一般通稱為可行解 (Feasible Solution) 但是在這一群可行解中,如果能夠讓目標函數最佳化,則這一個可行解就稱為最佳解 (Optimal Solution) Greedy Approach 是一種階段性 (Stage) 的方法 具有一選擇程序 (Selection Procedure),自某起始點(值) 開始,在每一個階段逐一檢查每一個輸入是否適合加入答案中,重複經過多個階段後,即可順利獲得最佳解 一個選擇程序正確與否,會影響貪婪法則所設計出之演算法在執行過後的答案是否為最佳答案。 較為簡單 如果所要處理的最佳化問題無法找到一個選擇程序,則需要考慮所有的可能情況,就是屬於Dynamic Programming Dynamic Programming 先把所有的情況都看過一遍,才去挑出最佳的結果 考慮問題所有可能的情況,將最佳化問題的目標函數表示成一個遞迴關係式,結合Table的使用以找出最佳解 ▓ Concepts of Greedy Approach Greedy approach 從一組資料序列中抓取資料時,每一階段要抓一個該階段最佳的資料是根據一些準則 (選擇程序) 來決定,且此次的決定和先前及往後的階段所做之任何一個決定無關。 設計方法: 根據問題的目標函數,找出一個選擇程序 (Selection Procedure)。 根據這一個選擇程序,由所有的輸入中,每次逐一選擇一個最佳的輸入加以檢查,如果這一個輸入可以符合問題的限制條件,則將這一個輸入加入;反之則必須捨棄這一個輸入。 每一階段可以重覆上述選擇、檢查的程序。所有階段執行完畢後,最後可以得到一個最佳解或是不存在任何一組可行解。 貪婪演算法的演算過程由一個空的解集合開始,藉由循序的加入新的解直到符合問題需求的最終解得到為止。 重複下列程序: 選擇程序 (Selection procedure) 挑選出下一個項目加入到解集合中。 選擇程序的執行,是根據滿足每一階段之局部最佳化條件(locally optimal consideration)的貪婪原則來進行。 可行性檢查 (Feasibility check) 決定加入新項目後的新的解集合,是否在可行解的範圍之內。 解答檢查 (Solution check) 決定此新的解集合是否為此問題的最終結果。 [找零錢問題]: 售貨員在找零錢問題中,不但要找對錢 (限制條件),而且還要找給顧客最少的銅板 (目標函數)。 利用Greedy Approach如下 (例:要找給客人75元): 選擇程序 (selection procedure): 售貨員開始找尋收銀機中最大幣值的硬幣時,選擇的準則是究竟哪一枚硬幣的幣值是目前最佳的選擇 (局部最佳解) 可行性檢查 (feasibility check): 售貨員必須判斷他剛剛選擇出那一枚硬幣的幣值加上 “目前顧客方已經收到的幣值總數” 是否超過 “應找給顧客的最後總數”。(是否有超過75元) 解答檢查 (solution check): 售貨員必須檢查目前 “已找給顧客方的零錢總數” 是否等於 “應找給顧客的最後總數”。(是否已經等於75元) 如果兩者不相等,則售貨員必須繼續利用他的選擇硬幣機制拿出硬幣,並重複上述三個過程直到 “已找給顧客方的零錢總數” 等於 “應找給顧客的最後總數”; 或是收銀機裡的硬幣全部用盡為止。 ▓ Minimum Spanning Tre
您可能关注的文档
- 6525 nm 而雷射则是诱发放射 - 正修科技大学.PPT
- 7植物学实验讲义.DOC
- 73系统测试.PPT
- 7年级自然-潮州国中.DOC
- 7 IBM ESS企业存储服务器 - Portal.DOC
- 806物理光学.PDF
- 62植物光合作用的场所.PDF
- 71识读与绘制螺栓连接装配图.PPT
- 811无机化学大纲(2007版)-南京工业大学研究生院.DOC
- 8-羟基喹啉锂及其衍生物电子光谱性质的理论-发光学报.PDF
- 东海证券-轮胎行业月报:2024年高景气收官,节后开工恢复性提升.pdf
- 东吴证券-环保行业跟踪周报:欧盟终裁略下调对华生柴反倾销关税,开始跟踪SAF进口,持续推荐现金流资产.pdf
- 北京博观众智信息科技-日本保健品行业繁荣发展的背后及发展现状.pdf
- 兴业证券-电力设备行业深度报告:机器人业务打开锂电精密加工企业成长空间.pdf
- 信达证券-航空运输月度专题:1月油汇向好、国内线运力同比微增,客座率高位维稳.pdf
- 兴业证券-德昌股份-605555-家电汽零双轮驱动,多元布局兑现高成长.pdf
- 东吴证券-九方智投控股-09636.HK-基本面夯实乘A股东风,AI赋能拓成长蓝海.pdf
- 民生证券-计算机行业深度报告:DeepSeek系列报告之AI+医疗.pdf
- 兴业证券-基础化工行业周报:国常会研究提振消费及化解重点产业结构性矛盾继续关注化工核心资产及新材料成长.pdf
- 国金证券-A股投资策略周报:港股“狂飙”背后:哪些驱动因子与A股不一样?.pdf
最近下载
- 铁血丹心-钢琴谱 高清正版完整版五线谱.pdf
- SPC地板现状研究分析与发展前景预测报告2024年.docx VIP
- 以中国式现代化全面推进中华民族伟大复兴(ppt)(1).PPTX VIP
- (苏教版)三年级下册综合实践第三单元电子教案.pdf VIP
- 幼儿园小班主题我爱我家.pdf VIP
- 品管圈PDCA获奖案例-心血管内科降低经皮冠状动脉介入术后肢体肿胀发生率医院品质管理成果汇报.pptx
- 提高容积率的申请报告.doc
- 2024 年度民主生活会“四个对照”方面(存在问题、原因剖析及整改措施).docx VIP
- GB41022-2021 煤矿瓦斯抽采基本指标.pdf
- 2025年无锡工艺职业技术学院高职单招数学历年(2016-2024)频考点试题含答案解析.docx
文档评论(0)