Trucos sobre manejo de softwarelibre y gnu linux. También a los programas que hago en gambas3, python, java, etc.... Consejos y trucos sobre otros programas: excel, word, internet, instalación de programas, Arduino y demás....
Dedicado a mis proyectos en Gambas ,un lenguaje de programación parecido al Visual Basic + Java pero ampliamente mejorado y...¡¡para gnu/linux!!.La potencia del gnu/linux sumada a la facilidad del Basic
Consultas, Desarrollo de programas y petición de presupuestos:
Resolución del problema de la mochila en varias estrategias, algoritmos voraces
En algoritmia, el problema de la mochila, comúnmente abreviado por KP (del inglés Knapsack problem) es un problema de optimización combinatoria, es decir, que busca la mejor solución entre un conjunto de posibles soluciones a un problema. Modela una situación análoga al llenar una mochila, incapaz de soportar más de un peso determinado, con todo o parte de un conjunto de objetos, cada uno con un peso y valor específicos. Los objetos colocados en la mochila deben maximizar el valor total sin exceder el peso máximo
Estrategias para resolverlo, llenar la mochila:
1) Con los elementos más costosos
2) Con los elementos menos pesados
3) Con los elementos que tenga mayor beneficio por unidad de peso ( coeficiente entre valor y peso)
4) Algoritmo Backtracking (o vuelta atrás):
Es un recorrido en profundidad dentro de un grafo dirigido. El grafo en cuestión suele ser un árbol. El objetivo del recorrido es encontrar soluciones para algún problema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estas soluciones parciales limitan las regiones en las que se puede encontrar una solución completa. El recorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En este caso el algoritmo puede, o bien detenerse (si lo único que se necesita es una solución del problema) o bien seguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido no tiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. En tal caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminando sobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tiene uno o más vecinos sin explorar, prosigue el recorrido de una solución.
A continuación, este problema resueldo aplicando las distintas estrategias, usando Gambas3
Estructura del Proyecto:
Os dejo aqui una solución del clásico problema de poner 8 reinas (mejor dicho, damas) de ajedrez en un tablero sin que se ataquen entre ellas.
Basicamente el programa lo que hace es:
1-Coloca una reina en el tablero
2-Comprueba que no esta en una casilla atacada por otra reina
3- Si esta atacada la quita, y va al paso 1.
4- Si no lo esta, marca en el tablero las casillas que ataca esta reina
5- Si lleva 8 reinas termina el programa sino, va al paso 1.
He encontrado un proyecto sobre como programar la Inteligencia Artificial de juegos tipo tycoon además de explicar como realizar las gráficas en perspectiva isométrica usando SDL
Por lo que he leído fue un proyecto entre varios compañeros de clase, aunque la fuente donde he obtenido los pdf es el blog de Sergio Hidalgo, se trata de un juego parecido a Tycoon Hospital, pero referido a la universidad.
He encontrado muy poca información sobre como se programan este tipo de juegos, y esta muy interesante la documentación.
Ademas os dejo los enlaces de una copia espejo que he hecho: Inteligencia Artificial en juegos:
1) Diseño de IA en juego tipo Tycoon: se definen las clases y como interactúan entre ellas.
Nota:
Tycoon: Son tipos de videojuegos
en el que se debe dirigir algún tipo de empresa u organización, y el
objetivo es convertirte en el magnate del negocio. Como en todo
videojuego la dificultad es variable, en este tipo de videojuegos la
dificultad depende de la cantidad de variables de gestión involucradas
Mi primer juego de Inteligencia Artificial en Gambas3
Damas Inglesas o Checkers
Aplicando el algoritmo MiniMax
Os traigo aqui mi último programa, se trata de un juego de damas inglesas, cuidado porque hay muchos juegos derivados de las damas, y las reglas son muy distintas.
El programa que he realizado se basa en un programa escrito en SmallBasic por Ken Goldberg ( codigo fuente original ). Aunque en principio me parecio fácil, he tardado varias semanas ya hay diferencias entre como se tratan las listas en SmallBasic y en Gambas3, teniendo que usara clases, para poder "traducir a Gambas" el programa.
En el programa original (y en la versión de gambas) se podia jugar entre jugadores humanos o diversos niveles de I.A.
Le he añadido varias mejoras:
- Se pueden editar las piezas del tablero, para crear diversas situaciones a analizar
- Guardar la partida y recuperarla.
- Ver como se ha desarrollado la partida con los tipicos botones de adelante y atras.
- Configuraciones: colores del tablero y distintos tipos de piezas.
Para que veas la diferencia de como queda, os dejo un pantallazo de como es la version en SmallBasic y en Gambas3
He desarrollado un pequeño programa donde se pueden definir la posición de las piezas y resolver tableros de 8 piezas (3x3) y tableros de 15 piezas (4x4) y se puede resolver automáticamente (si tiene solución ) usando el algoritmo A estrella (A *).
Se basan en este algoritmo, aunque los tableros de 15 piezas (y en general los de orden superior a 4x4), se resuelven con un paso "intermedio"... os explico...
Tenemos que llegar a la posición de la figura 1, para resolver el puzzle.
El primer paso es conseguir que la columna 1 y fila 1 queden ordenadas:
Figura 2
Una vez conseguido esto, resolvermos el puzzle 8 (3x3) que nos queda.
En mi programa uso el algoritmo A* para resolver el puzzle. Haciendo los siguientes pasos.
El usuario define el tablero, y pulsa el botón de "Resolver"
Con el tablero ya definido, se lleva a la posicion de las fichas que indica en la figura 2. Para ello definimos el tableroFin como el de la figura 2 (teniendo en cuenta solo la fila 1 y columna 1, el resto me da igual lo que valgan)
Luego resuelvo el puzzle de 3x3, que ha quedado, llevandolo al estado final de la figura 3
Figura 3
Al terminar estos dos procesos, conseguimos ordenar el puzzle 15 (4x4).
En mi caso los cuadros se numeran del 1 al 16, siendo el 16 el cuadro "vacio".
He "aprovechado" , las mismas funciones de calculo algoritmo Start, F, H, para los dos tipos de tablero, añadiendo un parametro opcional que indicaba como era el tablero (de 8 o 15) y asi conocer cual es el estado fin al que hay que llegar.ç
De ese modo el programa puede resolver los dos tipos de de puzzles.
Aqui os dejo los archivos del código fuente y el ejecutable en gambas3.2:
Notas:
Mejoras Rendimiento:
Si se ejecuta como root y con el comando nice se le dice que le de la maxima prioridad se mejora el rendimiento de la aplicacion: $nice -n -19 ./Puzzle15slide.gambas
21/9/12: Actualizado. Corregido bug a la hora de introducir datos en el tablero, y añadido un reloj para indicar el tiempo que se ha tardado en encontrar la solución.
Esta es una de las cuestiones que siempre me plantee cuando tuve mi primer ordenador y empece a programar en Basic....
Pues bien, gracias a internet, he encontrado mucha información... el algoritmo que se usa es el minimax (o variantes sobre este)...
En la wikipedia, en ingles, encontre el algoritmo, ademas de varios enlaces interesantes... entre ellos uno que desarrolla gráficamente cualquier "arbol" que le demos...
Me hecho un pequeño esquema, con los pasos y los cambio de valores: Enlace
PseudoCódigo:
function alphabeta(node, depth, α, β, Player)
if depth = 0 or node is a terminal node
return the heuristic value of node
if Player = MaxPlayer
for each child of node
α := max(α, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break(* Beta cut-off *)return α
elsefor each child of node
β := min(β, alphabeta(child, depth-1, α, β, not(Player) ))
if β ≤ α
break(* Alpha cut-off *)return β
El algoritmo A estrella (A*), se usa para hallar el camino más corto (de menor coste) entre dos puntos de un mapa dado, teniendo encuentra los obstáculos. (ver wiki ). Se usa mucho por ejemplo en los juegos gráficos.
He encontrado un blog ( ver fuente) , donde su autor lo codifica en javascript.
Lo he podido traducir a Gambas3, haciendo un pequeño ejemplo, donde se crea el mapa de forma aleatoria y la posición inicial (un león) y la posición final (una gacela), imprimiéndose el camino que une a los dos, e informando de cuando pasos se dán.
Versión: 2.2
He mejorado algunas cosas:
-> Ahora incluyo en el mapa celdas que dejan pasar pero con dificultades (hierva y agua). El arbol no deja pasar al leon, como en la primera versión.
-> Puedes ver distintas funciones heuristicas (Por defecto, Manhathan, Euclidea o sin uso de función), y se puede ver el coste de cada opción (valoración del camino) y un parámetro que mide el número de operaciones que se realizan (exactamente no es eso), pero sirve para darse cuenta cuanto "trabaja" el ordenador para encontrar la solución.
-> La ruta es marcada con flechas, indicando la dirección que toma el león hasta llegar la Gacela.
Os dejo 2 enlaces donde os podeis descargar unos documentos .pdf, donde podeis ver algunos algoritmos para juegos- Inteligencia Artificial (minimax, por ejemplo), y dibujo 2d (relleno de areas)
Hola, os traigo mi primer programa realizado en Lazarus, que es un IDE para FreePascal. Tiene algunas ventajas frente a Gambas, ya que es multiplataforma, osea que puedes crear el programa y compilarlo para varios sistemas operativos (no solo para gnu/linux). Os he dejado al final los enlaces tanto del código fuente como los ejecutables para gnu/linux y windows.
El programa, es una utilidad para el cálculo del area de un poligono irregular (una de las entradas que ha tenido mas visitas en mi blog).
El programa en el ide (ubuntu 10.04)
Os dejo aqui parte del código (el completo esta en el enlace del final del articulo).
