-
Notifications
You must be signed in to change notification settings - Fork 0
/
search.c
266 lines (256 loc) · 10.8 KB
/
search.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
#include "structs.h"
#include "pointers.h"
#include "search.h"
#include "graph.h"
#include <stdio.h>
#include <stdlib.h>
/**
* inicializa tabela (das dims do mapa) de ponteiros para Node's
* @param _height altura do mapa
* @param _width largura do mapa
* @return ponteiro para a tabela
*/
Node ***createNodeMap( int _height, int _width){
Node ***map = safeMalloc(sizeof(Node**) * _height);
for (int row = 0; row < _height; row = row + 1){
map[row] = safeMalloc(sizeof(Node*) * _width);
for (int column = 0; column < _width; column = column + 1)
map[row][column] = NULL;
}
return map;
}
/**
* libeta memoria alocada para a tabela de Node's
* @param map ponteiro para
* @param _height altura do mapa
* @param _width largura do mapa
*/
void freeNodeMap(Node ***map, int _height, int _width){
for (int row = 0; row < _height; row = row + 1){
for (int column = 0; column < _width; column = column + 1)
free(map[row][column]);
free(map[row]);
}
free(map);
}
/**
* detemina caminho mais curto entre dois pontos
* implementa em conjunto com a func. explore()
* o algoritmo de dijkstra com uma lista prioritaria
* na forma de acervo/heap
* @param map tabela dos custos
* @param _height altura do mapa
* @param _width largura do mapa
* @param _origin_row coordenada y do ponto inicial
* @param _origin_column coordenada x do ponto inicial
* @param _dest_row coordenada y do ponto inicial
* @param _dest_column coordenada x do ponto inicial
* @param cost custo do caminho já percorrido (Var. B)
* @param num_points numero de pontos do caminho já percorrido (Var. B)
* @param previous_tail cauda da lista que guarda o caminho já percorrido (Var. B)
* @return caminho mais curto determinado
*/
Path *search( int **map, int _height, int _width,
int _origin_row, int _origin_column,
int _dest_row, int _dest_column,
int *cost, int *num_points, Path **previous_tail){
Node ***nodes = createNodeMap(_height, _width), *cur;
nodes[_origin_row][_origin_column] = createNode(NULL, _origin_row, _origin_column, map);
PQueue *q = createQueue(_height, _width);
insert(q, nodes[_origin_row][_origin_column]);
Path *shortest_path = NULL;
while(!empty(q)){ // enquanto houver pontos para explorar
cur = q->heap[0]; // ponto a explorar
popRoot(q);
explore(cur, map, _height, _width, nodes, q);
// se chegámos ao fim
if (nodes[_dest_row][_dest_column] != NULL){
shortest_path = createPath(nodes[_dest_row][_dest_column], NULL, _origin_row, _origin_column, num_points);
// ligar os caminhos
if (*previous_tail != NULL){
(*previous_tail)->next = shortest_path;
}
Path *aux = shortest_path;
while(aux->next != NULL)
aux = aux->next;
// atualizar a cauda do caminho
*previous_tail = aux;
*cost += nodes[_dest_row][_dest_column]->cost;
break;
}
}
freeNodeMap(nodes, _height, _width);
freeQueue(q);
return shortest_path;
}
/**
* aplica o dijkstra e preenche o nó do hipergrafo
* @param ix indice do ponto de origem
* @param graph grafo que tem os pontos turisticos e as arestas que
* os ligam. ponderado e direcionado
* @param map mapa dos custos
* @param _height largura do mapa dos custos
* @param _width altura do mapa dos custos
* @param tur_points pontos a visitar
* @param num_tur_points numero de pontos a visitar
*/
void fillNode(int ix, HyperNode *graph, int **map, int _height, int _width, int **tur_points, int num_tur_points){
initHyperNode(ix, graph, map, num_tur_points, tur_points);
Node ***nodes = createNodeMap(_height, _width), *cur;
nodes[tur_points[ix][0]][tur_points[ix][1]] = createNode(NULL, tur_points[ix][0], tur_points[ix][1], map);
PQueue *q = createQueue(_height, _width);
insert(q, nodes[tur_points[ix][0]][tur_points[ix][1]]);
int num_found_points = 0, num_points_to_find = num_tur_points - ix - 1, num_points_in_path;
while(!empty(q) && num_found_points != num_points_to_find){
cur = q->heap[0];
popRoot(q);
explore(cur, map, _height, _width, nodes, q);
for (int i = ix + 1; i < num_tur_points; i = i + 1){
// se chegámos a um novo ponto de destino
if(nodes[tur_points[i][0]][tur_points[i][1]] != NULL && graph[ix].edges[i] == NULL){
num_points_in_path = 0;
num_found_points = num_found_points + 1;
Path *p = createPath(nodes[tur_points[i][0]][tur_points[i][1]], NULL, tur_points[ix][0], tur_points[ix][1], &num_points_in_path);
graph[ix].edges[i] = createEdge(p, nodes[tur_points[i][0]][tur_points[i][1]]->cost, num_points_in_path);
}
}
}
freeNodeMap(nodes, _height, _width);
freeQueue(q);
}
/**
* explora os pontos à volta de "p" e atualiza a lista de prioridades com os
* melhores custos
* @param p ponto a partir do qual se faz a busca
* @param map tebela dos custos
* @param _height altura do mapa
* @param _width largura do mapa
* @param nodes mapa de nós
* @param q lista prioritaria - heap
*/
void explore(Node *p, int **map, int _height, int _width, Node ***nodes, PQueue *q){
char num_accessible_nodes;
Point *points = accessibleNodes(&(p->coords), map, _height, _width, &num_accessible_nodes);
Node *cur;
for (int i = 0; i < num_accessible_nodes; i = i + 1){
cur = nodes[points[i].row][points[i].column];
// se for a primeira vez que visitamos este ponto, criamos um nó para o mapa de nós
// e inserimos o nó na heap
if (cur == NULL){
nodes[points[i].row][points[i].column] = createNode(p, points[i].row, points[i].column, map);
insert(q, nodes[points[i].row][points[i].column]);
continue;
}
// caso contrário, ver se o custo de chegar ao ponto é inferior do que o do caminho guardado. Nesse caso,
// atualizar a heap com o novo valor
if (cur->cost > newCost(map, p, points + i)){
cur->parent = p; // o pai passa a ser o nó que estamos a explorar
cur->cost = newCost(map, p, points + i); // o custo do nó é atualizado
// descobrimos o indice deste ponto na heap, e garantimos que a condição de acervo é mantida com o novo custo
heapifyUp(q, cur->ix);
}
}
free(points);
}
/**
* gera um vetor com os pontos acessiveis a partir de "p"
* @param p ponto a partir do qual se faz a busca
* @param map tabela dos custos
* @param _height altura do mapa
* @param _width largura do mapa
* @param num_accessible_nodes numero de pontos acessiveis partindo de p
* @return vetor de Node's de Point's(struct das coordenadas) acessiveis
*/
Point *accessibleNodes(Point *p, int **map, int _height, int _width, char *num_accessible_nodes){
*num_accessible_nodes = 0;
Point points[8];
validatePoint(map, _height, _width, num_accessible_nodes, points, p->row + 2, p->column + 1);
validatePoint(map, _height, _width, num_accessible_nodes, points, p->row + 2, p->column - 1);
validatePoint(map, _height, _width, num_accessible_nodes, points, p->row + 1, p->column + 2);
validatePoint(map, _height, _width, num_accessible_nodes, points, p->row + 1, p->column - 2);
validatePoint(map, _height, _width, num_accessible_nodes, points, p->row - 2, p->column + 1);
validatePoint(map, _height, _width, num_accessible_nodes, points, p->row - 2, p->column - 1);
validatePoint(map, _height, _width, num_accessible_nodes, points, p->row - 1, p->column - 2);
validatePoint(map, _height, _width, num_accessible_nodes, points, p->row - 1, p->column + 2);
Point *to_access = safeMalloc(sizeof(Point) * (*num_accessible_nodes));
for (int i = 0; i < *num_accessible_nodes; i = i + 1)
to_access[i] = points[i];
return to_access;
}
/**
* guarda o ponto no vetor acima descrito se este for valido
* (dentro do mapa e com custo !=0)
* @param map tabela dos custos
* @param _height altura do mapa
* @param _width largura do mapa
* @param num_accessible_nodes numero de pontos asseciveis part de p
* @param points vetor auxiliar onde se guarda o ponto se for acessivel
* @param _row coord. ponto a validar
* @param _column coord. ponto a validar
*/
void validatePoint( int **map, int _height, int _width,
char *num_accessible_nodes, Point *points,
int _row, int _column){
if (isValidPoint(_row, _column, _height, _width, map)){
Point aux;
aux.row = _row;
aux.column = _column;
points[(int) *num_accessible_nodes] = aux;
*num_accessible_nodes = (*num_accessible_nodes) + 1;
}
}
/**
* gera as permutações do caminho e inidca a de melhor custo
* @param graph hipergrafo
* @param best_cost melhor custo ate ao momento
* @param num_points numeor de pontos do caminho melhor
* @param size numero de nós para os quais tem de se gerar
* permutacoes (num_tur_points-1(origem))
* @param answer ordem do melhor caminho
* @param visited vetor auxiliar que indica os nós visitados na análise
* em curso
* @param permutation vetor aux que guarda permutacao atual
* @param depth numero de nós visitados na analise em curso
* @param cost_acum custo da permutacao a ser analisada, no momento
*/
void checkPermutations(HyperNode *graph, int *best_cost, int *num_points, int size, int *answer, int *visited, int *permutation,
int depth, int cost_acum){
int cur_edge_cost = 0;
int aux_cost;
// se temos uma permutação completa cujo custo é inferior ao custo mínimo encontrado até agora
if (depth == size && ((aux_cost = pathCost(graph, permutation, size)) < *best_cost || *best_cost == -1 )){
*best_cost = aux_cost; // atualizar o custo
*num_points = 0;
int previous_ix = 0;
// atualizar a melhor permutação e o número de pontos no caminho
for (int i = 0; i < size; i++){
answer[i] = permutation[i];
*num_points = *num_points + graph[previous_ix].edges[permutation[i]]->num_points;
previous_ix = permutation[i];
}
return;
}
for (int i = 0; i < size; i++){
if (!visited[i]){
cur_edge_cost = depth ? graph[permutation[depth-1]].edges[i+1]->cost : graph[0].edges[i+1]->cost;
if (cur_edge_cost + cost_acum < *best_cost || *best_cost == -1){
visited[i] = 1;
permutation[depth] = i+1;
checkPermutations(graph, best_cost, num_points, size, answer, visited, permutation,depth + 1, cur_edge_cost + cost_acum);
visited[i] = 0;
}
}
}
}
/**
* calcula o custo do caminho de uma permutacao
*/
int pathCost(HyperNode *graph, int *permutation, int size){
int previous_ix = 0;
int cost = 0;
for (int i = 0; i < size; i = i + 1){
cost = cost + graph[previous_ix].edges[permutation[i]]->cost;
previous_ix = permutation[i];
}
return cost;
}