天天操好逼网,俺去听听婷婷,亭亭五月激情.,直接看黄色电影,中文人妻无码一区二区三区不卡,一级国产欧美成人A片,www.艹,黄片精品午夜福利在线免费观看豆花视频

寫在前面

哈羅大家好~！

想必大家在剛開始學(xué)習(xí)運(yùn)籌學(xué)模型時(shí)，會(huì)覺得有些茫然不知所措吧？比如一大堆神奇的名詞，各種各樣的約束。。。反正我一開始是很懵的狀態(tài)。

那么我們這次帶來一個(gè)比較基礎(chǔ)的帶時(shí)間窗的最短路問題（Shortest Path Problem with Time Windows，簡稱SPPTW），使用一個(gè)基礎(chǔ)的精確算法，即label-setting算法，來求解它。由于參考文獻(xiàn)年代比較久遠(yuǎn)，這種方法現(xiàn)在已經(jīng)有了很大的優(yōu)化。當(dāng)然，只有先從基礎(chǔ)開始，一步步攀登才能不斷解決更困難的問題。（說白了就是小編也還不會(huì)辣么難的問題啦）

話不多說，開始這篇文章吧！

一.? ? ?SPPTW簡介

二.?????Label-setting算法簡介

三. ??? 占優(yōu)剪枝：dominate

四. ?? ?標(biāo)記處理的順序：字典排序

五.? ? ?算法流程與例子

六.? C++源代碼分享

SPPTW簡介

先來簡單介紹要處理的問題。

最短路問題（Shortest Path Problem，簡稱SPP）：

在一個(gè)圖中，每條邊都有與它相關(guān)的數(shù)字，我們將這樣的數(shù)字稱為權(quán)。對下圖G=（N，A）而言，每條邊都只有一個(gè)權(quán)表示花費(fèi)（cost）（可以理解為該邊的長度）。給定起點(diǎn)p，求出p到達(dá)其余各點(diǎn)花費(fèi)最小的路徑。

例如上面這張圖。每條邊上都有一個(gè)權(quán)用來表示花費(fèi)。傳統(tǒng)的最短路問題要求我們求出起點(diǎn)（例如v_0）到其余各點(diǎn)的最小成本的路徑。比如v_0到v_4的最短路徑是v_0→v_2→v_3→v_4，其總花費(fèi)是19；而v_0→v_4這條路徑，總花費(fèi)為30，因此不是v_0到v_4的最短路徑。

?注意，在經(jīng)典的最短路問題中，邊上的權(quán)重一般為正值。

在SPPTW中：

圖中每條邊有兩個(gè)權(quán)重，其中一個(gè)表示消耗的時(shí)間（duration），一個(gè)表示聽過該邊的花費(fèi)（cost）。每個(gè)結(jié)點(diǎn)i都有一個(gè)時(shí)間窗[a_i，b_i]，路徑訪問該節(jié)點(diǎn)時(shí)需要滿足時(shí)間窗約束，即：

如果到達(dá)i點(diǎn)的時(shí)間早于時(shí)間窗開啟的時(shí)間a_i，則需要等待至?xí)r間窗開啟再進(jìn)入；若到達(dá)的時(shí)間超過時(shí)間關(guān)閉的時(shí)間b_i，則無法訪問該結(jié)點(diǎn)。

（圖中d_ij表示時(shí)間，c_ij表示花費(fèi)，[xx， yy]表示時(shí)間窗。具體定義見下文）

在此基礎(chǔ)上尋找起點(diǎn)p（圖中點(diǎn)v_1）到其余各點(diǎn)總花費(fèi)最小的路徑，就是我們要解決的問題。

在圖中我們可以看到v_1→v_4的cost權(quán)值為負(fù)。本文的算法不但能解決花費(fèi)為正值的情況，還能解決花費(fèi)為負(fù)的情況。只需要保證時(shí)間消耗為正。

在此基礎(chǔ)上建立問題的模型:

路徑X_1^0可以用下圖表示：

傳統(tǒng)的最短路問題建模可以直接去掉部分定義，不再贅述。下面我們先來看一下處理傳統(tǒng)最短路問題的標(biāo)號(hào)法。

?Label-setting算法簡介

標(biāo)號(hào)算法(Labeling algorithms)是解決最短路徑問題的一種重要方法，也是絕大多數(shù)最短路徑算法的核心部分。

按照不同的標(biāo)識(shí)結(jié)點(diǎn)處理策略，標(biāo)號(hào)算法又可分為標(biāo)號(hào)設(shè)定(Label Setting，簡稱LS)和標(biāo)號(hào)改正(Label Correcting，簡稱LC)兩大體系。

有關(guān)最短路徑問題的兩個(gè)經(jīng)典算法，Dijkstra算法和Bellman-Ford算法，分別屬于LS和LC。

