matlab廣度優先演算法

『壹』 matlab自帶深度優先搜索演算法程序嗎

深度優先和你的數據結構實現有關吧。不難

『貳』 matlab問題

1，FOUND=zeros(1,0); 定義了一個空矩陣，相當於 FOUND=[];
而FOUND = [FOUND, v]是將 v添加到原來的FOUND；
2，不是你說的那樣，那兩句是說，將與當前節點所在的行和列清零而已。

若滿意請採納。

『叄』 07年數學建模B題數據怎麼處理具體一點兒，各位大神幫幫忙

用excel可以讀入txt的數據，處理出每條線的上下行線路，沒有給出下行線路的按照自己的假設處理。然後matlab讀入，建立excel的線路矩陣，通過搜索演算法就可以求解出可行線路。我就是這么處理數據的，用廣度優先演算法，分為換乘次數0/1/2三種情況。由於此線路系統比較發達，換乘3次次數很少。

『肆』 有誰用matlab做過聚類演算法

分類演算法，參數分別為G（相似度矩陣），r（鄰居門限），lambda（類門限），返回值A，一個cell數組，每個元素是一個向量，包含了一個類的所有元素。
function A=BFSN_Algorithm(G,r,lambda)
%廣度優先搜索鄰居的聚類演算法實現
%G為相似度矩陣
%r和lambda為參數
%r為鄰居門限，相似度大於r即為鄰居
%lambda門限
%未分類元素對於某類的所有元素，如果是鄰居則令X(i)=1，否則為0.i為類元素的下標
%對X求和並除以類元素個數，若此值大於lambda門限，則該未分類元素屬於這類
%打開計時器
tic
%A為聚類結果
A={};
%k為分類計數
k=1;
%n為待分類元素個數
n=size(G,1);
%構建元素向量
member=1:n;
%只要member中還有未分類的元素就繼續循環
while numel(member)~=0
%從member中取出一個元素a
a=member(1);
%新建空類A並將a送入Ak類
Ak=a;
%從member中刪除a
member(1)=[];
%掃描member中的所有元素
%queue為廣度優先搜索使用的隊列
%將a送入queue中
queue=a;
%已訪問過的元素
visited=zeros(1,n);
%如果隊列非空說明還有沒有檢驗過的鄰居
while numel(queue)~=0
%一個元素出隊
p=queue(1);
queue(1)=[];
%掃描member中所有元素
for count=1:numel(member)
%用member(count)作為待分類的元素
%p是從queue中取出,找到p的所有未訪問鄰居
if G(p,member(count))>r && visited(member(count))==0
%滿足if的member(count)是未訪問過的鄰居
%放入queue中
queue=[queue member(count)];
%member(count)已經訪問過了
visited(member(count))=1;
if sum(G(member(count),Ak)>r)/numel(Ak)>=lambda
%滿足if的元素屬於Ak類，根據lambda門限判斷
Ak=[Ak member(count)];
member(count)=-1;
end
end
end
%刪除member中已分類的元素
member(member==-1)=[];
end
%將Ak保存在cell數組A的第k個位置
A{k}=Ak;
%k指向下一個分類
k=k+1;
end
%關閉計時器
toc
由於編寫的時候比較倉促，應該有很大的優化的餘地。
plotAllClass.m
繪制已分類數據的圖形，參數：data元素數據，A分類表，一個cell數組，調用BFSN_Algorithm得到。
function plotAllClass(data,A)
%data:m行2列的矩陣，m行代表m個元素，
%第一列為每個元素的橫坐標
%第二列為每個元素的縱坐標
%A為分類列表，
%有c個元素的cell數組
%每個元素是一個向量
%包含了一個分類的所有元素在data中的行
%n=類別數
n=numel(A);
%繪圖圖案列表
style=['r*';'g*';'b*';'c*';'m*';'y*';'k*';...
'r+';'g+';'b+';'c+';'m+';'y+';'k+';...
'rs';'gs';'bs';'cs';'ms';'ys';'ks';...
'rp';'gp';'bp';'cp';'mp';'yp';'kp';...
'rh';'gh';'bh';'ch';'mh';'yh';'kh';...
'rd';'gd';'bd';'cd';'md';'yd';'kd';...
'ro';'go';'bo';'co';'mo';'yo';'ko';...
'rx';'gx';'bx';'cx';'mx';'yx';'kx';...
'rv';'gv';'bv';'cv';'mv';'yv';'kv';...
'r<';'g<';'b<';'c<';'m<';'y<';'k<';...
'r>';'g>';'b>';'c>';'m>';'y>';'k>';...
'r^';'g^';'b^';'c^';'m^';'y^';'k^';...
'r.';'g.';'b.';'c.';'m.';'y.';'k.'];
figure;
hold on;
for count=1:n
plot(data(A{count},1),data(A{count},2),style(count,:));
end
hold off;
這個函數最多能夠繪制91個類別，如果有超過91個類，函數會出錯。
show.m
包含了一個完整的流程，包括數據生成，相似度矩陣生成，分類，類別繪制。
%show.m
data=rand(200,2);
figure;
plot(data(:,1),data(:,2),'+');
G=createSimiR(data);
A=BFSN_Algorithm(G,0.95,0.95);
plotAllClass(data,A);

