遞歸分支定界

2019-11-08 02:26:55

字體：大中小

供稿：網(wǎng)友

遞歸解分支定界問題

標(biāo)簽（空格分隔）：算法學(xué)習(xí)

一、算法描述

線性規(guī)劃是日常常用的算法之一，通過線性規(guī)劃的對偶單純性，可以解決最大流，最短路徑等常見的規(guī)劃問題。但是在TSP問題中，所要求得的解釋選擇或者不選擇當(dāng)前的邊，輸出結(jié)果也就是只有0,1兩種結(jié)果，此種問題也被稱為0,1規(guī)劃。或者當(dāng)我們計(jì)算給每條邊分配怎樣的權(quán)重的時(shí)候，最大最小化代價(jià)函數(shù)問題，也被稱為整數(shù)規(guī)劃的問題。

二、算法描述

(1)求整數(shù)規(guī)劃的松弛問題最優(yōu)解。 (2)若松弛問題的最優(yōu)解滿足整數(shù)要求，得到整數(shù)規(guī)劃的最優(yōu)解，否則轉(zhuǎn)下一步。 (3)任意選一個(gè)非整數(shù)解的變量，在松弛問題中加上約束及+1組成兩個(gè)新的松弛問題，稱為分支。新的松弛問題具有如下特征：當(dāng)原問題是求最大值時(shí)，目標(biāo)值是分支問題的上界；當(dāng)原問題足求最小值時(shí)，目標(biāo)值是分支問題的下界。 (4)檢查所有分支的解及目標(biāo)函數(shù)值，若某分支的解是整數(shù)并且目標(biāo)函數(shù)值大于(max)等于其他分支的目標(biāo)值，則將其他分支剪去不再計(jì)算，若還存在非整數(shù)解并且目標(biāo)值大于(max)整數(shù)解的目標(biāo)值，需要繼續(xù)分支，再檢查，直到得到最優(yōu)解算法的流程圖與說明見下圖所示此處輸入圖片的描述

三、具體代碼以及運(yùn)行實(shí)例

