API tools faq
paste
Advertisement
Guest User

Untitled

a guest
Nov 17th, 2018
100
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 29.07 KB | None | 0 0
raw download clone embed print report
  1. // Clase para el algoritmo: Busqueda en anchura
  2. public class BFS {
  3. // variables del algoritmo
  4. int j, n, m, s;
  5. int Step;
  6. String miObjetivo;
  7. Nodo nodo, suc, actual;
  8. LinkedList<String> cola;
  9. Graphics g;
  10.  
  11. // inicializa el algoritmo
  12. public BFS() {
  13. // inicializa el algoritmo en caso de que haya uno cargado
  14. if (ListaNodos.size() > 0)
  15. inicio();
  16. }
  17.  
  18. // metodos para gestionar variables
  19. public String getCola() {
  20. int temp;
  21. String cadena;
  22. if ((Step == 0) || (Step > 3)) {
  23. cadena = "QUEUE={";
  24. for (temp = 0; temp < cola.size(); temp++) {
  25. cadena += cola.get(temp);
  26. if (temp < cola.size() - 1)
  27. cadena += ", ";
  28. }
  29. cadena += "}";
  30. } else {
  31. cadena = "";
  32. }
  33. return cadena;
  34. }
  35.  
  36. // reinicia el algoritmo
  37. public void reset() {
  38. // inicia el algoritmo;
  39. if (ListaNodos.size() > 0)
  40. inicio();
  41. }
  42.  
  43. // ejecuta el algoritmo en modo temporizador
  44. public void run() {
  45. while (Step < 4) {
  46. switch (Step) {
  47. case 0:
  48. paso0();
  49. break;
  50. case 1:
  51. paso1();
  52. break;
  53. case 2:
  54. paso2();
  55. break;
  56. case 3:
  57. paso3();
  58. break;
  59. default:
  60. Grafo.this.NodoObjetivo = miObjetivo;
  61. Grafo.this.paintGrafo();
  62. }
  63. // retardo de un segundo
  64. try {
  65. Thread.sleep(Temporizador);
  66. } catch (Exception e) {
  67. }
  68. }
  69. Grafo.this.NodoObjetivo = miObjetivo;
  70. Grafo.this.paintGrafo();
  71. }
  72.  
  73. // ejecuta el algoritmo en modo paso por paso
  74. public boolean step() {
  75. boolean ejecutandose = true;
  76. switch (Step) {
  77. case 0:
  78. paso0();
  79. break;
  80. case 1:
  81. paso1();
  82. break;
  83. case 2:
  84. paso2();
  85. break;
  86. case 3:
  87. paso3();
  88. break;
  89. default: {
  90. ejecutandose = false;
  91. Grafo.this.NodoObjetivo = miObjetivo;
  92. Grafo.this.paintGrafo();
  93. }
  94. }
  95. return ejecutandose;
  96. }
  97.  
  98. // metodos para desglosar el algoritmo en pasos
  99. private void inicio() {
  100. // inicializa el objetivo
  101. miObjetivo = "";
  102. // inicializa variables para explorar sucesores
  103. j = 0;
  104. m = 0;
  105. nodo = null;
  106. suc = null;
  107. actual = null;
  108. // inicializa objetos
  109. cola = new LinkedList<String>();
  110. g = Grafo.this.getGraphics();
  111. // comienza por el nodo raiz
  112. nodo = ListaNodos.get(0);
  113. cola.add(nodo.toString());
  114. // siguiente paso
  115. Step = 0;
  116. }
  117.  
  118. // metodos para desglosar el algoritmo en pasos
  119. private void paso0() {
  120. if (cola.size() != 0) {
  121. // extrae el primer elemento de la cola
  122. n = IndiceNodos.indexOf(cola.poll());
  123. nodo = ListaNodos.get(n);
  124. // establece el nodo actual
  125. nodo.setEstado(Nodo.TEstado.ACTUAL);
  126. nodo.pintarNodo(g);
  127. actual = nodo;
  128. // si el nodo raiz es objetivo
  129. if (nodo.getEsObjetivo()) {
  130. // establece el nodo objetivo
  131. miObjetivo = nodo.toString();
  132. // termina con exito
  133. Step = 4;
  134. } else {
  135. // explora todos los nodos sucesores
  136. m = nodo.maxSucesores();
  137. j = 0;
  138. // establece el siguiente paso
  139. Step = 1;
  140. }
  141. } else {
  142. // termina sin exito
  143. Step = 4;
  144. }
  145. }
  146.  
  147. private void paso1() {
  148. if (j < m) {
  149. s = IndiceNodos.indexOf(nodo.getIdSucesor(j));
  150. suc = ListaNodos.get(s);
  151. // establece puntero a nodo si el sucesor no se ha generado
  152. suc.setIdPuntero(nodo.toString());
  153. suc.setCostePuntero(nodo.getCosteSucesor(j));
  154. suc.setCosteCamino(nodo.getCosteSucesor(j)
  155. + nodo.getCosteCamino());
  156. suc.setEstado(Nodo.TEstado.ABIERTO);
  157. suc.pintarNodo(g);
  158. cola.add(suc.toString());
  159. // comprueba si es objetivo
  160. if (suc.getEsObjetivo()) {
  161. // establece el nodo objetivo
  162. miObjetivo = suc.toString();
  163. // establece paso 2
  164. Step = 2;
  165. }
  166. j++;
  167. } else {
  168. // establece siguiente paso
  169. Step = 2;
  170. paso2();
  171. }
  172. }
  173.  
  174. private void paso2() {
  175. // actualiza el nodo actual
  176. actual.setEstado(Nodo.TEstado.CERRADO);
  177. actual.pintarNodo(g);
  178. // establece el siguiente paso
  179. if (miObjetivo != "")
  180. Step = 3;
  181. else
  182. Step = 0;
  183. }
  184.  
  185. private void paso3() {
  186. if (miObjetivo != "") {
  187. // establece el estado de exito
  188. n = IndiceNodos.indexOf(miObjetivo);
  189. nodo = ListaNodos.get(n);
  190. nodo.setEstado(Nodo.TEstado.ACTUAL);
  191. nodo.pintarNodo(g);
  192. }
  193. // terminan con exito
  194. Step = 4;
  195. }
  196. }
  197.  
  198. // Clase para el algoritmo: Busqueda en profundidad
  199. public class DFS {
  200. // variables del algoritmo
  201. int j, n, m, s;
  202. int Step;
  203. String miObjetivo;
  204. Nodo nodo, suc, actual;
  205. Stack<String> pila;
  206. Stack<String> buffer;
  207. Graphics g;
  208.  
  209. // inicializa el algoritmo
  210. public DFS() {
  211. // inicializa el algoritmo en caso de que haya uno cargado
  212. if (ListaNodos.size() > 0)
  213. inicio();
  214. }
  215.  
  216. // metodos para gestionar variables
  217. public String getPila() {
  218. int temp;
  219. String cadena;
  220. if ((Step == 0) || (Step > 3)) {
  221. cadena = "STACK={";
  222. for (temp = pila.size() - 1; temp >= 0; temp--) {
  223. cadena += pila.get(temp);
  224. if (temp > 0)
  225. cadena += ", ";
  226. }
  227. cadena += "}";
  228. } else {
  229. cadena = "";
  230. }
  231. return cadena;
  232. }
  233.  
  234. // reinicia el algoritmo
  235. public void reset() {
  236. // inicia el algoritmo;
  237. if (ListaNodos.size() > 0)
  238. inicio();
  239. }
  240.  
  241. // ejecuta el algoritmo en modo temporizador
  242. public void run() {
  243. while (Step < 4) {
  244. switch (Step) {
  245. case 0:
  246. paso0();
  247. break;
  248. case 1:
  249. paso1();
  250. break;
  251. case 2:
  252. paso2();
  253. break;
  254. case 3:
  255. paso3();
  256. break;
  257. default:
  258. Grafo.this.NodoObjetivo = miObjetivo;
  259. Grafo.this.paintGrafo();
  260. }
  261. // retardo de un segundo
  262. try {
  263. Thread.sleep(Temporizador);
  264. } catch (Exception e) {
  265. }
  266. }
  267. Grafo.this.NodoObjetivo = miObjetivo;
  268. Grafo.this.paintGrafo();
  269. }
  270.  
  271. // ejecuta el algoritmo en modo paso por paso
  272. public boolean step() {
  273. boolean ejecutandose = true;
  274. switch (Step) {
  275. case 0:
  276. paso0();
  277. break;
  278. case 1:
  279. paso1();
  280. break;
  281. case 2:
  282. paso2();
  283. break;
  284. case 3:
  285. paso3();
  286. break;
  287. default: {
  288. ejecutandose = false;
  289. Grafo.this.NodoObjetivo = miObjetivo;
  290. Grafo.this.paintGrafo();
  291. }
  292. }
  293. return ejecutandose;
  294. }
  295.  
  296. // metodos para desglosar el algoritmo en pasos
  297. private void inicio() {
  298. // inicializa el objetivo
  299. miObjetivo = "";
  300. // inicializa variables
  301. j = 0;
  302. m = 0;
  303. nodo = null;
  304. suc = null;
  305. actual = null;
  306. // inicializa objetos
  307. pila = new Stack<String>();
  308. buffer = new Stack<String>();
  309. g = Grafo.this.getGraphics();
  310. // comienza por el nodo raiz
  311. nodo = ListaNodos.get(0);
  312. pila.push(nodo.toString());
  313. // siguiente paso
  314. Step = 0;
  315. }
  316.  
  317. // metodos para desglosar el algoritmo en pasos
  318. private void paso0() {
  319. if (pila.size() != 0) {
  320. // extrae el primer elemento de la pila
  321. n = IndiceNodos.indexOf(pila.pop());
  322. nodo = ListaNodos.get(n);
  323. // establece el nodo actual
  324. nodo.setEstado(Nodo.TEstado.ACTUAL);
  325. nodo.pintarNodo(g);
  326. actual = nodo;
  327. // si el nodo raiz es objetivo
  328. if (nodo.getEsObjetivo()) {
  329. // establece el nodo objetivo
  330. miObjetivo = nodo.toString();
  331. // termina con exito
  332. Step = 4;
  333. } else {
  334. // explora todos los nodos sucesores
  335. m = nodo.maxSucesores();
  336. j = 0;
  337. // establece el siguiente paso
  338. Step = 1;
  339. }
  340. } else {
  341. // termina sin exito
  342. Step = 4;
  343. }
  344. }
  345.  
  346. private void paso1() {
  347. if (j < m) {
  348. s = IndiceNodos.indexOf(nodo.getIdSucesor(j));
  349. suc = ListaNodos.get(s);
  350. // establece puntero a nodo si el sucesor no se ha generado
  351. suc.setIdPuntero(nodo.toString());
  352. suc.setCostePuntero(nodo.getCosteSucesor(j));
  353. suc.setCosteCamino(nodo.getCosteSucesor(j)
  354. + nodo.getCosteCamino());
  355. suc.setEstado(Nodo.TEstado.ABIERTO);
  356. suc.pintarNodo(g);
  357. buffer.add(suc.toString());
  358. // comprueba si es objetivo
  359. if (suc.getEsObjetivo()) {
  360. // establece el nodo objetivo
  361. miObjetivo = suc.toString();
  362. // establece siguiente paso
  363. Step = 2;
  364. }
  365. j++;
  366. } else {
  367. // establece siguiente paso
  368. Step = 2;
  369. paso2();
  370. }
  371. }
  372.  
  373. private void paso2() {
  374. // actualiza el nodo actual
  375. actual.setEstado(Nodo.TEstado.CERRADO);
  376. actual.pintarNodo(g);
  377. // copia el buffer en la pila del algoritmo
  378. while (buffer.size() > 0)
  379. pila.push(buffer.pop());
  380. // establece el siguiente paso
  381. if (miObjetivo != "")
  382. Step = 3;
  383. else
  384. Step = 0;
  385. }
  386.  
  387. private void paso3() {
  388. if (miObjetivo != "") {
  389. // establece el estado de exito
  390. n = IndiceNodos.indexOf(miObjetivo);
  391. nodo = ListaNodos.get(n);
  392. nodo.setEstado(Nodo.TEstado.ACTUAL);
  393. nodo.pintarNodo(g);
  394. }
  395. // terminan con exito
  396. Step = 4;
  397. }
  398. }
  399.  
  400. // Clase para el algoritmo: Escalada simple
  401. public class SHC {
  402. // variables del algoritmo
  403. int j, n, m, s;
  404. int Step;
  405. String miObjetivo;
  406. String actual;
  407. Nodo nodo, suc;
  408. Graphics g;
  409.  
  410. // inicializa el algoritmo
  411. public SHC() {
  412. // inicializa el algoritmo en caso de que haya uno cargado
  413. if (ListaNodos.size() > 0)
  414. inicio();
  415. }
  416.  
  417. // reinicia el algoritmo
  418. public void reset() {
  419. // inicia el algoritmo;
  420. if (ListaNodos.size() > 0)
  421. inicio();
  422. }
  423.  
  424. // ejecuta el algoritmo en modo temporizador
  425. public void run() {
  426. while (Step < 3) {
  427. switch (Step) {
  428. case 0:
  429. paso0();
  430. break;
  431. case 1:
  432. paso1();
  433. break;
  434. case 2:
  435. paso2();
  436. break;
  437. default:
  438. Grafo.this.NodoObjetivo = miObjetivo;
  439. Grafo.this.paintGrafo();
  440. }
  441. // retardo de un segundo
  442. try {
  443. Thread.sleep(Temporizador);
  444. } catch (Exception e) {
  445. }
  446. }
  447. Grafo.this.NodoObjetivo = miObjetivo;
  448. Grafo.this.paintGrafo();
  449. }
  450.  
  451. // ejecuta el algoritmo en modo paso por paso
  452. public boolean step() {
  453. boolean ejecutandose = true;
  454. switch (Step) {
  455. case 0:
  456. paso0();
  457. break;
  458. case 1:
  459. paso1();
  460. break;
  461. case 2:
  462. paso2();
  463. break;
  464. default: {
  465. ejecutandose = false;
  466. Grafo.this.NodoObjetivo = miObjetivo;
  467. Grafo.this.paintGrafo();
  468. }
  469. }
  470. return ejecutandose;
  471. }
  472.  
  473. // metodos para desglosar el algoritmo en pasos
  474. private void inicio() {
  475. // inicializa el objetivo
  476. miObjetivo = "";
  477. // inicializa variables para explorar sucesores
  478. j = 0;
  479. m = 0;
  480. nodo = null;
  481. suc = null;
  482. // inicializa objetos
  483. actual = "";
  484. g = Grafo.this.getGraphics();
  485. // comienza por el primer nodo
  486. nodo = ListaNodos.get(0);
  487. actual = nodo.toString();
  488. // siguiente paso
  489. Step = 0;
  490. }
  491.  
  492. private void paso0() {
  493. // extrae el nodo de la cola
  494. n = IndiceNodos.indexOf(actual);
  495. nodo = ListaNodos.get(n);
  496. nodo.setEstado(Nodo.TEstado.ACTUAL);
  497. nodo.pintarNodo(g);
  498. // comprueba si es objetivo
  499. if (nodo.getEsObjetivo()) {
  500. // establece el objetivo encontrado
  501. miObjetivo = nodo.toString();
  502. // termina con exito
  503. Step = 3;
  504. } else {
  505. // se prepara para explorar los sucesores
  506. m = nodo.maxSucesores();
  507. j = 0;
  508. // siguiente paso
  509. Step = 1;
  510. }
  511. }
  512.  
  513. private void paso1() {
  514. if (j < m) {
  515. // seleccionar un operador que no haya sido aplicado con
  516. // aterioridad
  517. do {
  518. s = IndiceNodos.indexOf(nodo.getIdSucesor(j));
  519. suc = ListaNodos.get(s);
  520. if (suc.getEstado() != Nodo.TEstado.NOGENERADO) {
  521. // siguiente sucesor
  522. j++;
  523. }
  524. } while ((j < m)
  525. && (suc.getEstado() != Nodo.TEstado.NOGENERADO));
  526. if (suc.getEstado() == Nodo.TEstado.NOGENERADO) {
  527. // establece puntero a nodo
  528. suc.setIdPuntero(nodo.toString());
  529. suc.setCostePuntero(nodo.getCosteSucesor(j));
  530. suc.setCosteCamino(nodo.getCosteSucesor(j)
  531. + nodo.getCosteCamino());
  532. // pinta el nodo abierto
  533. suc.setEstado(Nodo.TEstado.ABIERTO);
  534. suc.pintarNodo(g);
  535. // si es un estado objetivo, devolverlo y terminar
  536. if (suc.getEsObjetivo()
  537. || (suc.getValor() < nodo.getValor())) {
  538. // siguiente paso
  539. Step = 2;
  540. } else {
  541. // si no es objetivo ni es mejor continuar bucle
  542. j++;
  543. }
  544. } else {
  545. // termina con fracaso
  546. Step = 3;
  547. }
  548. } else {
  549. // termina con fracaso
  550. Step = 3;
  551. }
  552. }
  553.  
  554. private void paso2() {
  555. // pinta el nodo
  556. nodo.setEstado(Nodo.TEstado.CERRADO);
  557. nodo.pintarNodo(g);
  558. // actualiza la cola
  559. actual = suc.toString();
  560. // siguiente paso
  561. Step = 0;
  562. }
  563. }
  564.  
  565. // Clase para el algoritmo: Escalada por la maxima pendiente
  566. public class SAHC {
  567. // variables del algoritmo
  568. int j, n, m, s;
  569. int Step;
  570. String miObjetivo;
  571. String actual;
  572. Nodo nodo, suc, succ;
  573. Graphics g;
  574.  
  575. // inicializa el algoritmo
  576. public SAHC() {
  577. // inicializa el algoritmo en caso de que haya uno cargado
  578. if (ListaNodos.size() > 0)
  579. inicio();
  580. }
  581.  
  582. // reinicia el algoritmo
  583. public void reset() {
  584. // inicia el algoritmo;
  585. if (ListaNodos.size() > 0)
  586. inicio();
  587. }
  588.  
  589. // ejecuta el algoritmo en modo temporizador
  590. public void run() {
  591. while (Step < 4) {
  592. switch (Step) {
  593. case 0:
  594. paso0();
  595. break;
  596. case 1:
  597. paso1();
  598. break;
  599. case 2:
  600. paso2();
  601. break;
  602. case 3:
  603. paso3();
  604. break;
  605. default:
  606. Grafo.this.NodoObjetivo = miObjetivo;
  607. Grafo.this.paintGrafo();
  608. }
  609. // retardo de un segundo
  610. try {
  611. Thread.sleep(Temporizador);
  612. } catch (Exception e) {
  613. }
  614. }
  615. Grafo.this.NodoObjetivo = miObjetivo;
  616. Grafo.this.paintGrafo();
  617. }
  618.  
  619. // ejecuta el algoritmo en modo paso por paso
  620. public boolean step() {
  621. boolean ejecutandose = true;
  622. switch (Step) {
  623. case 0:
  624. paso0();
  625. break;
  626. case 1:
  627. paso1();
  628. break;
  629. case 2:
  630. paso2();
  631. break;
  632. case 3:
  633. paso3();
  634. break;
  635. default: {
  636. ejecutandose = false;
  637. Grafo.this.NodoObjetivo = miObjetivo;
  638. Grafo.this.paintGrafo();
  639. }
  640. }
  641. return ejecutandose;
  642. }
  643.  
  644. // metodos para desglosar el algoritmo en pasos
  645. private void inicio() {
  646. // inicializa el objetivo
  647. miObjetivo = "";
  648. // inicializa variables para explorar sucesores
  649. j = 0;
  650. m = 0;
  651. nodo = null;
  652. suc = null;
  653. succ = null;
  654. // inicializa objetos
  655. actual = "";
  656. g = Grafo.this.getGraphics();
  657. // comienza por el primer nodo
  658. nodo = ListaNodos.get(0);
  659. actual = nodo.toString();
  660. // siguiente paso
  661. Step = 0;
  662. }
  663.  
  664. private void paso0() {
  665. // extrae el nodo actual
  666. n = IndiceNodos.indexOf(actual);
  667. nodo = ListaNodos.get(n);
  668. nodo.setEstado(Nodo.TEstado.ACTUAL);
  669. nodo.pintarNodo(g);
  670. // comprueba si es objetivo
  671. if (nodo.getEsObjetivo()) {
  672. // establece el objetivo encontrado
  673. miObjetivo = nodo.toString();
  674. // termina con exito
  675. Step = 4;
  676. } else {
  677. // se prepara para explorar los sucesores
  678. m = nodo.maxSucesores();
  679. j = 0;
  680. // siguiente paso
  681. Step = 1;
  682. }
  683. }
  684.  
  685. private void paso1() {
  686. if ((j < m) && (j == 0)) {
  687. // asigna el primer sucesor a succ para comparar
  688. s = IndiceNodos.indexOf(nodo.getIdSucesor(0));
  689. succ = ListaNodos.get(s);
  690. // establece puntero a nodo
  691. succ.setIdPuntero(nodo.toString());
  692. succ.setCostePuntero(nodo.getCosteSucesor(j));
  693. succ.setCosteCamino(nodo.getCosteSucesor(j)
  694. + nodo.getCosteCamino());
  695. // pinta el nodo abierto
  696. succ.setEstado(Nodo.TEstado.ABIERTO);
  697. succ.pintarNodo(g);
  698. j++;
  699. // siguiente paso
  700. Step = 2;
  701. } else {
  702. // termina con fracaso
  703. Step = 4;
  704. }
  705. }
  706.  
  707. private void paso2() {
  708. // explora los sucesores
  709. if (j < m) {
  710. s = IndiceNodos.indexOf(nodo.getIdSucesor(j));
  711. suc = ListaNodos.get(s);
  712. // establece puntero a nodo
  713. suc.setIdPuntero(nodo.toString());
  714. suc.setCostePuntero(nodo.getCosteSucesor(j));
  715. suc.setCosteCamino(nodo.getCosteSucesor(j)
  716. + nodo.getCosteCamino());
  717. // pinta el nodo abierto
  718. suc.setEstado(Nodo.TEstado.ABIERTO);
  719. suc.pintarNodo(g);
  720. // si es un estado objetivo, devolverlo y terminar
  721. if (suc.getEsObjetivo()) {
  722. // selecciona el mejor estado
  723. succ = suc;
  724. // siguiente paso
  725. Step = 3;
  726. } else if (suc.getValor() < succ.getValor()) {
  727. // selecciona el mejor estado
  728. succ = suc;
  729. }
  730. // siguiente sucesor
  731. j++;
  732. } else {
  733. if (succ.getValor() < nodo.getValor()) {
  734. // siguiente paso
  735. Step = 3;
  736. paso3();
  737. } else {
  738. // termina con fracaso
  739. Step = 4;
  740. }
  741. }
  742. }
  743.  
  744. private void paso3() {
  745. // pinta el nodo
  746. nodo.setEstado(Nodo.TEstado.CERRADO);
  747. nodo.pintarNodo(g);
  748. // actualiza el nodo actual
  749. actual = succ.toString();
  750. // siguiente paso
  751. Step = 0;
  752. }
  753. }
  754.  
  755. // Clase para el algoritmo: Primero el mejor
  756. public class BF {
  757. // variables del algoritmo
  758. int j, n, m, s;
  759. int Step;
  760. String miObjetivo;
  761. Nodo nodo, suc;
  762. Vector<String> abiertos;
  763. Vector<String> cerrados;
  764. Graphics g;
  765.  
  766. // inicializa el algoritmo
  767. public BF() {
  768. // inicializa el algoritmo en caso de que haya uno cargado
  769. if (ListaNodos.size() > 0)
  770. inicio();
  771. }
  772.  
  773. // metodos para gestionar variables
  774. public String getAbierta() {
  775. int temp;
  776. String cadena;
  777. int itemp;
  778. Nodo ntemp;
  779. if (Step == 0) {
  780. cadena = "OPENED={";
  781. for (temp = 0; temp < abiertos.size(); temp++) {
  782. cadena += abiertos.get(temp) + "(";
  783. itemp = IndiceNodos.indexOf(abiertos.get(temp));
  784. ntemp = ListaNodos.get(itemp);
  785. cadena += Double.toString(ntemp.getValor());
  786. cadena += ")";
  787. if (temp < abiertos.size() - 1)
  788. cadena += ", ";
  789. }
  790. cadena += "}";
  791. } else {
  792. cadena = "";
  793. }
  794. return cadena;
  795. }
  796.  
  797. public String getCerrada() {
  798. int temp;
  799. String cadena;
  800. if (Step == 0) {
  801. cadena = "CLOSED={";
  802. for (temp = 0; temp < cerrados.size(); temp++) {
  803. cadena += cerrados.get(temp);
  804. if (temp < cerrados.size() - 1)
  805. cadena += ", ";
  806. }
  807. cadena += "}";
  808. } else {
  809. cadena = "";
  810. }
  811. return cadena;
  812. }
  813.  
  814. // reinicia el algoritmo
  815. public void reset() {
  816. // inicia el algoritmo;
  817. if (ListaNodos.size() > 0)
  818. inicio();
  819. }
  820.  
  821. // ejecuta el algoritmo en modo temporizador
  822. public void run() {
  823. while (Step < 2) {
  824. switch (Step) {
  825. case 0:
  826. paso0();
  827. break;
  828. case 1:
  829. paso1();
  830. break;
  831. default:
  832. Grafo.this.NodoObjetivo = miObjetivo;
  833. Grafo.this.paintGrafo();
  834. }
  835. // retardo de un segundo
  836. try {
  837. Thread.sleep(Temporizador);
  838. } catch (Exception e) {
  839. }
  840. }
  841. Grafo.this.NodoObjetivo = miObjetivo;
  842. Grafo.this.paintGrafo();
  843. }
  844.  
  845. // ejecuta el algoritmo en modo paso por paso
  846. public boolean step() {
  847. boolean ejecutandose = true;
  848. switch (Step) {
  849. case 0:
  850. paso0();
  851. break;
  852. case 1:
  853. paso1();
  854. break;
  855. default: {
  856. ejecutandose = false;
  857. Grafo.this.NodoObjetivo = miObjetivo;
  858. Grafo.this.paintGrafo();
  859. }
  860. }
  861. return ejecutandose;
  862. }
  863.  
  864. // metodos para desglosar el algoritmo en pasos
  865. private void inicio() {
  866. // inicializa el objetivo
  867. miObjetivo = "";
  868. // inicializa variables para explorar sucesores
  869. j = 0;
  870. m = 0;
  871. nodo = null;
  872. suc = null;
  873. // inicializa objetos
  874. abiertos = new Vector<String>();
  875. cerrados = new Vector<String>();
  876. g = Grafo.this.getGraphics();
  877. // comienza por el primer nodo
  878. nodo = ListaNodos.get(0);
  879. // encola el primer nodo
  880. abiertos.add(nodo.toString());
  881. // siguiente paso
  882. Step = 0;
  883. }
  884.  
  885. private void paso0() {
  886. if (abiertos.size() != 0) {
  887. // extrae el primer nodo de la pila abiertos
  888. n = IndiceNodos.indexOf(abiertos.remove(0));
  889. nodo = ListaNodos.get(n);
  890. nodo.setEstado(Nodo.TEstado.ACTUAL);
  891. nodo.pintarNodo(g);
  892. if (!nodo.getEsObjetivo()) {
  893. // se inserta en la lista de cerrados
  894. cerrados.add(nodo.toString());
  895. // se prepara para explorar los sucesores
  896. m = nodo.maxSucesores();
  897. j = 0;
  898. // siguiente paso
  899. Step = 1;
  900. } else {
  901. // establece el objetivo encontrado
  902. miObjetivo = nodo.toString();
  903. // termina con exito
  904. Step = 2;
  905. }
  906. } else {
  907. // termina con fracaso
  908. Step = 2;
  909. }
  910. }
  911.  
  912. private void paso1() {
  913. if (j < m) {
  914. // obtiene el nodo sucesor
  915. s = IndiceNodos.indexOf(nodo.getIdSucesor(j));
  916. suc = ListaNodos.get(s);
  917. if (suc.getEstado() == Nodo.TEstado.NOGENERADO) {
  918. // establece puntero a nodo si el sucesor no se ha generado
  919. suc.setIdPuntero(nodo.toString());
  920. suc.setCostePuntero(nodo.getCosteSucesor(j));
  921. suc.setCosteCamino(nodo.getCosteSucesor(j)
  922. + nodo.getCosteCamino());
  923. // inserta el elemento en la lista ABIERTOS
  924. suc.setEstado(Nodo.TEstado.ABIERTO);
  925. suc.pintarNodo(g);
  926. // inserta el sucesor en la lista de abiertos
  927. abiertos.add(suc.toString());
  928. } else if ((suc.getEstado() == Nodo.TEstado.ABIERTO)) {
  929. // modifica el puntero del sucesor a nodo
  930. suc.setIdPuntero(nodo.toString());
  931. suc.setCostePuntero(nodo.getCosteSucesor(j));
  932. suc.setCosteCamino(nodo.getCosteSucesor(j)
  933. + nodo.getCosteCamino());
  934. suc.pintarNodo(g);
  935. } else if ((suc.getEstado() == Nodo.TEstado.CERRADO)) {
  936. // no se que hacer
  937. }
  938. j++;
  939. } else {
  940. if (abiertos.size() != 0) {
  941. // pinta el nodo
  942. nodo.setEstado(Nodo.TEstado.CERRADO);
  943. nodo.pintarNodo(g);
  944. // reordena la lista de abiertos en funcion de: f = h + g
  945. reordenar(abiertos);
  946. // siguiente paso
  947. Step = 0;
  948. } else {
  949. // termina con fracaso
  950. Step = 2;
  951. }
  952. }
  953. }
  954.  
  955. private void reordenar(Vector<String> vector) {
  956. // Ordenacion por seleccion
  957. Nodo ntemp;
  958. int itemp;
  959. String nodoi, nodoj, minn;
  960. double valori, valorj;
  961. int minj;
  962. double minx;
  963. int N = vector.size();
  964. int i, j;
  965. for (i = 0; i < N - 1; i++) {
  966. nodoi = (String) vector.get(i);
  967. itemp = IndiceNodos.indexOf(nodoi);
  968. ntemp = ListaNodos.get(itemp);
  969. valori = ntemp.getValor();
  970.  
  971. minj = i;
  972. minx = valori;
  973. minn = nodoi;
  974. for (j = i; j < N; j++) {
  975. nodoj = vector.get(j);
  976. itemp = IndiceNodos.indexOf(nodoj);
  977. ntemp = ListaNodos.get(itemp);
  978. valorj = ntemp.getValor();
  979. if (valorj <= minx) {
  980. minj = j;
  981. minx = valorj;
  982. minn = nodoj;
  983. }
  984. }
  985. vector.set(minj, nodoi);
  986. vector.set(i, minn);
  987. }
  988. }
  989. }
  990.  
  991. // Clase para el algoritmo: A* (A estrella)
  992. public class AE {
  993. // variables del algoritmo
  994. int j, n, m, s, k;
  995. int Step;
  996. String miObjetivo;
  997. Nodo nodo, suc, prop;
  998. Vector<String> abiertos;
  999. Vector<String> cerrados;
  1000. Graphics g;
  1001.  
  1002. // inicializa el algoritmo
  1003. public AE() {
  1004. // inicializa el algoritmo en caso de que haya uno cargado
  1005. if (ListaNodos.size() > 0)
  1006. inicio();
  1007. }
  1008.  
  1009. // metodos para gestionar variables
  1010. public String getAbierta() {
  1011. int temp;
  1012. String cadena;
  1013. int itemp;
  1014. Nodo ntemp;
  1015. if (Step == 0) {
  1016. cadena = "OPENED={";
  1017. for (temp = 0; temp < abiertos.size(); temp++) {
  1018. cadena += abiertos.get(temp) + "(";
  1019. itemp = IndiceNodos.indexOf(abiertos.get(temp));
  1020. ntemp = ListaNodos.get(itemp);
  1021. cadena += Double.toString(ntemp.getValor()
  1022. + ntemp.getCosteCamino());
  1023. cadena += ")";
  1024. if (temp < abiertos.size() - 1)
  1025. cadena += ", ";
  1026. }
  1027. cadena += "}";
  1028. } else {
  1029. cadena = "";
  1030. }
  1031. return cadena;
  1032. }
  1033.  
  1034. public String getCerrada() {
  1035. int temp;
  1036. String cadena;
  1037. if (Step == 0) {
  1038. cadena = "CLOSED={";
  1039. for (temp = 0; temp < cerrados.size(); temp++) {
  1040. cadena += cerrados.get(temp);
  1041. if (temp < cerrados.size() - 1)
  1042. cadena += ", ";
  1043. }
  1044. cadena += "}";
  1045. } else {
  1046. cadena = "";
  1047. }
  1048. return cadena;
  1049. }
  1050.  
  1051. // reinicia el algoritmo
  1052. public void reset() {
  1053. // inicia el algoritmo;
  1054. if (ListaNodos.size() > 0)
  1055. inicio();
  1056. }
  1057.  
  1058. // ejecuta el algoritmo en modo temporizador
  1059. public void run() {
  1060. while (Step < 2) {
  1061. switch (Step) {
  1062. case 0:
  1063. paso0();
  1064. break;
  1065. case 1:
  1066. paso1();
  1067. break;
  1068. default:
  1069. Grafo.this.NodoObjetivo = miObjetivo;
  1070. Grafo.this.paintGrafo();
  1071. }
  1072. // retardo de un segundo
  1073. try {
  1074. Thread.sleep(Temporizador);
  1075. } catch (Exception e) {
  1076. }
  1077. }
  1078. Grafo.this.NodoObjetivo = miObjetivo;
  1079. Grafo.this.paintGrafo();
  1080. }
  1081.  
  1082. // ejecuta el algoritmo en modo paso por paso
  1083. public boolean step() {
  1084. boolean ejecutandose = true;
  1085. switch (Step) {
  1086. case 0:
  1087. paso0();
  1088. break;
  1089. case 1:
  1090. paso1();
  1091. break;
  1092. default: {
  1093. ejecutandose = false;
  1094. Grafo.this.NodoObjetivo = miObjetivo;
  1095. Grafo.this.paintGrafo();
  1096. }
  1097. }
  1098. return ejecutandose;
  1099. }
  1100.  
  1101. // metodos para desglosar el algoritmo en pasos
  1102. private void inicio() {
  1103. // inicializa el objetivo
  1104. miObjetivo = "";
  1105. // inicializa variables para explorar sucesores
  1106. j = 0;
  1107. m = 0;
  1108. nodo = null;
  1109. suc = null;
  1110. prop = null;
  1111. // inicializa objetos
  1112. abiertos = new Vector<String>();
  1113. cerrados = new Vector<String>();
  1114. g = Grafo.this.getGraphics();
  1115. // comienza por el primer nodo
  1116. nodo = ListaNodos.get(0);
  1117. // encola el primer nodo
  1118. abiertos.add(nodo.toString());
  1119. // siguiente paso
  1120. Step = 0;
  1121. }
  1122.  
  1123. private void paso0() {
  1124. if (abiertos.size() != 0) {
  1125. // extrae el primer nodo de la pila abiertos
  1126. n = IndiceNodos.indexOf((String) abiertos.remove(0));
  1127. nodo = ListaNodos.get(n);
  1128. nodo.setEstado(Nodo.TEstado.ACTUAL);
  1129. nodo.pintarNodo(g);
  1130. if (!nodo.getEsObjetivo()) {
  1131. // se inserta en la lista de cerrados
  1132. cerrados.add(nodo.toString());
  1133. // se prepara para explorar los sucesores
  1134. m = nodo.maxSucesores();
  1135. j = 0;
  1136. // siguiente paso
  1137. Step = 1;
  1138. } else {
  1139. // establece el objetivo encontrado
  1140. miObjetivo = nodo.toString();
  1141. // termina con exito
  1142. Step = 2;
  1143. }
  1144. } else {
  1145. // termina con fracaso
  1146. Step = 2;
  1147. }
  1148. }
  1149.  
  1150. private void paso1() {
  1151. if (j < m) {
  1152. // obtiene el nodo sucesor
  1153. s = IndiceNodos.indexOf(nodo.getIdSucesor(j));
  1154. suc = ListaNodos.get(s);
  1155. if (suc.getEstado() == Nodo.TEstado.NOGENERADO) {
  1156. // establece puntero a nodo si el sucesor no se ha generado
  1157. suc.setIdPuntero(nodo.toString());
  1158. suc.setCostePuntero(nodo.getCosteSucesor(j));
  1159. suc.setCosteCamino(nodo.getCosteSucesor(j)
  1160. + nodo.getCosteCamino());
  1161. // inserta el elemento en la lista ABIERTOS
  1162. suc.setEstado(Nodo.TEstado.ABIERTO);
  1163. suc.pintarNodo(g);
  1164. // inserta el sucesor en la lista de abiertos
  1165. abiertos.add(suc.toString());
  1166. } else if ((suc.getEstado() == Nodo.TEstado.ABIERTO)) {
  1167. // modifica el puntero del sucesor a nodo
  1168. if (suc.getCosteCamino() > (nodo.getCosteSucesor(j) + nodo
  1169. .getCosteCamino())) {
  1170. suc.setIdPuntero(nodo.toString());
  1171. suc.setCostePuntero(nodo.getCosteSucesor(j));
  1172. suc.setCosteCamino(nodo.getCosteSucesor(j)
  1173. + nodo.getCosteCamino());
  1174. suc.pintarNodo(g);
  1175. }
  1176. } else if ((suc.getEstado() == Nodo.TEstado.CERRADO)) {
  1177. // modifica el puntero del sucesor a nodo
  1178. if (suc.getCosteCamino() > (nodo.getCosteSucesor(j) + nodo
  1179. .getCosteCamino())) {
  1180. suc.setIdPuntero(nodo.toString());
  1181. suc.setCostePuntero(nodo.getCosteSucesor(j));
  1182. suc.setCosteCamino(nodo.getCosteSucesor(j)
  1183. + nodo.getCosteCamino());
  1184. suc.pintarNodo(g);
  1185. // propagar nuevo camino a sucesores de sucesor
  1186. for (k = 0; k < suc.maxSucesores(); k++) {
  1187. prop = ListaNodos.get(IndiceNodos.indexOf(suc
  1188. .getIdSucesor(k)));
  1189. prop.setIdPuntero(suc.toString());
  1190. prop.setCostePuntero(suc.getCosteSucesor(k));
  1191. prop.setCosteCamino(suc.getCosteSucesor(k)
  1192. + suc.getCosteCamino());
  1193. }
  1194. }
  1195. }
  1196. j++;
  1197. } else {
  1198. if (abiertos.size() != 0) {
  1199. // pinta el nodo
  1200. nodo.setEstado(Nodo.TEstado.CERRADO);
  1201. nodo.pintarNodo(g);
  1202. // reordena la lista de abiertos en funcion de: f = h + g
  1203. reordenar(abiertos);
  1204. // siguiente paso
  1205. Step = 0;
  1206. } else {
  1207. // termina con fracaso
  1208. Step = 2;
  1209. }
  1210. }
  1211. }
  1212.  
  1213. private void reordenar(Vector<String> vector) {
  1214. // Ordenacion por seleccion
  1215. Nodo ntemp;
  1216. int itemp;
  1217. String nodoi, nodoj, minn;
  1218. double valori, valorj;
  1219. int minj;
  1220. double minx;
  1221. int N = vector.size();
  1222. int i, j;
  1223. for (i = 0; i < N - 1; i++) {
  1224. nodoi = vector.get(i);
  1225. itemp = IndiceNodos.indexOf(nodoi);
  1226. ntemp = ListaNodos.get(itemp);
  1227. valori = ntemp.getValor() + ntemp.getCosteCamino();
  1228.  
  1229. minj = i;
  1230. minx = valori;
  1231. minn = nodoi;
  1232. for (j = i; j < N; j++) {
  1233. nodoj = vector.get(j);
  1234. itemp = IndiceNodos.indexOf(nodoj);
  1235. ntemp = ListaNodos.get(itemp);
  1236. valorj = ntemp.getValor() + ntemp.getCosteCamino();
  1237. if (valorj <= minx) {
  1238. minj = j;
  1239. minx = valorj;
  1240. minn = nodoj;
  1241. }
  1242. }
  1243. vector.set(minj, nodoi);
  1244. vector.set(i, minn);
  1245. }
  1246. }
  1247. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
Public Pastes
Advertisement
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!