花店櫥窗布置

⑴ 花店裝修設計應該遵循哪些理念

花店的裝修要注重時尚溫馨經典，而且這個花店裡面的設備要注重時尚前衛，可以隨時隨地地設計一些可以移動的花架，另外櫥窗的展示也很重要。櫥窗也能夠起到點睛之筆的作用，櫥窗是很好的展示花店的藝術水平，櫥窗設計獨特，本身就是最好的廣告。

⑵ 花店裝修要注意什麼花店設計推薦家公司。

花店裝修有兩個方面需要注意：一是要體現出花店的特色;二要嚴格控制花店的裝修費用。花店裝修一定要根據開店構想
設計和施工，不能馬虎，因為開店一後很難進行更改。在裝修的過程中，應嚴格按照清單采購必要的營業設備，如保險櫃，空調等，並安裝調試。花店裝修和采購營業設備要按照開業計劃實施，不能影響花店正常開業。

花店所處位置，招牌設計，櫥窗布置，店堂內部裝修及花卉商品陳列方式等諸多因素都會給顧客不同的印象和感受，影響顧客的購買心理和購買決策的確立與實施。因此，迎合顧客心理。布置出一個優美的購物環境，可以增加銷售量。

花店的裝修與內部設計是營造美好的店堂環境所不可缺少的環節。為了保證顧客在愉悅的放鬆的情緒中購物，店內照明要明亮而柔和，內部裝飾的色調要宜人。花店
內的裝修要簡潔，色彩以淺色調，明快為主。花店裝飾可通過店內家庭式不止等有創新的構思，獨特的布局，高雅。充滿魅力的藝術氛圍，給人以高品質的文化享
受。花店可播放柔和的音樂，以便讓消費者在括靜，安逸的氛圍中精心選購。在花店內合理地設置一些POP廣告，內容可涉及鮮花保鮮知識，花卉新品種信息，各
種場合用花常識，並經常更換內容，保持新鮮感。這樣就容易使顧客花費更多的時間停留在店內咨詢，觀賞，也很容易激發他們的選購慾望。即使本次進店沒有進行
購買，也會給顧客留下好印象，對其今後的購買行為產生影響。

花店的布局

花店布局的核心是顧客流動路線的設計，成功的設計能最大限度地延長顧客在花店的停留時間。不同顧客因年齡，性別，性格的差異，其移動的路線當然有所不同。
一般而言，中老年人進入花店的時間較長，他們會漫漫地仔細地閱讀各類說明和POP廣告，選擇自己所需要的花卉品種。而青年人一般停留時間較短，他們進店
後，想盡快地看到自己所需要的花卉，購買後迅速離開。顧客走動多的地方往往有利與花卉的促銷，走的少的地方則為滯銷區。花店要避免把暢銷的花卉品種放在顧
客走動少的地方，應考慮整體布局，把各類不同的花卉品種有序得擺放，在流動路線設計方面清晰分類，能讓顧客自由自在地選購。同時，花店的店堂布局作為消費
通道，合理的店堂布局能促進銷售的實現。花店的布局一般分為兩類，即格子布局和自由流動式布局。

①格子式布局是一種十分規范的布局方式，擺設互成直角，構成曲徑式通道，使整個花店內結構嚴謹規范，給人以整齊，管理井然有序的印象，這種印象很容易使顧
客對花店產生信任心理，大多用於開架式銷售。格子式布局的缺點是顧客通常會產生孤獨和乏味的感覺，由於在通道中自然形成的驅動力，選購中的顧客會有一種加
速購買的心理壓力，而觀賞和休閑的願望將被大打折扣，同時，由於布局的規范化，使得花店發揮裝飾效應的能力受到限制，難以產生有裝飾形成的購買情趣與效
果。格子式布局的整體投入低，符合普通人求廉的價格心理。從經營角度看，格子式布局更利於銷售安全和保持花店衛生。

②自由流動式布局是根據花卉的特點，形成各種不同的組合獨立或聚合，沒有固定或專設的布局形式，銷售形式也不是固定不變。在實際布局中常見的有條形或矩形
環形。馬蹄形，三角形等多種，這類布局中，通道一般比較寬敞或在花店中央留有較大的空間，用與環境裝飾，這是一種自由式布局，所以能利用裝飾布局創造較好
的環境氣氛，對各種類型的顧客都能產生一定的吸引力，環境促銷的作用十分明顯。自由流動式布局一般要有較大的空間，可以給顧客提供觀賞的環境，這樣即可創
造顧客購買計劃之外的購物機會，又能使顧客享受到購物之外的快樂，這類布局導致使用面積的利用率偏低，適用於面積較大的花店。這類布局如果搞的不好，會給
人留下布局混亂不清的印象，同時，投入費用較高，影響花卉整體價格水平。從經營的角度看，搞好完全生產和清潔衛生的難度也較大。

⑶ 物流信息技術需求分析有哪些方法 A自頂向下B規劃的方法C全面與重點結合D先分析後改進 多選題

