算法合集之用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問(wèn)題(已修改)
2025-01-21 19:02 本頁(yè)面
【正文】 從 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)算法的思想。 【目錄】 一、概述 ....................................................................................................................... 2 二、引子：從一道 IQ 題說(shuō)起 ..................................................................................... 2 三、改進(jìn)算法的途徑 ................................................................................................... 3 (1)直接增加算法的規(guī)模，解決問(wèn)題 .................................................................... 3 【例一】街道問(wèn)題及其擴(kuò)展。（經(jīng)典問(wèn)題） .............................................. 3 (2)用枚舉處理增加的規(guī)模，從而解決問(wèn)題 ........................................................ 4 【例二】旅 行（廣東省奧林匹克競(jìng)賽 2022） ............................................. 4 【例三】炮兵陣地。（ NOI2022） .............................................................. 5 (3)用貪心解決增加的規(guī)模，從而解決問(wèn)題 ........................................................ 5 【例四】求網(wǎng)絡(luò)的最小費(fèi)用最 大流。（經(jīng)典問(wèn)題） .................................. 5 (4)多種途徑的綜合運(yùn)用 ........................................................................................ 6 【例五】 Team Selection (Balkan OI 2022 Day1) .......................................... 6 四、總結(jié) ....................................................................................................................... 9 【感謝】 ....................................................................................................................... 9 【參考文獻(xiàn)】 ............................................................................................................. 10 【附錄】 ..................................................................................................................... 11 (廣東省奧林匹克競(jìng)賽 2022) ............................................................ 11 （ NOI2022） ............................................................................. 12 Selection (BalkanOI 2022 Day 1 Task 2) ......................................... 13 從 1 到 2，從 2 到 3—— 用改進(jìn)算法的思想解決規(guī)模維數(shù)增大的問(wèn)題 廣東省韶關(guān)一中 張偉達(dá) 2022 集訓(xùn)隊(duì)論文 2 一、概 述 每個(gè)學(xué)習(xí)信息學(xué)奧林匹克的選手總是要先學(xué)習(xí)一些基本的算法，然后才能把算法應(yīng)用到題目當(dāng)中去。但是，題目形式多種多樣，這些算法往往是不能夠直接套用的。有的時(shí)候我們分析到某個(gè)問(wèn)題好像可以用某種方法解決，但是這個(gè)問(wèn)題卻與之前見過(guò)的問(wèn)題有些不同，例如本文所討論的情況：?jiǎn)栴}的規(guī)模維數(shù)比原問(wèn)題大，一維的變二維的，二維的變?nèi)S的，等等。我們不妨把這類問(wèn)題叫做規(guī)模維數(shù)增大的問(wèn)題，解決這一類問(wèn)題，往往需要觀察問(wèn)題的特殊性，改進(jìn)原有算法，從而解決實(shí)際問(wèn)題。 二、引子：從一道 IQ題說(shuō)起 【 IQ 題題目】在走入正題之前，還是讓我們來(lái) 玩一道 IQ 題 (據(jù)說(shuō)是 IBM 公司招聘面試用過(guò)的題目 )： 有兩根 完全相同但 分布不均勻的香 （提示：不妨假設(shè)是蚊香，一圈圈的那種） ，每根香燒完的時(shí)間是一個(gè)小時(shí)，你能用什么方法來(lái)確定一段 45 分鐘的時(shí)間？ 【??】（思考中） 【思路】在公布答案之前，還是讓我們來(lái)循序漸進(jìn)地思考下去吧。 要確定 45 分鐘的時(shí)間，而每根香燒完的時(shí)間是一個(gè)小時(shí)，現(xiàn)在應(yīng)該有三個(gè)模型讓我們思考： ，兩根香加在一起計(jì)時(shí)是 45 分鐘； ，使其計(jì)時(shí)減小，直接計(jì)時(shí) 45 分鐘； ，使兩根香加起來(lái)是 45 分鐘 。 A 模型顯然是不可能成立的； B、 C 模型的共同點(diǎn)是：我們必須使一根香的計(jì)時(shí)減小。但是怎樣減，能減成什么呢？顯然是不能直接把它們分開的，因?yàn)橄愕姆植疾痪鶆?。由于這里筆者已經(jīng)降低了難度，根據(jù)提示，比較容易想到香是可以兩頭一起燒的。這樣，我們就能把一根香的計(jì)時(shí)減成半個(gè)小時(shí)。方案已經(jīng)更進(jìn)一步了。通過(guò)這一步， B 模型只用一根香，是很容易被排除的。 余下的選擇只有“ C 模型 +兩頭燒方法”了，但是 C 模型不能直接應(yīng)用“兩頭燒”，因?yàn)檫@樣套用的話， + 仍然等于 1。我們需要對(duì)“兩頭燒”做進(jìn)一步改進(jìn)：如果一根香只燒了一頭， 當(dāng)剩余時(shí)間為 t 的時(shí)候，我們把另一頭也點(diǎn)燃—— 那么，我們就能夠計(jì)出 t/2 的時(shí)間了（前提是我們已知當(dāng)前剩余時(shí)間 t）。特別地，當(dāng) t=60min 時(shí)， t/2=30min。 根據(jù)這一改進(jìn)后的方法，我們很容易就得出正確的解法：分別點(diǎn)燃第一根的兩頭和第二根的一頭，第一根燒完的時(shí)候，已經(jīng)過(guò)了 30 分鐘；第二根還剩 30分鐘，點(diǎn)燃第二根的另一頭；當(dāng)?shù)诙矡炅?，即時(shí)間又過(guò)了 15 分鐘。那么我們計(jì)出的總的時(shí)間就為 45 分鐘了。 【小結(jié)】上面這個(gè)例子中，我們從構(gòu)造模型和改進(jìn)算法兩方面入手，一步一步地達(dá)到了優(yōu)化的解法。主要流程是： 1. 找出原 始解法和可能改進(jìn)的方向（即分析成 A、 B、 C 模型）； 2. 分析算法
試題試卷相關(guān)推薦
鄂ICP備17016276號(hào)-1