LS算法通過迭代過程對label進(jìn)行逐步修正，每次迭代均選擇候選結(jié)點(diǎn)集中標(biāo)號(hào)最小者退出候選結(jié)點(diǎn)集，并將該結(jié)點(diǎn)標(biāo)號(hào)從臨時(shí)標(biāo)號(hào)轉(zhuǎn)變久為永久標(biāo)號(hào)。這是一種基于貪心策略的最短路徑算法，每一次轉(zhuǎn)化為永久標(biāo)號(hào)的label都代表到當(dāng)前結(jié)點(diǎn)的最短路徑，考慮的是“當(dāng)前最優(yōu)”。

?LC算法在每次迭代時(shí)并不一定將任何結(jié)點(diǎn)標(biāo)號(hào)從臨時(shí)標(biāo)號(hào)轉(zhuǎn)變?yōu)橛谰脴?biāo)號(hào)，只是對臨時(shí)標(biāo)號(hào)進(jìn)行一次修正，所有結(jié)點(diǎn)標(biāo)號(hào)仍然為臨時(shí)標(biāo)號(hào)；只有在所有迭代終止時(shí)，所有結(jié)點(diǎn)標(biāo)號(hào)同時(shí)轉(zhuǎn)變?yōu)橛谰脴?biāo)號(hào)。LC算法考慮的是“最終最優(yōu)”，最短路徑需要等待多次迭代直到整個(gè)算法運(yùn)行結(jié)束才能被確定。

我們主要介紹LS算法。這里介紹解決不帶時(shí)間窗約束的最短路問題的Dijkstra算法。該算法中，對于節(jié)點(diǎn)i，其label是(C[i], p[i])，其中C[i]表示從起點(diǎn)到節(jié)點(diǎn)i的最短距離，p[i]記錄在d[i]距離下，從起點(diǎn)到節(jié)點(diǎn)i的路徑中，節(jié)點(diǎn)i的前一個(gè)節(jié)點(diǎn)編號(hào)。s_0表示起點(diǎn)。c_ij表示通過邊（i,j）的距離。執(zhí)行流程如下：

Step0：初始化。令S為空，S*=N，C[s_0]=0，p[s_0]=-1；對N中的頂點(diǎn)i(i≠s_0)令初始距離標(biāo)號(hào)C[j]=∞。

Step1：邊界判斷。如果S=N，則C[j]為最短路徑長度，其最短路徑可以通過p[j]所記錄的信息反向追蹤獲得。結(jié)束。否則繼續(xù)step2。

Step2：更新標(biāo)記。從S*中找到總花費(fèi)最小的結(jié)點(diǎn)i，把它從S*中刪除，加入S。對于所有從i出發(fā)的可到達(dá)的后繼點(diǎn)j，若C[j]>C[i]+c_ij，則令C[j]=C[i]+c_ij，p[j]=i。轉(zhuǎn)step1。

該算法的主要計(jì)算量在于step2循環(huán)。它包括兩個(gè)過程：尋找結(jié)點(diǎn)的過程(從S*中找到花費(fèi)最小的結(jié)點(diǎn)i)和總花費(fèi)更新的過程(更新與結(jié)點(diǎn)i相鄰的結(jié)點(diǎn)的花費(fèi))。

然而，簡單的Dijkstra算法無法處理時(shí)間窗約束，也無法處理負(fù)權(quán)邊：在不斷循環(huán)的過程中，實(shí)際上有一些邊被我們忽視了，及時(shí)它的權(quán)值為負(fù)，能夠優(yōu)化花費(fèi)，我們也不會(huì)去管。

下面我們將提出LS算法的改進(jìn)版，既能處理時(shí)間窗約束，又能滿足負(fù)權(quán)邊。

占優(yōu)剪枝：dominate

在了解了解決最短路問題的LS算法后，我們再回到時(shí)間窗約束下的最短問題。因?yàn)榧由狭藭r(shí)間這一權(quán)重，我們的標(biāo)記不能再像上一部分那樣只記錄一個(gè)變量cost。我們?yōu)槊恳粭l路徑到達(dá)的每一個(gè)點(diǎn)時(shí)的狀態(tài)分別制作一個(gè)label,為(T, C)，記錄這條路徑到達(dá)該點(diǎn)時(shí)消耗的總時(shí)間、總花費(fèi)。

根據(jù)定義，我們可以給出標(biāo)記的處理方法：

當(dāng)然可以用窮舉直接用類似Dijkstra的方法解決問題。但我們希望找出一種有效的剪枝手段以避免窮舉帶來的高時(shí)間復(fù)雜度。值得慶幸的是，對于尋找起點(diǎn)到每個(gè)點(diǎn)的最短路徑而言，并不是所有標(biāo)記都是有效的。我們通過舉例來說明：