動態規劃的特點及其應用安徽張辰【關鍵詞】動態規劃階段【摘要】動態規劃是信息學競賽中的常見演算法，本文的主要內容就是分析它的特點。文章的第一部分首先探究了動態規劃的本質，因為動態規劃的特點是由它的本質所決定的。第二部分從動態規劃的設計和實現這兩個角度分析了動態規劃的多樣性、模式性、技巧性這三個特點。第三部分將動態規劃和遞推、搜索、網路流這三個相關演算法作了比較，從中探尋動態規劃的一些更深層次的特點。文章在分析動態規劃的特點的同時，還根據這些特點分析了我們在解題中應該怎樣利用這些特點，怎樣運用動態規劃。這對我們的解題實踐有一定的指導意義。【正文】動態規劃是編程解題的一種重要的手段，在如今的信息學競賽中被應用得越來越普遍。最近幾年的信息學競賽，不分大小，幾乎每次都要考察到這方面的內容。因此，如何更深入地了解動態規劃，從而更為有效地運用這個解題的有力武器，是一個值得深入研究的問題。要掌握動態規劃的應用技巧，就要了解它的各方面的特點。首要的，是要深入洞悉動態規劃的本質。§1動態規劃的本質動態規劃是在本世紀50年代初，為了解決一類多階段決策問題而誕生的。那麼，什麼樣的問題被稱作多階段決策問題呢？§1.1多階段決策問題說到多階段決策問題，人們很容易舉出下面這個例子。[例1]多段圖中的最短路徑問題：在下圖中找出從A1到D1的最短路徑。仔細觀察這個圖不難發現，它有一個特點。我們將圖中的點分為四類（圖中的A、B、C、D），那麼圖中所有的邊都處於相鄰的兩類點之間，並且都從前一類點指向後一類點。這樣，圖中的邊就被分成了三類（AàB、BàC、CàD）。我們需要從每一類中選出一條邊來，組成從A1到D1的一條路徑，並且這條路徑是所有這樣的路徑中的最短者。從上面的這個例子中，我們可以大概地了解到什麼是多階段決策問題。更精確的定義如下：多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列[1]。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。從上述的定義中，我們可以明顯地看出，這類問題有兩個要素。一個是階段，一個是決策。§1.2階段與狀態階段：將所給問題的過程，按時間或空間特徵分解成若干相互聯系的階段，以便按次序去求每階段的解。常用字母k表示階段變數。[1]階段是問題的屬性。多階段決策問題中通常存在著若干個階段，如上面的例子，就有A、B、C、D這四個階段。在一般情況下，階段是和時間有關的；但是在很多問題（我的感覺，特別是信息學問題）中，階段和時間是無關的。從階段的定義中，可以看出階段的兩個特點，一是「相互聯系」，二是「次序」。階段之間是怎樣相互聯系的？就是通過狀態和狀態轉移。狀態：各階段開始時的客觀條件叫做狀態。描述各階段狀態的變數稱為狀態變數，常用sk表示第k階段的狀態變數，狀態變數sk的取值集合稱為狀態集合，用Sk表示。[1]狀態是階段的屬性。每個階段通常包含若干個狀態，用以描述問題發展到這個階段時所處在的一種客觀情況。在上面的例子中，行人從出發點A1走過兩個階段之後，可能出現的情況有三種，即處於C1、C2或C3點。那麼第三個階段就有三個狀態S3={C1,C2,C3}。每個階段的狀態都是由以前階段的狀態以某種方式「變化」而來，這種「變化」稱為狀態轉移（暫不定義）。上例中C3點可以從B1點過來，也可以從B2點過來，從階段2的B1或B2狀態走到階段3的C3狀態就是狀態轉移。狀態轉移是導出狀態的途徑，也是聯系各階段的途徑。說到這里，可以提出應用動態規劃的一個重要條件。那就是將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的發展，而只能通過當前的這個狀態。換句話說，每個狀態都是「過去歷史的一個完整總結[1]」。這就是無後效性。對這個性質，下文還將會有解釋。§1.3決策和策略上面的階段與狀態只是多階段決策問題的一個方面的要素，下面是另一個方面的要素——決策。決策：當各段的狀態取定以後，就可以做出不同的決定，從而確定下一階段的狀態，這種決定稱為決策。表示決策的變數，稱為決策變數，常用uk(sk)表示第k階段當狀態為sk時的決策變數。在實際問題中，決策變數的取值往往限制在一定范圍內，我們稱此范圍為允許決策集合。常用Dk(sk)表示第k階段從狀態sk出發的允許決策集合。顯然有uk(sk)?Dk(sk)。[1]決策是問題的解的屬性。決策的目的就是「確定下一階段的狀態」，還是回到上例，從階段2的B1狀態出發有三條路，也就是三個決策，分別導向階段3的C1、C2、C3三個狀態，即D2(B1)={C1,C2,C3}。有了決策，我們可以定義狀態轉移：動態規劃中本階段的狀態往往是上一階段和上一階段的決策結果，由第k段的狀態sk和本階段的決策uk確定第k+1段的狀態sk+1的過程叫狀態轉移。狀態轉移規律的形式化表示sk+1=Tk(sk,uk)稱為狀態轉移方程。這樣看來，似乎決策和狀態轉移有著某種聯系。我的理解，狀態轉移是決策的目的，決策是狀態轉移的途徑。各段決策確定後，整個問題的決策序列就構成一個策略，用p1,n={u1(s1),u2(s2),…,un(sn)}表示。對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作P1,n，使整個問題達到最有效果的策略就是最優策略。[1]說到這里，又可以提出運用動態規劃的一個前提。即這個過程的最優策略應具有這樣的性質：無論初始狀態及初始決策如何，對於先前決策所形成的狀態而言，其以後的所有決策應構成最優策略[1]。這就是最優化原理。簡言之，就是「最優策略的子策略也是最優策略」。§1.4最優化原理與無後效性這里，我把最優化原理定位在「運用動態規劃的前提」。這是因為，是否符合最優化原理是一個問題的本質特徵。對於不滿足最優化原理的一個多階段決策問題，整體上的最優策略p1,n同任何一個階段k上的決策uk或任何一組階段k1…k2上的子策略pk1,k2都不存在任何關系。如果要對這樣的問題動態規劃的話，我們從一開始所作的劃分階段等努力都將是徒勞的。而我把無後效性定位在「應用動態規劃的條件」，是因為動態規劃是按次序去求每階段的解，如果一個問題有後效性，那麼這樣的次序便是不合理的。但是，我們可以通過重新劃分階段，重新選定狀態，或者增加狀態變數的個數等手段，來是問題滿足無後效性這個條件。說到底，還是要確定一個「序」。在信息學的多階段決策問題中，絕大部分都是能夠滿足最優化原理的，但它們往往會在後效性這一點上來設置障礙。所以在解題過程中，我們會特別關心「序」。對於有序的問題，就會考慮到動態規劃；對於無序的問題，也會想方設法來使其有序。§1.5最優指標函數和規劃方程最優指標函數：用於衡量所選定策略優劣的數量指標稱為指標函數，最優指標函數記為fk(sk)，它表示從第k段狀態sk採用最優策略p*k,n到過程終止時的最佳效益值[1]。最優指標函數其實就是我們真正關心的問題的解。在上面的例子中，f2(B1)就表示從B1點到終點D1點的最短路徑長度。我們求解的最終目標就是f1(A1)。最優指標函數的求法一般是一個從目標狀態出發的遞推公式，稱為規劃方程：其中sk是第k段的某個狀態，uk是從sk出發的允許決策集合Dk(sk)中的一個決策，Tk(sk,uk)是由sk和uk所導出的第k+1段的某個狀態sk+1，g(x,uk)是定義在數值x和決策uk上的一個函數，而函數opt表示最優化，根據具體問題分別表為max或min。，稱為邊界條件。上例中的規劃方程就是：邊界條件為這里是一種從目標狀態往回推的逆序求法，適用於目標狀態確定的問題。在我們的信息學問題中，也有很多有著確定的初始狀態。當然，對於初始狀態確定的問題，我們也可以採用從初始狀態出發往前推的順序求法。事實上，這種方法對我們來說要更為直觀、更易設計一些，從而地出現在我們的解題過程中。我們本節所討論的這些理論雖然不是本文的主旨，但是卻對下面要說的動態規劃的特點起著基礎性的作用。§2動態規劃的設計與實現上面我們討論了動態規劃的一些理論，本節我們將通過幾個例子中，動態規劃的設計與實現，來了解動態規劃的一些特點。§2.1動態規劃的多樣性[例2]花店櫥窗布置問題（IOI99）試題見附錄本題雖然是本屆IOI中較為簡單的一題，但其中大有文章可作。說它簡單，是因為它有序，因此我們一眼便可看出這題應該用動態規劃來解決。但是，如何動態規劃呢？如何劃分階段，又如何選擇狀態呢？以花束的數目來劃分階段。在這里，階段變數k表示的就是要布置的花束數目（前k束花），狀態變數sk表示第k束花所在的花瓶。而對於每一個狀態sk，決策就是第k-1束花應該放在哪個花瓶，用uk表示。最優指標函數fk(sk)表示前k束花，其中第k束插在第sk個花瓶中，所能取得的最大美學值。狀態轉移方程為規劃方程為（其中A(i,j)是花束i插在花瓶j中的美學值）邊界條件（V是花瓶總數，事實上這是一個虛擬的邊界）以花瓶的數目來劃分階段。在這里階段變數k表示的是要佔用的花瓶數目（前k個花瓶），狀態變數sk表示前k個花瓶中放了多少花。而對於任意一個狀態sk，決策就是第sk束花是否放在第k個花瓶中，用變數uk=1或0來表示。最優指標函數fk(sk)表示前k個花瓶中插了sk束花，所能取得的最大美學值。狀態轉移方程為規劃方程為邊界條件為兩種劃分階段的方法，引出了兩種狀態表示法，兩種規劃方式，但是卻都成功地解決了問題。只不過因為決策的選擇有多有少，所以演算法的時間復雜度也就不同。[2]這個例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規劃方法。有時各種方法所產生的效果是差不多的，但的時候，就像我們的例子一樣，兩種方法會在某個方面有些區別。所以，在用動態規劃解題的時候，可以多想一想是否有其它的解法。對於不同的解法，要注意比較，好的演算法好在哪裡，差一點的演算法差在哪裡。從各種不同演算法的比較中，我們可以更深刻地領會動態規劃的構思技巧。§2.2動態規劃的模式性這個可能做過動態規劃的人都有體會，從我們上面對動態規劃的分析也可以看出來。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的，否則問題就無法求解。選擇狀態：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。確定決策並寫出狀態轉移方程：之所以把這兩步放在一起，是因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以，如果我們確定了決策，狀態轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態之間的關系來確定決策。寫出規劃方程（包括邊界條件）：在第一部分中，我們已經給出了規劃方程的通用形式化表達式。一般說來，只要階段、狀態、決策和狀態轉移確定了，這一步還是比較簡單的。動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。大體上的框架如下：對f1(s1)初始化（邊界條件）fork?2ton（這里以順序求解為例）對每一個sk?Skfk(sk)?一個極值（∞或－∞）對每一個uk(sk)?Dk(sk)sk-1?Tk(sk,uk)t?g(fk-1(sk-1),uk)yt比fk(sk)更優nfk(sk)?t輸出fn(sn)這個N-S圖雖然不能代表全部，但足可以概括大多數。少數的一些特殊的動態規劃，其實現的原理也是類似，可以類比出來。我們到現在對動態規劃的分析，主要是在理論上、設計上，原因也就在此。掌握了動態規劃的模式性，我們在用動態規劃解題時就可以把主要的精力放在理論上的設計。一旦設計成熟，問題也就基本上解決了。而且在設計演算法時也可以按部就班地來。但是「物極必反」，太過拘泥於模式就會限制我們的思維，扼殺優良演算法思想的產生。我們在解題時，不妨發揮一下創造性，去突破動態規劃的實現模式，這樣往往會收到意想不到的效果。[3]§2.3動態規劃的技巧性上面我們所說的動態規劃的模式性，主要指的是實現方面。而在設計方面，雖然它較為嚴格的步驟性，但是它的設計思想卻是沒有一定的規律可循的。這就需要我們不斷地在實踐當中去掌握動態規劃的技巧，下面僅就一個例子談一點我自己的體會。[例3]街道問題：在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。這是一道簡單而又典型的動態規劃題，許多介紹動態規劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的：按照圖中的虛線來劃分階段，即階段變數k表示走過的步數，而狀態變數sk表示當前處於這一階段上的哪一點（各點所對應的階段和狀態已經用ks在地圖上標明）。這時的模型實際上已經轉化成了一個特殊的多段圖。用決策變數uk=0表示向右走，uk=1表示向上走，則狀態轉移方程如下：（這里的row是地圖豎直方向的行數）我們看到，這個狀態轉移方程需要根據k的取值分兩種情況討論，顯得非常麻煩。相應的，把它代入規劃方程而付諸實現時，演算法也很繁。因而我們在實現時，一般是不會這么做的，而代之以下面方法：將地圖中的點規則地編號如上，得到的規劃方程如下：（這里Distance表示相鄰兩點間的邊長）這樣做確實要比上面的方法簡單多了，但是它已經破壞了動態規劃的本來面目，而不存在明確的階段特徵了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分階段的話，那麼它的「狀態轉移」就不全是在兩個階段之間進行的了。也許這沒什麼大不了的，因為實踐比理論更有說服力。但是，如果我們把題目擴展一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，並且要求兩條路徑的總長度最短。這時，再用這種「簡單」的方法就不太好了。如果非得套用這種方法的話，則最優指標函數就需要有四維的下標，並且難以處理兩條路徑「不能重疊」的問題。而我們回到原先「標准」的動態規劃法，就會發現這個問題很好解決，只需要加一維狀態變數就成了。即用sk=(ak,bk)分別表示兩條路徑走到階段k時所處的位置，相應的，決策變數也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方向。狀態轉移時將兩條路徑分別考慮：在寫規劃方程時，只要對兩條路徑走到同一個點的情況稍微處理一下，減少可選的決策個數：從這個例子中可以總結出設計動態規劃演算法的一個技巧：狀態轉移一般是在相鄰的兩個階段之間（有時也可以在不相鄰的兩個階段間），但是盡量不要在同一個階段內進行。動態規劃是一種很靈活的解題方法，在動態規劃演算法的設計中，類似的技巧還有很多。要掌握動態規劃的技巧，有兩條途徑：一是要深刻理解動態規劃的本質，這也是我們為什麼一開始就探討它的本質的原因；二是要多實踐，不但要多解題，還要學會從解題中探尋規律，總結技巧。§3動態規劃與一些演算法的比較動態規劃作為諸多解題方法中的一種，必然和其他一些演算法有著諸多聯系。從這些聯系中，我們也可以看出動態規劃的一些特點。§3.1動態規劃與遞推——動態規劃是最優化演算法由於動態規劃的「名氣」如此之大，以至於很多人甚至一些資料書上都往往把一種與動態規劃十分相似的演算法，當作是動態規劃。這種演算法就是遞推。實際上，這兩種演算法還是很容易區分的。按解題的目標來分，信息學試題主要分四類：判定性問題、構造性問題、計數問題和最優化問題。我們在競賽中碰到的大多是最優化問題，而動態規劃正是解決最優化問題的有力武器，因此動態規劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態規劃在這兩個方面的聯系。[例4]mod4最優路徑問題：在下圖中找出從第1點到第4點的一條路徑，要求路徑長度mod4的余數最小。這個圖是一個多段圖，而且是一個特殊的多段圖。雖然這個圖的形式比一般的多段圖要簡單，但是這個最優路徑問題卻不能用動態規劃來做。因為一條從第1點到第4點的最優路徑，在它走到第2點、第3點時，路徑長度mod4的余數不一定是最小，也就是說最優策略的子策略不一定最優——這個問題不滿足最優化原理。但是我們可以把它轉換成判定性問題，用遞推法來解決。判斷從第1點到第k點的長度mod4為sk的路徑是否存在，用fk(sk)來表示，則遞推公式如下：（邊界條件）（這里lenk,i表示從第k-1點到第k點之間的第i條邊的長度，方括弧表示「或(or)」運算）最後的結果就是可以使f4(s4)值為真的最小的s4值。這個遞推法的遞推公式和動態規劃的規劃方程非常相似，我們在這里借用了動態規劃的符號也就是為了更清楚地顯示這一點。其實它們的思想也是非常相像的，可以說是遞推法借用了動態規劃的思想解決了動態規劃不能解決的問題。有的多階段決策問題（像這一題的階段特徵就很明顯），由於不能滿足最優化原理等使用動態規劃的先決條件，而無法應用動態規劃。在這時可以將最優指標函數的值當作「狀態」放到下標中去，從而變最優化問題為判定性問題，再借用動態規劃的思想，用遞推法來解決問題。§3.2動態規劃與搜索——動態規劃是高效率、高消費演算法同樣是解決最優化問題，有的題目我們採用動態規劃，而有的題目我們則需要用搜索。這其中有沒有什麼規則呢？我們知道，撇開時空效率的因素不談，在解決最優化問題的演算法中，搜索可以說是「萬能」的。所以動態規劃可以解決的問題，搜索也一定可以解決。把一個動態規劃演算法改寫成搜索是非常方便的，狀態轉移方程、規劃方程以及邊界條件都可以直接「移植」，所不同的只是求解順序。動態規劃是自底向上的遞推求解，而搜索則是自頂向下的遞歸求解（這里指深度搜索，寬度搜索類似）。反過來，我們也可以把搜索演算法改寫成動態規劃。狀態空間搜索實際上是對隱式圖中的點進行枚舉，這種枚舉是自頂向下的。如果把枚舉的順序反過來，變成自底向上，那麼就成了動態規劃。（當然這里有個條件，即隱式圖中的點是可排序的，詳見下一節。）正因為動態規劃和搜索有著求解順序上的不同，這也造成了它們時間效率上的差別。在搜索中，往往會出現下面的情況：對於上圖(a)這樣幾個狀態構成的一個隱式圖，用搜索演算法就會出現重復，如上圖(b)所示，狀態C2被搜索了兩次。在深度搜索中，這樣的重復會引起以C2為根整個的整個子搜索樹的重復搜索；在寬度搜索中，雖然這樣的重復可以立即被排除，但是其時間代價也是不小的。而動態規劃就沒有這個問題，如上圖(c)所示。一般說來，動態規劃演算法在時間效率上的優勢是搜索無法比擬的。（當然對於某些題目，根本不會出現狀態的重復，這樣搜索和動態規劃的速度就沒有差別了。）而從理論上講，任何拓撲有序（現實中這個條件常常可以滿足）的隱式圖中的搜索演算法都可以改寫成動態規劃。但事實上，在很多情況下我們仍然不得不採用搜索演算法。那麼，動態規劃演算法在實現上還有什麼障礙嗎？考慮上圖(a)所示的隱式圖，其中存在兩個從初始狀態無法達到的狀態。在搜索演算法中，這樣的兩個狀態就不被考慮了，如上圖(b)所示。但是動態規劃由於是自底向上求解，所以就無法估計到這一點，因而遍歷了全部的狀態，如上圖(c)所示。一般說來，動態規劃總要遍歷所有的狀態，而搜索可以排除一些無效狀態。更重要的事搜索還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。如何協調好動態規劃的高效率與高消費之間的矛盾呢？有一種折衷的法就是記憶化演算法。記憶化演算法在求解的時候還是按著自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，以後再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜索和動態規劃兩方面的優點，因而還是很有實用價值的。§3.3動態規劃與網路流——動態規劃是易設計易實現演算法由於圖的關系復雜而無序，一般難以呈現階段特徵（除了特殊的圖如多段圖，或特殊的分段方法如Floyd），因此動態規劃在圖論中的應用不多。但有一類圖，它的點卻是有序的，這就是有向無環圖。在有向無環圖中，我們可以對點進行拓撲排序，使其體現出有序的特徵，從而據此劃分階段。在有向無還圖中求最短路徑的演算法[4]，已經體現出了簡單的動態規劃思想。但動態規劃在圖論中還有更有價值的應用。下面先看一個例子。[例6]N個人的街道問題：在街道問題（參見例3）中，若有N個人要從左下角走向右上角，要求他們走過的邊的總長度最大。當然，這里每個人也只能向右或向上走。下面是一個樣例，左圖是從出發地到目的地的三條路徑，右圖是他們所走過的邊，這些邊的總長度為5+4+3+6+3+3+5+8+8+7+4+5+9+5+3=78（不一定是最大）。這個題目是對街道問題的又一次擴展。仿照街道問題的解題方法，我們仍然可以用動態規劃來解決本題。不過這一次是N個人同時走，狀態變數也就需要用N維來表示，。相應的，決策變數也要變成N維，uk=(uk,1,uk,2,…,uk,N)。狀態轉移方程不需要做什麼改動：在寫規劃方程時，需要注意在第k階段，N條路徑所走過的邊的總長度的計算，在這里我就用gk(sk,uk)來表示了：邊界條件為可見將原來的動態規劃演算法移植到這個問題上來，在理論上還是完全可行的。但是，現在的這個動態規劃演算法的時空復雜度已經是關於N的指數函數，只要N稍微大一點，這個演算法就不可能實現了。下面我們換一個思路，將N條路徑看成是網路中一個流量為N的流，這樣求解的目標就是使這個流的費用最大。但是本題又不同於一般的費用流問題，在每一條邊e上的流費用並不是流量和邊權的乘積，而是用下式計算：為了使經典的費用流演算法適用於本題，我們需要將模型稍微轉化一下：如圖，將每條邊拆成兩條。拆開後一條邊上有權，但是容量限制為1；另一條邊沒有容量限制，但是流過這條邊就不能計算費用了。這樣我們就把問題轉化成了一個標準的最大費用固定流問題。這個演算法可以套用經典的最小費用最大流演算法，在此就不細說了。（參見附錄中的源程序）這個例題是我仿照IOI97的「障礙物探測器」一題[6]編出來的。「障礙物探測器」比這一題要復雜一些，但是基本思想是相似的。類似的題目還有99年冬令營的「迷宮改造」[7]。從這些題目中都可以看到動態規劃和網路流的聯系。推廣到一般情況，任何有向無環圖中的費用流問題在理論上說，都可以用動態規劃來解決。對於流量為N（如果流量不固定，這個N需要事先求出來）的費用流問題，用N維的變數sk=(sk,1,sk,2,…,sk,N)來描述狀態，其中sk,i?V(1￡i￡N)。相應的，決策也用N維的變數uk=(uk,1,uk,2,…,uk,N)來表示，其中uk,i?E(sk,i)(1￡i￡N)，E(v)表示指向v的弧集。則狀態轉移方程可以這樣表示：sk-1,i=uk,i的弧尾結點規劃方程為邊界條件為但是，由於動態規劃演算法是指數級演算法，因而在實現中的局限性很大，僅可用於一些N非常小的題目。然而在競賽解題中，比如上面說到的IOI97以及99冬令營測試時，我們使用動態規劃的傾向性很明顯（「障礙物探測器」中，我們用的是貪心策略，求N=1或N=2時的局部最優解[8]）。這主要有兩個原因：一．雖然網路流有著經典的演算法，但是在競賽中不可能出現經典的問題。如果要運用網路流演算法，則需要經過一番模型轉化，有時這個轉化還是相當困難的。因此在演算法的設計上，靈活巧妙的動態規劃演算法反而要更為簡單一些。二．網路流演算法實現起來很繁，這是被人們公認的。因而在競賽的緊張環境中，實現起來有一定模式的動態規劃演算法又多了一層優勢。正由於動態規劃演算法在設計和實現上的簡便性，所以在N不太大時，也就是在動態規劃可行的情況下，我們還是應該盡量運用動態規劃。§4結語本文的內容比較雜，是我幾年來對動態規劃的參悟理解、心得體會。雖然主要的篇幅講的都是理論，但是根本的目的還是指導實踐。動態規劃，據我認為，是當今信息學競賽中最靈活、也最能體現解題者水平的一類解題方法。本文內容雖多，不能涵蓋動態規劃之萬一。「紙上得來終覺淺，絕知此事要躬行。」要想真正領悟、理解動態規劃的思想，掌握動態規劃的解題技巧，還需要在實踐中不斷地挖掘、探索。實踐得多了，也就能體會到漸入佳境之妙了。動態規劃，演算法之常，運用之妙，存乎一心。

