《技術(shù)參考貪心策略》ppt課件-預(yù)覽頁(yè)
【正文】 我們通過特點(diǎn) 2向大家介紹了貪心策略的數(shù)學(xué)描述。 一、貪心策略的定義 【 定義 1】 貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值 (或較優(yōu)解 )的一種解題方法。（貪心選擇性質(zhì)和局部最優(yōu)解）介紹了3種體現(xiàn) 貪心 思想的圖形算法： Dijkstra算法、 Prim算法和 Kruskal算法，并著重給出了近幾年來在各級(jí)各類程序設(shè)計(jì)競(jìng)賽中出現(xiàn)的一些題目。從全局來看，運(yùn)用貪心策略解決的問題在程序的運(yùn)行過程中無回溯過程。 在遇到具體問題時(shí)，許多選手往往分不清哪些題該用貪心策略求解，哪些題該用動(dòng)態(tài)規(guī)劃法求解。下面我們就來介紹貪心策略的理論 矩陣胚。 如果對(duì) S的每一個(gè)元素 X（ X∈S ）賦予一個(gè)正的權(quán)值 W（ X），則稱矩陣胚 M=（ S， I）為一個(gè)加權(quán)矩陣胚。 四 、 幾種典型的貪心算法 貪心策略在圖論中有著極其重要的應(yīng)用。其中一類被稱為 P類問題，它存在有效算法，可求得最優(yōu)解；另一類問題被稱為 NPC類問題，這類問題到目前為止人們尚未找到求得最優(yōu)解的有效算法，這就需要每一位程序設(shè)計(jì)人員根據(jù)自己對(duì)題目的理解設(shè)計(jì)出求較優(yōu)解的方法。在這些問題中，有的題目可以用貪心策略來直接求解，有的題目運(yùn)用貪心策略后可以使問題得到極大的簡(jiǎn)化，使得程序?qū)Υ笮畔⒘康奶幚硖峁┝丝赡?。此題所需處理的數(shù)據(jù)從表面上看是一個(gè)整數(shù)。 編程任務(wù) ：對(duì)于給定的數(shù)列，編程計(jì)算出極差 M。 下面我們以求 max為例來討論此題用貪心策略求解的合理性。 這是一道兩次運(yùn)用貪心策略解決的一道問題，它要求選手有較高的數(shù)學(xué)推理能力。他很想去Ｓ公園游玩。 寫一個(gè)程序，幫助阿昌尋找一個(gè)最優(yōu)乘車方案，使他在從ＣＵＰ飯店到Ｓ公園的過程中換車的次數(shù)最少。此時(shí)要使換車次數(shù)最少，應(yīng)乘坐線路Ｂ的巴士，路線為：ａ → ｂ → ｃ → ｅ，換車次數(shù)為０；要使途經(jīng)車站數(shù)最少，乘坐線路應(yīng)為ａ → ｄ → ｅ，換車次數(shù)為１。我們根據(jù)題中所給數(shù)據(jù)來建立一個(gè)圖后會(huì)發(fā)現(xiàn)該圖中存在大量的環(huán)，因而不適合用搜索法求解。而從近幾年的信息學(xué)奧林匹克競(jìng)賽的命題方向上看，題目更加靈活，同時(shí)測(cè)試數(shù)據(jù)較大，規(guī)定的出解時(shí)間較短。游客在旅游街上只能從西向東走，在林蔭道上既可以由南向北走，也可以從北向南走。請(qǐng)你寫一個(gè)程序，幫助阿隆尋找一條最佳的瀏覽路線，使得這條路線的所有分值總和最大。這是一種貪心策略。其實(shí)在這一步我們同樣可以采用貪心法求解。第二階段為 1997年至今。在對(duì) P類較優(yōu)解問題的求解過程中，貪心策略無疑扮演著重要角色。探測(cè)車 MEV不能通過有障礙的地面。這兩項(xiàng)都做到會(huì)使你的得分最高。 輸出： 表示 MEV移向 transmitter的行動(dòng)序列
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1