算法合集之淺談類比思想(編輯修改稿)
2024-09-14 16:49 本頁面
【文章內容簡介】 轉、平移、縮放的操作都有無限種可能。 關注點集中的不變量質心。設n個點的坐標分別為(x1,y1 ),(x2,y2),…,(xn,yn)，則質心O坐標為下文可以看到，求出質心的好處在于可以將相對于直角坐標系的的坐標轉化成相對于質心的量?？s放是對點集整體縮放。假設點集中任意一點與質心間都有線段連接，并且點P縮放后變?yōu)镻’，則有下列恒等式：其中A,B是點集S中任意兩點。這個式子表明無論如何縮放，點集中任意兩條線段長度之比是恒定的。也就是說其中m是點集中所有線段長度的最大值。易知這個最大值可以在O(n)的時間內求出。由此我們便求出了S到S’的縮放比k，按照縮放比將坐標擴大k倍即可。現在到了關鍵的部分，注意每個點P與質心的關系，點P可以看作從質心出發(fā)，引一條長度為|OP|的線段，再從與橫軸平行的方向順時針旋轉alpha度（也就是說P關于O的方向角是alpha度）。把所有的點按照方向角優(yōu)先、到質心距離次優(yōu)先的規(guī)則進行排序，那么一個點集就可以看成n次操作，每次操作將一條一個端點在O的線段順時針旋轉一個量，再拉長或縮短。一次操作可以用一個二元組(delta,distance)來描述，其中delta就是排序后相鄰兩點的方向角之差。這樣一個n個點的點集S就被對應成了一個長度為n的串T。并且點集可以旋轉，也就是串的起始位置不確定，是一個環(huán)串。因此兩個點集同構，即是它們轉換后得到的環(huán)串相同。而判斷環(huán)串T與T’ 是否相同，可以把T和T’從某個地方截斷得到U和U’，再使用kmp算法判斷U’在串UU中是否出現即可。概括一下上面的討論：求質心的費用為O(n)，排序的耗費為O(nlog2n)，執(zhí)行kmp算法的費用為O(3n)，最后翻轉再判斷的費用為O(n)，因此整個算法的復雜度就是O(nlog2n)。有一點需要補充的是，以上的討論都忽略了某個點與質心重合的情況，但處理此問題只需要特判即可。小結本題的關鍵是處理旋轉和平移。我們忽略圖形的次要信息——絕對坐標，把關注的重點變?yōu)辄c跟質心的關系以及點跟點的關系，因此平移問題就不存在了，用環(huán)串類比旋轉操作自然就產生了最后的解法。三、總結：本文對類比作了一定的介紹，同時較深入地討論了一些常見的類比模式。以上所有的解題方法都包含了一種思想，就是類比思想。類比思想是一種轉化的思想，但是類比思想在轉化過程中突出的不是演繹式的化歸，而是跳躍式的比較。固然，類比在思考過程中可能是逐步進行的，但是在外在表現上一般是天馬行空的。從這一點上來說，類比是一種相當不好掌握的思想方法。但無論怎么樣的類比，都會有以下的特性：1．可類比性：原問題和轉化后的問題具有某些相似之處，正是這些相似之處為類比提供了理論依據和思考動機。2．可簡化性：轉化后的問題必然要比原問題更簡單。這個“簡單”可以是更直觀，便于解題者思考；可以是更常見，能利用的理論較多；也可以是更規(guī)范，能用標準的方法解決。3．可移植性：轉化后問題的解法要與類比對象密切相關。例如在例三中把點集類比為環(huán)串后，要密切注意串的匹配、求最長某某子串這一類算法。解法與類比對象相關，才能體現出類比的必要與優(yōu)越。盡管類比思想非常優(yōu)秀，但并非沒有局限性。類比要在轉化的前提下才能完成，也就是說對于那些不需要轉化的問題，類比是沒有任何作用的。四、感謝：衷心感謝向期中老師在我寫這篇論文時對我的指導和幫助。衷心感謝劉汝佳教練對我的指導和啟發(fā)。衷心感謝陳啟峰、楊沐、郭華陽、楊浩、馮子明、吳戈、袁昕顥、周玉姣、劉靚等同學在臨近期末考試時還能幫助審閱我的論文，并提出很多寶貴的意見。五、參考文獻：[1]《數學闖關——數學思想和方法的領悟》 袁銀宗編著[2]《算法藝術與信息學競賽》 劉汝佳 黃亮 著[3] USACO OPEN05： peaks[4] USACO FEB05： secret[5] Poland Olympiad of Informatics 2005 Stage I：PUN六、附錄：例一的原題：Problem 4: Landscaping [Brian Dean, 2005]Farmer John is making the difficult transition from raising mountaingoats to raising cows. His farm, while ideal for mountain goats,is far too mountainous for cattle and thus needs to be flattenedout a bit. Since flattening is an expensive operation, he wants toremove the smallest amount of earth possible.The farm is long and narrow and is described in a sort of twodimensionalprofile by a single array of N (1 = N = 1000) integer elevations(range 1..1,000,000) like this:1 2 3 3 3 2 1 3 2 2 1 2,which represents the farm39。s elevations in profile, depicted belowwith asterisks indicating the heights: * * * * * * * * * * * * ** * * * * * * * * * * *1 2 3 3 3 2 1 3 2 2 1 2A contiguous range of one or more equal elevations in this arrayis a peak if both the left and right hand sides of the range areeither the boundary of the array or an element that is lower inelevation than the peak. The example above has three peaks.
環(huán)評公示相關推薦
鄂ICP備17016276號-1