⑷ 幫我講一下 動態規劃

動態規劃的特點及其應用
安徽 張辰

目 錄
(點擊進入)
【關鍵詞】
【摘要】
【正文】
§1動態規劃的本質
§1.1多階段決策問題
§1.2階段與狀態
§1.3決策和策略
§1.4最優化原理與無後效性
§1.5最優指標函數和規劃方程
§2動態規劃的設計與實現
§2.1動態規劃的多樣性
§2.2動態規劃的模式性
§2.3動態規劃的技巧性
§3動態規劃與一些演算法的比較
§3.1動態規劃與遞推
§3.2動態規劃與搜索
§3.3動態規劃與網路流
§4結語
【附錄：部分試題與源程序】
1.「花店櫥窗布置問題」試題
2.「釘子與小球」試題
3.例2「花店櫥窗布置問題」方法1的源程序
4.例2「花店櫥窗布置問題」方法2的源程序
5.例3「街道問題」的擴展
6.例4「mod 4最優路徑問題」的源程序
7.例5「釘子與小球」的源程序
8.例6的源程序,「N個人的街道問題」
【參考文獻】

【關鍵詞】動態規劃 階段
【摘要】
動態規劃是信息學競賽中的常見演算法，本文的主要內容就是分析它的特點。
文章的第一部分首先探究了動態規劃的本質，因為動態規劃的特點是由它的本質所決定的。第二部分從動態規劃的設計和實現這兩個角度分析了動態規劃的多樣性、模式性、技巧性這三個特點。第三部分將動態規劃和遞推、搜索、網路流這三個相關演算法作了比較，從中探尋動態規劃的一些更深層次的特點。
文章在分析動態規劃的特點的同時，還根據這些特點分析了我們在解題中應該怎樣利用這些特點，怎樣運用動態規劃。這對我們的解題實踐有一定的指導意義。
【正文】
動態規劃是編程解題的一種重要的手段，在如今的信息學競賽中被應用得越來越普遍。最近幾年的信息學競賽，不分大小，幾乎每次都要考察到這方面的內容。因此，如何更深入地了解動態規劃，從而更為有效地運用這個解題的有力武器，是一個值得深入研究的問題。
要掌握動態規劃的應用技巧，就要了解它的各方面的特點。首要的，是要深入洞悉動態規劃的本質。
§1動態規劃的本質
動態規劃是在本世紀50年代初，為了解決一類多階段決策問題而誕生的。那麼，什麼樣的問題被稱作多階段決策問題呢？
§1.1多階段決策問題
說到多階段決策問題，人們很容易舉出下面這個例子。
[例1] 多段圖中的最短路徑問題：在下圖中找出從A1到D1的最短路徑。
仔細觀察這個圖不難發現，它有一個特點。我們將圖中的點分為四類（圖中的A、B、C、D），那麼圖中所有的邊都處於相鄰的兩類點之間，並且都從前一類點指向後一類點。這樣，圖中的邊就被分成了三類（AB、BC、CD）。我們需要從每一類中選出一條邊來，組成從A1到D1的一條路徑，並且這條路徑是所有這樣的路徑中的最短者。
從上面的這個例子中，我們可以大概地了解到什麼是多階段決策問題。更精確的定義如下：
多階段決策過程，是指這樣的一類特殊的活動過程，問題可以按時間順序分解成若干相互聯系的階段，在每一個階段都要做出決策，全部過程的決策是一個決策序列[1]。要使整個活動的總體效果達到最優的問題，稱為多階段決策問題。
從上述的定義中，我們可以明顯地看出，這類問題有兩個要素。一個是階段，一個是決策。
§1.2階段與狀態
階段：將所給問題的過程，按時間或空間特徵分解成若干相互聯系的階段，以便按次序去求每階段的解。常用字母k表示階段變數。[1]
階段是問題的屬性。多階段決策問題中通常存在著若干個階段，如上面的例子，就有A、B、C、D這四個階段。在一般情況下，階段是和時間有關的；但是在很多問題（我的感覺，特別是信息學問題）中，階段和時間是無關的。從階段的定義中，可以看出階段的兩個特點，一是「相互聯系」，二是「次序」。
階段之間是怎樣相互聯系的？就是通過狀態和狀態轉移。
狀態：各階段開始時的客觀條件叫做狀態。描述各階段狀態的變數稱為狀態變數，常用sk表示第k階段的狀態變數，狀態變數sk的取值集合稱為狀態集合，用Sk表示。[1]
狀態是階段的屬性。每個階段通常包含若干個狀態，用以描述問題發展到這個階段時所處在的一種客觀情況。在上面的例子中，行人從出發點A1走過兩個階段之後，可能出現的情況有三種，即處於C1、C2或C3點。那麼第三個階段就有三個狀態S3={C1,C2,C3}。
每個階段的狀態都是由以前階段的狀態以某種方式「變化」而來，這種「變化」稱為狀態轉移（暫不定義）。上例中C3點可以從B1點過來，也可以從B2點過來，從階段2的B1或B2狀態走到階段3的C3狀態就是狀態轉移。狀態轉移是導出狀態的途徑，也是聯系各階段的途徑。
說到這里，可以提出應用動態規劃的一個重要條件。那就是將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的發展，而只能通過當前的這個狀態。換句話說，每個狀態都是「過去歷史的一個完整總結[1]」。這就是無後效性。對這個性質，下文還將會有解釋。
§1.3決策和策略
上面的階段與狀態只是多階段決策問題的一個方面的要素，下面是另一個方面的要素——決策。
決策：當各段的狀態取定以後，就可以做出不同的決定，從而確定下一階段的狀態，這種決定稱為決策。表示決策的變數，稱為決策變數，常用uk(sk)表示第k階段當狀態為sk時的決策變數。在實際問題中，決策變數的取值往往限制在一定范圍內，我們稱此范圍為允許決策集合。常用Dk(sk)表示第k階段從狀態sk出發的允許決策集合。顯然有uk(sk) Dk(sk)。[1]
決策是問題的解的屬性。決策的目的就是「確定下一階段的狀態」，還是回到上例，從階段2的B1狀態出發有三條路，也就是三個決策，分別導向階段3的C1、C2、C3三個狀態，即D2(B1)={C1,C2,C3}。
有了決策，我們可以定義狀態轉移：動態規劃中本階段的狀態往往是上一階段和上一階段的決策結果，由第k段的狀態sk和本階段的決策uk確定第k+1段的狀態sk+1的過程叫狀態轉移。狀態轉移規律的形式化表示sk+1=Tk(sk,uk)稱為狀態轉移方程。
這樣看來，似乎決策和狀態轉移有著某種聯系。我的理解，狀態轉移是決策的目的，決策是狀態轉移的途徑。
各段決策確定後，整個問題的決策序列就構成一個策略，用p1,n={u1(s1),u2(s2),…, un(sn)}表示。對每個實際問題，可供選擇的策略有一定范圍，稱為允許策略集合，記作P1,n，使整個問題達到最有效果的策略就是最優策略。[1]
說到這里，又可以提出運用動態規劃的一個前提。即這個過程的最優策略應具有這樣的性質：無論初始狀態及初始決策如何，對於先前決策所形成的狀態而言，其以後的所有決策應構成最優策略[1]。這就是最優化原理。簡言之，就是「最優策略的子策略也是最優策略」。
§1.4最優化原理與無後效性
這里，我把最優化原理定位在「運用動態規劃的前提」。這是因為，是否符合最優化原理是一個問題的本質特徵。對於不滿足最優化原理的一個多階段決策問題，整體上的最優策略p1,n同任何一個階段k上的決策uk或任何一組階段k1…k2上的子策略pk1,k2都不存在任何關系。如果要對這樣的問題動態規劃的話，我們從一開始所作的劃分階段等努力都將是徒勞的。
而我把無後效性定位在「應用動態規劃的條件」，是因為動態規劃是按次序去求每階段的解，如果一個問題有後效性，那麼這樣的次序便是不合理的。但是，我們可以通過重新劃分階段，重新選定狀態，或者增加狀態變數的個數等手段，來是問題滿足無後效性這個條件。說到底，還是要確定一個「序」。
在信息學的多階段決策問題中，絕大部分都是能夠滿足最優化原理的，但它們往往會在後效性這一點上來設置障礙。所以在解題過程中，我們會特別關心「序」。對於有序的問題，就會考慮到動態規劃；對於無序的問題，也會想方設法來使其有序。
§1.5最優指標函數和規劃方程
最優指標函數：用於衡量所選定策略優劣的數量指標稱為指標函數，最優指標函數記為fk(sk)，它表示從第k段狀態sk採用最優策略p*k,n到過程終止時的最佳效益值[1]。
最優指標函數其實就是我們真正關心的問題的解。在上面的例子中，f2(B1)就表示從B1點到終點D1點的最短路徑長度。我們求解的最終目標就是f1(A1)。
最優指標函數的求法一般是一個從目標狀態出發的遞推公式，稱為規劃方程：

