Satanick surfer en...: enero 2009

Que tal baturros

les dejo los algoritmos A* BFS y DFS

1 // ianuevo.cpp : Defines the entry point for the console application.

2 //

4 #include <stdio.h>

5 #include <math.h>

6 #include <iostream>

8 #include <GL/gl.h>

9 #include <GL/glut.h>

11 #define MAXNODOS 50

12 #define MAXVERTICES 200

13 #define max 50

14 #define nodostotal 21

18 struct punto

19 {

20 float x,y;

21 };

23 struct separacion

24 {

25 float sx,sy;

26 };

27 struct nodo

28 {

29 int rojo;

30 int id;

31 punto geometria;

32 separacion metrica;

33 };

35 struct grafo

36 {

37 int numeronodos;

38 nodo nodos[MAXNODOS];

39 punto pmin,pmax;

40 };

42 //usamos estas estructuras para calcular las posiciones relativas de los nodos

44 struct queue

45 {

46 int inicio, final, total;

47 int info[max];

48 };

50 struct stack

51 {

52 int topo;

53 int info[max + 1];

54 };

59 /*

60 id.- ciudad

61 01.- Amealco 08.- Huimilpan 15.- San Joaquín

62 02.- Arroyo Seco 09.- Jalpan de Serra 16.- San Juan del Río

63 03.- Bernal 10.- Landa de Matamoros 17.- Santa Rosa

64 04.- Cadereyta 11.- Pedro Escobedo 18.- Tequisquiapan

65 05.- La Cañada 12.- Peñamiller 19.- Tolimán

66 06.- Colón 13.- Pinal de Amoles 20.- Villa del Pueblito

67 07.- Ezequiel Montes 14.- Querétaro

68 */

70 char *ciudades[21] = {

71 "","Amealco","Arroyo Seco","Bernal","Cadereyta","La Canada","Colon","Ezequiel Montes",

72 "Huimilpan","Jalpan de Serra","Landa de Matamoros","Pedro Escobedo","Penamiller","Pinal de Amoles",

73 "Queretaro","San Joaquin","San Juan del Rio","Santa Rosa","Tequisquiapan","Toliman","Villa del Pueblito"

75 /* "","Amealco","Arroyo Seco","Bernal","Cadereyta","La Cañada","Colón","Ezequiel Montes",

76 "Huimilpan","Jalpan de Serra","Landa de Matamoros","Pedro Escobedo","Peñamiller","Pinal de Amoles",

77 "Querétaro","San Joaquín","San Juan del Río","Santa Rosa","Tequisquiapan","Tolimán","Villa del Pueblito"

78 */ };

79 int matrizadyacencia[21][21] =

