Club Delphi  
    FTP   CCD     Buscar   Trucos   Trabajo   Foros

Retroceder   Foros Club Delphi > Principal > Varios
Registrarse FAQ Miembros Calendario Guía de estilo Temas de Hoy

Grupo de Teaming del ClubDelphi

 
 
Herramientas Buscar en Tema Desplegado
  #1  
Antiguo 14-04-2006
Avatar de Delphius
[Delphius] Delphius is offline
Miembro Premium
 
Registrado: jul 2004
Ubicación: Salta, Argentina
Posts: 5.582
Poder: 25
Delphius Va camino a la fama
Exclamation sobre punteros... y memoria ¿Como perder su valor, sin hacerlo?

Buenas, a todos los foristas...
Pues, la verdad que esto me está comiendo el cerebro... no entiendo que puede estar pasando en mi sistema.

Antes que nada... no se cuantos de aquí sabrán algo de inteligencia artificial. Pues, es casi indispensable conocer un poco de esto...
Les explico: en sistema expertos se nos ha pedido que desarrollemos algoritmos de búsqueda (en arboles) para encontrar la solución para un problema cualquiera; con una estrategia y una heuristica deseada. Por tanto, el algoritmo de búsqueda debe ser capaz de resolver cualquier problema que posea una heuristica y estrategia definida.
Hasta allí bárbaro.

Nos pidieron que resolvieramos el 8-Puzzle, con dos algoritmo de búsqueda a elección. Por ahora elegí el A*, que es uno de los que encontrará la solución en forma más rápida y económica (si es que existe). Pero tengo problemas en su implementación. ¡Lo malo es que debo presentar esto el día 20!
Para refrescar mejor, explico como se debe proceder:
Hay dos estructuras bases: un árbol (donde los hijos deben apuntar al padre) y una Frontera.

Explicación del Árbol:
El nodo del arbol debe contener:
* Estado: una representación numérica de la condición actual del problema.
* H: valor heurístico, que se obtiene de una función heuristica, que tiene como finalidad "ayudar" en la elección del posible mejor nodo a expandir.
* G: valor de la profundidad, es decir la cantidad de niveles que se van expandiendo.
* F: que es la suma de H y G.

Explicación de la Frontera:
La frontera es una lista con TODOS los punteros a los nodos de los árboles que NO han sido expandidos. Por tanto, cada vez que se expanda un nodo (cuando se le crean los hijos) debe desaparecer de la frontera, y sus hijos deber almacenarse en ésta. Además, cada nodo de Frontera, tiene que poseer un campo F, que recibirá el mismo valor del nodo representativo del árbol. Este F permitirá determinar cual será el siguiente nodo a expandir. Inicialmente Frontera deberá contar con el nodo raíz (con el estado inicial del problema).

Explicación de A*:
1. Lo primero que hace es fijarse si está vacia la frontera, si lo está da un fallo y finalizar.
2. Luego debe tomar el primer nodo del arbol y verificarse si dicho nodo es meta (si su estado es igual al estado correspondiente a la solución). Si lo es, finalizar e indicar la solución. En otro caso, lo expande (debe seguir buscando, mediante una estrategia definida). Esto implica hacer lo que he explicado en frontera.
3. Elegir el siguiente nodo: buscar en frontera aquel nodo que posea el menor valor de F, en caso de empate... elige cualquiera (en este caso se nos ha pedido que sea el de más a la izquierda).
4. Repetir el paso 2 con el nodo seleccionado.
La estrategia no es más que una simple ordenación de los nodos. Para este ejemplo: se nos indicó que se pongan en el siguiente orden: Izquierda, Arriba, Derecha, Abajo. Que quiere decir esto? Muy simple: que el primer hijo corresponderá al estado del movimiento de la celda vacia hacia la izquierda; el segundo el que corresponde hacia arriba, y así... sucesivamente, si se lo permite.

A* deberá devolver la solución, es decir los "pasos" requeridos. Para ello explora los nodos (desde el estado que cumplió con la condición 2), a traves del padre hasta llegar a la raiz. Obviamente, la solución real es la inversa.

Bueno, la cosa es que anda bien mis algoritmos... excepto cuando hago obtener el siguiente nodo a expandir. debugué (¿se dice así?) mi aplicación paso a paso y noto que me devuelve dcha dirección de memoria... pero el valor del estado no coincide con el que debería devolver, cuando intenta agregar dicho valor (estado) a una TStringList, me aparece un error indicando que no se tiene acceso a memoria. No me explico como es posible que me devuelva algo que inicialmente había almacenado bien, y dicho error... no se porqué salta, si la memoria analizada está disponible.
Probé esto con un ejemplo que hicimos en clase (¡y a mano!):
Estado Inicial: 2 - 8 - 3/1 - 6 - 4/7 - 0 - 5
Estado Final: 1 - 2 - 3/8 - 0 - 4/7 - 6 - 5

Según mis pasos, debería moverse primero a la Izquierda, luego a Arriba y por último Abajo. El próximo nodo a elegir es el que corresponde al de arriba: Y al parecer... devuelve el nodo que lo representa, pero su valor no es el esperado.

Agradecería cualquier ayuda que me puedan brindar, desde ya muchas gracias... mil disculpas por haber sido tan extenso, pero no encontraba mejor manera de explicar el tema. Adjunto código (pas, dfm, y dpr).
PD: tal vez se pregunten porqué no hago uso de los objetos que brinda Delphi, la explicación es que se nos quitarán puntos por cualquier estructura que nos "simplifique" la tarea; cuantas más usemos... menos puntos. Nos vemos obligados a confeccionar las estructuras ya comentabas, porque el objetivo de nuestra profesora es que aprendamos a usar y codificar dichos algoritmos.
¡Ha! Disculpen que haga una segunda pregunta aquí,... ¿Se liberará toda la memoria que emplee mi aplicación (la correspondiente a los nodos) al momento de cerrarla? ¿Bastará con el simple caFree o debo hacer Dispose() para todos los nodos que cree? Tengo entendido que cada programa tiene su porción de memoria... y que si pido con New() debo liberar con Dispose()... no encuentro referencia alguna en la ayuda de que estos nodos dinámicos se creen en dicha porción.
Archivos Adjuntos
Tipo de Archivo: zip 8 Puzzle.zip (10,6 KB, 40 visitas)
__________________
Delphius
[Guia de estilo][Buscar]
Responder Con Cita
 



Normas de Publicación
no Puedes crear nuevos temas
no Puedes responder a temas
no Puedes adjuntar archivos
no Puedes editar tus mensajes

El código vB está habilitado
Las caritas están habilitado
Código [IMG] está habilitado
Código HTML está deshabilitado
Saltar a Foro

Temas Similares
Tema Autor Foro Respuestas Último mensaje
como hacerlo?¿ tiagor64 Conexión con bases de datos 4 09-02-2005 15:55:04
Cómo hacerlo ... Jordy Conexión con bases de datos 2 19-08-2004 10:21:39
D7 a D5 como perder 1 hora. marcoszorrilla Varios 1 22-06-2004 13:59:47
Cómo hacerlo instalable ? K4RL0S Varios 1 03-01-2004 14:50:31
No se como hacerlo apolo18 Impresión 4 19-05-2003 23:13:27


La franja horaria es GMT +2. Ahora son las 19:25:40.


Powered by vBulletin® Version 3.6.8
Copyright ©2000 - 2024, Jelsoft Enterprises Ltd.
Traducción al castellano por el equipo de moderadores del Club Delphi
Copyright 1996-2007 Club Delphi