『伍』 matlab + &優先順序問題

算術運算符『加減乘除』優先於邏輯運算符『與或非』
MATLAB的優先順序和C基本是一樣的

『陸』 急求人工神經網路的MATLAB演算法~~求大蝦教我

1、採用2-5-1三層BP網路結構即可實現其
MATLAB 程序如下：
clc
clear
a=rand(2,200);
x=a(1,:);
y=a(2,:);
F=x.^2+y.^2;
net=newff(minmax(a),[5,1],{'tansig' 'purelin'},'trainlm');
net.trainParam.epochs=100;
net.trainParam.lr=0.1;
net.trainparam.goal=0.001;
net=train(net,a,F)
b=rand(2,100);
x1=b(1,:);
y1=b(2,:);
F1=x1.^2+y1.^2;
ty=sim(net,b);
subplot(1,2,1)
plot(F1);
subplot(1,2,2)
plot(ty,'r')

以上程序我運行很好，。

2、神經網路的核心就是求權值W，偏置值b，很多演算法都可實現，當V,M收斂後，就確定這個函數了，只是這個函數為非線性函數，非常復雜，表達困難，已經包含在訓練好的神經網路了，此時，可以用這個網路進行預測和分類

記住分給我啊，這個matlab程序花了很多時間，注釋懶的寫了，你應該看的懂的。

『柒』 圖論演算法及其MATLAB實現的圖書目錄

第1章 圖論的基礎知識1
1.1圖論的起源1
1.2著名的圖論學者——歐拉1
1.3圖2
1.4特殊圖類3
1.5有向圖4
1.6圖的矩陣表示5
1.6.1鄰接矩陣5
1.6.2關聯矩陣5
1.7圖論的基本性質和定理6
1.8計算有向圖的可達矩陣的演算法及其MATLAB實現6
1.9關聯矩陣和鄰接矩陣的相互轉換演算法及其MATLAB實現7
習題一11
第2章 最短路12
2.1路12
2.2最短路問題13
2.3求連通圖最短距離矩陣的演算法及其MATLAB實現14
2.4求兩點間最短路的Dijkstra演算法及其MATLAB實現15
2.4.1 Dijkstra演算法16
2.4.2 Dijkstra演算法的MATLAB實現16
2.5求兩點間最短路的改進的Dijkstra演算法及其MATLAB實現18
2.5.1 Dijkstra矩陣演算法Ⅰ18
2.5.2 Dijkstra矩陣演算法Ⅱ18
2.6 求兩點間最短路的WarshallFloyd演算法及其MATLAB實現21
2.6.1 Floyd演算法的基本思想22
2.6.2 Floyd演算法的基本步驟22
2.6.3 WarshallFloyd演算法的MATLAB實現22
2.7求任意兩點間最短路的演算法及其MATLAB實現25
2.8求從一固定點到其他所有點最短路的演算法及其MATLAB實現27
2.9求必須通過指定兩個點的最短路的演算法及其MATLAB實現29
2.10求圖的兩頂點間最短路與次短路的演算法及其MATLAB實現32
2.11求最大可靠路的演算法及其MATLAB實現34
2.12求最大期望容量路的演算法及其MATLAB實現36
習題二38
第3章 連通圖40
3.1判斷圖的連通性演算法及其MATLAB實現40
3.2連通圖的中心和加權中心的演算法及其MATLAB實現42
3.3連通無向圖一般中心的演算法及其MATLAB實現44
習題三46
第4章 樹48
4.1樹及其性質48
4.2割點、割邊、割集50
4.3二元樹與Huffman樹51
4.3.1有序二元樹51
4.3.2 Huffman樹51
4.4求Huffman樹及其MATLAB實現52
4.5廣度優先搜索演算法及其MATLAB實現55
4.6深度優先搜索演算法及其MATLAB實現57
4.7求割點演算法及其MATLAB實現61
4.8生成樹及其個數65
4.9求無向圖的生成樹演算法及其MATLAB實現67
4.10求有向圖的生成樹演算法及其MATLAB實現69
4.11求有向連通圖的外向樹與內向樹數目的演算法及其MATLAB實現71
4.12最小生成樹問題73
4.13求最小生成樹的Kruskal演算法及其MATLAB實現74
4.13.1 Kruskal演算法的基本思想74
4.13.2 Kruskal演算法的MATLAB實現74
4.14求最小生成樹的Prim演算法及其MATLAB實現76
4.14.1 Prim演算法的基本思想76
4.14.2 Prim演算法的MATLAB實現77
習題四79
第5章Euler圖和Hamilton圖81
5.1 Euler圖81
5.2「一筆畫」問題及其理論81
5.3中國郵遞員問題82
5.4 Fleury演算法及其MATLAB實現82
5.4.1 Fleury演算法的步驟82
5.4.2 Fleury演算法的MATLAB實現82
5.5 Hamilton圖87
5.6旅行售貨員問題88
5.7改良圈演算法及其MATLAB實現89
習題五92
第6章 匹配問題及其演算法93
6.1問題起源——婚配問題93
6.2二分圖的有關知識93
6.3匹配、完美匹配、最大匹配93
6.4匹配的基本定理94
6.5應用案例——BernolliEuler錯放信箋問題95
6.6尋求圖的一個較大基數匹配演算法及其MATLAB實現95
6.7人員分配問題97
6.8匈牙利演算法及其MATLAB實現97
6.8.1匈牙利演算法基本步驟97
6.8.2匈牙利演算法的MATLAB實現98
6.8.3案例及其MATLAB實現100
6.9最優分配問題101
6.10 KuhnMunkres演算法及其MATLAB實現101
6.10.1 KuhnMunkres演算法的基本思想101
6.10.2利用可行頂點標記求最佳匹配的KuhnMunkras演算法步驟102
6.10.3 KuhnMunkres演算法的MATLAB實現102
6.10.4簡單實驗105
習題六107
第7章 網路流的演算法108
7.1網路、流和割108
7.1.1網路和流108
7.1.2割109
7.2網路的最大流問題110
7.3最大流最小割定理110
7.4 FordFulkerson標號演算法及其MATLAB實現111
7.4.1 FordFulkerson標號演算法的基本步驟111
7.4.2 FordFulkerson 標號演算法的MATLAB實現112
7.4.3案例及其MATLAB實現113
7.5 Dinic演算法及其MATLAB實現114
7.5.1 Dinic演算法的基本思想114
7.5.2 Dinic演算法的MATLAB實現115
7.5.3案例

