公園的導(dǎo)游圖

1、 用C+語言設(shè)計一個公園的導(dǎo)游圖 第26頁 共26頁 用C+語言設(shè)計一個公園的導(dǎo)游圖摘 要 現(xiàn)實生活中，常常會遇到求最短路徑的問題。本課程設(shè)計旨在提供一種解決這類問題的實例，把某一公園的景點與路線抽象成頂點和邊，從而構(gòu)成圖，進而解決一系列相關(guān)的最短路徑，最佳路線等問題。在課程設(shè)計中，系統(tǒng)開發(fā)平臺為Windows XP，程序設(shè)計設(shè)計語言采用C+，程序運行平臺為Windows 98/2000/XP。對于求解最短路徑，使用了著名的Dijkstra算法。對于求最佳路徑，采用了常用于解決TSP問題的貪心法。程序通過調(diào)試運行，初步實現(xiàn)了設(shè)計目標，并且經(jīng)過適當(dāng)完善后，這一導(dǎo)游圖系統(tǒng)將同樣適用于其他公園。關(guān)鍵

2、詞 程序設(shè)計；數(shù)據(jù)結(jié)構(gòu)；圖；最短路徑；Dijkstra算法；TSP問題1 引 言現(xiàn)實生活中，常常會遇到求最短路徑的問題，本課程設(shè)計將把這類問題實例化，把一個公園的景點頂點化、路徑邊化，建成一個圖，再通過比較對圖中各邊及頂點的關(guān)系，實現(xiàn)對公園各個景點進行訪問，并能根據(jù)要求，求出任意兩個頂點的最短路徑，還能給出一條依次不重復(fù)訪問各點的最短路徑?！具@部分應(yīng)寫明前人相關(guān)的研究成果、理論與實踐依據(jù)，內(nèi)容可包括研究的目的、意義、主要方法、范圍和背景等?！侩S著計算機科學(xué)的迅速發(fā)展，計算機已深入到揉社會的各個領(lǐng)域，它的應(yīng)用已不再局限于科學(xué)計算，以解決一些數(shù)學(xué)問題，而且可以解決一些抽象化的具體問題，更多地用于控

3、制，管理及數(shù)據(jù)處理等非數(shù)值計算的處理工作，這便為我們的日常生活提供了很多的方便，譬如說火車售票系統(tǒng)，學(xué)生成績管理，車廂調(diào)度等實際問題。如今程序設(shè)計的語言很多，有發(fā)展比較完善高級語言，也有最基本的低級語言，然而再好的程序設(shè)計也要有一個比較清晰的思路算法。為了編寫好一個好程序，必須分析待處理對象的特性以及各處理對象之間的關(guān)系，于是數(shù)據(jù)結(jié)構(gòu)便成為我們絕佳的選擇。數(shù)據(jù)結(jié)構(gòu)是計算機程序設(shè)計的重要理論技術(shù)基礎(chǔ)，它不僅是計算機科學(xué)的核心課程，而且已成為其他理工專業(yè)的熱門選修課。2程序的功能需求分析2. 1 程序的功能分析一個公園的導(dǎo)游圖，至少應(yīng)該有一個簡單的景點分布圖，讓游客能對公園概況一目了然。其次，應(yīng)該

4、能提供相關(guān)的景點信息：包括景點名稱，景點簡介等。以上功能是基礎(chǔ)，在此基礎(chǔ)上，使公園的導(dǎo)游圖系統(tǒng)更具人性化，更具有實用性：為導(dǎo)游圖系統(tǒng)添加景點最短路徑的計算，提供依次不重復(fù)訪問所有景點的最佳旅游路線。2.2 菜單項及其基本操作擁有了完整的功能的導(dǎo)游圖系統(tǒng)，還需要有清爽，簡易的操作界面，讓游客一目了然，操作方便。本導(dǎo)游圖用數(shù)字鍵的選擇方式，加以提示，提供給用戶如圖2.1的簡單方便的操作。圖2.1 抽象化的公園導(dǎo)游圖至此，已經(jīng)規(guī)劃好導(dǎo)游圖系統(tǒng)的功能和操作的基本構(gòu)架，下一步就是著手為每一個操作的實現(xiàn)做程序?qū)崿F(xiàn)的考慮了。3 程序的算法分析要完成對整個導(dǎo)游圖系統(tǒng)的功能實現(xiàn)，需要對的每一項功能都有清楚的設(shè)想