dominate?rule 能讓我們篩選掉無效標(biāo)記。

我們可以用一個(gè)函數(shù)來直觀表示這種關(guān)系：

很顯然，在圖中，如果兩點(diǎn)間斜率k>=0，終點(diǎn)is dominated。（如X_i^1?dominateX_i^5）因?yàn)閮蓚€(gè)標(biāo)記所代表的兩條路徑都將到達(dá)同一個(gè)點(diǎn)，而斜率終點(diǎn)的那條路徑時(shí)間和cost都更高，當(dāng)然更差了。而k=0時(shí)，我們在圖中畫了幾條直線。每條直線都由一個(gè)點(diǎn)（代表一個(gè)標(biāo)記）引出，下一個(gè)點(diǎn)結(jié)束。這代表，在這條直線對應(yīng)的時(shí)間內(nèi)，該標(biāo)記的花費(fèi)為最小花費(fèi)。其他情況，并不能判斷哪條路徑更優(yōu)。

我們通過一個(gè)函數(shù)EFF（）來篩選。在第一部分LS的介紹中我們提到了永久標(biāo)記的概念，意思是對永久標(biāo)記我們已確保其有效，在之后的拓展過程中其標(biāo)記值將不再改變。我們給出拓展結(jié)點(diǎn)j對應(yīng)的永久標(biāo)記的方法。

定義：

Q_j為結(jié)點(diǎn)j的永久標(biāo)記的集合。（Q_j中所有標(biāo)記中的最小花費(fèi)即為p到j(luò)的最短路徑）

通過以下方式拓展Q_j：

這里的拓展其實(shí)暗示了Q_j中必須要存在所有可能dominate新label的所有l(wèi)abel。如何保證這一點(diǎn)呢？我們在下一節(jié)中給出解決方法。

標(biāo)記處理的順序：字典排序

在LS處理標(biāo)記的過程中，我們是按結(jié)點(diǎn)順序拓展標(biāo)記的，所以對于一個(gè)結(jié)點(diǎn)的多個(gè)標(biāo)記我們需要依照一個(gè)順序進(jìn)行處理。這個(gè)順序最好能在拓展過程中揪出所有無效點(diǎn)，即一邊拓展一邊進(jìn)行EFF查找。

在函數(shù)圖像中我們用斜率k來表示統(tǒng)治關(guān)系，容易想到從左到右判斷k，找出所有的k>=0的線段。轉(zhuǎn)化過來，就是按照先比較T再比較C的順序進(jìn)行排序。因此，我們在存儲(chǔ)標(biāo)記的時(shí)候也考慮按先判斷T再判斷C的順序存儲(chǔ)，處理時(shí)從小到大處理。這就是所謂的字典排序。顯然，這是一種全排序，滿足我們的需求。

我們有以下三個(gè)命題：

字典序是為了配合dominate的判斷而生的。這些都是類似剪枝的操作，以避免窮舉。加了這兩個(gè)操作以后，你在枚舉的過程中，就會(huì)發(fā)現(xiàn)很多不可行的路徑，一旦不可行，立馬停止該路徑的擴(kuò)展。

我們將所有標(biāo)記分為三個(gè)部分：

Q為永久標(biāo)記的集合

P為已處理標(biāo)記的集合。

T為未處理標(biāo)記的集合。

我們按照字典序?qū)λ袠?biāo)記進(jìn)行排序處理，可以保證所有T中的標(biāo)記無法dominate P中的標(biāo)記。因?yàn)槊恳粭l邊的時(shí)間d_ij都為正值，因此被拓展出的新標(biāo)記必定排列在原標(biāo)記后，無法再dominate原標(biāo)記。dominate關(guān)系有傳遞性，依照歸納法可得，T中的標(biāo)記無法對任意中的P標(biāo)記進(jìn)行dominate處理。

我們還可以利用P、Q、T的定義給出一個(gè)關(guān)系式：

在算法中我們可以利用這個(gè)式子來計(jì)算T。

算法流程與例子

A simple example：

代碼分享

下面提供C++代碼。栗子用的是上面的簡單栗子，命名按照上述定義。理解了算法的流程后，代碼本身并不難。這里的代碼重點(diǎn)在配合講解，作為一個(gè)參考，所以沒有選擇復(fù)雜的數(shù)據(jù)結(jié)構(gòu)和語法技巧，有需要的朋友可以自己作為練習(xí)自己嘗試。