『捌』 matlab最優化演算法有哪些

matlab最優化程序包括

無約束一維極值問題 進退法 黃金分割法 斐波那契法 牛頓法基本牛頓法 全局牛頓法 割線法 拋物線法 三次插值法 可接受搜索法 Goidstein法 Wolfe.Powell法

單純形搜索法 Powell法 最速下降法 共軛梯度法 牛頓法 修正牛頓法 擬牛頓法 信賴域法 顯式最速下降法， Rosen梯度投影法 罰函數法 外點罰函數法

內點罰函數法 混合罰函數法 乘子法 G－N法 修正G－N法 L－M法 線性規劃 單純形法 修正單純形法 大M法 變數有界單純形法 整數規劃 割平面法 分支定界法 0-1規劃 二次規劃

拉格朗曰法 起作用集演算法 路徑跟蹤法 粒子群優化演算法 基本粒子群演算法 帶壓縮因子的粒子群演算法 權重改進的粒子群演算法 線性遞減權重法 自適應權重法 隨機權重法

變學習因子的粒子群演算法 同步變化的學習因子 非同步變化的學習因子 二階粒子群演算法 二階振盪粒子群演算法

『玖』 數學建模優秀論文

這是07年數模比賽獲獎的：

乘公交 看奧運

二 符號說明
：第i條公汽線路標號,i=1,2 …10400,當 時, 表示上行公汽路線, 當 時, 表示與上行路線 相對應的下行公汽路線；
：經過第i條公汽路線的第g個公汽站點標號；
：第j條地鐵路線標號, j=1,2；
：經過第j條地鐵線路的第h個地鐵站點標號；
：轉乘n次的路線；
：選擇第k種路線的總時間；
：選擇第k種路線公汽換乘公汽的換乘次數；
：選擇第k種路線地鐵換乘地鐵的換乘次數；
：選擇第k種路線地鐵換乘公汽的換乘次數；
：選擇第k種路線公汽換乘地鐵的換乘次數；
：第k種路線、乘坐第m輛公汽的計費方式，其中：
表示實行單一票價， 表示實行分段計價；
：第k種路線，乘坐第m輛公汽的費用；
：選擇第k種路線的總費用；
：選擇第k種路線，乘坐第m輛公汽需要經過的公汽站個點數；
：選擇第k種路線，乘坐第n路地鐵需要經過的地鐵站個點數；
：表示對於第k種路線的第m路公汽的路線是否選擇步行， 為0-1變數， 表示不選擇步行， 表示選擇步行；
：對於第k種路線的第n路地鐵的路線是否選擇步行， 為0-1變數， 表示不選擇步行， 表示選擇步行；

三 模型假設
3.1基本假設
1、相鄰公汽站平均行駛時間(包括停站時間)： 3分鍾
2、相鄰地鐵站平均行駛時間(包括停站時間)： 2.5分鍾
3、公汽換乘公汽平均耗時：5分鍾(其中步行時間2分鍾)
4、地鐵換乘地鐵平均耗時：4分鍾(其中步行時間2分鍾)
5、地鐵換乘公汽平均耗時：7分鍾(其中步行時間4分鍾)
6、公汽換乘地鐵平均耗時：6分鍾(其中步行時間4分鍾)
7、公汽票價：分為單一票價與分段計價兩種；
單一票價：1元
其中分段計價的票價為：0 ～20站：1元
21～40站：2元
40站以上：3元
8、地鐵票價：3元（無論地鐵線路間是否換乘）
9、假設同一地鐵站對應的任意兩個公汽站之間可以通過地鐵站換乘，且無需支付地鐵費
3.2 其它假設
10、查詢者轉乘公交的次數不超過兩次；
11、所有環行公交線路都是雙向的；
12、地鐵線T2也是雙向環行的；
13、各公交車都運行正常，不會發生堵車現象；
14、公交、列車均到站停車
四 問題的分析
在北京舉行奧運會期間，公眾如何在眾多的交通路線中選擇最優乘車路線或轉乘路線去看奧運，這是我們要解決的核心問題。針對此問題，我們考慮從公交線路的角度來尋求最優線路。首先找出過任意兩站點（公眾所在地與奧運場地）的所有路線，將其存儲起來，形成數據文件。這些路線可能包含有直達公交線路，也有可能是兩條公交線路通過交匯而形成的（此時需要轉乘公交一次），甚至更多公交線路交匯而成。然後在這些可行路線中搜尋最優路線。
對於路線的評價，我們可以分別以總行程時間，總轉乘次數，總費用為指標，也可以將三種指標標准化後賦以不同權值形成一個綜合指標。而最優路線則應是總行程時間最短，總費用最少或總轉乘次數最少，或者三者皆有之。之所以這樣考慮目標，是因為對於不同年齡階段的查詢者，他們追求的目標會有所不同，比如青年人比較熱衷於比賽，因而他們會選擇最短時間內到達奧運賽場觀看比賽。而中年人則可能較傾向於綜合指標最小，即較快、較省，轉乘次數又不多。老年人總願意以最省的方式看到奧運比賽。而對於殘疾人士則總轉乘次數最少為好。
不同的路線查詢需求用圖4.1表示如下：