5、和認識，了解并明確每一項功能的實現(xiàn)需要解決的問題，選擇正確并且高效的算法把問題逐個解決，最終實現(xiàn)程序的正確調(diào)試運行。為此，可把系統(tǒng)分為以下幾個核心：圖的初始化、圖的遍歷、求兩點間的最短路徑、求最佳路線。3.1 圖的初始化圖是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，表現(xiàn)在不僅各個頂點的度可以相差很多，而且頂點之間的邏輯關(guān)系鄰接關(guān)系也錯綜復(fù)雜1。從圖的定義可知，一個圖包括兩部分信息：頂點的信息以及描述頂點之間關(guān)系（邊或?。┑男畔?。圖的初始化是所有相關(guān)操作的基礎(chǔ)，其存儲結(jié)構(gòu)將直接影響到程序的實現(xiàn)的難易度、空間性能和時間性能，因此選擇適合本次程序的存儲結(jié)構(gòu)至關(guān)重要。圖的存儲結(jié)構(gòu)有鄰接矩陣、鄰接表、十字鏈表、鄰接多重表、邊

6、集數(shù)組等多種，較常用的有鄰接矩陣和鄰接表，而這兩者的存儲方式的比較如表3-1。表3-1 鄰接矩陣與鄰接表存儲結(jié)構(gòu)的比較存儲方式空間性能比較時間性能比較唯一性比較鄰接矩陣O(n2)O(n2)唯一鄰接表O(n+e)O(n+e)非唯一圖的鄰接矩陣和鄰接表存儲各有利弊，應(yīng)用時要根據(jù)圖的稠密和稀疏程度以及問題的需求進行選擇2。仔細比較這兩種存儲方式容易知道，由于鄰接矩陣特殊的存儲方式，如圖2.2所示，它非常便于快速的查找兩個頂點之間的邊上的權(quán)值。所以，圖采用帶權(quán)的鄰接矩陣存儲。V2V1V4V3V04375792Vertex5 =V0V1V2V3V495734Arc55=937254772圖3.1 無向圖

7、及其鄰接矩陣存儲示意圖決定了圖的存儲方式后，需要有一個公園的實例，本程序選擇本人所在地的姑婆山國家森林公園的游覽地圖作為藍本，把公園地圖抽象化成頂點與邊構(gòu)成的圖形式，如圖3.2，途中紅色數(shù)字代表線的權(quán)值。150346725132432413223圖3.2 抽象化的公園導(dǎo)游圖3.2 圖的遍歷圖的遍歷是圖中最基本的操作。圖的遍歷是指從圖中某一頂點出發(fā)，對圖中所有頂點訪問一次且僅訪問一次。導(dǎo)游圖需要把每條路徑的信息都向游客展示，就需要讀取每兩個頂點間的路徑信息。由于采用了帶權(quán)的鄰接矩陣存儲結(jié)構(gòu)進行存儲，所以需要針對這一存儲結(jié)構(gòu)對路線進行遍歷操作。其遍歷算法如圖3.3所示，執(zhí)行效果如圖3.4所示。選擇

8、圖片控件For循環(huán)語句（i=0；i<頂點數(shù)；i+）NFor循環(huán)語句(j=0;j<i;j+)YYNY開始結(jié)束如果路徑存在輸出該路徑信息N圖3.3 圖的遍歷算法流程圖第一次循環(huán)第二次循環(huán)第三次循環(huán)第四次循環(huán)V2V1V4V3V04375792 圖3.4 圖的遍歷算法執(zhí)行效果示意圖3.3 最短路徑（Dijkstra算法）基于本程序中圖的存儲是鄰接矩陣結(jié)構(gòu)存儲的圖結(jié)構(gòu)，因而采用適合該存儲結(jié)構(gòu)的Dijkstra算法用于解決求最短路徑的問題。迪杰斯特拉（Dijkstra）提出了一個按路徑長度遞增的持續(xù)產(chǎn)生最短路徑的算法，其基本思想是：設(shè)置一個集合S存放已經(jīng)找到最短路徑的頂點，S的初始狀態(tài)只包含源

