階石法

階石法是指在數字格中的數字用圓圈圈上，再用虛線從上到下，從左到右把各個圓圈聯繫起來，由圓圈和虛線所組成的圖形很像一個台階，所以這種解運輸問題的方法也叫登石法。

基本介紹

• 中文名：階石法
• 外文名：Step stone method
• 拼音：Jiē shí fǎ
• 別稱：登石法
• 隸屬：數理科學
• 學科：運籌學
• ：

基本概念

運輸問題不僅是最最佳化模型中最為普遍的一類問題而且經常作為某些複雜最最佳化問題(如旅行商問題)的子問題出現，具有極其廣泛的套用。目前各類文獻上針對運輸問題的算法比較多，但是哪種方法對於運輸問題更有效還沒有定論。一般對同一個問題如果有多個算法可以解決時，偏向選擇執時間上界較小的算法。但是實踐中，很多情況下算法中基本操作重複執行的次數隨問題的輸入數據集不同而改變，使得在實用時需根據不同情況選擇適用的算法。算法主要有階石法與元素判別值分配法。

求解實現

階石法算法檢驗數的求解實現是基於行序為主序，通過對執行過程中一次循環時間與循環次數的分析表明，對於m×n= C常數的運輸問題，雖然問題中矩形的長寬比率P加大，使得決定哪一個非基變數進入基中所需時間增加而導致一次單純形疊代所需要的時間增加，但是因為在通常運輸密度條件下，矩形運輸問題所含的未知變數的個數比方型運輸問題少，所以疊代次數明顯減少，算法的執行時間減少。而對於常數的運輸問題，隨著問題中矩形的長寬比率P加大，一次單純形疊代中不僅決定哪一個非基變數要進入基中所需時間增加，而且由於矩形問題比方型問題含有更多的約束方程參數，所以基變數個數增加。則算法定義在基變數上的操作時間增加，使得算法中第三步到第六步的每一個循環時間顯著增加。雖然矩形運輸問題所含的未知變數的個數比方型運輸問題減少，但是不能補償一次循環時間增加而導致的算法整體執行時間增加量，所以階石法算法的執行時間增大。另外階石法實際上是一種特殊的單純形方法，所以從單純形方法的角度分析，在最壞情況下它時間複雜性可能達到指數級。

比較

按照自頂向下逐步求精的原則，在研究運算步驟時，首先考慮算法頂層的運算步驟，然後再考慮底層的運算步驟。頂層的運算步驟是指定義在數據模型級上的運算步驟，或者叫巨觀運算，它們組成算法的主幹部分。表達頂層運算步驟這部分算法的程式就是主程式，其中涉及的數據是數據模型中的一個變數，暫時不關心它的數據結構；涉及的運算以數據模型中的數據變數作為運算對象，或作為運算結果，或二者兼而有之。底層的運算步驟是指頂層抽象的運算的具體實現。它們依賴於數據模型的結構，是頂層運算的細化。頂層算法每個組成步驟可以看作是一個標準子程式模組，每個子程式可以有多個不同的底層算法實現。

限制

用計算機解決一個確定的數學問題，需要設計問題求解的方法即算法設計。這一步要求建立問題的求解模型，確定問題的數據模型並在此模型上定義一組運算。接著藉助於對這組運算的調用和控制，形成算法並用自然語言來表述.然後將非形式自然語言標的算法轉變為一種程式設計語言表達的算法。一般來說，算法的執行效率受3個因素的制約：

1. 算法本身的複雜性。算法的複雜性是算法運行所需要的計算機資源的量，需要的時間資源的量稱作時間複雜性，需要的空間(即存儲器)資源的量稱作空間複雜性。這個量集中反映算法中所採用的方法的效率。
   
2. 數據模型上的運算以數據模型中的數據變數作為運算對象，或者運算結果，或者二者兼而有之。所以數據模型上的運算依賴於數據模型的具體表示。有了數據模型的具體表示，有了數據模型上運算的具體實現，運算的執行效率隨著確定。
   
3. 開發語言和運行環境支持編程框架分為解釋型的編程框架和編譯型的編程框架兩種。後者由於它是編譯後運行的，所以執行效率要比前者高得多。