圖4.1 公交線路查詢目標圖
經分析，本問題的解決歸結為一個求最短路徑的問題，但是傳統的Dijkstra最短路徑演算法並不適用於本問題，因為Dijkstra演算法採用的存儲結構和計算方法難以應付公交線路網路拓撲的復雜性,而且由於執行效率的問題，其很難滿足實時系統對時間的嚴格要求。
為此我們在實際求解的過程中，採用了效率高效得廣度優先演算法，其基本思路是每次搜索指定點，並將其所有未訪問過的近鄰點加入搜索隊列，循環搜索過程直到隊列為空。此方法在後文中有詳細說明。
五 建模前的准備
為了後面建模與程序設計的方便，在建立此模型前，我們有必要做一些准備工作。
5．1數據的存儲
由於所給的數據格式不是很規范，我們需要將其處理成我們需要的數據存儲格式。從所給文件中讀出線路上的站點信息，存入txt文檔中，其存儲格式為：兩行數據，第一行表示上行線上的站點信息，第二行表示下行線的站點信息，其中下行路線標號需要在原標號的基礎上加上520，用以區分上行線和下行線。
如果上行線與下行線的站點名不完全相同，那麼存儲的兩行數據相應的不完全相同，以公交線L009為例：
L009:3739 0359 1477 2159 2377 2211 2482 2480 3439 1920 1921 0180 2020 3027 2981
L529:2981 3027 2020 0180 1921 1920 3439 3440 2482 2211 2377 2159 1478 0359 3739
L529為L009所對應的下行線路。
如果下行線是上行線原路返回，那麼存儲的兩行數據中的站點信息剛好順序顛倒，以公交線路L001為例：
L001:0619 1914 0388 0348 0392 0429 0436 3885 3612 0819 3524 0820 3914 0128 0710
L521:0710 0128 3914 0820 3524 0819 3612 3885 0436 0429 0392 0348 0388 1914 0619
如果是環線的情況（如圖5.1所示），則可以等效為兩條線路:
順時針方向：S1→S2→S3→S4→S1→S2→S3→S4；
逆時針方向：S1→S4→S3→S2→S1→S4→S3→S2。
經過分析，此兩條」單行路線」線路的作用等同於原環形路線

圖5.1 環行線路示意圖
以環形公交線L158為例，此環形路線存儲數據如下：
L153: 534 649 2355 1212 812 171 170 811 2600 172 1585 814 264 3513 1215 1217 251 2604 2606 534 649 2355 1212 812 171 170 811 2600 172 1585 814 264 3513 1215 1217 251 2604 2606
L673: 534 2606 2604 251 1217 1215 3513 264 814 1585 172 2600 811 170 171 812 1212 2355 649 534 2606 2604 251 1217 1215 3513 264 814 1585 172 2600 811 170 171 812 1212 2355 649
在這里，L153被看作成上行路線，L673被當成下行路線。這樣對於每條公交線路都可以得到兩行線路存儲信息。
5．2搜尋經過每個站點的公交路線
處理5.1所得信息，找出通過每個站點的所有公交路線，並將它們存入數據文件中。
例如，通過搜尋得出經過站點S0001的線路和經過站點S0002的線路如下：
經過S0001的線路有：L421
經過S0002的線路有：L027 L152 L365 L395 L485
5．3統計任意兩條公交線路的相交（相近）站點
依次統計出任意兩條公交線路之間相交(相近)的站點，將其存入1040×1040的矩陣A中，但是這個矩陣的元素是維數不確定的向量，具體實現的時候可以將用隊列表示。
例如：公交線路L001與公交線路L025相交的站點為A[1][25]=｛S0619，S1914，S0388，S0348｝。

六 模型的建立與求解
6．1模型一的建立
該模型針對問題一，僅考慮公汽線路，先找出經過任意兩個公汽站點 與 最多轉乘兩次公汽的路線，然後再根據不同查詢者的需求搜尋出最優路線。
6．1．1 公汽路線的數學表示
任意兩個站點間的路線有多種情況，如果最多允許換乘兩次，則換乘路線分別對應圖6.1的四種情況。該圖中的A、B為出發站和終點站，C、D、E、F為轉乘站點。