9、點v，對于viV-S，假設(shè)從源點v到vi的有向邊為最短路徑。以后每求得一條最短路徑v，vk，就將vk加入集合S中，并將路徑v，vk，vi，與原來的假設(shè)相比較，取路徑長度較小者為最短路徑。重復(fù)上述過程，直到集合V中全部頂點加入到集合S中。如圖3.5所示。集合S集合V-SVVkVi圖3.5 圖的遍歷算法執(zhí)行效果示意圖輔助數(shù)組distn：元素disti表示當(dāng)前找到的從源點到終點vi的最短路徑的長度。初態(tài)為:若從v到vi有弧，則disti為弧上的權(quán)值；否則置disti為。若當(dāng)前求得的終點為vk,則根據(jù)下式進行迭代：disti=mindisti,distk+arcki 1in輔助數(shù)組pathn:元素pa

10、thi是一個串，表示當(dāng)前所找到的從源點到終點vi的最短路徑。初態(tài)為：若從v到vi有弧，則pathi為“vvk”，否則置pathi為空串。數(shù)組sn：存放源點和已經(jīng)生成的終點（即集合S），初態(tài)為只有一個源點v。算法的偽代碼描述是：1.初始化數(shù)組dist、path和s；2.while（s中的元素個數(shù)<n）2.1 在distn中求最小值，其下標為k（則vk為正在生成的終點）；2.2 輸出distj和pathj；2.3 修改數(shù)組dist和path;2.4 將頂點vk添加到數(shù)組s中；3.4 最佳訪問路線（貪心法）在解決最佳訪問路線問題時，不得不提到TSP問題。所謂的TSP問題就是指旅行家要旅行n個城

11、市，要求各個城市經(jīng)歷且僅經(jīng)歷一次，并要求所走的路程最短，最后返回到出發(fā)點。該這個又稱貨郎擔(dān)問題、郵遞員問題，是圖問題中最廣為人知的問題。對于TSP問題，一種最容易想到，也肯定能得到最佳解的算法是窮舉法，即考慮所有可能的旅游路線，從中選擇最佳的一條。但是用窮舉法求解TSP問題的時間復(fù)雜度為O（n?。?，當(dāng)n大到一定程度后是不可解的3。在這里就引出解決此問題的一個經(jīng)典算法：貪心法。貪心法（ Greedy algorithm ，直譯：貪心算法） 是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)（即最有利）的選擇，從而希望導(dǎo)致結(jié)果是最好或最優(yōu)的算法。比如在旅行推銷員問題中，如果旅行員每次都選擇最近的城市

12、，那這就是一種貪心算法4。因此貪心法非常適合程序的最佳旅游路徑的求解。貪心法可以解決一些最優(yōu)性問題，如：求圖中的最小生成樹、求哈夫曼編碼對于其他問題，貪心法一般不能得到我們所要求的答案。一旦一個問題可以通過貪心法來解決，那么貪心法一般是解決這個問題的最好辦法。由于貪心法的高效性以及其所求得的答案比較接近最優(yōu)結(jié)果，貪心法也可以用作輔助算法或者直接解決一些要求結(jié)果不特別精確的問題。對于大部分的問題，貪心法通常(但不一定)都不能找出最佳解, 因為他們一般沒有測試所有可能的解。貪心法容易過早做決定, 因而沒法達到最佳解。然而，貪心法的好處在于容易設(shè)計和很多時能達到好的近似解5。本程序的最佳路線問題的解

13、決辦法，就采用這種求近似最優(yōu)解的算法。貪心法算法用偽代碼描述如下：1.任意選擇某個頂點v作為出發(fā)點；2.執(zhí)行下述過程，直到所有點都被訪問：v= 最后一個被訪問的頂點； 在頂點v的鄰接點中查找距離頂點v最近的未被訪問的鄰接點j； 訪問頂點j；3.從最后一個訪問的頂點回到出發(fā)點v；以圖3.2為導(dǎo)游圖系統(tǒng)實例代入后，最佳路線的算法按照如圖3.6所示的方式進行圖的頂點遍歷。150346725132432413223最佳路徑長度：1+5+2+3+2+1+3+2=19最佳路徑：(0)-(1)-(5)-(7)-(3)-(6)-(4)-(2)-(0)圖3.6 實際最佳路徑及路徑長度4程序的運行與測試4.1程序

