算法合集之《轉(zhuǎn)化目標(biāo)在解題中的應(yīng)用》

《算法合集之《轉(zhuǎn)化目標(biāo)在解題中的應(yīng)用》》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、IOI2004國家集訓(xùn)隊(duì)論文栗師轉(zhuǎn)化目標(biāo)在解題中的應(yīng)用湖南省長沙市長郡中學(xué)栗師【摘要】本文主要簡單討論目標(biāo)轉(zhuǎn)化思想對(duì)算法和分析解決問題的應(yīng)用。第一部分概述了為什么要目標(biāo)轉(zhuǎn)化。第二部分舉例說明了轉(zhuǎn)化目標(biāo)在算法設(shè)計(jì)中的作用，先達(dá)到轉(zhuǎn)化后的目標(biāo)，再通過轉(zhuǎn)化后的目標(biāo)得到最終目標(biāo)。第三部分也通過一道例題，介紹了轉(zhuǎn)化目標(biāo)在分析問題中的作用。最后總結(jié)一些常見的轉(zhuǎn)化目標(biāo)的方法，以及怎樣才能靈活的運(yùn)用它。【關(guān)鍵字】轉(zhuǎn)化目標(biāo)、放大、縮小、簡化問題【正文】一、引言在信息學(xué)算法設(shè)計(jì)的過程中，總會(huì)遇到這樣或者那樣的困難。一個(gè)很大的原因就是人的思維的深度和廣度都是有限的，而未知

2、世界是無窮的。當(dāng)遇到一道難解決的問題時(shí)，總是覺得目標(biāo)太遙遠(yuǎn)，關(guān)系錯(cuò)綜復(fù)雜，無從下手。這時(shí)，不妨嘗試轉(zhuǎn)化一下目標(biāo)，從轉(zhuǎn)化后的目標(biāo)進(jìn)行思考。例如，減少限制，放松條件，縮小范圍等。解決了轉(zhuǎn)化后的目標(biāo)后，再站在一個(gè)新的高度設(shè)計(jì)算法，或第1頁共15頁IOI2004國家集訓(xùn)隊(duì)論文栗師者把轉(zhuǎn)化的目標(biāo)的算法推廣到原目標(biāo)。目標(biāo)轉(zhuǎn)化思想從兩個(gè)方向?yàn)槲覀兲峁┝私輳剑核惴ê退悸贰６?、在算法設(shè)計(jì)中應(yīng)用轉(zhuǎn)化目標(biāo)方法如果一步不能達(dá)到目的，那么就分步解決，每一步就達(dá)到了一個(gè)中間目標(biāo)，這種方法會(huì)經(jīng)常用到。最常見的就是，如果目標(biāo)有多個(gè)限制，先只對(duì)一個(gè)限制的得出結(jié)論，再從得出的結(jié)論出發(fā)，

3、考慮其它的限制。下面是以PolandOlympiadofInformatics2003的一題為例，來說明這一種方法。[例1]超級(jí)馬在一個(gè)無限的棋盤上有一個(gè)超級(jí)馬，它可以完成各種動(dòng)作。每一種動(dòng)作都是通過兩個(gè)整數(shù)來確定——第一個(gè)數(shù)說明列的數(shù)（正數(shù)向右，負(fù)數(shù)向左），第二個(gè)數(shù)說明行的數(shù)（正數(shù)向上，負(fù)數(shù)向下），移動(dòng)馬來完成這個(gè)動(dòng)作。任務(wù)編寫一個(gè)程序從文本文件SUP.IN輸入說明各種超級(jí)馬的數(shù)據(jù)庫。對(duì)每一個(gè)超級(jí)馬進(jìn)行確認(rèn)，是否通過自己的行動(dòng)可以到達(dá)盤面上的每一個(gè)區(qū)。將結(jié)果存儲(chǔ)到文本文件SUP.OUT。輸入在文本文件SUP.IN的第一行中存在一個(gè)整數(shù)k，它代表數(shù)據(jù)