其中sk是第k段的某個狀態，uk是從sk出發的允許決策集合Dk(sk)中的一個決策，Tk(sk,uk)是由sk和uk所導出的第k+1段的某個狀態sk+1，g(x,uk)是定義在數值x和決策uk上的一個函數，而函數opt表示最優化，根據具體問題分別表為max或min。
，稱為邊界條件。
上例中的規劃方程就是：

邊界條件為
這里是一種從目標狀態往回推的逆序求法，適用於目標狀態確定的問題。在我們的信息學問題中，也有很多有著確定的初始狀態。當然，對於初始狀態確定的問題，我們也可以採用從初始狀態出發往前推的順序求法。事實上，這種方法對我們來說要更為直觀、更易設計一些，從而更多地出現在我們的解題過程中。
我們本節所討論的這些理論雖然不是本文的主旨，但是卻對下面要說的動態規劃的特點起著基礎性的作用。
§2動態規劃的設計與實現
上面我們討論了動態規劃的一些理論，本節我們將通過幾個例子中，動態規劃的設計與實現，來了解動態規劃的一些特點。
§2.1動態規劃的多樣性
[例2] 花店櫥窗布置問題（IOI99）試題見附錄
本題雖然是本屆IOI中較為簡單的一題，但其中大有文章可作。說它簡單，是因為它有序，因此我們一眼便可看出這題應該用動態規劃來解決。但是，如何動態規劃呢？如何劃分階段，又如何選擇狀態呢？
<方法1>以花束的數目來劃分階段。在這里，階段變數k表示的就是要布置的花束數目（前k束花），狀態變數sk表示第k束花所在的花瓶。而對於每一個狀態sk，決策就是第k-1束花應該放在哪個花瓶，用uk表示。最優指標函數fk(sk)表示前k束花，其中第k束插在第sk個花瓶中，所能取得的最大美學值。
狀態轉移方程為
規劃方程為
（其中A(i,j)是花束i插在花瓶j中的美學值）
邊界條件 （V是花瓶總數，事實上這是一個虛擬的邊界）
<方法2>以花瓶的數目來劃分階段。在這里階段變數k表示的是要佔用的花瓶數目（前k個花瓶），狀態變數sk表示前k個花瓶中放了多少花。而對於任意一個狀態sk，決策就是第sk束花是否放在第k個花瓶中，用變數uk=1或0來表示。最優指標函數fk(sk)表示前k個花瓶中插了sk束花，所能取得的最大美學值。
狀態轉移方程為
規劃方程為
邊界條件為
兩種劃分階段的方法，引出了兩種狀態表示法，兩種規劃方式，但是卻都成功地解決了問題。只不過因為決策的選擇有多有少，所以演算法的時間復雜度也就不同。[2]
這個例子具有很大的普遍性。有很多的多階段決策問題都有著不止一種的階段劃分方法，因而往往就有不止一種的規劃方法。有時各種方法所產生的效果是差不多的，但更多的時候，就像我們的例子一樣，兩種方法會在某個方面有些區別。
所以，在用動態規劃解題的時候，可以多想一想是否有其它的解法。對於不同的解法，要注意比較，好的演算法好在哪裡，差一點的演算法差在哪裡。從各種不同演算法的比較中，我們可以更深刻地領會動態規劃的構思技巧。
§2.2動態規劃的模式性
這個可能做過動態規劃的人都有體會，從我們上面對動態規劃的分析也可以看出來。動態規劃的設計都有著一定的模式，一般要經歷以下幾個步驟。
劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的，否則問題就無法求解。
選擇狀態：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
確定決策並寫出狀態轉移方程：之所以把這兩步放在一起，是因為決策和狀態轉移有著天然的聯系，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以，如果我們確定了決策，狀態轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態之間的關系來確定決策。
寫出規劃方程（包括邊界條件）：在第一部分中，我們已經給出了規劃方程的通用形式化表達式。一般說來，只要階段、狀態、決策和狀態轉移確定了，這一步還是比較簡單的。
動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。大體上的框架如下：
對f1(s1)初始化（邊界條件）
for k2 to n（這里以順序求解為例）
對每一個skSk
fk(sk)一個極值（∞或－∞）
對每一個uk(sk)Dk(sk)
sk-1Tk(sk,uk)
tg(fk-1(sk-1),uk)
y t比fk(sk)更優 n
fk(sk)t
輸出fn(sn)
這個N-S圖雖然不能代表全部，但足可以概括大多數。少數的一些特殊的動態規劃，其實現的原理也是類似，可以類比出來。我們到現在對動態規劃的分析，主要是在理論上、設計上，原因也就在此。
掌握了動態規劃的模式性，我們在用動態規劃解題時就可以把主要的精力放在理論上的設計。一旦設計成熟，問題也就基本上解決了。而且在設計演算法時也可以按部就班地來。
但是「物極必反」，太過拘泥於模式就會限制我們的思維，扼殺優良演算法思想的產生。我們在解題時，不妨發揮一下創造性，去突破動態規劃的實現模式，這樣往往會收到意想不到的效果。[3]
§2.3動態規劃的技巧性
上面我們所說的動態規劃的模式性，主要指的是實現方面。而在設計方面，雖然它較為嚴格的步驟性，但是它的設計思想卻是沒有一定的規律可循的。這就需要我們不斷地在實踐當中去掌握動態規劃的技巧，下面僅就一個例子談一點我自己的體會。
[例3] 街道問題：在下圖中找出從左下角到右上角的最短路徑，每步只能向右方或上方走。
這是一道簡單而又典型的動態規劃題，許多介紹動態規劃的書與文章中都拿它來做例子。通常，書上的解答是這樣的：