//SPPTW GLSA //By ZLL_HUST
#include #include using namespace std;
class label  //標(biāo)記類，存放該路徑當(dāng)前所在的結(jié)點(diǎn)，總時(shí)間，總花費(fèi) {  public:    int node;    int time;       int cost;      label(){node=-1,time=-1,cost=-1;};};
int const N=4;int const INF=9999;
vector<vector > Q(N);//將集合Q，P定義為二維向量，存放每一個(gè)結(jié)點(diǎn)的labels vector<vector > P(N);
double cost[N][N];//這里采用簡單的二維表來存儲(chǔ)數(shù)據(jù)，不多作展開，可以關(guān)注公眾號(hào)以后的推文 double time[N][N];double time_win_a[N]={0,3,4,4};double time_win_b[N]={0,10,6,10};
//初始化數(shù)據(jù) void init();//查找字典序最小的label label minlex(vector &);//構(gòu)造集合T：未處理的labels bool buildT(vector &);//dominance判斷，剪枝無效label bool EFF(label);//對label的總處理 void treatlabel(label);//GLSA總流程 void GLSA();
//初始化數(shù)據(jù) ，采用推文中所選例子，加入了負(fù)權(quán)邊 void init(){  label X0;  X0.cost=0;  X0.time=0;  X0.node=0;  vector X;  X.push_back(X0);  Q[0]=X;   for (int i=0;i      for(int j=0;j          cost[i][j]=time[i][j]=-INF;  cost[0][1]=2;  time[0][1]=3;  cost[1][2]=5;  time[1][2]=2;  cost[0][3]=-7;  time[0][3]=5;  cost[3][1]=1;  time[3][1]=1; }
//查找字典序最小的label ，優(yōu)先判斷time，其次判斷cost label minlex(vector &T){  label min;  min.time=INF;  for (int i=0;i    if (T[i].time      min=T[i];  return min;}
//構(gòu)造集合T：未處理的labels。由于我們往集合Q和P中加入labels是有序的，所以只需要從P.size后面開始加入。bool buildT(vector &T){  for (int i=0;i    for (int j=P[i].size();j       T.push_back(Q[i][j]);   if (T.size()==0)      return false;//若所有標(biāo)記都已處理，返回false值，退出程序   else      return true;}
//dominance判斷，剪枝無效label bool EFF(label next){  bool is_dominated=false;  for (int i=0;i    if (next.time>Q[next.node][i].time && next.cost>Q[next.node][i].cost)        is_dominated=true;  return !is_dominated;}
//對label的總處理 void treatlabel(label FT){  for(int succ=1;succ  {  if (cost[FT.node][succ]!=-INF)//尋找后繼結(jié)點(diǎn)   {    if ((FT.time+time[FT.node][succ])<=time_win_b[succ])//時(shí)間窗約束     {      label next;//更新標(biāo)記       next.time=(FT.time+time[FT.node][succ])>time_win_a[succ]?(FT.time+time[FT.node][succ]):time_win_a[succ];      next.cost=FT.cost+cost[FT.node][succ];      next.node=succ;      //cout<      if (EFF(next))         Q[next.node].push_back(next);    }  }    }  P[FT.node].push_back(FT);//FT已處理，加入集合P }
//GLSA總流程 void GLSA(){  bool flag=true;  vector T;  flag=buildT(T);  int i=0;  while(flag)  {    label FT=minlex(T);    treatlabel(FT);    T.clear();    flag=buildT(T);    cout<<"F(T)'s cost is  "<"\t"<<"F(T)'s time is  "<"\t"<<"F(T)'s node is  "<endl;  }  for (int i=1;i//由于加入集合時(shí)按照先時(shí)間后花費(fèi)的標(biāo)準(zhǔn)，因此每個(gè)結(jié)點(diǎn)的最后一個(gè)label為最遲、最短路徑      cout<<"起點(diǎn)1到達(dá)點(diǎn)"<1<<"的最短路徑花費(fèi)為"<-1].cost<<endl; }
int main(){  init();  GLSA();  return 0;}

本期的文章到這里就差不多該結(jié)束啦~

這期的推文反復(fù)修改了多次。感謝鄧發(fā)珩學(xué)長和秦虎老師對我的支持，提供了很多修改意見！非常感謝！

小編會(huì)努力為大家寫出更精彩的推文的！

咱們下次再見( ^_^ )/~~

參考:

Martin Desrochers,?Francois Soumis?(1988)?A generalized permanent labeling algorithm for the shortest path problem with time windows.?INFOR Information Systems and Operational Research.?26(3):191-212.

?贊賞?

長按下方二維碼打賞

感謝您，

支持學(xué)生們的原創(chuàng)熱情！

鄭重承諾

打賞是對工作的認(rèn)可

所有打賞所得

都將作為酬勞支付給辛勤工作的學(xué)生

指導(dǎo)老師不取一文

?
?

代碼 | 自適應(yīng)大鄰域搜索系列之(1) - 使用ALNS代碼框架求解TSP問題

代碼 | 自適應(yīng)大鄰域搜索系列之(2) - ALNS算法主邏輯結(jié)構(gòu)解析