質問編集履歴
1
ソースの変更
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -12,198 +12,4 @@
|
|
|
12
12
|
|
|
13
13
|
教えていただけると幸いです。
|
|
14
14
|
|
|
15
|
-
|
|
16
|
-
|
|
17
|
-
現在はこのソースコードを改良してやろうと思っているのですが、
|
|
18
|
-
|
|
19
|
-
どのように考えれば良いかわからず今止まっています。
|
|
20
|
-
|
|
21
15
|
よろしくお願い致します。
|
|
22
|
-
|
|
23
|
-
|
|
24
|
-
|
|
25
|
-
```C
|
|
26
|
-
|
|
27
|
-
#include<stdio.h>
|
|
28
|
-
|
|
29
|
-
|
|
30
|
-
|
|
31
|
-
#define N 10
|
|
32
|
-
|
|
33
|
-
|
|
34
|
-
|
|
35
|
-
void print_route(int prev[], int g)
|
|
36
|
-
|
|
37
|
-
{
|
|
38
|
-
|
|
39
|
-
int tmp;
|
|
40
|
-
|
|
41
|
-
printf("%d",g);
|
|
42
|
-
|
|
43
|
-
tmp = prev[g];
|
|
44
|
-
|
|
45
|
-
while(tmp >= 0){
|
|
46
|
-
|
|
47
|
-
printf(" <- %d",tmp);
|
|
48
|
-
|
|
49
|
-
tmp = prev[tmp];
|
|
50
|
-
|
|
51
|
-
}
|
|
52
|
-
|
|
53
|
-
printf("\n");
|
|
54
|
-
|
|
55
|
-
return;
|
|
56
|
-
|
|
57
|
-
}
|
|
58
|
-
|
|
59
|
-
|
|
60
|
-
|
|
61
|
-
int length(int tree[][3], int arc_num, int s, int t)
|
|
62
|
-
|
|
63
|
-
{
|
|
64
|
-
|
|
65
|
-
int i;
|
|
66
|
-
|
|
67
|
-
for(i = 0; i < arc_num; i++){
|
|
68
|
-
|
|
69
|
-
if(tree[i][0] == s && tree[i][1] == t){
|
|
70
|
-
|
|
71
|
-
return tree[i][2];
|
|
72
|
-
|
|
73
|
-
}
|
|
74
|
-
|
|
75
|
-
}
|
|
76
|
-
|
|
77
|
-
return -1;
|
|
78
|
-
|
|
79
|
-
}
|
|
80
|
-
|
|
81
|
-
|
|
82
|
-
|
|
83
|
-
int distance(int prev[], int node, int tree[][3], int arc_num)
|
|
84
|
-
|
|
85
|
-
{
|
|
86
|
-
|
|
87
|
-
int tmp = node, d = 0;
|
|
88
|
-
|
|
89
|
-
while(prev[tmp] != -1){
|
|
90
|
-
|
|
91
|
-
d += length(tree, arc_num, prev[tmp], tmp);
|
|
92
|
-
|
|
93
|
-
tmp = prev[tmp];
|
|
94
|
-
|
|
95
|
-
}
|
|
96
|
-
|
|
97
|
-
return d;
|
|
98
|
-
|
|
99
|
-
}
|
|
100
|
-
|
|
101
|
-
|
|
102
|
-
|
|
103
|
-
int main(void)
|
|
104
|
-
|
|
105
|
-
{
|
|
106
|
-
|
|
107
|
-
int tree[][3] = {{0,1,1},{0,2,3},{1,2,1},{1,6,6},{2,6,6},{2,3,6},
|
|
108
|
-
|
|
109
|
-
{2,7,3},{3,7,2},{3,4,5},{3,8,4}, {4,8,2},{5,1,1},
|
|
110
|
-
|
|
111
|
-
{6,5,7},{6,7,2},{7,8,1},{7,9,7},{8,9,5}};
|
|
112
|
-
|
|
113
|
-
int arc_num = sizeof(tree)/sizeof(tree[0]);
|
|
114
|
-
|
|
115
|
-
int open[N];
|
|
116
|
-
|
|
117
|
-
int size = 0;
|
|
118
|
-
|
|
119
|
-
int start = 0;
|
|
120
|
-
|
|
121
|
-
int goal = 9;
|
|
122
|
-
|
|
123
|
-
int top,i,mindex,tmp;
|
|
124
|
-
|
|
125
|
-
int cost[N] = {100,7,4,6,4,2,3,4,2,0};
|
|
126
|
-
|
|
127
|
-
int prev[N] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
|
|
128
|
-
|
|
129
|
-
int closed[N] = {0,0,0,0,0,0,0,0,0,0};
|
|
130
|
-
|
|
131
|
-
|
|
132
|
-
|
|
133
|
-
open[size++] = start;
|
|
134
|
-
|
|
135
|
-
|
|
136
|
-
|
|
137
|
-
while(size > 0){
|
|
138
|
-
|
|
139
|
-
mindex = 0;
|
|
140
|
-
|
|
141
|
-
for(i = 0; i < size; i++){
|
|
142
|
-
|
|
143
|
-
if((distance(prev, open[mindex], tree, arc_num)+cost[open[mindex]]) > (distance(prev, open[i], tree, arc_num)+cost[open[i]])){
|
|
144
|
-
|
|
145
|
-
mindex = i;
|
|
146
|
-
|
|
147
|
-
}
|
|
148
|
-
|
|
149
|
-
}
|
|
150
|
-
|
|
151
|
-
|
|
152
|
-
|
|
153
|
-
tmp = open[mindex];
|
|
154
|
-
|
|
155
|
-
open[mindex] = open[size-1];
|
|
156
|
-
|
|
157
|
-
open[size - 1] = tmp;
|
|
158
|
-
|
|
159
|
-
top = open[--size];
|
|
160
|
-
|
|
161
|
-
|
|
162
|
-
|
|
163
|
-
if(top == goal){
|
|
164
|
-
|
|
165
|
-
print_route(prev,goal);
|
|
166
|
-
|
|
167
|
-
return 0;
|
|
168
|
-
|
|
169
|
-
}
|
|
170
|
-
|
|
171
|
-
|
|
172
|
-
|
|
173
|
-
|
|
174
|
-
|
|
175
|
-
for(i = 0; i < arc_num; i++){
|
|
176
|
-
|
|
177
|
-
if(tree[i][0] == top){
|
|
178
|
-
|
|
179
|
-
if(closed[tree[i][1]] == 0){
|
|
180
|
-
|
|
181
|
-
open[size++] = tree[i][1];
|
|
182
|
-
|
|
183
|
-
prev[tree[i][1]] = top;
|
|
184
|
-
|
|
185
|
-
closed[tree[i][1]] = 1;
|
|
186
|
-
|
|
187
|
-
}else if(closed[tree[i][1]] == 1){
|
|
188
|
-
|
|
189
|
-
if(distance(prev, tree[i][1], tree, arc_num) > distance(prev, top, tree,arc_num) + length(tree, arc_num ,start, goal)){
|
|
190
|
-
|
|
191
|
-
prev[tree[i][1]] = top;
|
|
192
|
-
|
|
193
|
-
}
|
|
194
|
-
|
|
195
|
-
}
|
|
196
|
-
|
|
197
|
-
}
|
|
198
|
-
|
|
199
|
-
}
|
|
200
|
-
|
|
201
|
-
}
|
|
202
|
-
|
|
203
|
-
return 0;
|
|
204
|
-
|
|
205
|
-
}
|
|
206
|
-
|
|
207
|
-
|
|
208
|
-
|
|
209
|
-
```
|