按照圖中的虛線來劃分階段，即階段變數k表示走過的步數，而狀態變數sk表示當前處於這一階段上的哪一點（各點所對應的階段和狀態已經用ks在地圖上標明）。這時的模型實際上已經轉化成了一個特殊的多段圖。用決策變數uk=0表示向右走，uk=1表示向上走，則狀態轉移方程如下：

（這里的row是地圖豎直方向的行數）
我們看到，這個狀態轉移方程需要根據k的取值分兩種情況討論，顯得非常麻煩。相應的，把它代入規劃方程而付諸實現時，演算法也很繁。因而我們在實現時，一般是不會這么做的，而代之以下面方法：
將地圖中的點規則地編號如上，得到的規劃方程如下：

（這里Distance表示相鄰兩點間的邊長）
這樣做確實要比上面的方法簡單多了，但是它已經破壞了動態規劃的本來面目，而不存在明確的階段特徵了。如果說這種方法是以地圖中的行（A、B、C、D）來劃分階段的話，那麼它的「狀態轉移」就不全是在兩個階段之間進行的了。
也許這沒什麼大不了的，因為實踐比理論更有說服力。但是，如果我們把題目擴展一下：在地圖中找出從左下角到右上角的兩條路徑，兩條路徑中的任何一條邊都不能重疊，並且要求兩條路徑的總長度最短。這時，再用這種「簡單」的方法就不太好辦了。
如果非得套用這種方法的話，則最優指標函數就需要有四維的下標，並且難以處理兩條路徑「不能重疊」的問題。
而我們回到原先「標准」的動態規劃法，就會發現這個問題很好解決，只需要加一維狀態變數就成了。即用sk=(ak,bk)分別表示兩條路徑走到階段k時所處的位置，相應的，決策變數也增加一維，用uk=(xk,yk)分別表示兩條路徑的行走方向。狀態轉移時將兩條路徑分別考慮：

