巡回セールスマン問題プログラム
1 ：デフォルトの名無しさん：
現在、巡回セールスマン問題に関して、二重同心円上の都市問題のプログラムを作ろうとしているのですが、なかなかうまくいきません。誰かご教授お願いします。
外円の半径が１で、内円の半径r(0<r<1)を動かして、その最短経路を調べます。円上に都市は各々nずつ等間隔に並んでいます。
外円の半径が１で、内円の半径r(0<r<1)を動かして、その最短経路を調べます。円上に都市は各々nずつ等間隔に並んでいます。
|
|
|
2 ：デフォルトの名無しさん：05/02/10 07:49:08
知らんがな
3 ：デフォルトの名無しさん：05/02/10 10:11:30
在日さんですか？
日本語難しいね
ローカルルール読めないかな？
日本人に迷惑かけちゃだめだよ
日本語難しいね
ローカルルール読めないかな？
日本人に迷惑かけちゃだめだよ
4 ：デフォルトの名無しさん：05/02/10 14:47:56
総当たりしろよ。
5 ：デフォルトの名無しさん：05/02/10 16:44:28
>>1
それぞれの街同士の距離をマトリックスにする。
あとは平面巡回セールスマン問題と同じ。
double **matrix;
int *visited;
int pointnum;
double k;
int search( int num, double len, int last_path ) {
double now_len;
int i;
if( num == pointnum ){
now_len = len + matrix[0][last_path];
if( now_len < k ) return TRUE;
else return FALSE;
} else {
for( i = 1; i < pointnum; i++ ){
if( visited[i] == FALSE ){
now_len = len + matrix[i][last_path];
visited[i] = TRUE;
if ( search( num + 1, now_len, i ) == TRUE )
return TRUE;
visited[i] = FALSE;
}
}
}
}
それぞれの街同士の距離をマトリックスにする。
あとは平面巡回セールスマン問題と同じ。
double **matrix;
int *visited;
int pointnum;
double k;
int search( int num, double len, int last_path ) {
double now_len;
int i;
if( num == pointnum ){
now_len = len + matrix[0][last_path];
if( now_len < k ) return TRUE;
else return FALSE;
} else {
for( i = 1; i < pointnum; i++ ){
if( visited[i] == FALSE ){
now_len = len + matrix[i][last_path];
visited[i] = TRUE;
if ( search( num + 1, now_len, i ) == TRUE )
return TRUE;
visited[i] = FALSE;
}
}
}
}
6 ：デフォルトの名無しさん：05/02/10 16:45:13
これは決定問題の場合だった。
7 ：１年目：05/02/10 19:41:30
サラリーマンもうやだ
8 ：デフォルトの名無しさん：05/02/10 21:03:57
道が出来てから都市が出来るので任意の都市へは直線で行けない。
9 ：デフォルトの名無しさん：05/02/10 22:31:44
通勤サラリーマン問題スレにしようぜ
10 ：デフォルトの名無しさん：05/02/10 22:43:46
普通何ヶ所も通勤しない
11 ：デフォルトの名無しさん：05/02/10 22:49:30
１0足のわらじをはいたセールスマン
12 ：デフォルトの名無しさん：05/02/10 22:53:53
ナップサック問題を解く方が楽しいべ。
まずは、バナナがおやつに入るのかどうかを決めよう。
まずは、バナナがおやつに入るのかどうかを決めよう。
13 ：デフォルトの名無しさん：05/02/10 23:00:50
弁当箱に入ったバナナは弁当、その他はおやつ。
14 ：デフォルトの名無しさん：05/02/11 04:05:58
>>1 セールスマンてｗ
↓巡回サラリーマン問題が正解だろ？(ﾌﾟｹﾞﾗｯﾁｮﾘｰﾇ
http://www.google.co.jp/search?sourceid=navclient&hl=ja&ie=UTF-8&rls=GGLD,GGLD:2003-40,GGLD:ja&q=%E5%B7%A1%E5%9B%9E%E3%82%B5%E3%83%A9%E3%83%AA%E3%83%BC%E3%83%9E%E3%83%B3%E5%95%8F%E9%A1%8C
↓巡回サラリーマン問題が正解だろ？(ﾌﾟｹﾞﾗｯﾁｮﾘｰﾇ
http://www.google.co.jp/search?sourceid=navclient&hl=ja&ie=UTF-8&rls=GGLD,GGLD:2003-40,GGLD:ja&q=%E5%B7%A1%E5%9B%9E%E3%82%B5%E3%83%A9%E3%83%AA%E3%83%BC%E3%83%9E%E3%83%B3%E5%95%8F%E9%A1%8C
15 ：デフォルトの名無しさん：05/02/11 04:25:43
そんな餌で(ry
16 ：デフォルトの名無しさん：05/02/11 06:35:52
>>14
大変良くできました。わろた。
大変良くできました。わろた。
17 ：デフォルトの名無しさん：05/02/11 07:23:14
ところで何を売ってるセールスマン？
18 ：デフォルトの名無しさん：05/02/11 07:25:48
この問題を解くには適切な交配が求められる。？？？？
19 ：デフォルトの名無しさん：05/02/11 13:41:28
>>17
勿論、コンドームやXXXX,ZZZZ,YYYY,WWW、ピィー、ピィー、ピィーです。
勿論、コンドームやXXXX,ZZZZ,YYYY,WWW、ピィー、ピィー、ピィーです。
20 ：デフォルトの名無しさん：05/02/12 20:29:31
「団地妻の誘惑」？
21 ：デフォルトの名無しさん：05/02/12 22:30:16
>>20はかなりのおさーん
22 ：デフォルトの名無しさん：2005/06/27(月) 11:30:29
GAつかえば
23 ：デフォルトの名無しさん：2005/07/03(日) 20:33:04
TSPでGA使えというやつは素人
24 ：デフォルトの名無しさん：2005/07/04(月) 07:18:48
まあ勉強には良いんじゃない？
ナップサックと並んで定番だし。
ナップサックと並んで定番だし。
25 ：デフォルトの名無しさん：2005/07/04(月) 10:01:59
弾力ネット使え
26 ：デフォルトの名無しさん：2005/10/11(火) 21:22:52
TSPLIBのTSPのデータの見方がわかりません・・・。誰かご教授あれ。
27 ：デフォルトの名無しさん：2005/11/15(火) 02:04:37
28 ：デフォルトの名無しさん：2006/03/04(土) 19:40:09
学校では、一般にもよく出くわす実用的な問題だって習ったけど、
いまだ一度も出会ったこと無いな。
ナップサック問題も。
いまだ一度も出会ったこと無いな。
ナップサック問題も。
29 ：デフォルトの名無しさん：2006/03/04(土) 19:47:39
ザックザック宝屋の解法はまだですか?
30 ：デフォルトの名無しさん：2006/03/04(土) 20:49:05
「巡回セールスマン問題」と「通勤サラリーマン問題」と「中国人郵便配達夫問題」の違いがよく分かりません。
詳しい人マジレスｷﾎﾞﾝﾇ
詳しい人マジレスｷﾎﾞﾝﾇ
31 ：デフォルトの名無しさん：2006/03/04(土) 21:02:45
セールスマン：全ての頂点をちょうど１回ずつ通る
郵便配達夫：全ての辺を少なくとも１回ずつ通る
サラリーマン：聞いたことない
郵便配達夫：全ての辺を少なくとも１回ずつ通る
サラリーマン：聞いたことない
32 ：デフォルトの名無しさん：2006/03/05(日) 15:43:25
いけませんわ、私には主人が！
33 ：デフォルトの名無しさん：2006/03/05(日) 19:32:29
郵便配達夫はなぜ中国人でなければならないのか。
34 ：デフォルトの名無しさん：2006/03/11(土) 02:53:32
セールスマン だと！？
フェミ団体から苦情がくるぞ
フェミ団体から苦情がくるぞ
35 ：デフォルトの名無しさん：2006/03/11(土) 06:24:20
セールス男ならよいですか？
セールスパースンです。