學(xué)校超市選址問題課程設(shè)計(jì)


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