質問編集履歴
1
ソースの変更
title
CHANGED
|
File without changes
|
body
CHANGED
|
@@ -5,101 +5,4 @@
|
|
|
5
5
|
AからJまで行くような探索をしたいと思っています。
|
|
6
6
|
このような感じでA-starを使っていて経路探索をしているサイトがありましたら
|
|
7
7
|
教えていただけると幸いです。
|
|
8
|
-
|
|
9
|
-
現在はこのソースコードを改良してやろうと思っているのですが、
|
|
10
|
-
どのように考えれば良いかわからず今止まっています。
|
|
11
|
-
よろしくお願い致します。
|
|
8
|
+
よろしくお願い致します。
|
|
12
|
-
|
|
13
|
-
```C
|
|
14
|
-
#include<stdio.h>
|
|
15
|
-
|
|
16
|
-
#define N 10
|
|
17
|
-
|
|
18
|
-
void print_route(int prev[], int g)
|
|
19
|
-
{
|
|
20
|
-
int tmp;
|
|
21
|
-
printf("%d",g);
|
|
22
|
-
tmp = prev[g];
|
|
23
|
-
while(tmp >= 0){
|
|
24
|
-
printf(" <- %d",tmp);
|
|
25
|
-
tmp = prev[tmp];
|
|
26
|
-
}
|
|
27
|
-
printf("\n");
|
|
28
|
-
return;
|
|
29
|
-
}
|
|
30
|
-
|
|
31
|
-
int length(int tree[][3], int arc_num, int s, int t)
|
|
32
|
-
{
|
|
33
|
-
int i;
|
|
34
|
-
for(i = 0; i < arc_num; i++){
|
|
35
|
-
if(tree[i][0] == s && tree[i][1] == t){
|
|
36
|
-
return tree[i][2];
|
|
37
|
-
}
|
|
38
|
-
}
|
|
39
|
-
return -1;
|
|
40
|
-
}
|
|
41
|
-
|
|
42
|
-
int distance(int prev[], int node, int tree[][3], int arc_num)
|
|
43
|
-
{
|
|
44
|
-
int tmp = node, d = 0;
|
|
45
|
-
while(prev[tmp] != -1){
|
|
46
|
-
d += length(tree, arc_num, prev[tmp], tmp);
|
|
47
|
-
tmp = prev[tmp];
|
|
48
|
-
}
|
|
49
|
-
return d;
|
|
50
|
-
}
|
|
51
|
-
|
|
52
|
-
int main(void)
|
|
53
|
-
{
|
|
54
|
-
int tree[][3] = {{0,1,1},{0,2,3},{1,2,1},{1,6,6},{2,6,6},{2,3,6},
|
|
55
|
-
{2,7,3},{3,7,2},{3,4,5},{3,8,4}, {4,8,2},{5,1,1},
|
|
56
|
-
{6,5,7},{6,7,2},{7,8,1},{7,9,7},{8,9,5}};
|
|
57
|
-
int arc_num = sizeof(tree)/sizeof(tree[0]);
|
|
58
|
-
int open[N];
|
|
59
|
-
int size = 0;
|
|
60
|
-
int start = 0;
|
|
61
|
-
int goal = 9;
|
|
62
|
-
int top,i,mindex,tmp;
|
|
63
|
-
int cost[N] = {100,7,4,6,4,2,3,4,2,0};
|
|
64
|
-
int prev[N] = {-1,-1,-1,-1,-1,-1,-1,-1,-1,-1};
|
|
65
|
-
int closed[N] = {0,0,0,0,0,0,0,0,0,0};
|
|
66
|
-
|
|
67
|
-
open[size++] = start;
|
|
68
|
-
|
|
69
|
-
while(size > 0){
|
|
70
|
-
mindex = 0;
|
|
71
|
-
for(i = 0; i < size; i++){
|
|
72
|
-
if((distance(prev, open[mindex], tree, arc_num)+cost[open[mindex]]) > (distance(prev, open[i], tree, arc_num)+cost[open[i]])){
|
|
73
|
-
mindex = i;
|
|
74
|
-
}
|
|
75
|
-
}
|
|
76
|
-
|
|
77
|
-
tmp = open[mindex];
|
|
78
|
-
open[mindex] = open[size-1];
|
|
79
|
-
open[size - 1] = tmp;
|
|
80
|
-
top = open[--size];
|
|
81
|
-
|
|
82
|
-
if(top == goal){
|
|
83
|
-
print_route(prev,goal);
|
|
84
|
-
return 0;
|
|
85
|
-
}
|
|
86
|
-
|
|
87
|
-
|
|
88
|
-
for(i = 0; i < arc_num; i++){
|
|
89
|
-
if(tree[i][0] == top){
|
|
90
|
-
if(closed[tree[i][1]] == 0){
|
|
91
|
-
open[size++] = tree[i][1];
|
|
92
|
-
prev[tree[i][1]] = top;
|
|
93
|
-
closed[tree[i][1]] = 1;
|
|
94
|
-
}else if(closed[tree[i][1]] == 1){
|
|
95
|
-
if(distance(prev, tree[i][1], tree, arc_num) > distance(prev, top, tree,arc_num) + length(tree, arc_num ,start, goal)){
|
|
96
|
-
prev[tree[i][1]] = top;
|
|
97
|
-
}
|
|
98
|
-
}
|
|
99
|
-
}
|
|
100
|
-
}
|
|
101
|
-
}
|
|
102
|
-
return 0;
|
|
103
|
-
}
|
|
104
|
-
|
|
105
|
-
```
|