圖6.1 公汽路線圖
對於任意兩個公汽站點 與 ，經過 的公汽線路表示為 ，有 ；經過 的公汽線路表示為 ，有 ；
1）直達的路線 （如圖6.1（a）所示）表示為：

2）轉乘一次的路線 （如圖6.1（b）所示）表示為：

其中：SC為 ， 的一個交點；
3）轉乘兩次的路線 （如圖6.1（c）所示）表示為：

通過以上轉乘路線的建模過程，可以看出不同轉乘次數間可作成迭代關系，進而對更多轉乘次數的路線進行求尋。不過考慮到實際情況，轉乘次數以不超過2次為佳，所以本文未對轉乘三次及三次以上的情形做討論。
6．1．2最優路線模型的建立
找出了任意兩個公汽站點間的可行路線，就可以對這些路線按不同需求進行選擇，找出最優路線了:
1）以時間最短作為最優路線的模型：行程時間 等於乘車時間與轉車時間之和。
（6.1式）
其中，第k路線是以上轉乘路線中的一種或幾種。
2）以轉乘次數最少作為最優路線的模型：
（6.2式）
此模型等效為以上轉乘路線按直達、轉乘一次、兩次的優先次序來考慮。
3）以費用最少作為最優路線的模型：
（6.3式）
其中， （6.4式）
6．1．3模型的演算法描述
針對該問題的優化模型，我們採用廣度優先演算法找出任意兩個站點間的可行路線，然後搜索出最優路線。現將此演算法運用到該問題中，結合圖6.2敘述如下：（該圖中的 、 、 、 、 表示公汽站點， 、 、 、 、 、 表示公汽線路。其中（a）、（b）、（c）圖分別表示了從點 到點 直達、轉乘一次、轉乘兩次的情況）

圖6.2 公交直達、轉乘圖
（1）首先輸入需要查詢的兩個站點 與 （假設 為起始站， 為終點站）；
（2）搜索出經過 的公汽線路 （i=1,2,…,m）和經過 的公汽線路 ( =1,2, …，n)，存入數據文件；判斷是 與 是否存在相同路線，若有則站點 與 之間有直達路線(如圖6.2中的 )，則該路線是換乘次數最少(換乘次數等於0)的路線，若有多條直達路線，則可以在此基礎上找出時間最省的路線；這樣可以找出所有直達路線，存入數據文件；
（3）找出經過 的公汽線路 (如圖6.2中的 )中的另一站點 和經過 的公汽線路 中的另一站點 。判斷 與 中是否存在相同的點，若存在(如圖6.2中的 )則站點 與 間有一次換乘的路線(如圖6.2中的 與 )，該相同點即為換乘站點；這樣又找出了一次換乘路線，存入數據文件；
（4）再搜索出經過 (如圖6.2中的 )線路上除了站點 的另一站點 (如圖6.2中的 )的公汽線路 (如圖6.2中的 )，找出公汽線路 上的其他站點 ；判斷，如果 與經過 的公汽線路 中的其他站點 存在相同的點(如圖6.2中的 )，則 與 間有二次換乘的路線(如圖6.2中的 、 、 )，該相同點和點 是換乘站點；將此二次換乘的路線存入數據文件中；
（5）對上述存儲的經過兩個站點 與 的不同路線，根據不同模型進行最優路線進行搜索，得出查詢者滿意的最優路線。
6. 1. 4模型一的求解
根據以上演算法和前面建立的模型一，用VC++進行編程（程序見附錄）就可以得出不同目標下的最優路線。
1） 以耗時最少為目標的最優路線
起始站S3359到終到站S1828耗時最少為64 min，耗時最少的最優路線（轉乘次數較少，費用較省的路線）有28條(註：表6.1選擇了其中的10條表示)；
起始站S1557到終到站S0481耗時最少為106 min，耗時最少的最優路線有2條；起始站S0971到終到站S0485耗時最少為106 min，耗時最少的最優路線有2條；起始站S0008到終到站S0073耗時最少為67 min，耗時最少的最優路線有2條；起始站S0148到終到站S0485耗時最少為106 min，耗時最少的最優路線有3條；起始站S0087到終到站S3676耗時最少為46 min，耗時最少的最優路線有12條；其耗時最少的最優路線如表6.1所示。
表6.1 耗時最少的最優路線表
起始站 公汽線路 中轉站 公汽線路 中轉站 公汽線路 終到站 轉乘次數 所需費用
S3359 L0535 S2903 L1005 S1784 L0687 S1828 2 3
S3359 L0535 S2903 L1005 S1784 L0737 S1828 2 3
S3359 L0123 S2903 L1005 S1784 L0687 S1828 2 3
S3359 L0123 S2903 L1005 S1784 L0737 S1828 2 3
S3359 L0652 S2903 L1005 S1784 L0687 S1828 2 3
S3359 L0652 S2903 L1005 S1784 L0737 S1828 2 3
S3359 L0844 S2027 L1005 S1784 L0687 S1828 2 3
S3359 L0844 S2027 L1005 S1784 L0737 S1828 2 3
S3359 L0844 S1746 L1005 S1784 L0687 S1828 2 3
S3359 L0844 S1746 L1005 S1784 L0737 S1828 2 3
S1557 L0604 S1919 L0709 S3186 L0980 S0481 2 3
S1557 L0883 S1919 L0709 S3186 L0980 S0481 2 3
S0971 L0533 S2517 L0810 S2480 L0937 S0485 2 3
S0971 L0533 S2517 L0296 S2480 L0937 S0485 2 3
S0008 L0198 S3766 L0296 S2184 L0345 S0073 2 3
S0008 L0198 S3766 L0296 S2184 L0345 S0073 2 3
S0148 L0308 S0036 L0156 S2210 L0937 S0485 2 3
S0148 L0308 S0036 L0156 S3332 L0937 S0485 2 3
S0148 L0308 S0036 L0156 S3351 L0937 S0485 2 3
S0087 L0541 S0088 L0231 S0427 L0097 S3676 2 3
S0087 L0541 S0088 L0231 S0427 L0982 S3676 2 3
S0087 L0541 S0088 L0901 S0427 L0097 S3676 2 3
S0087 L0541 S0088 L0901 S0427 L0982 S3676 2 3
S0087 L0206 S0088 L0231 S0427 L0097 S3676 2 3
S0087 L0206 S0088 L0231 S0427 L0982 S3676 2 3
S0087 L0206 S0088 L0901 S0427 L0097 S3676 2 3
S0087 L0206 S0088 L0901 S0427 L0982 S3676 2 3
S0087 L0974 S0088 L0231 S0427 L0097 S3676 2 3
S0087 L0974 S0088 L0231 S0427 L0982 S3676 2 3
S0087 L0974 S0088 L0901 S0427 L0097 S3676 2 3
S0087 L0974 S0088 L0901 S0427 L0982 S3676 2 3

