算法合集之用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問(wèn)題-文庫(kù)吧資料
2025-01-15 19:02本頁(yè)面
【正文】 一條費(fèi)用最?。ǘ曳钦┑目稍鰪V路徑，直到最終不存在費(fèi)用非正的可增廣路徑。（弧的費(fèi)用由可能為負(fù)）所以網(wǎng)絡(luò)的最小費(fèi)用最大流是指可行流中費(fèi)用最小的。 那么，又 如何把費(fèi)用也考慮進(jìn)去呢？我們先來(lái)看看網(wǎng)絡(luò)的費(fèi)用的定義吧。（經(jīng)典問(wèn)題） 顯然，求最小費(fèi)用最大流可以由求最大流的算法改進(jìn)。)( 2 ??? jsjsmj 。3,1m a x13ifPaiPaiffiiiii 且且 但是當(dāng)問(wèn)題擴(kuò)展到多列的情況，就復(fù)雜了：不僅要考慮一列是否能引用上一行的函數(shù)值，而且要多列同時(shí)考慮。31,139。,1111 Ha Paf ，動(dòng)態(tài)規(guī)劃方程：???????????????1,39。,0 39。 可以用貪心，盡量把炮兵往上放，也可以這樣遞推：用 fi表示前 i 行最多能放炮兵數(shù)， ai表示第 i 行的地形，則邊界條件：??? ??? 39。 從 1 到 2，從 2 到 3—— 用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問(wèn)題 廣東省韶關(guān)一中 張偉達(dá) 2022 集訓(xùn)隊(duì)論文 5 【例三】炮兵陣地。 【小結(jié)】在這個(gè)例題中，我們用了最簡(jiǎn)單的方法 —— 枚舉，來(lái)改進(jìn)一維數(shù)列的最大子序列的解法，從而解決問(wèn)題的規(guī)模的增加。對(duì)于這道題的數(shù)據(jù)規(guī)模，似乎沒(méi)有必要構(gòu)造 O(N2)時(shí)間的算法。于是簡(jiǎn)單的動(dòng)態(tài)規(guī)劃就出來(lái)了，用 fi表示以 i 為終點(diǎn)的數(shù)列的最大和，有： ??? ? ??? ?1, 1),m a x(11ia iaaff iiii 不過(guò)，我們得到的只是子問(wèn)題的算法，如何改進(jìn)算法能使它適用于矩陣的問(wèn)題呢？我們需要找出矩陣和數(shù)列的關(guān)系：矩 陣是若干條數(shù)列，但是它又不僅僅是簡(jiǎn)單的若干條數(shù)列，不同數(shù)列中的相同位置的數(shù)也構(gòu)成了聯(lián)系。其實(shí) 我們計(jì)算 Si,j ( ijaaaS ijjji ????? ? ,1, ?)時(shí)，可以由 ijiji aSS ?? ? ,1,獲得。 對(duì)于一維的子問(wèn)題，可以這樣來(lái)想：如果用最基本的方法，可以枚舉每個(gè)子序列。因?yàn)樗莾删S的問(wèn)題，我們可以嘗試著把維數(shù)降低。 【問(wèn)題分析】初一看題目，想到枚舉每一個(gè)子矩陣，求出子矩陣的和，比較得出最大值。狀態(tài)轉(zhuǎn)移時(shí)將兩條路徑分別考慮： ??? ?????? ?????????? r owkybbxaa r owkybbxaakkkkkkkkkkkk ,1, ,1,1111 【小結(jié)】從這個(gè)例子可以看出，改進(jìn)的時(shí)候不能只依靠原始算法，還要分析原始算法的本質(zhì)。通過(guò)這一步觀察，我們 就會(huì)發(fā)現(xiàn)這個(gè)問(wèn)題很好解決，只需要5 5 5 5 5 4 4 4 6 4 2 2 3 3 3 3 3 3 3 8 8 8 7 7 7 7 6 9 4 6 6 從 1 到 2，從 2 到 3—— 用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問(wèn)題 廣東省韶關(guān)一中 張偉達(dá) 2022 集訓(xùn)隊(duì)論文 4 加一維狀態(tài)變量就成了。這時(shí)的模型實(shí)際上已經(jīng)轉(zhuǎn)化成了一個(gè)特殊的多段圖。如果非得套用這種方法的話，則最優(yōu)指標(biāo)函數(shù)就需要有四維的下標(biāo)，并且難以處理兩條路徑“不能重疊”的問(wèn)題?！紨U(kuò)展〗在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，并且要求兩條路徑的總長(zhǎng)度最短。 【例一】街道問(wèn)題及其擴(kuò)展。 但是如何來(lái)改進(jìn)原有的算法呢，筆者認(rèn)為可以有以下途徑： 1. 直接增加算法的規(guī)模，解決問(wèn)題 2. 用枚舉處理增加的規(guī)模，從而解決問(wèn)題 3. 用貪心解決增加的規(guī)模，從而解決問(wèn)題 4. 以上各個(gè)途徑的綜合運(yùn)用 圍繞這一主線，筆 者將用例題做進(jìn)一步的闡明。 【小結(jié)】上面這個(gè)例子中，我們從構(gòu)造模型和改進(jìn)算法兩方面入手，一步一步地達(dá)到了優(yōu)化的解法。 根據(jù)這一改進(jìn)后的方法，我們很容易就得出正確的解法：分別點(diǎn)燃第一根的兩頭和第二根的一頭，第一根燒完的時(shí)候，已經(jīng)過(guò)了 30 分鐘；第二根還剩 30分鐘，點(diǎn)燃第二根的另一頭；當(dāng)?shù)诙矡炅耍磿r(shí)間又過(guò)了 15 分鐘。我們需要對(duì)“兩頭燒”做進(jìn)一步改進(jìn)：如果一根香只燒了一頭， 當(dāng)剩余時(shí)間為 t 的時(shí)候，我們把另一頭也點(diǎn)燃—— 那么，我們就能夠計(jì)出 t/2 的時(shí)間了（前提是我們已知當(dāng)前剩余時(shí)間 t）。通過(guò)這一步， B 模型只用一根香，是很容易被排除的。這樣，我們就能把一根香的計(jì)時(shí)減成半個(gè)小時(shí)。但是怎樣減，能減成什么呢？顯然是不能直接把它們分開(kāi)的，因?yàn)橄愕姆植疾痪鶆颉? 要確定 45 分鐘的時(shí)間，而每根香燒完的時(shí)間是一個(gè)小時(shí)，現(xiàn)在應(yīng)該有三個(gè)模型讓我們思考： ，兩根香加在一起計(jì)時(shí)是 45 分鐘； ，使其計(jì)時(shí)減小，直接計(jì)時(shí) 45 分鐘； ，使兩根香加起來(lái)是 45 分鐘 。我們不妨把這類問(wèn)題叫做規(guī)模維數(shù)增大的問(wèn)題，解決這一類問(wèn)題，往往需要觀察問(wèn)題的特殊性，改進(jìn)原有算法，從而解決實(shí)際問(wèn)題。但是，題目形式多種多樣，這些算法往往是不能夠直接套用的。（ NOI2022） .............................................................. 5 (3)用貪心解決增加的規(guī)模，從而解決問(wèn)題 ........................................................ 5 【例四】求網(wǎng)絡(luò)的最小費(fèi)用最 大流。 【目錄】 一、概述 ....................................................................................................................... 2 二、引子：從一道 IQ 題說(shuō)起 ..................................................................................... 2 三、改進(jìn)算法的途徑 ................................................................................................... 3 (1)直接增加算法的規(guī)模，解決問(wèn)題 .................................................................... 3 【例一】街道問(wèn)題及其擴(kuò)展。 從 1 到 2，從 2 到 3—— 用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問(wèn)題 廣東省韶關(guān)一中 張偉達(dá) 2022 集訓(xùn)隊(duì)論文 1 用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問(wèn)題 廣東韶關(guān)一中 張偉達(dá) 【關(guān)鍵字】 增大規(guī)模 改進(jìn)算法 降維 分析 構(gòu)造 【摘要】 我們常常會(huì)遇到一些特殊的問(wèn)題，它們把我們能夠解決的問(wèn)題改了一改，增加了一維，或者增加了一個(gè)因素，從 1 到 2 或者是從 2 到 3，本文把它們統(tǒng)稱規(guī)模維數(shù)增大的問(wèn)題。 解決這類問(wèn)題可以用改進(jìn)算法的思想：本文第一部分先是概述這種思想；第二部分則從一道有趣的 IQ 題目說(shuō)起，引入改進(jìn)算法的基本思路和基本途徑；第三部分則用多個(gè)例子解釋說(shuō)明如何改進(jìn)算法；最后一部分是總結(jié)改進(jìn)算法的思想。（經(jīng)典問(wèn)題） .............................................. 3 (2)用枚舉處理增加的規(guī)模，從而解決問(wèn)題 ........................................................ 4 【例二】旅 行（廣東省奧林匹克競(jìng)賽
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1