在寫規劃方程時，只要對兩條路徑走到同一個點的情況稍微處理一下，減少可選的決策個數：

從這個例子中可以總結出設計動態規劃演算法的一個技巧：狀態轉移一般是在相鄰的兩個階段之間（有時也可以在不相鄰的兩個階段間），但是盡量不要在同一個階段內進行。
動態規劃是一種很靈活的解題方法，在動態規劃演算法的設計中，類似的技巧還有很多。要掌握動態規劃的技巧，有兩條途徑：一是要深刻理解動態規劃的本質，這也是我們為什麼一開始就探討它的本質的原因；二是要多實踐，不但要多解題，還要學會從解題中探尋規律，總結技巧。
§3動態規劃與一些演算法的比較
動態規劃作為諸多解題方法中的一種，必然和其他一些演算法有著諸多聯系。從這些聯系中，我們也可以看出動態規劃的一些特點。
§3.1動態規劃與遞推
——動態規劃是最優化演算法
由於動態規劃的「名氣」如此之大，以至於很多人甚至一些資料書上都往往把一種與動態規劃十分相似的演算法，當作是動態規劃。這種演算法就是遞推。實際上，這兩種演算法還是很容易區分的。
按解題的目標來分，信息學試題主要分四類：判定性問題、構造性問題、計數問題和最優化問題。我們在競賽中碰到的大多是最優化問題，而動態規劃正是解決最優化問題的有力武器，因此動態規劃在競賽中的地位日益提高。而遞推法在處理判定性問題和計數問題方面也是一把利器。下面分別就兩個例子，談一下遞推法和動態規劃在這兩個方面的聯系。
[例4] mod 4 最優路徑問題：在下圖中找出從第1點到第4點的一條路徑，要求路徑長度mod 4的余數最小。
這個圖是一個多段圖，而且是一個特殊的多段圖。雖然這個圖的形式比一般的多段圖要簡單，但是這個最優路徑問題卻不能用動態規劃來做。因為一條從第1點到第4點的最優路徑，在它走到第2點、第3點時，路徑長度mod 4的余數不一定是最小，也就是說最優策略的子策略不一定最優——這個問題不滿足最優化原理。
但是我們可以把它轉換成判定性問題，用遞推法來解決。判斷從第1點到第k點的長度mod 4為sk的路徑是否存在，用fk(sk)來表示，則遞推公式如下：
（邊界條件）