2） 以轉乘次數最少為目標的最優路線
起始站S3359到終到站S1828的最少轉乘次數為1次，轉乘次數最少的最優路線（所需時間較短，費用較省的路線）有2條；
起始站S1557到終到站S0481的最少轉乘次數為2次，轉乘次數最少的最優路線有2條與耗時最少的最優路線相同（表示在表6.1中，下同）；
起始站S0971到終到站S0485的最少轉乘次數為1次，轉乘次數最少的最優路線有1條；
起始站S0008到終到站S0073的最少轉乘次數為1次，轉乘次數最少的最優路線有9條；
起始站S0148到終到站S0485的最少轉乘次數為2次，轉乘次數最少的最優路線有3條與耗時最少的最優路線相同；
起始站S0087到終到站S3676的最少轉乘次數為2次，轉乘次數最少的最優路線有6條與耗時最少的最優路線相同；
其餘轉乘次數最少的最優路線路線如表6.2所示。
表6.2 轉乘次數最少的最優路線表
起始站 公汽線路 中轉站 公汽線路 終到站 耗時 所需費用
S3359 L0956 S1784 L0687 S1828 101 3
S3359 L0956 S1784 L0737 S1828 101 3
S0971 L0533 S2184 L0937 S0485 128 3
S0008 L0679 S0291 L0578 S0073 83 2
S0008 L0679 S0491 L0578 S0073 83 2
S0008 L0679 S2559 L0578 S0073 83 2
S0008 L0679 S2683 L0578 S0073 83 2
S0008 L0679 S3614 L0578 S0073 83 2
S0008 L0875 S2263 L0345 S0073 83 2
S0008 L0875 S2303 L0345 S0073 83 2
S0008 L0875 S3917 L0345 S0073 83 2
S0008 L0983 S2083 L0057 S0073 83 2
3）以費用最少為目標的最優路線
起始站S3359到終到站S1828的最少費用為3元，最少費用的最優路線（所需時間較短，轉乘次數較少的路線）有30條，其中28條路線所需時間為64 min，轉乘次數為2次，另外兩條路線所需時間為101 min，轉乘次數為1次；
起始站S1557到終到站S0481的最少費用為3元，最少費用的最優路線有2條，所需時間為106 min，轉乘次數為2次；
起始站S0971到終到站S0485的最少費用為3元，最少費用的最優路線有3條，其中兩條所需時間為106 min，轉乘次數為2次，另外一條所需時間為128 min，轉乘次數為1次；
起始站S0008到終到站S0073的最少費用為2元，最少費用的最優路線有9條，所需時間為83 min，轉乘次數為1次；
起始站S0148到終到站S0485的最少費用為3元，最少費用的最優路線有3條，所需時間為106min，轉乘次數為2次；
起始站S0087到終到站S3676的最少費用為3元，最少費用的最優路線有12條，所需時間為46 min，轉乘次數為2次；
最少費用的最優路線表示在表6.1和表6.2中。
6．2．1模型二的建立
該模型針對問題二，將公汽與地鐵同時考慮，找出可行路線，然後尋找最優路線。對於地鐵線路，也可以將其作為公交線路，本質上沒有什麼區別，只不過乘車費用、時間，換乘時間不一樣罷了。因此地鐵站可等效為公交站，地鐵和公交的轉乘站即可作為兩者的交匯點。因此該模型的公交換乘路線模型與模型一中的基本相同。現建立模型二下的最優路線模型。
1）以時間最短的路線作為最優路線的模型：可行路線的總時間為乘公交（公汽和地鐵）時間與公汽與地鐵換乘、公汽間、地鐵間換乘時間之和。
（6.5式）
其中，第k路線為同時考慮公汽與地鐵的轉乘路線中的一種或幾種。
2）以轉乘次數最少的路線作為最優路線的模型：
（6.6式）
此模型等效為以上轉乘路線按直達、轉乘一次、兩次（包括公交與地鐵間的轉乘）的優先次序來考慮。
3）以費用最少的路線作為最優路線的模型：可行路線的費用為乘公交和地鐵費用的總和。
（6.7式）
其中， 仍滿足（6.4式）。
6．2．2模型二的求解
不難發現，問題一是問題二解的一部分。在問題二中，新產生的最優解主要源於在通過換乘地鐵、換乘附近相近站點的路線上，如下圖所示：