#define _CRT_SECURE_NO_WARNINGS#include<stdio.h>#include<stdlib.h>#include "search_route.h"#include "lp_lib.h"#include<math.h>#define INF 65535#define NaN -65535#define LEFT 1#define RIGHT 2double UB;double* UB_X;int BB_JYLL(lPRec* lp, int lp_length);int IsArrInteger(double*, int);int FindFirstDecimal(double *, int, double&);double RoundDouble(const double);int main(){ lprec *lp; int ret = 0, count, ret_int; int colno[2] = { 1, 2 }; // 未知數(shù)個(gè)數(shù)編號 count = 2; // 未知數(shù)個(gè)數(shù) lp = make_lp(0, count); //double row[3] = { -1, -1, 0 }; // 目標(biāo)函數(shù)系數(shù) //double row_LE[8] = { 14, 9, -6, 3, -1, 0, 0, -1}; // LE 約束系數(shù)左邊 //double B_LE[4]= { 51, 1, 0, 0 }; // LE 約束系數(shù)右邊 //double row[3] = { -5, -8, 0 }; // 目標(biāo)函數(shù)系數(shù) //double row_LE[8] = { 5, 9, 1,1, -1, 0, 0, -1 }; // LE 約束系數(shù)左邊 //double B_LE[4] = { 45, 6, 0, 0 }; // LE 約束系數(shù)右邊 double row[3] = { -3, -2, 0 }; // 目標(biāo)函數(shù)系數(shù) double row_LE[8] = { 2, 3, 1, 0.5, -1, 0, 0, -1 }; // LE 約束系數(shù)左邊 double B_LE[4] = { 14, 4.5, 0, 0 }; // LE 約束系數(shù)右邊 UB_X = new double[count]; // set the objective in lpsolve set_obj_fnex(lp, count, row, colno); //double row_LE[2]; for (int i = 0; i < 4; ++i) { add_constraintex(lp, count, row_LE + i * count, colno, LE, B_LE[i]); } ret_int = BB_JYLL(lp, count); if (ret_int == 0) // 有整數(shù)解 { printf("有整數(shù)解 /n"); for (int i = 0; i < count; i++) { printf("%lf/n", UB_X[i]); } printf("最優(yōu)代價(jià) : %lf /n/n", UB); } else { printf("無解/n"); } delete[] UB_X; return 0;}//==================================================================================================================================================================================================//==================================================================================================================================================================================================//==================================================================================================================================================================================================int BB_JYLL(lprec* lp, int lp_length){ int ret = 0; lprec* lp_hat = NULL; lp_hat = copy_lp(lp); // 線性規(guī)劃松弛條件 ret = solve(lp_hat); if (ret == 0) // LP 有解 { double* x_hat; double y_hat; x_hat = (double *)malloc(lp_length * sizeof(double)); // 獲取 x_hat y_hat get_variables(lp_hat, x_hat); y_hat = get_working_objective(lp_hat); if (y_hat <= UB) // y_hat 在界內(nèi) { if (IsArrInteger(x_hat, lp_length)) // x_hat 為整數(shù) { UB = y_hat; // 存上界為 y_hat memcpy(UB_X, x_hat, lp_length * sizeof(double)); // 存 x_hat return 0; } else // x_hat 為分?jǐn)?shù) { int xk_id; double xk_val; xk_id = FindFirstDecimal(x_hat, lp_length, xk_val); //============================== int* colno; colno = new int[lp_length]; for (int i = 0; i < lp_length; i++) { colno[i] = i + 1; } lprec *lp_l, *lp_r; lp_l = copy_lp(lp_hat); lp_r = copy_lp(lp_hat); int flag_l, flag_r; double* row_LE = NULL; // 新增左側(cè) row_LE = (double*)malloc(lp_length * sizeof(double)); //memset(row_LE, 0, lp_length * sizeof(double)); for (int i = 0; i < lp_length; i++) { row_LE[i] = 0; } printf("/n/n %lf %lf /n/n", xk_val, floor(xk_val)); printf("/n/n %lf /n/n", ceil(xk_val)); row_LE[xk_id] = 1; add_constraintex(lp_l, lp_length, row_LE, colno, LE, double(floor(xk_val))); // 左側(cè)分支 //flag_l = solve(lp_l); flag_l = BB_JYLL(lp_l, lp_length); row_LE[xk_id] = -1; add_constraintex(lp_r, lp_length, row_LE, colno, LE, -ceil(xk_val)); // 右側(cè)分支 flag_r = BB_JYLL(lp_r, lp_length); free(row_LE); delete[] colno; if ((flag_l + flag_r) < 2) // 有解 { return 0; } else // 無解 { return 1; } } } else // y_hat 在界外 { return 1; } } else // LP無解 { return 1; }}static int IsArrInteger(double *arr, int length){ // function : // 檢查一維數(shù)組是否全為整數(shù) // // input : // arr : 被檢測一維數(shù)組 // length : 數(shù)組長度 // // output : // return 1 : 數(shù)組中全為整數(shù) // return 0 : 數(shù)組中不全為整數(shù)，存在分?jǐn)?shù) // // 2016.04.06 // JY double diff = 0; for (int i = 0; i < length; ++i) { diff = fabs(arr[i] - RoundDouble(arr[i])); if (diff >= 0.00001) // 數(shù)組 arr 中存在分?jǐn)?shù) return 0; } return 1; // 數(shù)組 arr 中全為整數(shù)}int FindFirstDecimal(double *arr, int length, double& xk_val){ // function : // 找到數(shù)組 arr 中第一個(gè)小數(shù)位置 // // input : // arr : 被搜索數(shù)組 // // output : // return 小數(shù)位置索引 // 如果返回 -1 ，則代表數(shù)組中無小數(shù) // // 2016.04.06 // JY for (int i = 0; i < length; ++i) { if (fabs((arr[i] - RoundDouble(arr[i]))) >= 0.00001) { xk_val = arr[i]; return i; } } return -1;}double RoundDouble(const double dVal){ // function : // 對單個(gè) double 型變量四舍五入取整 // // input : // dVal : 輸入數(shù)據(jù) // // output : // // 返回 dVal 的四舍五入數(shù)據(jù) // // // 2016.04.05 // JY int res = (int)(dVal)+((int)(10 * dVal) % 10 < 5 ? 0 : 1); return double(res);}

程序說明，此程序時(shí)用來接min整數(shù)規(guī)劃，要求解最大值的時(shí)候，需要設(shè)置下界為全局變量。程序中的線性規(guī)劃的實(shí)現(xiàn)是基于在線開源庫lp_solver http://www.gnu.org/software/glpk/glpk.html $http://www.gnu.org/software/glpk/glpk.html$

以上過程的實(shí)現(xiàn)可以總結(jié)為0,1規(guī)劃問題。0,1規(guī)劃可以用在線開源庫GLPK進(jìn)行實(shí)現(xiàn)

上一篇：常用排序算法小結(jié)

下一篇：【牛腩新聞發(fā)布系統(tǒng)】網(wǎng)頁發(fā)布問題梳理