Open List & Closed List (estrutura dadus iha A*)
Open List (lista aberta) mak lista ne’ebé armazena node sira ne’ebé deskobre maibé seidauk ekspande.
Node sira ne’e prontu atu avalia tuir prioridade f(n).
Closed List (lista taka) mak lista ne’ebé armazena node sira ne’ebé ona ekspande (la presiza visita fali).
Open List → prioridade (f(n) ki’ik) Closed List → evita siklu
Iha A*, open list (fila prioretária) uza hodi hili node ho f(n) mínimu. Closed list preveni algoritmu atu la re-ekspande node ne’ebé ona prosesa, hasa'e efisiénsia.
Open List fila prioretária
Kontén node sira ne’ebé hetan ona maibé seidauk espande. Ordena tuir f(n). Eksemplu: [B(12), C(14)]
Closed List taka
Node sira ne’ebé ona espande. La presiza vizita fali. Eksemplu: [A, B, D]
Exemplu Simulasaun: Open no Closed List iha A*
Konsidera grafu ho inísiu A no objetivu E. Kustu g(n) no heurístika h(n) f(n) = g+h.
A —7→ C —2→ E
B —4→ E
Simulasaun pasu husi A*:
Open = [B(11), C(11)] ; Closed = [A]
Open = [C(11), E(9), D(13)] ; Closed = [A, B].
E agora iha open ho f=9.
A* para tanba E mak objetivu. Open restante: [C(11), D(13)] ; Closed = [A, B, E].
Observasaun: Open List sempre kontén node sira ne’ebé seidauk espande, ordena tuir f(n). Closed List grava node ne’ebé ona espande atu evita prosesa fali. Se node E iha Closed, signifika nia ona espande (ka objetivu).
| Pasu | Open List (node:f(n)) | Closed List | Aksaun |
|---|---|---|---|
| 1 | A:10 | – | Espande A |
| 2 | B:11, C:11 | A | – |
| 3 | C:11, E:9, D:13 | A, B | Espande B, inklui E |
| 4 | E:9, C:11, D:13 | A, B | Hili E (objetivu) |
| 5 | – | A, B, E | Remata |
Open List muda bainhira node espande; Closed List aumenta ho node ne’ebé espande ona.
Função importante Open no Closed List
✔ Open List – prioridade ba node ne’ebé promete (f(n) ki’ik).
✔ Closed List – preveni loop no redundánsia. A* só re-espande node iha closed se hetan dalan ho g(n) ne’ebé di’ak liu (raro).
✔ Estrutura ida ne’e efisiente tebes ba informé busca informada.
Visualizasaun estrutura lista
Imajen: Open List (fila prioridade) iha node sira ne’ebé aguarda espansaun, ordena tuir f(n). Closed List nu’udar “memória” husi node ne’ebé ona prosesa. Iha diagrama, seta hatudu fluxu: node husi Open ba Closed depois espansaun, no node foun tama Open.
Exemplu visual open/closed
Open List no Closed List — papel iha A*
📂 Open List: node sira ne’ebé deskobre maibé seidauk espande (prioridade f(n)).
🔒 Closed List: node sira ne’ebé ona espande, preveni siklu no redundánsia.
⚙️ A* nia efisiéncia depende ba jestaun di’ak husi open no closed list.