14、運行初始界面程序運行，后臺對圖結(jié)構(gòu)進行初始化，運行結(jié)果如圖4.1。圖4.1 最短路徑算法正確輸出實現(xiàn)4.2查看公園地圖公園地圖的查看，輸出用cout語句建立的公園地圖。圖4.2 公園地圖4.3查看路程信息遍歷圖的所有路徑并依次輸出路徑信息。圖4.3 所有邊的信息4.4 求最短路徑根據(jù)用戶要求，求始點到終點的最短路徑信息和所有路徑信息。如圖4.4和4.5所示。圖4.4 兩景點間的最短路徑圖4.5 始發(fā)點到所有景點的最短路徑4.4 求最佳路徑為游客提供一條可以依次不重復(fù)地游覽所有景點并最終回到起點的最短路徑。4.5 退出用break實現(xiàn)程序退出。5 存在的不足與對策由于設(shè)計者水平有限，本導(dǎo)游圖系統(tǒng)

15、的功能還比較簡單，還有一些好的設(shè)想沒有實現(xiàn)：比如添加管理模式，使得公園管理人員能夠同樣方便的更改導(dǎo)游圖，因此更改這一導(dǎo)游圖還必須在程序員的幫助下進行。另外，本導(dǎo)游圖系統(tǒng)還有一定的局限性，如果存在只有一條通路的景點，導(dǎo)游圖將無法求得最佳旅游路徑。公園的導(dǎo)游圖系統(tǒng)的這些不足請老師多多諒解。今后我會更多的學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的相關(guān)知識，更深刻地理解圖的基本操作，不斷提升認識，提高編程技巧，借以不斷地提高程序設(shè)計水平。參考文獻1 朱戰(zhàn)立. 數(shù)據(jù)結(jié)構(gòu)使用C+語言. 西安：西安電子科技大學(xué)出版社，20012王紅梅，胡明，王濤. 數(shù)據(jù)結(jié)構(gòu)(C+版). 北京：清華大學(xué)出版社，20053馬春江，李慧勇，孟繁軍. 新編數(shù)

16、據(jù)結(jié)構(gòu)教程. 北京：中國電力出版社，20064貪心法_維基百科. 維基百科，/wiki/%E8%B4%AA%E5%BF%83%E6%B3%95：2008-9-045田魯懷. 數(shù)據(jù)結(jié)構(gòu). 北京：電子工業(yè)出版社，2006附錄 A 用C+語言設(shè)計一個公園的導(dǎo)游圖/ 程序名稱：ParkGuide.h/ 程序功能：程序的變量及函數(shù)聲明#ifndef PARKGUIDE_H /定義頭文件#define PARKGUIDE_H #include<string> /引入標準庫中的頭文件using namespace std; const int MaxS

17、ize=12; /圖中最多頂點個數(shù)template <class T>class ParkGuidepublic: ParkGuide(int* a, T* v,int n); /構(gòu)造函數(shù)，初始化具有n個頂點的圖 ParkGuide( )  /析構(gòu)函數(shù) void Dijkstra( int v,int endv);/最小距離 void PutOutArcInfo(); /輸出路徑void TSP(int v); /求最優(yōu)路徑private: T vertexMaxSize; /存放圖中頂點的數(shù)組 int arcMaxSizeMaxSize;  /存放圖中邊的數(shù)組

18、 int vertexNum; /圖的頂點數(shù)和邊數(shù) ;#endif/ 程序名稱：ParkGuideMain.cpp/ 程序功能：程序的#include <iostream>#include <string> /引入標準庫中的頭文件#include "ParkGuide.cpp"    /引用 ParkGuide.cpp 文件#include "TSP.cpp"     /引用解決最佳旅游路線的TSP文件using namespace std;int main(i

19、nt argc, char* argv) const int numv = 8; /頂點數(shù)int control=1;    /控制 int which;  /功能選擇變量string name;  /插入頂點的值int bordernumvnumv=  /按鄰接矩陣確定頂點的權(quán)值10000,1,2,2,10000,10000,10000,10000, /0號景點1,10000,10000,10000,10000,5,10000,10000,/1號景點2,10000,10000,3,3,10000,4,10000, /2號景點2,10000,3

