BFS con agentes

BFS con agentes preview image

1 collaborator

Tags

bfs 

Tagged by Fernando Sancho Caparrini about 5 years ago

busqueda ciega 

Tagged by Fernando Sancho Caparrini about 5 years ago

busqueda en profundidad 

Tagged by Fernando Sancho Caparrini about 5 years ago

Part of project 'Prueba Caso'
Model group Forma1 | Visible to everyone | Changeable by the author
Model was written in NetLogo 5.0.2 • Viewed 305 times • Downloaded 56 times • Run 0 times
Download the 'BFS con agentes' modelDownload this modelEmbed this model

Do you have questions or comments about this model? Ask them here! (You'll first need to log in.)


Comments and Questions

Please start the discussion about this model! (You'll first need to log in.)

Click to Run Model

; Los estados serán agentes
breed [estados estado]
estados-own 
[
  contenido  ; Almecena el contenido del estado (el valor)
  explorado? ; Indica si ha sido explorado o no
  camino     ; Almacena el camino para llegar a él
]

; Las transiciones se representarán como links
directed-link-breed [transiciones transicion]
transiciones-own
[
  regla   ; Almacena la versión "representable" de la regla aplicada
]

;--------------- Funciones personalizables -------------------

; Las reglas se representan por medio de pares [ "representación" f ]
; de forma que f permite pasar entre estados (es la función de transición)
; y "representación" es una cadena de texto que permite identificar qué
; regla se ha aplicado

to-report transiciones-aplicables
  report (list 
           (list "*3" (task [? * 3])) 
           (list "+7" (task [? + 7])) 
           (list "-2" (task [? - 2])))
end 

; estado-final? ofrece un report de agente que identifica los estados finales

to-report igual? [ob]
  report ( contenido = ob)
end 

;-------------------- Algoritmo BFS y auxiliares ----------------
; Esencialmente, el algoritmo va calculando los estados hijos de cada estado 
; no explorado y los enlaza por medio de la transición que lo ha generado, hasta
; alcanzar el estado objetivo.

to BFS [estado-inicial estado-final]
  ca
  salida
  ; Creamos el agente asociado al estado inicial
  create-estados 1
  [
    set shape "circle"
    set color green
    set contenido estado-inicial
    set label contenido
    set camino (list self)
    set explorado? false
  ]
  ; Mientras halla estados no explorados (la verificación de haber encontrado
  ; el objetivo se hace dentro)
  while [any? estados with [not explorado?]]
  [
    ask estados with [not explorado?]
    [
      ; Calculamos los estados sucesores aplicando cada regla al estado actual
      foreach transiciones-aplicables
      [
        let estado-aplicado (run-result (last ?) contenido)
        ; Solo consideramos los estados nuevos
        if not any? estados with [contenido = estado-aplicado]
        [
          ; Creamos un nuevo agente para cada estado nuevo
          hatch-estados 1
          [
            set contenido estado-aplicado
            set label contenido
            set explorado? false
            ; y lo enlazamos con su padre por medio de un link etiquetado
            create-transicion-from myself [set regla ? set label first ?]
            set color blue
            ; Formamos el camino desde el inicio hasta él
            set camino lput self camino
          ]
        ]
        ; Podríamos calcular también los diversos caminos para llegar a todos los nodos,
        ; pero en BFS eso complica el grafo de búsqueda construido y la reconstrucción
        ; del camino cuando se halla el objetivo
        ;
        ; create-transicion-to one-of estados with [contenido = estado-aplicado]
        ; [
        ;  set regla ?
        ;  set label first ? 
        ; ]
        
        ; Actualizamos la representación 
        if layout? [layout]
      ]
      ; Cuando hemos calculado todos sus sucesores, marcamos el estado como explorado
      set explorado? true
    ]
    ; Comprobamos si hemos alcanzado el estado objetivo
    if any? estados with [igual? estado-final]
     [ 
       ; Y si es así, lo destacamos en rojo y destacamos el camino que ha llevado 
       ; hasta él (por medio de un reduce con una funciónn adecuada)
       ask one-of estados with [igual? estado-final] 
       [
         set color red
         let a reduce resalta camino
       ]
       output-print (word "Estados explorados: " count turtles)
       stop
     ]
  ]
end 

; La función resalta se usa dentro de un reduce, lo que hace es que dados 
; dos nodos, destaca el link que los une y devuelve el segundo

to-report resalta [x y]
  ask transicion [who] of x [who] of y [set color red set thickness .3]
  report y
end 

; El procedimiento limpia aprovecha que hemos construido un árbol (no vale para
; grafos) para eliminar de forma recursiva todos los nodos que no están en el 
; camino que une estado-inicial y estado-final

to limpia [o1 o2]
  while [any? estados with [grado = 1 and contenido != o2 and contenido != o1]]
  [
    ask estados with [grado = 1 and contenido != o2 and contenido != o1][die]
  ]
end 

; Devuelve el grado de un nodo

to-report grado
  report (count my-in-links + count my-out-links)
end 

; Representación del grafo de forma más adecuada

to layout
  layout-radial estados transiciones estado 0
  ;layout-spring estados transiciones .7 4 .8
end 

; Salida Output

to salida
  output-print (word "Ir desde " Estado_Inicial " hasta " Estado_final)
  output-print (word "usando las operaciones:")
  foreach transiciones-aplicables
  [
    output-print (first ?)
  ]
end 

There is only one version of this model, created about 5 years ago by Fernando Sancho Caparrini.

Attached files

File Type Description Last updated
BFS con agentes.png preview View about 5 years ago, by Fernando Sancho Caparrini Download

This model does not have any ancestors.

This model does not have any descendants.