4、庫的數(shù)1≤k≤100。在這個(gè)數(shù)字后出現(xiàn)K數(shù)據(jù)庫。它們的每一個(gè)第一行中會(huì)出現(xiàn)整數(shù)N，它是馬能夠完成的各種動(dòng)作的數(shù)，1≤n≤100。接下來數(shù)據(jù)庫的每一個(gè)行中包含兩個(gè)整數(shù)P和Q，它們由單個(gè)空格分開，說明動(dòng)作，-100≤p,q≤100。輸出文本文件SUP.OUT應(yīng)由K行組成，當(dāng)?shù)趇個(gè)數(shù)據(jù)庫的超級(jí)馬可以到達(dá)盤面的每一個(gè)區(qū)，第i行應(yīng)包含一個(gè)詞TAK，而另一個(gè)詞NIE則恰恰相反。輸入樣例252422-3-3431351-3第2頁共15頁IOI2004國家集訓(xùn)隊(duì)論文栗師21414-22-2輸出樣例TAKNIE2.1確定算法模型?？吹筋}目，最容易想到的算法是廣搜。從當(dāng)

5、前已知能夠到達(dá)的格子出發(fā)，按照馬的走法，擴(kuò)展出另外一些能到達(dá)的格子，一直擴(kuò)展下去，最后判斷是不是擴(kuò)展完了所有的棋盤。很快會(huì)發(fā)現(xiàn)這種做法是不行的，棋盤上格子的個(gè)數(shù)是無限的，不能判斷能夠到達(dá)所有的格子。但這個(gè)困難馬上就有了解決的辦法，顯然只要判斷超級(jí)馬是否能到達(dá)開始點(diǎn)的4個(gè)相鄰格。因?yàn)槿绻軌虻竭_(dá)這4個(gè)格子，那么必然能夠到達(dá)棋盤上的任意一個(gè)位置。問題解決了沒有？沒有。雖然最終目標(biāo)只需要判斷四個(gè)格子，但是，它在走到這4個(gè)格子的過程中經(jīng)過的點(diǎn)可能會(huì)有很多個(gè)。更糟糕的是，當(dāng)問題無解時(shí)，無法進(jìn)行正確的判斷，最后實(shí)現(xiàn)算法時(shí)造成死機(jī)。如果把無限的棋盤變成相當(dāng)大的有界

6、棋盤，看它在這個(gè)有界棋盤上能否到達(dá)這4個(gè)格子。但這仍然是無用功，這個(gè)有界棋盤會(huì)有很大，這樣時(shí)間效率很低，算法也缺乏證明。嘗試各種圖論算法、動(dòng)態(tài)規(guī)劃、貪心等，最后都以意料之中的結(jié)果——失敗而告終。要得到高效的算法，似乎只有一條出路：數(shù)學(xué)思想。要用數(shù)學(xué)思想解題，先要建立數(shù)學(xué)模型。以超級(jí)馬最開始的格子為原點(diǎn)建立平面坐標(biāo)系。然后把馬的一種動(dòng)作用一個(gè)平面向量Pi來表示，Pi=(xi,yi)。那么，我們要判斷，對(duì)于任意的x,y，是否都存在一組c1,c2,c3……cn(ci>=0,1≤i≤n)，n使得?ciiP=(xy,)。i=1于是，就確定了這題的數(shù)學(xué)模型：解方

7、程。第3頁共15頁IOI2004國家集訓(xùn)隊(duì)論文栗師進(jìn)一步，只需要判斷(x,y)為(-1,0)，(1,0)，(0,-1)，(0,1)的情況。而這四種情況是一樣的，可以只考慮(0,1)。那么，要判斷下面的方程是否有非負(fù)整數(shù)解：cP+cP+......+=cP(0,1)…………………………………方程①1122nn例如，題目中樣例的第1個(gè)數(shù)據(jù)n=5,5個(gè)向量是P1=(2,4),P2=(2,2),P3=(-3,-3),P4=(4,3),P5=(1,3)，那么方程①的一個(gè)非負(fù)整數(shù)解就是：3(2,4)+5(2,2)+13(-3,-3)+5(4,3)+3(1,3)=

8、(0,1)。2.2“放大”目標(biāo)。這是一個(gè)線性方程，未知數(shù)比較多，而方程只有一個(gè)。直覺告訴我們，如果方程有解的