20、,10000,10000,3,2,3, /3號景點10000,10000,3,10000,10000,10000,1,10000,/4號景點10000,5,10000,3,10000,10000,5,2, /5號景點10000,10000,4,2,1,5,10000,4, /6號景點10000,10000,10000,3,10000,2,4,10000  /7號景點; string vnamenumv="公園正門","牛頭寨","梅園山莊","方家茶園","情人林","獼猴園

21、","仙姑瀑布","仙姑廟" /初始化各頂點 int* p; /定義指針pstring* q; /定義指針qp = &border00; /p指針指向cost數(shù)組的起始位置q = vname;  /q指針指向vname數(shù)組ParkGuide<string> g(p, q, numv ); /調(diào)用Graph程序 while ( control=1 ) /控制cout<<" * "<<endl;cout<<" *歡迎您到姑婆山國家森林公園* "

22、<<endl;cout<<"*"<<endl;cout<<"*請選擇你想要進行的操作： *"<<endl;cout<<"*1、查看公園地圖*"<<endl;cout<<"*2、查看路程信息*"<<endl;cout<<"*3、提供游覽景點的最短路徑*"<<endl;cout<<"*4、提供游覽公園的一種最佳路徑*"<<en

23、dl;cout<<"*5、退出*"<<endl;cout<<"*"<<endl; cin >> which; switch( which )  /功能選擇 case 1: /輸出圖的各頂點的值cout<<" 公園地圖 "<<endl;cout<<" <7> 仙姑廟   "<<endl;cout<<" . . .  "<&

24、lt;endl;cout<<" . . .  "<<endl;cout<<" <6> 仙姑瀑布 . <5>獼猴園 "<<endl;cout<<" . . . . . . "<<endl;cout<<" . . . . . . "<<endl;cout<<" <4> 情人林 . . . . . "<<endl;cout<<

25、" . . <3>方家茶園 . "<<endl;cout<<" . . . . . "<<endl;cout<<" . . . . "<<endl;cout<<" <2>梅園山莊 . <1> 牛頭寨 "<<endl;cout<<" . . . "<<endl;cout<<" . . . "<<endl;cout

26、<<" <0> 正 門 "<<endl; break; case 2: /輸出圖中的路徑 int i; int j; cout<<"所有的邊的信息為:"<<"n" try g.PutOutArcInfo(); catch(char*) cout<<"輸出不正確！"<<endl; break; case 3: /求最短路徑 cout<<"請輸入您所在景點序號:"<<"n"

27、 int vv ; cin>>vv; cout<<"請輸入您想到的景點序號，若要全部顯示請輸入9:"<<"n" int vvt ; cin>>vvt; try g.Dijkstra(vv,vvt); catch(char*) cout<<"輸出頂點不正確！"<<endl; break; case 4: cout<<"本公園為您提供的最佳旅游路線是："<<"n" g.TSP(0); /求最優(yōu)旅游路線 b

28、reak; case 5: /退出 control=0; cout<<""<<endl; cout<<"謝謝使用,祝您旅途愉快!"<<endl; cout<<""<<endl; break; default:cout<<"對不起，輸入錯誤，請重新輸入!"<<endl<<endl<<endl; return 0;/ 程序名稱：ParkGuide.cpp/ 程序功能：完成游戲的初始化、對鼠標響應(yīng)及判斷

29、游戲是否完成功能#include<iostream>#include <string> /引入標準庫中的頭文件#include "ParkGuide.h" /引入頭文件using namespace std;/* 前置條件：圖不存在 輸入：無 功能：圖的初始化 輸出：無 后置條件：構(gòu)造一個有值的圖*/template <class T>ParkGuide<T>:ParkGuide(int* a,T* v, int n ) /構(gòu)造圖 int i,j; vertexNum=n; /頂點數(shù) for (i=0; i<MaxSiz

30、e; i+) /初始化鄰接矩陣 for (j=0; j<MaxSize; j+) /定義邊 arcij = 10000; for ( i=0; i<vertexNum; i+) vertexi=vi; /存儲頂點信息 for (i=0; i<vertexNum; i+) /給邊賦置 for (j=0; j<vertexNum; j+) arcij=*(a+i*n+j); int tt=0; /* 前置條件：圖已存在 輸入：無 功能：輸出圖中所有的路徑 輸出：圖中所有頂點的數(shù)據(jù)信息 后置條件：圖保持不變*/template <class T>void Park

