liyanzi
一般會員
發表:51 回覆:45 積分:19 註冊:2005-01-24
發送簡訊給我
|
想請問各位大大~~我現在是在寫最短路徑的程式 不過是判斷連接的道路是分叉點的話~~看哪條最短就往哪條走,不過結果卻不會是最短的。。 比如說~~1->2->3->4有四條路, 1 ↗ 2 → 4
?↘ 3 ↗ 要求1->4最短的, 1->2的距離為20,2->4的距離為130
1->3的距離為30,3->4的距離為20 現在我所做的路徑~~會變成1->2->4,總距離為150,很明顯應該錯誤了 但結果應該是要1->3->4,想請問各位大大有解決的方法嗎?
|
RedSnow
版主
發表:79 回覆:1322 積分:845 註冊:2003-12-15
發送簡訊給我
|
liyanzi 妳好: 妳至少也得將妳現在寫的相關程式敘述貼上來,這樣子才能讓有心幫忙的人暸解問題是出在那裡啊? 7 天天敲鍵盤 v 時時按滑鼠 8
|
liangnet
中階會員
發表:19 回覆:148 積分:83 註冊:2004-01-03
發送簡訊給我
|
有一種演算法叫A*,可以解決你的問題。 我先大概說一下。
一開始位置在1,有二條路徑可移動,先選擇2。
移動到2後,計算剛從1到2的距離,並且記錄在2的位置。
[2] = 20 移到2後,再往下一個位置移動,移到4,計算2到4的距離,並且加上2位置的值。
130 20 = 150
[4] = 150 移動到4後,因無下一個位置,就往後退到2,2也因為無再下一個位置,而退到1。 1到3,在3的位置記錄距離。
[3] = 30 3移到4,計算距離20 30 = 50
因為4位置已經有記錄值(表示有搜尋過),因此和4的位置記錄值比較,如果小於
該值,則將取代,[4] = 50,並且繼續搜尋下去。反之如果是大於,就退後,不
進行搜尋4後的路徑。 最後得到的資料如下
[1] = 0
[2] = 20
[3] = 30
[4] = 50 0 ↗ 20 → 50
?↘ 30 ↗
由4的位置開始往後找最小值。
4 -> 2 -> 1
這樣就求出最短路徑了。 發表人 - liangnet 於 2005/07/25 19:31:38
|
liyanzi
一般會員
發表:51 回覆:45 積分:19 註冊:2005-01-24
發送簡訊給我
|
DList *find_Bestroad(DList *pointer, String end_road
{
DList *temp[ 10 ] ;
int temp_count = 0 ;
for ( int i = 0; i < 10; i )
temp[ i ] = new DList ;
creat_Memo( pointer -> roadname ) ;//印出起始路名
while ( pointer -> road_numeral != 0 || pointer -> an_road_numeral != 0 )//當一字串裡兩條路的距離都等於0時,就等於終點
{
if ( pointer -> roadname == end_road )
break ;
else if ( pointer -> road_numeral != 0 && pointer -> an_road_numeral != 0 )
{//這個判斷是選擇兩條路中一條最短的路徑
if ( pointer -> road_numeral > pointer -> an_road_numeral )
{
temp[ temp_count ] = pointer -> road ;
delete_road[ temp_count ] -> roadname = pointer -> roadname ;
temp[ temp_count ] -> num = all_num pointer -> road_numeral;
all_num = all_num pointer -> an_road_numeral ;//算出目前的總距離
pointer = pointer -> an_road ;//指向下一個道路,以便繼續搜尋
creat_Memo( pointer -> roadname ) ;
}
else
{
temp[ temp_count ] = pointer -> an_road ;
delete_road[ temp_count ] -> roadname = pointer -> roadname ;
temp[ temp_count ] -> num = all_num pointer -> an_road_numeral ;
all_num = all_num pointer -> road_numeral ;//算出目前的總距離
pointer = pointer -> road ;//指向下一個道路,以便繼續搜尋
creat_Memo( pointer -> roadname ) ;
}
}
else if ( pointer -> an_road_numeral == 0 )
{
all_num = all_num pointer -> road_numeral ;//算出目前的總距離
pointer = pointer -> road ;//指向下一個道路,以便繼續搜尋
creat_Memo( pointer -> roadname ) ;
}
else if ( pointer -> road_numeral == 0 )
{
all_num = all_num pointer -> an_road_numeral ;//算出目前的總距離
pointer = pointer -> an_road ;//指向下一個道路,以便繼續搜尋
creat_Memo( pointer -> roadname ) ;
}
}
*temp_road = *temp ;
counti = temp_count ;
return pointer ;
}
大大您好~~這是我目前寫判斷的程式!!關於要寫~~記錄的地方,能舉例子讓我改嗎?=.=" 發表人 - liyanzi 於 2005/07/25 15:56:28
|
taishyang
站務副站長
發表:377 回覆:5490 積分:4563 註冊:2002-10-08
發送簡訊給我
|
您好: PO程式碼的方式與版規說明請參考下面連結,煩請修改謝謝您的配合
>
|
RedSnow
版主
發表:79 回覆:1322 積分:845 註冊:2003-12-15
發送簡訊給我
|
liyanzi 妳好: 可否將 DList、delete_road、all_num....等相關宣告與用途資訊一併貼上來?並且說明一下妳在呼叫這個 find_Bestroad() 函式時,前後相關的程式敘述為何?總之請儘量提供完整或足夠的資訊,或者是將相關檔案打包上傳到 "會員求助程式檔案上傳區" 吧,這樣子比較方便做測試。 7 天天敲鍵盤 v 時時按滑鼠 8
|
liyanzi
一般會員
發表:51 回覆:45 積分:19 註冊:2005-01-24
發送簡訊給我
|
#include
#pragma hdrstop
#include "Unit1.h"
int all_num = 0, counti = 0, find_count ;
//counti用來計算字串陣列現在使用到哪裡
//all_num是用來計算總距離
#pragma argsused
//---------------------------------------------------------------------------
#pragma package(smart_init)
#pragma resource "*.dfm"
TForm1 *Form1;
//完整的路徑
struct DList
{
String roadname ;//用來存道路名稱
int num ;
int number ;//目前沒有用到
int road_numeral ;//用來存一條距離用的
int an_road_numeral ;//用來存另一條距離用的
DList *road ;//用來連接下一條道路用的
DList *an_road ;//用來連接另下一條道路用的
};
DList *head, *temp_road[ 10 ], *find_head, *find_temp[ 10 ] ;
struct Save_roadname
{
String roadname ;
Save_roadname *next ;
};
Save_roadname *save_head, *save_tail, *find_ptr, *delete_road[ 6 ] ;
//---------------------------------------------------------------------------
__fastcall TForm1::TForm1(TComponent* Owner)
: TForm(Owner)
{
} //---------------------------------------------------------------------------
void creat_combobox(String road)//從comboBox1所選擇的道路往下搜尋得到的道路新增到comboBox2的暫存字串裡
{
Save_roadname *pointer, *an_pointer ;
an_pointer = new Save_roadname ;
an_pointer -> roadname = road ;
an_pointer -> next = NULL ;
save_head -> roadname = save_head -> roadname ;
pointer = save_head ;
while ( pointer != NULL )
{
if ( pointer -> roadname == road || pointer -> roadname == "" )
break ;
else
{
if ( pointer -> next != NULL )
pointer = pointer -> next ;
else
break ;
}
}
if ( pointer -> next == NULL && pointer -> roadname != road )
{
if ( pointer -> roadname == "" )
pointer -> roadname = road ;
else
pointer -> next = an_pointer ;
}
}
//--------------------------------------------------------------------------- void creat_Memo(String road)//從comboBox1所選擇的道路往下搜尋得到的道路新增到comboBox2的暫存字串裡
{
Save_roadname *pointer, *an_pointer ;
an_pointer = new Save_roadname ;
an_pointer -> roadname = road ;
an_pointer -> next = NULL ;
save_head -> roadname = save_head -> roadname ;
pointer = save_head ;
while ( pointer != NULL )
{
if ( pointer -> roadname == road || pointer -> roadname == "" )
break ;
else
{
if ( pointer -> next != NULL )
pointer = pointer -> next ;
else
break ;
}
}
if ( pointer -> next == NULL && ( pointer -> roadname != road || pointer -> roadname == road ) )
{
if ( pointer -> roadname == "" )
pointer -> roadname = road ;
else
pointer -> next = an_pointer ;
}
}
//---------------------------------------------------------------------------
void printer_combobox()//將暫存的道路顯示在comboBox2上
{
Save_roadname *ptr ;
ptr = save_head ;
ptr -> roadname = ptr -> roadname ;
while ( ptr != NULL )
{
Form1 -> ComboBox2 -> Items -> Add( ptr -> roadname ) ;
if ( ptr -> next != NULL )
ptr = ptr -> next ;
else
break ;
}
}
//---------------------------------------------------------------------------
void printer_Memo()
{ }
//---------------------------------------------------------------------------
void Delete_road(String Delete)
{
Save_roadname *ptr ;
ptr = save_head ;
while ( ptr != NULL )
{
if ( ptr -> roadname == Delete )
{
ptr -> next = NULL ;
break ;
}
else if ( ptr -> next != NULL )
ptr = ptr -> next ;
else
break ;
}
}
//---------------------------------------------------------------------------
void find_endroad( DList *pointer, String start_road )
{
DList *temp[ 6 ], *ptr;//
int temp_count = 0 ;
save_tail = save_head ;
for ( int i = 0; i < 6; i )
temp[ i ] = new DList ;
ptr = pointer ;
while ( ptr -> road_numeral != 0 || ptr -> an_road_numeral != 0 )
{
if ( ptr -> road_numeral != 0 && ptr -> an_road_numeral != 0 )
{
if ( ptr -> roadname != start_road && ptr -> roadname != Form1 -> ComboBox1 -> Text )
creat_combobox( ptr -> roadname ) ;
temp[ temp_count ] = ptr -> an_road ;
temp[ temp_count-1] -> roadname = temp[ temp_count-1] -> roadname ;
ptr = ptr -> road ;
}
else if ( ptr -> an_road_numeral == 0 )
{
if ( ptr -> roadname != start_road && ptr -> roadname != Form1 -> ComboBox1 -> Text )
creat_combobox( ptr -> roadname ) ;
ptr = ptr -> road ;
}
else
{
if ( ptr -> roadname != start_road && ptr -> roadname != Form1 -> ComboBox1 -> Text )
creat_combobox( ptr -> roadname ) ;
ptr = ptr -> an_road ;
}
}
creat_combobox( ptr -> roadname ) ;
*temp_road = *temp ;
counti = temp_count ;
}
//---------------------------------------------------------------------------
DList *find_Bestroad(DList *pointer, String end_road )//以下是改良後的程式碼
{
DList *temp[ 10 ] ;
int temp_count = 0 ;
for ( int i = 0; i < 10; i )
temp[ i ] = new DList ;
creat_Memo( pointer -> roadname ) ;//先印出起始路名
while ( pointer -> road_numeral != 0 || pointer -> an_road_numeral != 0 )//當一字串裡兩條路的距離都等於0時,就等於終點
{
if ( pointer -> roadname == end_road )
break ;
else if ( pointer -> road_numeral != 0 && pointer -> an_road_numeral != 0 )
{//這個判斷是選擇兩條路中一條最短的路徑
if ( pointer -> road_numeral > pointer -> an_road_numeral )
{
temp[ temp_count ] = pointer -> road ;
delete_road[ temp_count ] -> roadname = pointer -> roadname ;
temp[ temp_count ] -> num = all_num pointer -> road_numeral;
all_num = all_num pointer -> an_road_numeral ;//算出目前的總距離
pointer = pointer -> an_road ;//指向下一個道路,以便繼續搜尋
creat_Memo( pointer -> roadname ) ;
}
else
{
temp[ temp_count ] = pointer -> an_road ;
delete_road[ temp_count ] -> roadname = pointer -> roadname ;
temp[ temp_count ] -> num = all_num pointer -> an_road_numeral ;
all_num = all_num pointer -> road_numeral ;//算出目前的總距離
pointer = pointer -> road ;//指向下一個道路,以便繼續搜尋
creat_Memo( pointer -> roadname ) ;
}
}
else if ( pointer -> an_road_numeral == 0 )
{
all_num = all_num pointer -> road_numeral ;//算出目前的總距離
pointer = pointer -> road ;//指向下一個道路,以便繼續搜尋
creat_Memo( pointer -> roadname ) ;
} }
*temp_road = *temp ;
counti = temp_count ;
return pointer ;
}
//--------------------------------------------------------------------------- void __fastcall TForm1::FormCreate(TObject *Sender)
{
for ( int i = 0; i < 6; i )
delete_road[ i ] = new Save_roadname ;
head = new DList ;//先將其設為NULL
find_head = new DList ;
for ( int i = 0; i < 10; i )
temp_road[ i ] = new DList ;
all_num = 0 ;
DList *pointer, *temp[6] ; for ( int i = 0; i < 6; i )
temp[ i ] = new DList ;
head -> number = 1 ;
head -> an_road_numeral = 0 ;
head -> roadname = "成功路" ;
ComboBox1 -> Items -> Add( head -> roadname ) ;
head -> road_numeral = 35 ; temp[ 0 ] -> road_numeral = 45 ;
temp[ 0 ] -> an_road_numeral = 30 ;
temp[ 0 ] -> roadname = "自由路" ;
ComboBox1 -> Items -> Add( temp[ 0 ] -> roadname ) ;
temp[ 0 ] -> number = 2 ;
head -> road = temp[ 0 ] ; temp[ 1 ] -> number = 3 ;
temp[ 1 ] -> road_numeral = 25 ;
temp[ 1 ] -> an_road_numeral = 0 ;
temp[ 1 ] -> roadname = "博愛路" ;
ComboBox1 -> Items -> Add( temp[ 1 ] -> roadname ) ;
temp[ 0 ] -> road = temp[ 1 ] ; temp[ 2 ] -> road_numeral = 45 ;
temp[ 2 ] -> number = 4 ;
temp[ 2 ] -> an_road_numeral = 130 ;
temp[ 2 ] -> roadname = "中正路" ;
ComboBox1 -> Items -> Add( temp[ 2 ] -> roadname ) ;
temp[ 0 ] -> an_road = temp[ 2 ] ;
temp[ 0 ] = temp[ 2 ] ; temp[ 3 ] -> an_road_numeral = 0 ;
temp[ 3 ] -> number = 5 ;
temp[ 3 ] -> road_numeral = 100 ;
temp[ 3 ] -> roadname = "仁愛路" ;
ComboBox1 -> Items -> Add( temp[ 3 ] -> roadname ) ;
temp[ 1 ] -> road = temp[ 3 ] ; //第三點接到第五點
temp[ 1 ] = temp[ 3 ] ;
temp[ 0 ] -> road = temp[ 3 ] ;//第四點接到第五點 temp[ 4 ] -> number = 6 ;
temp[ 4 ] -> road_numeral = 0 ;
temp[ 4 ] -> an_road_numeral = 0 ;
temp[ 4 ] -> roadname = "中山路" ;
ComboBox1 -> Items -> Add( temp[ 4 ] -> roadname ) ;
temp[ 0 ] -> an_road = temp[ 4 ] ;
temp[ 1 ] -> road = temp[ 4 ] ;
}
//---------------------------------------------------------------------------
DList *start_find( DList *ptr, String main_roadname )//找出先要找的道路字串位指
{
DList *temp[ 10 ] ;
int count = 0 ;
for ( int i = 0; i < 10; i )
temp[ i ] = new DList ;
while ( ptr -> roadname != main_roadname && ptr -> road_numeral != 0 || ptr -> an_road_numeral != 0 )
{
if ( ptr -> road_numeral != 0 && ptr -> an_road_numeral != 0 )
{
if ( ptr -> roadname == main_roadname )
break ;
else
{
temp[ count ] = ptr -> an_road ;
ptr = ptr -> road ;
}
}
else if ( ptr -> an_road_numeral == 0 )
{
if ( ptr -> roadname != main_roadname )
ptr = ptr -> road ;
else
break ;
}
else
{
if ( ptr -> roadname != main_roadname )
ptr = ptr -> an_road ;
else
break ;
}
}
*temp_road = *temp ;
counti = count ;
return ptr ;
}
//---------------------------------------------------------------------------
/*void find_road( String main_roadname, String nain_anroadname, int direct )
{
DList *ptr;
ptr = head ;
//*ptr = start_find( ptr, main_roadname ) ;
/*
if ( find_count == 0 )
Application -> MessageBox("並沒有找到您所要新增的路名,請重新輸入您要新增的路名","未尋找到",16) ; }*/
//---------------------------------------------------------------------------
void creat_list( DList *ptr_road1, DList *ptr_road2, int direct )
{
if ( ptr_road1 -> road_numeral == 0 )
{
ptr_road1 -> road_numeral = StrToInt( direct ) ;
ptr_road1 -> road = ptr_road2 ;
}
else if ( ptr_road1 -> an_road_numeral == 0 )
{
ptr_road1 -> an_road_numeral = direct ;
ptr_road1 -> an_road = ptr_road2 ;
}
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button2Click(TObject *Sender)
{
DList *ptr_road, *ptr_anroad ;
int direct ;
String road1, road2 ;
direct = StrToInt( Edit3 -> Text ) ;
road1 = Edit1 -> Text ;
road2 = Edit2 -> Text ; //道路1的位址
ptr_road = start_find( head, road1 ) ;
if ( ptr_road -> roadname != road1 )
for ( int i = 0; i < counti; i )
ptr_road = start_find( temp_road[ i ], road1 ) ; //道路2的位址
ptr_anroad = start_find( head, road2 ) ;
if ( ptr_anroad -> roadname != road2 )
for ( int i = 0; i < counti; i )
ptr_anroad = start_find( temp_road[ i ], road2 ) ;
if ( ptr_anroad -> roadname != road2 )
{
ptr_anroad = new DList ;
ptr_anroad -> roadname = road2 ;
ptr_anroad -> road_numeral = ptr_anroad -> an_road_numeral = 0 ;
}
creat_list( ptr_road, ptr_anroad, direct ) ;
}
//--------------------------------------------------------------------------- void __fastcall TForm1::ComboBox1Click(TObject *Sender)
{
DList *en_road[ 10 ] ;
int an_count ;
for ( int i = 0; i < 10; i )
en_road[ i ] = new DList ;
save_head = new Save_roadname ;
save_head -> next = NULL ;
ComboBox2 -> Clear() ;
//int sel_item ;
String sel_road ;
String sel_road1 ;
//sel_item = ComboBox1 -> ItemIndex ;
sel_road = ComboBox1 -> Text ;
DList *start_ptr, *end_ptr ; //以下三行是搜尋道路位址
start_ptr = start_find( head, sel_road ) ;
if ( start_ptr -> roadname != sel_road )
for ( int i = 0; i < counti; i )
start_ptr = start_find( temp_road[ i ], sel_road ) ;
*find_head = *start_ptr ;
find_endroad( start_ptr, sel_road ) ;
*en_road = *temp_road ;
an_count = counti ;
for ( int i = 0; i < an_count; i )
find_endroad( en_road[ i ], sel_road ) ;
printer_combobox() ; }
//--------------------------------------------------------------------------- void __fastcall TForm1::ComboBox2Click(TObject *Sender)
{
DList *ptr ;
save_head = new Save_roadname ;
save_head -> next = NULL ;
all_num = 0 ;
String sel_end ;
sel_end = ComboBox2 -> Text ;
for ( int i = 0; i < 10; i )
find_temp[ i ] = new DList ;
ptr = find_Bestroad( find_head, sel_end ) ;
if ( ptr -> roadname != sel_end )
for ( int i = 0; i < counti; i )
{
Delete_road( delete_road[ i ] -> roadname ) ;
all_num = temp_road[ i ] -> num ;
ptr = find_Bestroad( temp_road[ i ], sel_end ) ;
}
printer_Memo() ;
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button1Click(TObject *Sender)
{
Edit4->Text="";
Memo1->Lines->Clear();
}
//---------------------------------------------------------------------------
void __fastcall TForm1::Button3Click(TObject *Sender)
{
if(RadioButton1->Checked==true)
{
Form1 -> Memo1 -> Text="救人ㄛ!不會算啦!!";
} else if(RadioButton2->Checked==true)
{ Form1 -> Memo1 -> Clear() ;
Save_roadname *ptr ;
ptr = save_head ;
Form1 -> Memo1 -> Text = "從" ptr -> roadname ;
while ( ptr != NULL )
{
if ( ptr -> next != NULL )
{
ptr = ptr -> next ;
Form1 -> Memo1 -> Text = Form1 -> Memo1 -> Text "->" ptr -> roadname ;//先印出起始路名
}
else
break ;
}
Form1 -> Edit4 -> Text = IntToStr( all_num ) ;//顯示出最後距離總和
} else if(RadioButton3->Checked==true)
{
Form1 -> Memo1 -> Text="救人ㄛ!不會算啦!!"; } }
//-------------------------------------------------------------------
各位大大
我現在是做三個radiobutton~分別要算出三種方法,其中一種已經做出來
就是選取按完起點與終點再選radiobutton2,結果就會顯示在memo1上。 但卻不是最短的~~ 發表人 - liyanzi 於 2005/07/25 23:47:08
|
andychang1690
資深會員
發表:20 回覆:694 積分:442 註冊:2003-03-14
發送簡訊給我
|
liyanzi:我的觀念並不一定正確,但我覺得妳應該以地圖座標的方式
來處理最短路徑的問題!依妳的問題
1 ↗ 2 → 4
?↘ 3 ↗
要求1->4最短的,
1->2的距離為20,2->4的距離為130
1->3的距離為30,3->4的距離為20
依地圖觀點應該是
1← 2
3↗
4↗
如此2到4才會有2->4的距離為130的發生
所以我會編座標(我以單一編號為例)成為
51← 62
43↗
34↗
原1->51,2->62,3->43,4->34。
現我要從51到34以座標看51>34所以要向左走到43,43>34還是向左走到43(ok)
以上方式不知可否供參考!
Andy Chang
------ Andy Chang
|
RedSnow
版主
發表:79 回覆:1322 積分:845 註冊:2003-12-15
發送簡訊給我
|
liyanzi 妳好: 有一些資訊請妳提供: - Edit1, Edit2, Edit3 的用途為何?分別要填入何種資料?各個資料的意義又為何?
- 詳細的操作順序 (步驟) 是什麼?是不是:
A. 圈選 RadioButton2
B. 選擇 ComboBox1 與 ComboBox2 項目
C. 在 Edit1, Edit2, Edit3 分別填入一些數字及資料
D. 點選 Button2 開始找尋最短路徑
E. 點選 Button3 顯示結果於 Memo 上
- 妳測試時的兩個 ComboBox 分別選擇了什麼項目?何種結果才是正確的?
7 天天敲鍵盤 v 時時按滑鼠 8
|
liyanzi
一般會員
發表:51 回覆:45 積分:19 註冊:2005-01-24
發送簡訊給我
|
感謝這位大大~~ 我已將檔案上傳至~~會員求助區了~~ 在此回答您的問題 Edit1, Edit2, Edit3 的用途為何?分別要填入何種資料?各個資料的意義又為何?
*目前Edit1, Edit2, Edit3 還不需用到,與計算路徑方法不影響 詳細的操作順序 (步驟) 是什麼?是不是:
A. 圈選 RadioButton2
B. 選擇 ComboBox1 與 ComboBox2 項目
C. 在 Edit1, Edit2, Edit3 分別填入一些數字及資料
D. 點選 Button2 開始找尋最短路徑
E. 點選 Button3 顯示結果於 Memo 上 *一開始先選B->A->E就好了 妳測試時的兩個 ComboBox 分別選擇了什麼項目?何種結果才是正確的?
*ComboBox1選成功路
*ComboBox2選中山路 顯示結果應該是210 路徑為成功路->自由路->中正路->仁愛路->中山路 但顯示結果應該為195 我所寫之程式~~路徑圖
1→2↗4 →5?↘
??↘3 ↗?→?6
1指的是成功路
2指的是自由路
3指的是中正路
4指的是博愛路
5指的是仁愛路
6指的是中山路
1->2距離為35
2->3距離為30
2->4距離為45
3->5距離為45
4->5距離為25
5->6距離為100
3->6距離為130 發表人 - liyanzi 於 2005/07/26 16:09:20
|
andychang1690
資深會員
發表:20 回覆:694 積分:442 註冊:2003-03-14
發送簡訊給我
|
http://vcl.vclxx.org/DELPHI/D32SAMPL/BINARYTREE2.ZIP
示範如何以 C Builder 讀入資料結構中的二元樹並將整棵樹繪製出來,並可針對二元樹做搜尋,
作者 : 吳燈進。
妳應該可以參考一下!
Andy Chang
------ Andy Chang
|
RedSnow
版主
發表:79 回覆:1322 積分:845 註冊:2003-12-15
發送簡訊給我
|
liyanzi 妳好: 妳的程式我測試過了,但是我看得眼睛都花了,還是沒法完全消化掉,因此未能確認問題之所在,我大致做了瞭解後,覺得好像是妳的處理程序是逐一比對距離數,僅抓取距離較短的路徑繼續處理,並未抓取完整路徑後才做比對,因此才會產生錯誤的結果。 我自己另外寫了一段作測試,雖然不是很周詳,但是測試結果尚能達到妳的要求,我使用的是遞迴的方式,先將每條可能路徑都抓出來,並將全程距離加總,然後才做比對。 為了不破壞妳原來的程式敘述,我另寫了一個自定函式,並另增一個命名為 Button4 的 Button 以便單獨進行測試,當妳設定好 ComboBox1 與 ComboBox2 的首尾路名後,就點選新增的那個 Button4 即可獲得結果,妳參考看看好了: #include TStringList* roadPaths; // 存放找到的路徑之用
vector roadLen; // 存放找到路徑的距離加總之用 void FindPath(DList *pointer, String end_road, int index)
{
// 如果不是路徑開頭則加上 "->" 符號以作分隔
if(roadPaths->Strings[index] != "") roadPaths->Strings[index] = roadPaths->Strings[index] "->";
// 加上找到的路名到路徑內
roadPaths->Strings[index] = roadPaths->Strings[index] pointer->roadname; if (pointer->an_road_numeral != 0 ) { // 如果有分支道路
if (pointer->roadname != end_road) { // 若不是 ComboBox2 所設之終點路名
int k = roadPaths->Add(roadPaths->Strings[index]); // 增加路徑陣列
roadLen.push_back(roadLen[index]); // 增加距離加總陣列,並設初值為之前加總距離
roadLen[k] = roadLen[k] pointer->an_road_numeral; // 加上本次分支道路的距離
FindPath(pointer->an_road, end_road, k); // 遞迴找尋這條分支道路
}
} if (pointer->road_numeral != 0) { // 如果後邊有連接道路
if (pointer->roadname != end_road) { // 若不是 ComboBox2 所設之終點路名
roadLen[index] = roadLen[index] pointer->road_numeral; // 加上到下一條道路的距離
FindPath(pointer->road, end_road, index); // 遞迴找尋這條道路的下一條路
}
}
} void __fastcall TForm1::Button4Click(TObject *Sender)
{
roadPaths = new TStringList();
int k = roadPaths->Add(""); // 新增第一條路徑
roadLen.push_back(0); // FindPath(find_head, ComboBox2->Text, k); // 開始找尋路徑 Memo1->Clear();
int shortRoad = 9999; // 比對最短路徑之用,先隨意設一個最大值
int shortIndex = 0; // 比對後,存放最短路徑的索引值
int PathNo = 0;
for(int i=0; iCount; i ){
// 因為找到的路徑都是搜尋到最後一個路名 (中山路),因此要過濾掉不包含 ComboBox2 所設路名的路徑
if(roadPaths->Strings[i].Pos(ComboBox2->Text) > 0){
PathNo ;
Memo1->Lines->Add("第 " IntToStr(PathNo) " 條路徑:" roadPaths->Strings[i] " (" IntToStr(roadLen[i]) ")");
if(roadLen[i] < shortRoad){ // 比對路徑總距離
shortRoad = roadLen[i]; // 取得較短路徑之距離數
shortIndex = i; // 取得較短路徑之 StringList 索引值
}
}
}
Memo1->Lines->Add("\r\n最短路徑為:" roadPaths->Strings[shortIndex] " (" IntToStr(roadLen[shortIndex]) ")"); roadLen.clear();
delete roadPaths;
} 7 天天敲鍵盤 v 時時按滑鼠 8
|
liyanzi
一般會員
發表:51 回覆:45 積分:19 註冊:2005-01-24
發送簡訊給我
|
真的是謝謝各位大大的指教~~ 超級感謝RedSnow大大的程式解救~~~ 才想到原來可以用遞迴做~~真是謝謝!!
|
liyanzi
一般會員
發表:51 回覆:45 積分:19 註冊:2005-01-24
發送簡訊給我
|
想再請問各位大大~~突然發現一個錯誤 我現在的路是寫死~~一個接一個下一條路 並不能~~往回選擇路名~~~ 依正確的常理來講~~好像不行~~ 有解決的辦法嗎?
|
RedSnow
版主
發表:79 回覆:1322 積分:845 註冊:2003-12-15
發送簡訊給我
|
liyanzi 妳好: 妳現在的 DList 結構中並未設定往回連結的路名與距離,如果要往回選擇路名的話,我想妳必須另設一組結構資料,或者將原有的 DList 結構擴充一下,比照原先往前的方式設定往回走的連接路名與往回到前一個路名之距離的項目,而處理方式也是比照原先的方式應該就可以了。 7 天天敲鍵盤 v 時時按滑鼠 8
|
988078
一般會員
發表:23 回覆:15 積分:7 註冊:2005-03-02
發送簡訊給我
|
各位前輩想請問~
目前這各程式它的路名..距離..要連結哪一條路~
這些都是直接寫在程式裡面~
但是我的問題是~要怎麼從資料庫去抓那些欄位的資料進來處理
我該怎麼去設計?煩請前輩的指教~
下面是我所建的資料庫
高高屋海苔
------ 高高屋海苔
|
RedSnow
版主
發表:79 回覆:1322 積分:845 註冊:2003-12-15
發送簡訊給我
|
988078 妳好: 引言:各位前輩想請問~
目前這各程式它的路名..距離..要連結哪一條路~
這些都是直接寫在程式裡面~
但是我的問題是~要怎麼從資料庫去抓那些欄位的資料進來處理
我該怎麼去設計?煩請前輩的指教~
下面是我所建的資料庫 本篇討論已結案,建議妳另外開題討論,如果討論內容與本篇有關,可以用連結或引用的方式加以說明。 7 天天敲鍵盤 v 時時按滑鼠 8
|