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.

Algunas aclaraciones
 

Buenas, he notado que el largo y aburrido (por no agregar, complicado) hilo que abrí ha sido leído ya por más de dos decenas... gracias por dedicar unos momentos de su tiempo para leerlo.

A lo mejor no me he sido muy detallista, he vuelto a correr paso a paso el algoritmo y me detuve en aquella línea en que devo obtener el estado del nodo elegido para almacenarlo en la solución. El estado que debería obtenerse, si se sigue el ejemplo que había remarcado anteriormente, es 247888748 mientras que se devuelve otro número muchísimo más extenso. Este estado corresponde a la matriz 2 - 8 - 3/1 - 0 - 4/7 - 6 -, 5 es decir que el algoritmo ha elegido por mover hacia arriba la ficha vacia. La posición de memoria del nodo devuelto por el algoritmo de BuscarF() corresponde al nodo correcto del árbol.... y me llama la atención de que no pueda obtenerse el valor indicado.

Si se presiona una vez más F7, se obtiene el siguiente error:
Nunca he tenido problemas con punteros en Delphi, yo ya manejaba rutinas con punteros y nunca se me ha presentado este error. Si alguien puede hacerme vez la luz le estaré muy agradecido.
Nuervamente gracias,

Por favor, ayuda!
 

Por favor, si alguien entiende lo que puede ser lo que está fallando... aviseme. Debo presentar esto para el día 20, y ya me agota las neuronas... aparentemente está bien... pero ese error me saca de mis casillas:confused: .

Mil disculpas por ser insistente, pero la verdad es que ando muy perdido en el problema...:confused:

Muchas gracias a todas aquellas personas que se han tomado un pequeño tiempo para leer todo esto.

Ya esta solucionado
 

Pues, ya logre ver la luz.... era una simple y estupida... cosa mía.
Resulta que mis algoritmos se producían demasiado rápido y en ocasiones... cuando intentaba acceder a a un valor... este no estaba disponible.
Con un simple Application.ProccessMessages se arregló.
Ya puedo dormir tranquilo....

Lamento a los cincuentas y tantos que hayan leído esto y/o a cualquier personas que haya vuelto loco con mis p......
Saludos

Me alegro que esté solucionado el problemilla :)

Pues claro... que me alegró...
 

Pues yo estoy muy chocho... ¡al ver aparecer los resultados en pantalla se me empezaron a salir lágrimas de la emoción!:D
Llo importante es que resuelva el problema.... el "problemita" menor, que lo había dejado pendiente es que me encontraba con algunas complicaciones para liberar la enorme cantidad de memoria que estos punteros me ocupaban. Me estaba preguntando si existiese alguna función que libere toda la memoria que haya empleado y no estar haciendo Dispose() por todos lados...
Es muy bien sabido que a cada programa se le asigna un espacio en memoria. Pero mi gran duda es que si en dicho espacio se crearan esos nodos.... y si es así ¿bastaría con emplear caFree para que libere todo?

En teoría, sí, al cerrar el form donde haces todo el trabajo, se liberaría la memoria usada.

Yo siempre mando a liberar la memoria. En la ayuda de New, dice que debemos usar Dispose :confused:

No creo que delphi se meta en liberar esa memoria que nosotros hemos creado, precisamente por lo que comenta en la ayuda de Dispose:
Desde luego es un tema interesante, puede que desde la version X de delphi si se tenga en cuenta esas cosas. Yo al menos seguiré liberando mis objetos "por si acaso" ;)

Saludos

No había leído esa parte de tu pregunta, pero, sí, ciertamente cuando "reservas" memoria explícitamente, también debes "liberarla" después. No lo hace delphi.