31、Guide<T>:PutOutArcInfo() /輸出圖中所有的路徑 int i=0; /假設(shè)源點是第0個頂點，即頂點序號是0 int j=0;if ( i>vertexNum| j>vertexNum) throw "位置" /錯誤拋出異常 else for(i=0;i<vertexNum;i+) /輸出任意兩點之間的路徑 for(j=0;j<i;j+) if(arcij<10000) /兩點之間存在路徑 cout<<"從 "<<vertexi<<" 到 &quo

32、t;<<vertexj<<" 的路程為："<<arcij<<"公里n" /若兩點間有路，則輸出該兩點間的路徑 /* 前置條件：圖已存在 輸入：頂點v ，endv 功能：假如endv存在，求v到endv的最短路徑；假如不輸入endv，則求v到任意頂點的最短路徑 輸出：所求得的最短路徑及所經(jīng)歷的位置 后置條件：圖保持不變*/template <class T>void ParkGuide<T>:Dijkstra(int v,int endv) /求從v頂點到endv點的最短路徑 if (

33、 v>vertexNum) throw "位置" /v頂點或endv頂點輸出不正確則拋出異常 int numv=vertexNum; /頂點數(shù) int distMaxSize; /最短長度 int pathMaxSize; /當(dāng)前找到的最短路徑 int sMaxSize; /存放源點和已生成的終點的集合 int max= 10000; /代表無窮大 int i,j,k,wm; for(i=0;i<numv;i+) /按網(wǎng)的鄰接矩陣確定各頂點最短路徑的初值 disti=arcvi; if(i!=v&& disti< max) /如果v、i之間

34、有路 pathi=v; /當(dāng)前找到的最短路徑為v else pathi=-1; /否則v與i頂點不存在路徑 si = 0; /給s集合確定初值0 sv=1;distv=0; /將頂點v本身排除在外 for(k =0;k<numv-1;k+) /求其他numv-1各頂點的最短路徑 wm = max;j=v; /確定當(dāng)前最短路徑wm及頂點的序號j for( i=0;i<numv;i+) if(!si&&disti<wm) /如果v、i之間有路 j=i;wm = disti; /把當(dāng)前找到的路徑確定為最大值 sj=1; for(i =0;i<numv;i+)

35、/更新未確定最短路徑各頂點的當(dāng)前最短路徑 if(!si&&distj+arcji<disti) /如果v、i兩點的距離加上i、j小于從v點到j(luò)點的距離 disti=distj+arcji;pathi=j; /disti取最小值 if (endv < numv && endv >=0 ) /endv點存在 string mmm="" /初始化字符串 int j =endv; while(j > -1 ) string nnn = vertexj; /依次把頂點存放在nnn字符串中 nnn+=mmm; mmm = &quo

36、t; "+nnn; j = pathj; cout<<"從 "<<vertexv.c_str()<<" 到 "<<vertexendv.c_str()<<" 的最短路程為："<<distendv<<"公里 途經(jīng)："<<mmm.c_str()<<"n"/輸出從v點到endv點的最短路徑 else /endv點不存在for(i=0;i<numv;i+) string mmm=&

37、quot;" /初始化字符串 int j =i; while(j > -1 ) string nnn = vertexj; /依次把頂點存放在nnn字符串中 nnn+=mmm; mmm = " "+nnn; j = pathj; cout<<"從 "<<vertexv.c_str()<<" 到 "<<vertexi.c_str()<<" 的最短路程為："<<disti<<"公里 途經(jīng)："<<mmm.c_str()<<"n"/輸出從v點到任意點的最短路徑 / 程序名稱：TSP.cpp/ 程序功能：解決導(dǎo)游圖的TSP問題：求不重復(fù)地訪問每一個并回到起點的最短路徑#include<iostream>#include <string> /引入標準庫中的頭文件#include "ParkGuide.h" /引入頭文件using namespace std;/* 前置條件：圖已存在 輸入：起點 功能：用貪心法進行圖的遍歷 輸出：所求得的最優(yōu)路徑及所經(jīng)歷的位置 后置條件：圖保持不變*