（這里lenk,i表示從第k-1點到第k點之間的第i條邊的長度，方括弧表示「或(or)」運算）
最後的結果就是可以使f4(s4)值為真的最小的s4值。
這個遞推法的遞推公式和動態規劃的規劃方程非常相似，我們在這里借用了動態規劃的符號也就是為了更清楚地顯示這一點。其實它們的思想也是非常相像的，可以說是遞推法借用了動態規劃的思想解決了動態規劃不能解決的問題。
有的多階段決策問題（像這一題的階段特徵就很明顯），由於不能滿足最優化原理等使用動態規劃的先決條件，而無法應用動態規劃。在這時可以將最優指標函數的值當作「狀態」放到下標中去，從而變最優化問題為判定性問題，再借用動態規劃的思想，用遞推法來解決問題。
[例5] 釘子與小球（NOI99）試題見附錄
這個題目一看就不覺讓人想起一道經典的動態規劃題。下面先讓我們回顧一下這個問題。
數字三角形（IOI94）在下圖中求從頂至低某處的一條路徑，使該路徑所經過的數字的總和最大，每一步只能向左下或右下走。
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
在這個問題中，我們按走過的行數來劃分階段，以走到每一行時所在的位置來作為狀態，決策就是向左下走（用0表示）或向右下走（用1表示）。
狀態轉移方程：
規劃方程：
邊界條件：
這是一個比較簡單的最優化問題，我們還可以把這個問題改成一個更加簡單的整數統計問題：求頂點到每一點的路徑總數。把這個總數用fk(sk)表示，那麼遞推公式就是：

在這里，雖然求和公式只有兩項，但我們仍然用∑的形式表示，就是為了突出這個遞推公式和上面的規劃方程的相似之處。這兩個公式的邊界條件都是一模一樣的。
再回到我們上面的「釘子與小球」問題，這是一個概率統計問題。我們繼續沿用上面的思想，用fk(sk)表示小球落到第k行第sk個釘子上的概率，則遞推公式如下：

（這里函數Existk(sk)表示第k行第sk個釘子是否存在，存在則取1，不存在則取0）
邊界條件
可以看出這個公式較之上面的兩個式子雖然略有變化，但是其基本思想還是類似的。在解這個問題的過程中，我們再次運用了動態規劃的思想。
一般說來，很多最優化問題都有著對應的計數問題；反過來，很多計數問題也有著對應的最優化問題。因此，我們在遇到這兩類問題時，不妨多聯系、多發展，舉一反三，從比較中更深入地理解動態規劃的思想。
其實遞推和動態規劃這兩種方法的思想本來就很相似，也不必說是誰借用了誰的思想。關鍵在於我們要掌握這種思想，這樣我們無論在用動態規劃法解最優化問題，或是在用遞推法解判定型、計數問題時，都能得心應手、游刃有餘了。
§3.2動態規劃與搜索
——動態規劃是高效率、高消費演算法
同樣是解決最優化問題，有的題目我們採用動態規劃，而有的題目我們則需要用搜索。這其中有沒有什麼規則呢？
我們知道，撇開時空效率的因素不談，在解決最優化問題的演算法中，搜索可以說是「萬能」的。所以動態規劃可以解決的問題，搜索也一定可以解決。
把一個動態規劃演算法改寫成搜索是非常方便的，狀態轉移方程、規劃方程以及邊界條件都可以直接「移植」，所不同的只是求解順序。動態規劃是自底向上的遞推求解，而搜索則是自頂向下的遞歸求解（這里指深度搜索，寬度搜索類似）。
反過來，我們也可以把搜索演算法改寫成動態規劃。狀態空間搜索實際上是對隱式圖中的點進行枚舉，這種枚舉是自頂向下的。如果把枚舉的順序反過來，變成自底向上，那麼就成了動態規劃。（當然這里有個條件，即隱式圖中的點是可排序的，詳見下一節。）
正因為動態規劃和搜索有著求解順序上的不同，這也造成了它們時間效率上的差別。在搜索中，往往會出現下面的情況：
對於上圖(a)這樣幾個狀態構成的一個隱式圖，用搜索演算法就會出現重復，如上圖(b)所示，狀態C2被搜索了兩次。在深度搜索中，這樣的重復會引起以C2為根整個的整個子搜索樹的重復搜索；在寬度搜索中，雖然這樣的重復可以立即被排除，但是其時間代價也是不小的。而動態規劃就沒有這個問題，如上圖(c)所示。
一般說來，動態規劃演算法在時間效率上的優勢是搜索無法比擬的。（當然對於某些題目，根本不會出現狀態的重復，這樣搜索和動態規劃的速度就沒有差別了。）而從理論上講，任何拓撲有序（現實中這個條件常常可以滿足）的隱式圖中的搜索演算法都可以改寫成動態規劃。但事實上，在很多情況下我們仍然不得不採用搜索演算法。那麼，動態規劃演算法在實現上還有什麼障礙嗎？
考慮上圖(a)所示的隱式圖，其中存在兩個從初始狀態無法達到的狀態。在搜索演算法中，這樣的兩個狀態就不被考慮了，如上圖(b)所示。但是動態規劃由於是自底向上求解，所以就無法估計到這一點，因而遍歷了全部的狀態，如上圖(c)所示。
一般說來，動態規劃總要遍歷所有的狀態，而搜索可以排除一些無效狀態。更重要的事搜索還可以剪枝，可能剪去大量不必要的狀態，因此在空間開銷上往往比動態規劃要低很多。
如何協調好動態規劃的高效率與高消費之間的矛盾呢？有一種折衷的辦法就是記憶化演算法。記憶化演算法在求解的時候還是按著自頂向下的順序，但是每求解一個狀態，就將它的解保存下來，以後再次遇到這個狀態的時候，就不必重新求解了。這種方法綜合了搜索和動態規劃兩方面的優點，因而還是很有實用價值的。
§3.3動態規劃與網路流
——動態規劃是易設計易實現演算法
由於圖的關系復雜而無序，一般難以呈現階段特徵（除了特殊的圖如多段圖，或特殊的分段方法如Floyd），因此動態規劃在圖論中的應用不多。但有一類圖，它的點卻是有序的，這就是有向無環圖。
在有向無環圖中，我們可以對點進行拓撲排序，使其體現出有序的特徵，從而據此劃分階段。在有向無還圖中求最短路徑的演算法[4]，已經體現出了簡單的動態規劃思想。但動態規劃在圖論中還有更有價值的應用。下面先看一個例子。
[例6] N個人的街道問題：在街道問題（參見例3）中，若有N個人要從左下角走向右上角，要求他們走過的邊的總長度最大。當然，這里每個人也只能向右或向上走。下面是一個樣例，左圖是從出發地到目的地的三條路徑，右圖是他們所走過的邊，這些邊的總長度為5 + 4 + 3 + 6 + 3 + 3 + 5 + 8 + 8 + 7 + 4 + 5 + 9 + 5 + 3 = 78（不一定是最大）。
這個題目是對街道問題的又一次擴展。仿照街道問題的解題方法，我們仍然可以用動態規劃來解決本題。不過這一次是N個人同時走，狀態變數也就需要用N維來表示，。相應的，決策變數也要變成N維，uk=(uk,1,uk,2,…,uk,N)。狀態轉移方程不需要做什麼改動：

在寫規劃方程時，需要注意在第k階段，N條路徑所走過的邊的總長度的計算，在這里我就用gk(sk,uk)來表示了：

邊界條件為
可見將原來的動態規劃演算法移植到這個問題上來，在理論上還是完全可行的。但是，現在的這個動態規劃演算法的時空復雜度已經是關於N的指數函數，只要N稍微大一點，這個演算法就不可能實現了。
下面我們換一個思路，將N條路徑看成是網路中一個流量為N的流，這樣求解的目標就是使這個流的費用最大。但是本題又不同於一般的費用流問題，在每一條邊e上的流費用並不是流量和邊權的乘積 ，而是用下式計算：

