Algoritmo De Escalada

Algoritmo de Escalada por Máxima Pendiente
Cristian Andrés Tapia Jaya #1, David Ismael San Andrés Becerra *2
# Ingeniería de Sistemas, Universidad Politécnica Salesiana
Cuenca-Ecuador
1 ctapiaj@est.ups.edu.ec
3 dsan@est.ups.edu.ec

Abstract—This document will discuss the search algorithm for maximum slope climbing, its performance, upgrades and implementation in a game developed in JAVA(programming language) to learn the advantages of the improved algorithm.

Resumen— En el presente documento se tratara sobre el algoritmo de búsqueda de escalada por máxima pendiente, sobre su funcionamiento, sus mejoras y la implementación en un juego desarrollado en el Lenguaje de programación Java para conocer las ventajas sobre la mejora del algoritmo.

I. Introducción
Este documento se presenta unaaplicación sobre el método de búsqueda de escalada por máxima pendiente, el método de búsqueda de escalada por máxima pendiente es un algoritmo que cuenta con cierta información para poder llegar al objetivo requerido, la forma de trabajar de este algoritmo consiste en la implementación de una heurística, al ser un algoritmo informado este desplegara todos los posibles soluciones y según laheurística que este aplique tomara aquel camino que lo acerque más a la solución buscada remplazando el estado actual por uno mejor, a diferencia del algoritmo de escalada simple que toma la primera mejor solución tomado el valor de esta como el estado actual mejor.

El método Hill climb utiliza una valoración donde únicamente serán consideradas como aceptables aquellas soluciones que mejoren el costoactual, la búsqueda de este método termina cuando se ha alcanzado un optimo local [2].

Este tipo de algoritmo no garantiza que se encuentre o alcance la solución buscada por lo cual se aplica una mejora al algoritmo para evitar los máximos o mínimos, regresando a una posición anterior.
Este tipo de búsquedas son usadas para la resolución de en sistemas como SAIPE (Sistema de acceso a lainformación personal desde entornos con conectividad limitada) y FRA (Flora Retrieval Agent)

II. Estudio del Arte
En este apartado se tratara los diferentes algoritmos de búsqueda por escalada y las mejoras que se pueden aplicar a cada uno.
A. Algoritmo de Escalada Simple
El algoritmo de escalada simple se basa en el mejoramiento iterativo, partiendo del estado inicial y se selecciona aquel estado que seamejor al actual para lo cual se usa una función heurística. El mejor estado remplaza al actual en caso de que no se encuentre un estado mejor al actual el algoritmo buscara en el siguiente nodo o vecino y verificara si este tiene un estado mejor [1].
B. Algoritmo de Escalada por máxima pendiente
La manera en la que trabaja este algoritmo es desplegar todos los nodos o sub estados y remplazar elestado actual por aquel estado que sea mejor al actual. Con esta estrategia se determina que la mejor solución se encontrara atreves del nodo que mayor diferencia tenga en comparación con el estado actual [1].
C. Mejoras a los Algoritmos de Escalada
Se pueden emplear diferentes mejora a estos algoritmos de escalada las mismas que nos ayudan a evitar que la solución del problema no sea alcanzada,los problemas que se presenta en estos algoritmos es cuando se encuentra con un Máximo o Mínimo local, los valores de los nodos vecinos son iguales al estado actual, los valores de los nodos vecinos aumentan entre otros.
III. Desarrollo de la Aplicación
Para la implementación del algoritmo de escalada por máxima pendiente se plantea el siguiente problema donde se tiene una matriz de 8x8 en lacual existen obstáculos y dos puntos de partida, el primero será controlado por una persona y el segundo por la maquina en base al algoritmo de escalada por máxima pendiente, donde se desea llegar a un tercer punto, el programa se desarrollado en el lenguaje de programación Java.
Las restricciones para este problema son que los puntos de partida solo pueden moverse de forma vertical y horizontal...