學校超市選址問題課程設計


問題描述
對于某一學校超市，其他各單位到其的距離不同，同時各單位人員去超市的頻度也不同。請為超市選址，要求實現(xiàn)總體最優(yōu)。
1、需求分析
核心問題: 求最短路徑(選址的要求就是超市到各單位權(quán)值之和最少)
數(shù)據(jù)模型（邏輯結(jié)構(gòu)）: 帶權(quán)有向圖 (權(quán)值計算: 距離*頻度)
存儲結(jié)構(gòu): typedef struct
{
string vexs[MAX_VERTEX_SIZE];
int arcs[MAX_VERTEX_SIZE][MAX_VERTEX_SIZE];
int vexnum;// ,arcnum;
}MGraph;
核心算法: Floyd算法(弗洛伊德算法-每一對頂點之間的最短路徑)
輸入數(shù)據(jù): 各單位名稱，距離，頻度，單位個數(shù)．
輸出數(shù)據(jù): 所選單位名稱．
總體思路:　如果超市是要選在某個單位，那么先用floyd算法得出各頂點間的最短距離/最小權(quán)值。
假設頂點個數(shù)有n個，那么就得到n*n的一張表格，arcs(i,j)表示i單位到j單位的最短距離/最小權(quán)值 , 這張表格中和最小的那一行(假設為第t行)，那么超市選在t單位處就是最優(yōu)解。
運行環(huán)境
DEV-C++
2、概要設計
　Floyd算法利用動態(tài)規(guī)劃思想，通過把問題分解為子問題來解決任意兩點見的最短路徑問題。設G=(V, E, w)是一個帶權(quán)有向圖，其邊V={v1, v2, …, vn}。對于k≤n，考慮其結(jié)點V的一個子集。對于V中任何兩個結(jié)點vi、vj，考慮從vi到vj的中間結(jié)點都在vk中的所有路徑，設是其中最短的，并設的路徑長度為。如果結(jié)點vk不在從vi到vj的最短路徑上，則；反之則可以把分為兩段，其中一段從vi到vk，另一段從vk到vj，這樣便得到表達式。上述討論可以歸納為如下遞歸式：