80 {

81 /* A Ar B C lC Co E H J L P Pe Pi Q S Sj Sr T To V */

82 {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0},

83 {1, 0, 0, 0, 0, 0, 0, 0, 28, 0, 0, 0, 0, 0, 0, 0, 31, 0, 0, 0, 0}, // 01 Amealco -> 08 Huimilpan, 16 San Juan del Río

84 {2, 0, 0, 0, 0, 0, 0, 0, 0, 48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 02 Arroyo Seco -> 09 Jalpan de Serra

85 {3, 0, 0, 0, 0, 41, 23, 20, 0, 0, 0, 0, 62, 92, 0, 0, 0, 0, 0, 26, 0}, // 03 Bernal -> 05 La Cañada, 06 Colón, 07 Ezequiel Montes, 12 Peñamiller, 13 Pinal de Amoles, 19 Tolimán

86 {4, 0, 0, 0, 0, 0, 0, 12, 0, 0, 0, 0, 0, 0, 0, 64, 0, 0, 0, 0, 0}, // 04 Cadereyta -> 07 Ezequiel Montes, 15 San Joaquín

87 {5, 0, 0, 41, 0, 0, 50, 0, 0, 0, 0, 0, 0, 0, 7, 0, 0, 0, 50, 0, 0}, // 05 La Cañada -> 03 Bernal, 06 Colón, 14 Querétaro, 18 Tequisquiapan

88 {6, 0, 0, 23, 0, 50, 0, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 31, 0}, // 06 Colón -> 03 Bernal, 05 La Cañada, 07 Ezequiel Montes 19 Tolimán

89 {7, 0, 0, 20, 12, 0, 25, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 17, 0, 0}, // 07 Ezequiel Montes -> 03 Bernal, 04 Cadereyta, 06 Colón, 18 Tequisquiapan

90 {8, 28, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 34, 0, 0, 0, 0, 0, 30}, // 08 Huimilpan -> 01 Amealco, 14 Querétaro, 20 Villa del Pueblito

91 {9, 0, 48, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 40, 0, 0, 0, 0, 0, 0, 0}, // 09 Jalpan de Serra -> 02 Arroyo Seco, 10 Landa de Matamoros, 13 Pinal de Amoles

92 {0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, // 10 Landa de Matamoros -> 09 Jalpan de Serra

93 {1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 31, 0, 21, 0, 0, 0, 0}, // 11 Pedro Escobedo -> 14 Querétaro, 16 San Juan del Río

94 {2, 0, 0, 62, 0, 0, 0, 0, 0, 0, 0, 0, 0, 49, 0, 69, 0, 0, 0, 60, 0}, // 12 Peñamiller -> 03 Bernal, 13 Pinal de Amoles, 15 San Joaquín, 19 Tolimán

95 {3, 0, 0, 92, 0, 0, 0, 0, 0, 40, 0, 0, 49, 0, 0, 90, 0, 0, 0, 0, 0}, // 13 Pinal de Amoles -> 03 Bernal, 09 Jalpan de Serra, 12 Peñamiller

96 {4, 0, 0, 0, 0, 7, 0, 0, 34, 0, 0, 31, 0, 0, 0, 0, 0, 20, 0, 0, 7}, // 14 Querétaro -> 05 La Cañada, 08 Huimilpan, 11 Pedro Escobedo, 17 Santa Rosa, 20 Villa del Pueblito

97 {5, 0, 0, 0, 64, 0, 0, 0, 0, 0, 0, 0, 69, 90, 0, 0, 0, 0, 0, 0, 0}, // 15 San Joaquín -> 03 Bernal, 04 Cadereyta, 12 Peñamiller

98 {6, 31, 0, 0, 0, 0, 0, 0, 0, 0, 0, 21, 0, 0, 0, 0, 0, 0, 20, 0, 0}, // 16 San Juan del Río -> 0 1 Amealco, 11 Pedro Escobedo, 18 Tequisquiapan

99 {7, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0, 0, 26}, // 17 Santa Rosa -> 14 Querétaro, 20 Villa del Pueblito

100 {8, 0, 0, 0, 0, 50, 0, 17, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 0, 0}, // 18 Tequisquiapan -> 05 La Cañada, 07 Ezequiel Montes, 16 San Juan del Río

101 {9, 0, 0, 26, 0, 0, 31, 0, 0, 0, 0, 0, 60, 0, 0, 0, 0, 0, 0, 0, 0}, // 19 Tolimán -> 03 Bernal, 06 Colón, 12 Peñamiller

102 {0, 0, 0, 0, 0, 0, 0, 0, 30, 0, 0, 0, 0, 0, 7, 0, 0, 26, 0, 0, 0} // 20 Villa del Pueblito -> 08 Huimilpan, 14 Querétaro, 17 Santa Rosa

103 };

104

105 int d[21]={0};

106 int costos[21]={0};

107 int visitado[21]={0};

108 int padres[21]={0};

109 int vi[21]={0};

110 int pa[21]={0};

111 int r;

112 int nmin=0;

113 static char label[100];

114

115

116 float angulo=0.0;

117

118 grafo grafobusqueda;

119

120 void camino(int id)

121 {

122 if(padres[id]!=0)

123 {

124 camino(padres[id]);

125 }

126

127 printf(" %s ",ciudades[id]);

128 }

129

130

131 #pragma region geometria

132

133 float distancia(struct nodo a, struct nodo b)

134 {

135 float distx = a.geometria.x - b.geometria.x;

136 float disty = a.geometria.y - b.geometria.y;

137 float d = sqrt(distx*distx + disty*disty);

138 return d;

139 }

140 void repulsion(struct nodo a, struct nodo b)

141 {

142 int i = a.id;

143 int j = b.id;

144 float costo;

145 float k=1.0;//cte de separacion

146 float r=100;//radio maximo de desplazamiento, del mapa vi que la distancia maxima entre dos poblaciones era 90 asi que tome un valor un poco mayor

147 float d;//distancia de la repulsión

148 float f;//fuerza de la repulsión

149

150 float distx = a.geometria.x - b.geometria.x;

151 float disty = a.geometria.y - b.geometria.y;

152 d = sqrt(distx*distx + disty*disty);

153 costo= matrizadyacencia[i][j];

154

155 if(d<r)

156 {

157 f=powf(k,2.0f)/(powf(d,2.0f)*costo);

158 }

159 else

160 {

161 f=powf(k,2.0f)/(powf(r,2.0f)*costo);

162 }

163

164 b.metrica.sx += f*distx;

165 b.metrica.sy += f*disty;

166 a.metrica.sx -= f*distx;

167 a.metrica.sy -= f*disty;

168

169 }

170 void atraccion(struct nodo a, struct nodo b)

171 {

172

173 int i = a.id;

174 int j = b.id;

175

176 float k=1.0;//cte de separacion

177 float r=5;//radio minimo de desplazamiento, del mapa vi que la distancia minima entre dos poblaciones era 7 asi que tome un valor un poco menor

178 float d;//distancia de la repulsión

179 float f;//fuerza de la repulsión

180 float costo;

181

182 costo= matrizadyacencia[i][j];

183

184 float distx = a.geometria.x - b.geometria.x;

185 float disty = a.geometria.y - b.geometria.y;

186 d = sqrt(distx*distx + disty*disty);

187

188 if(costo!=0)

189 {

190 f=(powf(d,2.0f)-powf(costo,2.0f))/costo;

191 }

192 else

193 {

194 f=(powf(d,2.0f)-powf(costo,2.0f))*1;

195 }

196

197 f*=k*.5+100;

198 f/=d;

199

200

201 b.metrica.sx += f*distx;

202 b.metrica.sy += f*disty;

203 a.metrica.sx -= f*distx;

204 a.metrica.sy -= f*disty;

205

206 }

207

208 void calculaposiciones(void)

209 {

210 nodo a,b;

211

212 for(int i =1; i< nodostotal; i++)

213 {

214 a = grafobusqueda.nodos[i];

215 for(int j =1; j< nodostotal; j++)

216 {

217 b = grafobusqueda.nodos[j];

218 repulsion(a,b);

219 }

220 }

221 for(int i =1; i< nodostotal; i++)

222 {

223 a = grafobusqueda.nodos[i];

224 for(int j =1; j< nodostotal; j++)

225 {

226 b = grafobusqueda.nodos[j];

227 atraccion(a,b);

228 }

229 }

230

231 for(int i =1; i< nodostotal; i++)

232 {

233 grafobusqueda.nodos[i].geometria.x += grafobusqueda.nodos[i].metrica.sx;

234 grafobusqueda.nodos[i].geometria.y += grafobusqueda.nodos[i].metrica.sy;

235 }

236

237 }

238

239 void iniciagrafo(void)//estas rutinas son para acomodar el mapeo de los nodos de tal manera que me de las distancias relativas

240 { //para implementar el metodo a*

241 int i;

242 int n;

243 float inf = 1000;

244 grafobusqueda.numeronodos = nodostotal;

245

246 grafobusqueda.pmax.x = -inf;

247 grafobusqueda.pmax.y = -inf;

248 grafobusqueda.pmin.x = inf;

249 grafobusqueda.pmin.y = inf;

250

251 for(i=0;i<=grafobusqueda.numeronodos;i++)//se inician todos los nodos del grafo general a 0

252 {

253 grafobusqueda.nodos[i].id = i;

254 grafobusqueda.nodos[i].rojo = 0;

255 grafobusqueda.nodos[i].geometria.x = rand()%100;

256 grafobusqueda.nodos[i].geometria.y = rand()%100;

257 grafobusqueda.nodos[i].metrica.sx=0;

258 grafobusqueda.nodos[i].metrica.sy= 0;

259 }

260 grafobusqueda.nodos[14].geometria.x = 0;

261 grafobusqueda.nodos[14].geometria.y = 0;

262 grafobusqueda.nodos[2].geometria.x += 5;

263

264

265

266 }

267

268 void calculaminimoymaximo(void)

269 {

270 for(int n=1;n<nodostotal;n++)//vemos los limites del mapeo54

271 {

272 if(grafobusqueda.nodos[n].geometria.x < grafobusqueda.pmin.x)

273 {

274 grafobusqueda.pmin.x = grafobusqueda.nodos[n].geometria.x;

275 }

276 if(grafobusqueda.nodos[n].geometria.y < grafobusqueda.pmin.y)

277 {

278 grafobusqueda.pmin.y = grafobusqueda.nodos[n].geometria.y;

279 }

280 if(grafobusqueda.nodos[n].geometria.x > grafobusqueda.pmax.x)

281 {

282 grafobusqueda.pmax.x = grafobusqueda.nodos[n].geometria.x;

283 }

284 if(grafobusqueda.nodos[n].geometria.y > grafobusqueda.pmax.y)

285 {

286 grafobusqueda.pmax.y = grafobusqueda.nodos[n].geometria.y;

287 }

288 }

289 }

290

291 #pragma endregion operaciones geometricas para el calculo relativo de posiciones

292

293 #pragma region queue

294

295 void iniciarqueue(queue *q)

296 {

297 q->inicio = 1;

298 q->final = 0;

299 q->total = 0;

300 }

301

302 int queuevacio(queue *q)

303 {

304 return(q->total == 0 ? 1 : 0);

305 }

306

307 int queuelleno(queue *q)

308 {

309 return(q->total == nodostotal ? 1 : 0);

310 }

311

312 int cola(int id)

313 {

314 return(id==nodostotal ? 1 : id+1);

315 }

316 void insertarenqueue(queue *q, int id)

317 {

318 if(!queuelleno(q))

319 {

320 q->final=cola(q->final);

321 q->info[q->final]=id;

322 q->total++;

323 }

324 }

325 void anadiraqueue(queue *q, int id)

326 {

327 r++;

328 if(!queuelleno(q))

329 {

330 q->final=r;

331 q->info[q->final]=id;

332 q->total++;

333 }

334 }

335

336 int dequeue(queue *q)

337 {

338 int ret = 0;

339

340 if(!queuevacio(q))

341 {

342 ret = q->info[q->inicio];

343 q->inicio = cola(q->inicio );

344 q->total--;

345 }

346 return ret;

347 }

348

349 int quitardequeue(queue *q)

350 {

351 int ret = 0;

352

353 if(!queuevacio(q))

354 {

355 ret = q->info[q->inicio];

356 q->inicio = r--;

357 q->total--;

358 }

359 return ret;

360 }

361

362

363

364 #pragma endregion operaciones de queue

365

366 #pragma region stack

367

368 void iniciarstack(stack *s)

369 {

370 s->topo = 0;

371 }

372

373 int stackvacio(stack *s)

374 {

375 return s->topo==0 ? 1 : 0;

376 }

377

378 int stacklleno(stack *s)

379 {

380 return s->topo == max ? 1 : 0;

381 }

382

383 void Push(stack *s, int id)

384 {

385 if(!stacklleno(s))

386 {

387 s->topo++;

388 s->info[s->topo] = id;

389 }

390 }

391

392 int Pop(stack *s)

393 {

394 int ret = 0;

395

396 if(!stackvacio(s))

397 {

398 ret = s->info[s->topo];

399 s->topo--;

400 }

401

402 return ret;

403 }

404 #pragma endregion operaciones de stack

405

406 float heuristica(int inicio, int final)

407 {

408 stack *s = new stack();

409 int condicion =0;

410 float h =0;

411 iniciarstack(s);

412 Push(s, inicio);

413

414 for(int i =0;i<nodostotal;i++)

415 {

416 vi[i]=0;

417 }

418 for(int i=0;i<nodostotal+1;i++)

419 {

420 vi[i]=0;

421 pa[i]=0;

422 }

423

424

425 for(int j = 1;j<3;j++)

426 {

427 int y = Pop(s);

428 if(y == final)

429 {

430 camino(y);

431 condicion = 1;

432 }

433 else

434 {

435 vi[y] = 1;

436

437 for(int v = 1;v <= nodostotal-1; v++)

438 {

439 if(matrizadyacencia[y][v] != 0)

440 {

441 if(vi[v] == 0)

442 {

443 vi[v] = 1;

444 pa[v] = y;

445

446 if(v != final)

447 {

448 Push(s, v);

449 h=distancia(grafobusqueda.nodos[v],grafobusqueda.nodos[inicio]);

450 }

451 else

452 {

453 h=distancia(grafobusqueda.nodos[y],grafobusqueda.nodos[inicio]);

454 return h;

455 }

456 }

457 }

458 }

459 }

460 }

461 return h;

462 }

463

464

465

466

467 void bfs(int inicio, int final)

468 {

469 queue *q = new queue();

470 int condicion = 0;

471 r=0;

472 iniciarqueue(q);

473

474 anadiraqueue(q, inicio);

475

476 while(queuevacio(q)==0 || condicion == 1)

477 {

478 int u = quitardequeue(q);

479

480 if(u == final)

481 {

482 printf("mismo nodo");

483 camino(u);

484 condicion = 1;

485 }

486 else

487 {

488 visitado[u]= 1;

489

490 for(int v = 1;v<=nodostotal-1;v++)//leemos reenglon un de la matriz

491 {

492 if(matrizadyacencia[u][v] != 0)//vemos si hay algun nodo por el que nos podamos mover

493 {

494 if(visitado[v]==0)

495 {

496 visitado[v]=1;

497 padres[v]=u;

498

499 if(v !=final)

500 {

501 if(!queuelleno(q))

502 {

503 anadiraqueue(q, v);//agregamos el id del nodo por el cual nos movimos

504 camino(v);

505 printf("\n");

506 }

507 else

508 {

509 printf("queue lleno");

510 condicion =1;

511 }

512 }

513 else

514 {

515 camino(v);

516 return;

517 }

518 }

519 }

520 }

521 }

522 }

523 }

524

525

526

527 void ids(int inicio, int final)

528 {

529 queue *q = new queue();

530 int condicion = 0;

531 iniciarqueue(q);

532 insertarenqueue(q, inicio);

533

534 while(queuevacio(q)==0 || condicion == 1)

535 {

536 int u = dequeue(q);

537

538 if(u == final)

539 {

540 printf("mismo nodo");

541 camino(u);

542 condicion = 1;

543 }

544 else

545 {

546 visitado[u]= 1;

547

548 for(int v = 1;v<=nodostotal-1;v++)//leemos reenglon un de la matriz

549 {

550 if(matrizadyacencia[u][v] != 0)//vemos si hay algun nodo por el que nos podamos mover

551 {

552 if(visitado[v]==0)

553 {

554 visitado[v]=1;

555 padres[v]=u;

556

557 if(v !=final)

558 {

559 if(!queuelleno(q))

560 {

561 insertarenqueue(q, v);//agregamos el id del nodo por el cual nos movimos

562 camino(v);

563 printf("\n");

564 }

565 else

566 {

567 printf("queue lleno");

568 condicion =1;

569 }

570 }

571 else

572 {

573 camino(v);

574 return;

575 }

576 }

577 }

578 }

579 }

580 }

581 }

582

583

584

585 void dfs(int inicio, int final)

586 {

587

588 stack *s = new stack();

589 int condicion =0;

590

591 iniciarstack(s);

592 Push(s, inicio);

593

594 while(stackvacio(s) == 0 || condicion == 1)

595 {

596 int u = Pop(s);

597

598 if(u == final)

599 {

600 printf("mismo nodo");

601 camino(u);

602 condicion = 1;

603 }

604 else

605 {

606 visitado[u] = 1;

607

608 for(int v = 1; v <= nodostotal-1; v++)

609 {

610 if(matrizadyacencia[u][v] != 0)

611 {

612 if(visitado[v] == 0)

613 {

614 visitado[v] = 1;

615 padres[v] = u;

616

617

618 if(v != final)

619 {

620 if(!stacklleno(s))

621 {

622 Push(s, v);

623 camino(v);

624 printf("\n");

625 }

626 else

627 {

628 printf("Stack lleno.");

629 condicion = 1;

630 }

631 }

632 else

633 {

634 camino(v);

635 return;

636 }

637 }

638 }

639 }

640 }

641 }

642 }

643

644 void ucs(int inicio, int final)

645 {

646 stack *s = new stack();

647 int condicion = 0;

648 int min=1000;

649 int nodomin = 0;

650

651 iniciarstack(s);

652 Push(s, inicio);

653

654 while(stackvacio(s) == 0 || condicion == 1)

655 {

656 int u = Pop(s);

657 if(u == final)

658 {

659 printf("mismo nodo.");

660 camino(u);

661 condicion = 1;

662 }

663 else

664 {

665 visitado[u] = 1;

666 min=1000;

667 nodomin=0;

668

669 for(int v=1;v<nodostotal;v++){d[v]=matrizadyacencia[u][v];}

670

671 for(int v=1;v<nodostotal;v++)

672 {

673 if(visitado[v]!=0)

674 {

675 continue;

676 }

677 if(d[v]>0 && d[v]<min)

678 {

679 min=d[v];

680 nodomin=v;

681 }

682 }

683 visitado[nodomin] = 1;

684

685

686 if(visitado[nodomin]==visitado[u])

687 {

688 padres[nodomin] = u;

689 costos[nodomin] = d[nodomin];

690 if(nodomin != final)

691 {

692 if(!stacklleno(s))

693 {

694 Push(s, nodomin);

695 camino(nodomin);

696 printf(" %d",costos[nodomin]);

697 printf("\n");

698 }

699 else

700 {

701 printf("stack lleno.");

702 condicion = 1;

703 }

704 }

705 else

706 {

707 condicion=1;

708 camino(nodomin);

709 printf(" %d",costos[nodomin]);

710 return;

711 }

712 }

713 }

714

715 }

716 }

717

718 void a(int inicio, int final)

719 {

720 stack *s = new stack();

721 int condicion = 0;

722 int min=1000;

723 int nodomin = 0;

724

725 iniciarstack(s);

726 Push(s, inicio);

727

728 while(stackvacio(s) == 0 || condicion == 1)

729 {

730 int u = Pop(s);

731

732 if(u == final)

733 {

734 printf("mismo nodo.");

735 camino(u);

736 condicion = 1;

737 }

738 else

739 {

740

741 visitado[u] = 1;

742 min=1000;

743 nodomin=0;

744

745 for(int v = 1; v < nodostotal; v++){d[v]=matrizadyacencia[u][v];}

746

747 for(int v = 1; v < nodostotal; v++)

748 {

749 if(d[v] != 0)

750 {

751 d[v] += (int)heuristica(v,final);

752 }

753 }

754 for(int v=1;v<nodostotal;v++)

755 {

756 if(visitado[v]!=0)

757 {

758 continue;

759 }

760 if(d[v]>0 && d[v]<min)

761 {

762 min=d[v];

763 nodomin=v;

764 }

765 }

766 visitado[nodomin] = 1;

767 padres[nodomin] = u;

768 costos[nodomin] = d[nodomin];

769

770 if(visitado[nodomin]==visitado[u])

771 {

772 if(nodomin != final)

773 {

774 if(!stacklleno(s))

775 {

776 Push(s, nodomin);

777 camino(nodomin);

778 printf(" %d",costos[nodomin]);

779 printf("\n");

780 }

781 else

782 {

783 printf("stack lleno.");

784 condicion = 1;

785 }

786 }

787 else

788 {

789 condicion=1;

790 camino(nodomin);

791 printf(" %d",costos[nodomin]);

792 return;

793 }

794 }

795 }

796

797 }

798 }

799

800 void id(int inicio, int final)

801 {

802

803 stack *s = new stack();

804 int condicion =0;

805 int m =0;

806

807 iniciarstack(s);

808 Push(s, inicio);

809

810 for(m=1;m<nodostotal;m++)

811 {

812 int u = Pop(s);

813

814 if(u == final)

815 {

816 printf("mismo nodo");

817 camino(u);

818 condicion = 1;

819 return;

820 }

821 else

822 {

823

824

825 for(int v = 1; v <= nodostotal-1; v++)

826 {

827 if(matrizadyacencia[u][v] != 0)

828 {

829 if(visitado[v] == 0)

830 {

831 visitado[v] = 1;

832 padres[v] = u;

833

834

835 if(v != final)

836 {

837 if(!stacklleno(s))

838 {

839 visitado[u] = 1;

840 Push(s, v);

841 printf("%d",m);

842 camino(v);

843 printf("\n");

844 }

845 else

846 {

847 printf("Stack lleno.");

848 }

849 }

850 else

851 {

852 camino(v);

853 return;

854 }

855 }

856 }

857 }

858 }

859 }

860 }

861

862 #pragma region opengl

863

864 void init(void)

865 {

866 glClearColor (1.0, 1.0, 1.0, 0.5);

867 glShadeModel (GL_FLAT);

868 }

869

870 void inline drawString (char *s)

871 {

872 unsigned int i;

873 for (i=0; i<strlen(s); i++)

874 glutBitmapCharacter(GLUT_BITMAP_HELVETICA_12, s[i]);

875 }

876

877

878 void display(void)

879 {

880 glClear (GL_COLOR_BUFFER_BIT);

881 glColor3f (0, 0, 0);

882 glLoadIdentity();

883 gluLookAt (0.0, 0.0, 2.0, 0.0, 0.0, 0.0, 0.0, 1.0, 0.0);

884 glRotatef(angulo,0,0,1.0);

885

886 float x,y;

887

888 int cont,cont2;

889 for (cont=1;cont<grafobusqueda.numeronodos;cont++)

890 {

891 glPushMatrix();

892

893 if(grafobusqueda.nodos[cont].rojo ==1 )

894 {

895 glColor3f(0.2, 0.5, 0.1);

896 }

897 else

898 {

899 glColor3f(0.0, 0.0, 0.0);

900 }

901

902 glTranslatef(grafobusqueda.nodos[cont].geometria.x/grafobusqueda.pmax.x , grafobusqueda.nodos[cont].geometria.y/grafobusqueda.pmax.y, 0);

903 glutSolidSphere(.02, 32, 32);

904 glPopMatrix();

905 for (cont2=cont;cont2<grafobusqueda.numeronodos;cont2++)

906 {

907 if (matrizadyacencia[cont][cont2]!=0)

908 {

909 if(grafobusqueda.nodos[cont2].rojo ==1 )

910 {

911 glColor3f(0.2, 0.5, 0.1);

912 }

913 else

914 {

915 glColor3f(0.0, 0.0, 0.0);

916 }

917 glBegin(GL_LINES);

918 glVertex2f(grafobusqueda.nodos[cont].geometria.x/grafobusqueda.pmax.x , grafobusqueda.nodos[cont].geometria.y/grafobusqueda.pmax.y);

919 glVertex2f(grafobusqueda.nodos[cont2].geometria.x/grafobusqueda.pmax.x , grafobusqueda.nodos[cont2].geometria.y/grafobusqueda.pmax.y);

920 glEnd();

921 }

922 }

923

924 }

925 for(cont =1; cont<grafobusqueda.numeronodos;cont++)

926 {

927 glColor3f(0.2, 0.2, 0.2);

928 sprintf (label, " %2.0d %s",cont,ciudades[cont]);

929 glRasterPos2f (grafobusqueda.nodos[cont].geometria.x/grafobusqueda.pmax.x,grafobusqueda.nodos[cont].geometria.y/grafobusqueda.pmax.y);

930 drawString (label);

931 }

932

933

934

935 glFlush ();

936 glutSwapBuffers();

937 }

938

939 void reshape(int w, int h)

940 {

941 glViewport (0, 0, (GLsizei) w, (GLsizei) h);

942 glMatrixMode (GL_PROJECTION);

943 glLoadIdentity ();

944 glFrustum (-1, 1, -1, 1, 1.5, 25.0);

945 glMatrixMode (GL_MODELVIEW);

946 }

947

948 void keyboard(unsigned char key, int x, int y)

949 {

950 switch (key) {

951 case 27:

952 exit(0);

953 break;

954 }

955 }

956

957 void idle(void)

958 {

959 static int timelast=0;

960 int time;

961 time = glutGet(GLUT_ELAPSED_TIME);

962 if (time-timelast>10){

963 timelast=time;

964 if (angulo<360){

965 angulo+=0.05;

966 } else {

967 angulo=0.0;

968 }

969

970 }

971

972 calculaposiciones();

973

974

975

976 glutPostRedisplay();

977 }

978

979 #pragma endregion operaciones de opengl

980

981 int main(int argc, char** argv)

982 {

983 int inicio =1, fin=2,i;

984 int d;

985 int costototal=0;

986

987 printf("lista de ciudades en el mapa\n");

988

989 for(int i=1;i<=nodostotal - 1; i++)

990 {

991 printf("\n%2d - %s",i, ciudades[i]);

992 }

993

994 printf("\nIndique la ciudad de origen: ");

995 scanf("%d",&inicio);

996 // }while(inicio>0&&inicio<nodostotal);

997

998 printf("\nIndique la ciudad de destino: ");

999 scanf("%d",&fin);

1000 // }while(fin>0&&fin<nodostotal);

1001

1002 for(i = 0;i<=nodostotal-1;i++)

1003 {

1004 visitado[i]=0;

1005 }

1006

1007 printf("\n\nBFS\n");

1008 bfs(inicio, fin);

1009

1010 for(i = 0;i<=nodostotal-1;i++)

1011 {

1012 visitado[i]=0;

1013 }

1014

1015 printf("\n\nID\n");

1016 ids(inicio, fin);

1017

1018 for(i = 0;i<=nodostotal-1;i++)

1019 {

1020 visitado[i]=0;

1021 }

1022

1023 printf("\n\nDFS\n");

1024 dfs(inicio, fin);

1025

1026 for(i = 0;i<=nodostotal-1;i++)

1027 {

1028 visitado[i]=0;

1029 }

1030

1031 printf("\n\nUCS\n");

1032 ucs(inicio, fin);

1033

1034 for(int j=1;j<nodostotal;j++)

1035 {

1036 costototal += costos[j];

1037 }

1038 printf("\ncosto total: %d",costototal);

1039

1040 for(i = 0;i<nodostotal;i++)

1041 {

1042 visitado[i]=0;

1043 costos[i]=0;

1044 }

1045 iniciagrafo();

1046 calculaminimoymaximo();

1047

1048 printf("\n\nA*\n");

1049 a(inicio, fin);

1050

1051 for(int j=1;j<nodostotal;j++)

1052 {

1053 costototal += costos[j];

1054 }

1055 printf("\ncosto total: %d",costototal);

1056

1057 for(i = 0;i<=nodostotal-1;i++)

1058 {

1059 visitado[i]=0;

1060 }

1061

1062 printf("\n\nID segundo algoritmo\n");

1063 id(inicio, fin);

1064

1065

1066 /*

1067 * Inicializando OpenGL

1068 * */

1069 glutInit(&argc, argv);

1070 glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGB);

1071 glutInitWindowSize (800, 800);

1072 glutInitWindowPosition (100, 100);

1073 glutCreateWindow (argv[0]);

1074 init ();

1075 glutDisplayFunc(display);

1076 glutReshapeFunc(reshape);

1077 glutKeyboardFunc(keyboard);

1078 glutIdleFunc(idle);

1079

1080 /*

1081 * Inicializando Entrada del Grafo

1082 * */

1083

1084 /*

1085 * Entrando en el ciclo

1086 * */

1087

1088 glutMainLoop();

1089

1090 return 0;

1091 }

en post posteriores explicare paso por paso y el resultado del codigo

1/29/2009

The.Poughkeepsie.Tapes.DVDRip.XviD.2008-HOOKAH.avi

1/15/2009

volviendo al blog