從點A到B，圖(a)表示的是通過兩公交線路上相鄰公汽站S1,S2進行一次轉乘；圖(b)表示利用地鐵站進行二次轉乘；圖(c)表示利用另一條公汽路線為中介進行二次轉乘。
鐵路線路引入給題目的求解增加了難度，為了形象了解為數不多的兩條鐵路間的交叉關系，我們通過matlab編程（程序見附錄）作出了兩條鐵路的位置關系圖，如圖6.3所示。

圖6.3 T1與T2鐵路位置關系圖
註：圖四中的直線表示T1鐵路線，圓表示T2鐵路線，數值表示站點，例如1表示T1鐵路線上的D1鐵路站，26表示T2鐵路線上的D26鐵路站。此圖與網上查詢到的北京地鐵示意圖（如圖6.4所示）相吻合。

圖6.4 北京地鐵示意圖
同樣將地鐵線路等效為公交線路得出任意兩個站點間的可行線路，再將目標函數分別用模型二建立的模型表達式表達，用VC++進行編程（程序見附錄）求得出考慮地鐵情況的最優路線。
1）以轉乘次數最少為目標的最優路線
起始站S0008到終到站S0073的最少轉乘次數為1次，轉乘次數最少的最優路線有1條；
起始站S0087到終到站S3676的最少轉乘次數為0次，即有直達路線，直達下的最優路線有1條；
起始站S0148到終到站S0485的最少轉乘次數為2次，轉乘次數最少的最優路線有10條；
起始站S0971到終到站S0485的最少轉乘次數為2次，轉乘次數最少的最優路線有20條（注表6.4中羅列其中10條）；
起始站S1557到終到站S0481的最少轉乘次數為2次，轉乘次數最少的最優路線有17條（注表6.4中羅列其中10條）；
起始站S3359到終到站S1828的最少轉乘次數為2次，轉乘次數最少的最優路線有2條。
2）以耗時最少為目標的最優路線
起始站S3359到終到站S1828耗時最少為64 min，耗時最少的最優路線（轉乘次數較少，費用較省的路線）有28條(註：表6.1選擇了其中的10條表示)；
起始站S1557到終到站S0481耗時最少為109 min，耗時最少的最優路線有17條與轉乘次數最少的最優路線相同；
起始站S0971到終到站S0485耗時最少為96 min，耗時最少的最優路線有20條與轉乘次數最少的最優路線相同；
起始站S0008到終到站S0073耗時最少為55 min，耗時最少的最優路線有3條；
起始站S0148到終到站S0485耗時最少為87.5 min，耗時最少的最優路線有10條與轉乘次數最少的最優路線相同；
起始站S0087到終到站S3676耗時最少為33 min，耗時最少的最優路線有1條與轉乘次數最少的最優路線相同；
3） 最少費用的最優路線
起始站S3359到終到站S1828的最少費用為3元，最少費用的最優路線（所需時間較短，轉乘次數較少的路線）有2條；
起始站S1557到終到站S0481的最少費用為3元，最少費用的最優路線有17條；
起始站S0971到終到站S0485的最少費用為5元，最少費用的最優路線有20條；
起始站S0008到終到站S0073的最少費用為2元，最少費用的最優路線有1條；
起始站S0148到終到站S0485的最少費用為5元，最少費用的最優路線有10條；
起始站S0087到終到站S3676的最少費用為2元，最少費用的最優路線有1條；
在此種情況下，我們就只考慮可以通過地鐵站換乘的情況，不通過地鐵站的情況即為模型1的求解結果。模型2的求解結果見附件1。
6．3．1模型三的建立
該模型針對問題三，將步行方式考慮在了出行方式當中，更符合實際。因為當出發點與換乘點、終點站或轉乘站與轉乘站之間只相隔幾個站時，當然該段選擇步行方式更優。
因此作出如下假設：
一、如果存在某段路線，其兩端點站之間相隔站點數小等於2（即至多經過4個站點），則該段線路選擇步行方式到達目的地。其他的情況用模型二來處理。其中路線的兩端點站之間相隔站點數是根據公交直達換乘路線來確定的。
二、相鄰公交站點（包括地鐵站）間平均步行時間為5分鍾。
三、如果在公汽線路上選擇步行，則公汽間換乘次數減少1；如果在地鐵線路上選擇步行，則地鐵間換乘次數減少1，直達線路除外。
直達和轉乘一次、兩次的路線需要步行的路段示意圖如圖6.5所示。圖中（a）表示出發點A與終點站B間能直達，相隔的站點數等於2所以選擇步行；圖中（b）表示出發點A與終點站B間通過一次換乘能到達，其中路段AC的站點數等於2所以選擇步行,同樣如果CB路段的站點數小等於2，則也採取步行的方式；圖中（c）選擇步行方式的依據類似。