為了使經典的費用流演算法適用於本題，我們需要將模型稍微轉化一下：
如圖，將每條邊拆成兩條。拆開後一條邊上有權，但是容量限制為1；另一條邊沒有容量限制，但是流過這條邊就不能計算費用了。這樣我們就把問題轉化成了一個標準的最大費用固定流問題。
這個演算法可以套用經典的最小費用最大流演算法，在此就不細說了。（參見附錄中的源程序）
這個例題是我仿照IOI97的「障礙物探測器」一題[6]編出來的。「障礙物探

⑸ 我開了家花店，可是生意不是很好，能幫我想點注意嗎

位置好嗎？你的櫥窗布置、店裡的陳列、整體的裝修，廣告宣傳做得怎麼樣？

⑹ 鮮花店裝修注意事項

1、門面設計。門面裝飾不需要太過華麗，最重要的是顯示出門店的專溫暖、溫馨，所以在設計的屬時候要貼近自然，不要使用暗色裝飾，做好是使用原生態裝飾，比如是將自己包裝好的花卉放在門口，或者是放一些比較有特色，能夠打動人的標語。
2、燈光設計。燈光在花店的裝修也是必不可少的，精準的燈光能讓花束的美麗展現的淋漓盡致。花店的光線要明亮，以暖色調為主比較適宜。可以選擇可以調節的射燈，對以後烘托不同大小、位置的作品比較方便。
3、布局擺放。花店設計整體要布局好，花草的擺放要有規律，同樣的種類、相同的色系都要擺在一塊，不能給人混亂不清的感覺。
4、注意細節。可以在不同種類花的面前都寫上介紹和種植方法，這樣能增加顧客對花草的了解，對店鋪留下了深刻的印象。就算這次不買下次有需要也會優先考慮的。
5、貨架的利用。另外花店要充分利用好貨架的空間，在貨架最為引人注意最具經濟價值的位置擺放最易售出的花卉品種，也要擺放最受喜愛以及比較潮流趨勢的品種。

⑺ 花店裝修設計需要注意哪些地方

1.一是要體現出花店的特色;二要嚴格控制花店的裝修費用。花店裝修一定要根內據開店構想容
設計和施工，不能馬虎，因為開店一後很難進行更改。在裝修的過程中，應嚴格按照清單采購必要的營業設備，如保險櫃，空調等，並安裝調試。花店裝修和采購營業設備要按照開業計劃實施，不能影響花店正常開業。
2.花店所處位置，招牌設計，櫥窗布置，店堂內部裝修及花卉商品陳列方式等諸多因素都會給顧客不同的印象和感受，影響顧客的購買心理和購買決策的確立與實施。因此，迎合顧客心理。布置出一個優美的購物環境，可以增加銷售量。
3.花店的裝修與內部設計是營造美好的店堂環境所不可缺少的環節。為了保證顧客在愉悅的放鬆的情緒中購物，店內照明要明亮而柔和，內部裝飾的色調要宜人。花店內的裝修要簡潔，色彩以淺色調，明快為主。花店裝飾可通過店內家庭式不止等有創新的構思，獨特的布局，高雅。充滿魅力的藝術氛圍，給人以高品質的文化享受。

⑻ 關於花店設計的要素(希望多講點)

具體情況具體分來析,根據花店的位源置進行分析,比如說,花店設置在水邊的話,可以將花店設計的有點高度,兩層這樣,二層可以選用玻璃材質,可以觀水景;設置在公園的話,要兼顧公園的風格,外觀要具有一定的觀賞性,實用性也很重要的.
暫且說這么多,與樓主共勉!

⑼ 有沒有裝修鮮花店效果的圖片

http://www.f992.com/html/shangjituijian/xinqiqita/20081017/11696.html
http://image..com/i?ct=503316480&z=0&tn=imagedetail&word=%CF%CA%BB%A8%B5%EA%D7%B0%D0%DE&in=30344&cl=2&cm=1&sc=0&lm=-1&pn=0&rn=1&di=166130961&ln=99

⑽ 花店怎麼裝修設計比較好

1、燈光設計
花店燈光設計極為重要，直接影響人們對鮮花的視覺感受。盡量保持室內光線明亮，這樣才能使鮮花耀眼奪目，從而能吸引更多的顧客進行購買。同時，由於花色不同，所適合的燈光顏色也就不同，建議選擇暖色調的燈光，可以有效改善視覺效果。
2、天花板設計
花店內的天花板設計需要重視，天花板設計首先要簡潔大方，不宜有過多的裝飾，否則會讓人感到壓抑。同時，天花板的設計還要考慮空間面積，若是空間有限，建議將天花板設計的低點;若是空間寬敞，可以設計的高點。另外，顏色對於天花板設計也能起到很大的作用，淺色調具有延伸空間視覺效果。
3、牆面設計
牆面作為背景裝飾，裝修設計要考慮鮮花的顏色和種類，盡量保持整體統一。同時，牆面的設計也要與花店內的整體環境保持協調，盡量選擇同一種素凈的顏色進行裝修。
4、貨架設計
花店內少不了貨架，為了使整體環境更加整潔清爽，美觀大方，要重視貨架的設計。首先，貨架的設計要有很強的實用性，可以用來擺放很多花卉。同時，貨架要足夠的牢固穩定，盡量選擇金屬或是木質的架子，以免損壞導致鮮花掉落，損失嚴重。同時，貨架的擺放要合理，方便顧客觀賞和選擇。
5、地面設計
為了避免鮮花枯萎，需要經常給花卉澆水，所以店內地板上難免會有水漬。店內的地面設計有很多講究，盡量選擇防潮性強的材料，如地磚，防潮性較差的木地板則不宜使用。同時，地面要保持平穩，以免導致貨架搖晃，容易使人受傷。另外，為了節省時間，可以選用易清潔的裝修材料。
6、色彩搭配
花店內鮮花有各種各樣的顏色，為了避免讓人眼花繚亂，店內的裝修盡量選擇素雅的顏色，如白色、淺灰色等。當然，若是覺得單調或是素凈，可以使用壁紙進行裝飾。店內的裝修顏色也不宜過於繁雜，既會影響人們對鮮花的觀賞，也會影響整體的裝飾美感。另外，店內的裝修顏色要保持統一，不宜過於花哨，否則會破壞環境的協調性。
7、內部布局
花店內部的布局直接影響人們的選購心情，所以要保持一定的原則。首先，內部設計要具有便利性，不管是收銀台還是貨架擺設都要合理有序，要讓顧客感到輕松便利。其次，要有條理性，鮮花擺放要合理，可以根據花的種類或是顏色進行擺放，這樣才方便顧客選購。
8、花店通道
人們選擇花卉需要進行詳細的挑選，所以一個順暢的通道極為重要，直接影響人們的心情。店內的通道要足夠的寬敞，這樣才方便顧客選購。要注意，不宜採用過於復雜的迂迴式設計，既浪費空間，也不方便。若是店內鮮花品種多樣，可以進行環繞型設計，這樣利於讓顧客挑到自己喜歡的品種。
9、巧用玻璃鏡
花店裝修可以巧用玻璃鏡，在店內擺放一兩面玻璃鏡，既可以增加店內的面積，也可以讓鮮花種類看著更為多樣，利於吸引更多的顧客。而且，玻璃鏡價格實惠，所以對於小空間的花店來說，玻璃鏡是一個不錯的裝修材料。
10、櫥窗設計
櫥窗可以說是一個小型的花店設計，整體的設計直接影響人們對花店的第一印象，所以要格外重視。首先，花店櫥窗要簡潔大方，不宜將所有的產品都堆放進去，這樣只會起到反效果，讓人感到凌亂。其次，櫥窗設計要有明確的主題，如情人節、婚禮、聚會等，針對不同的主題進行不同的設計。同時，櫥窗最好定期更換一次，以免讓人產生視覺疲勞，具體時間可以根據店主的時間和能力。最重要的是，櫥窗需要每天打掃，保持整潔清爽，這樣才能吸引顧客。