圖6.5 步行示意圖
是否選擇步行方式的函數：
（6.8式）
其中 表示第m路公交路線是否步行， 表示第n路地鐵線路是否步行；
對於直達路線，如果出發點與終點站之間相隔站點數小等於2則步行，否則乘車。對於需要轉乘的路線的最優路線模型討論如下：
1）以時間最短的路線作為最優路線的模型：路線總時間等於乘車時間加上步行時間，再加上轉乘時間。
（6.9式）
其中，第k路線為同時考慮公汽與地鐵的轉乘路線中的一種或幾種。
2）以轉乘次數最少的路線作為最優路線的模型：每步行一次就少換乘一次車。
（6.20式）
此模型等效為以上轉乘路線按直達、轉乘一次、兩次、三次（包括公交與地鐵間的轉乘）的優先次序來考慮。
3）以費用最少的路線作為最優路線的模型：
（6.21式）
其中， 仍滿足（6.4式）。

七 模型的優缺點及改進
7.1模型的評價
7.1.1 模型優點
1、模型是由簡單到復雜一步步建立的，使得更貼近實際。
2、本文的模型簡單，其演算法直觀，容易編程實現。
3、本文模型比較注重數據的處理和存儲方式，大大提高了查詢效率。
4、本文模型注重效率的提高，通過大量的特徵信息的提取，並結合有效的演算法，使其完全可以滿足實時系統的要求。

7.1.2 模型缺點
在建模與編程過程中，使用的數據只是現實數據的一種近似，因而得出的結果可能與現實情況有一定的差距。

7.2 模型的改進
以上模型主要是從公交線路出發，尋找公交線路的交叉站作為換乘站點，進而找出經過任意兩個站點的可能乘車路線。我們也可以從公交站點的角度出發，用圖論的方法建立有向賦權圖（如圖7.1所示），此向賦權圖是針對問題三建立的圖論模型，問題一、問題二隻是此模型的簡化。圖7.1中 表示公汽線路標號，該線路是公汽線路 的上行線或下行線， 、 、 、 、 、 是公汽線路 上的站點標號； 表示地鐵線路標號，該地鐵線路是雙向行駛的， 、 、 、 、 是地鐵線路 上的站點標號；公汽 與地鐵 可以在公汽站 和地鐵站 間換乘。如果圖7.1中的地鐵線路替換成公汽線路，為了表示公汽間換乘所需的時間或者費用，應將同一個換乘站點用兩個站點來表示。

圖7.1 公交線路的有向賦權圖
根據不同的目標,給不同的站點間的邊賦上不同的權值。然後利用圖論的相關演算法,找出相應的最短路徑。
1）當以時間最短為目標時，給每條邊賦上時間的權值。給同一線路上任意兩個站點間的邊賦值時，其權值等於站點間的公交線路段數與平均時間的乘積。當某段線路的兩段點間間隔站點數小等於3時，選擇步行，該線路的權值等於步行時間。不同公汽和地鐵間進行換乘時需要賦給不同的權值，以表示換乘時間。
例如（如圖7.1）：
當j>4時， 到 的邊權值 ；，
從 到 不需要的轉車，但根據假設應選擇步行，其邊權值 ；，
從 到 要麼乘公交，然後轉車，要麼步行，根據步行的假設條件， 到 的站點間隔數小於2，因此選擇步行，其邊權值 ；，
當g>4時， 與 之間的邊權值 ；，
到 的邊權值 ；
到 的邊權值 ；
當j>4、g>4時， 到 的路徑長度為：
；
當 、g>4時，則從 到 選擇步行，再乘地鐵到 ，其路徑長度為； ；
找出任意兩點間可行路線的路徑長度後，再搜索出其中的最短路徑的的可行路線作為時間的最優路線。
2）當以費用最省為目標時，則給每條邊賦上費用的權值。
公汽站點間的邊權按（6.4式）賦值。
當公汽線路 按單一票價計費，對於 上任意兩個公汽站點 和 間，
若 ，則選擇步行 ；若 ，則 ；
當公汽線路 按分段計價，若 ，則 ；若 ，則 ；若 ，則 ；若 ，則 ；
地鐵線路 上任意兩個站點 和 間，若 ，則選擇步行 ；若 ，則 ；換乘站點 與 間的邊權值均為0，即 ；則從 通過站點 換乘 到 的一條可行路線的路徑長度為：
若 ， ，則從 到 選擇步行， ；
若 ， ，則 ；
同樣可以找出任意兩點間可行路線的路徑長度，然後再搜索出最短路徑作為費用的最優路線。

『拾』 淺談matlab在高新領域的應用和作用有哪些

摘要 用於數值計算、可視化和應用程序開發的高級語言