๋ฐ๊ฐ์ต๋๋ค. :)
Uninformed Search์
BFS์ DFS ํ์์
List๋ก
๋น๊ตํด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
BFS (๋๋น์ฐ์ ํ์)
: ๋ฐ์ผ๋ก ๋ด๋ ค๊ฐ๋ฉด์ ํ์
https://setori-dev.tistory.com/45
Listํํ
๋ค์์ BFS๊ธฐ๋ฒ์ผ๋ก ํ์ํ๋ ๊ณผ์ ์ List๋ก ํํํ์์ค.
๋งจ ์ฒ์ a๊ฐ Open List์ ๋ค์ด์ค๊ณ
Open | a | ||||||
Close |
Open List์ ๋ค์ด์จ
a๋ฅผ ํ์ํ๊ณ , ํ์ฅํ๊ณ ์ ํ ๋
a๊ฐ Close List๋ก ๋ค์ด์ต๋๋ค.
Open | a | ||||||
Close | a ํ์ฅ |
์ฆ,
a๊ฐ Close List์ ๋ค์ด์ค๋ฉด
a์ fringe๋ฅผ ํ์ฅํ ์ ์์ต๋๋ค.
ํ์ฅํ a์ fringe์ b์ c๋ก
Open List๋ก ๋ค์ด์ต๋๋ค.
Open | a | b | c | ||||
Close | a ํ์ฅ |
๊ทธ ๋ค์
BFS์ด๊ธฐ ๋๋ฌธ์ b๋ฅผ ๋จผ์
์์ a์ ๋์ผํ๊ฒ fringe๋ฅผ ํ์ฅํฉ๋๋ค.
b์ fringe์ d์ e๋ก
๋ค์ Open List๋ก ๋ค์ด์ต๋๋ค.
Open | a | b | c | d | e | ||
Close | a ํ์ฅ | b ํ์ฅ |
๋ค์ List์ ์์๋๋ก
c๋ฅผ ํ์ฅํฉ๋๋ค.
(c์ fringe๋ f์ g์ธ ๊ฒ ์ดํด ๋์์ฃ ?)
Open | a | b | c | d | e | f | g |
Close | a ํ์ฅ | b ํ์ฅ | c ํ์ฅ |
๊ทธ๋ผ ๋ชจ๋ fringe๊ฐ Open List์ ๋ค์ด์๊ณ ,
Open List ์์๋๋ก ํ์ฅ์ ํฉ๋๋ค.
d ํ์ฅ
Open | a | b | c | d | e | f | g |
Close | a ํ์ฅ | b ํ์ฅ | c ํ์ฅ | d ํ์ฅ |
e ํ์ฅ
Open | a | b | c | d | e | f | g |
Close | a ํ์ฅ | b ํ์ฅ | c ํ์ฅ | d ํ์ฅ | e ํ์ฅ |
f ํ์ฅ
Open | a | b | c | d | e | f | g |
Close | a ํ์ฅ | b ํ์ฅ | c ํ์ฅ | d ํ์ฅ | e ํ์ฅ | f ํ์ฅ |
g ํ์ฅ
Open | a | b | c | d | e | f | g |
Close | a ํ์ฅ | b ํ์ฅ | c ํ์ฅ | d ํ์ฅ | e ํ์ฅ | f ํ์ฅ | g ํ์ฅ |
์ด๋ ๊ฒ ํ์์ ์์๋ Close List์ ๋ค์ด์จ ์์๋๋ก ์งํ๋ฉ๋๋ค.
๋ฐ๋ผ์, ํ์ ์์๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์์ BFS์ ํ์๊ณผ
DFS์ ํ์์ ๋น๊ตํด๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
DFS (๊น์ด์ฐ์ ํ์)
: ์ผ์ชฝ๋ถํฐ ๊น๊ฒ ํ์
https://setori-dev.tistory.com/47
Listํํ
๋ค์์ DFS๊ธฐ๋ฒ์ผ๋ก ํ์ํ๋ ๊ณผ์ ์ List๋ก ํํํ์์ค.
๋์ผํ๊ฒ
๋งจ ์ฒ์ a๊ฐ Open List์ ๋ค์ด์ค๊ณ
Open | a | ||||||
Close |
Open List์ ๋ค์ด์จ
a๋ฅผ ํ์ํ๊ณ , ํ์ฅํ๊ณ ์ ํ ๋
a๊ฐ Close List๋ก ๋ค์ด์ต๋๋ค.
Open | a | ||||||
Close | a ํ์ฅ |
์ฆ,
a๊ฐ Close List์ ๋ค์ด์ค๋ฉด,
a์ fringe๋ฅผ ํ์ฅํ ์ ์์ต๋๋ค.
ํ์ฅํ a์ fringe์ b์ c๋ก
Open List๋ก ๋ค์ด์ต๋๋ค.
Open | a | b | c | ||||
Close | a ํ์ฅ |
๊ทธ ๋ค์
DFS์ด๊ธฐ ๋๋ฌธ์ b๋ฅผ ๋จผ์
์์ a์ ๋์ผํ๊ฒ b์ fringe๋ฅผ ํ์ฅํฉ๋๋ค.
b์ fringe์ d์ e๋ก
๋ค์ List๋ก ๋ค์ด์ต๋๋ค.
Open | a | b | d | e | c | ||
Close | a ํ์ฅ | b ํ์ฅ |
(์ฆ, c๋ฅผ ํ์ํ๊ธฐ ์ ์ d์ e๋ฅผ ํ์ํด์ผํ๋ฏ๋ก,
c์ ์์ผ๋ก ๋ฐฐ์น๊ฐ ๋ฉ๋๋ค.)
์ฌ๊ธฐ์ BFS์ ์ฐจ์ด์ ์ ์์๊ฒ ๋์?
๋ค์ List์ ์์๋๋ก
d๋ฅผ ํ์ฅํฉ๋๋ค.
Open | a | b | d | e | c | ||
Close | a ํ์ฅ | b ํ์ฅ | d ํ์ฅ |
๊ทธ๋ ๋ค๋ฉด!!
ํ์ฌ ์งํ์ฌํญ์ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ด์ ์์๋๋ก
e ํ์ฅ
Open | a | b | d | e | c | ||
Close | a ํ์ฅ | b ํ์ฅ | d ํ์ฅ | e ํ์ฅ |
c๋ฅผ ํ์ฅํ๋ฉด
f์ g๊ฐ Open List์ ๋ค์ด์ค๋ฉด์
๋ชจ๋ fringe๊ฐ List์ ๋ค์ด์ค๊ฒ ๋ฉ๋๋ค.
Open | a | b | d | e | c | f | g |
Close | a ํ์ฅ | b ํ์ฅ | d ํ์ฅ | e ํ์ฅ | c ํ์ฅ |
๋ง์ง๋ง์ผ๋ก
f ํ์ฅ
Open | a | b | d | e | c | f | g |
Close | a ํ์ฅ | b ํ์ฅ | d ํ์ฅ | e ํ์ฅ | c ํ์ฅ | f ํ์ฅ |
g ํ์ฅ
Open | a | b | d | e | c | f | g |
Close | a ํ์ฅ | b ํ์ฅ | d ํ์ฅ | e ํ์ฅ | c ํ์ฅ | f ํ์ฅ | g ํ์ฅ |
์ด๋ ๊ฒ ํ์์ ์์๋ Close List์ ๋ค์ด์จ ์์๋๋ก ์งํ๋ฉ๋๋ค.
๋ฐ๋ผ์, ํ์ ์์๋ ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
์ด๋ ๊ฒ BFS์ DFS์ ํ์์
๋น๊ตํ๋ฉด ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
BFS ํ์
DFS ํ์
List๋ก ๋ณด๊ฒ ๋๋ฉด,
BFS ํ์
-> ์ผ๋ ฌ๋ก ๋ค์ด์ค๋ ์์๋๋ก ์ฐจ๋ก๋๋ก ์งํ
Queue(ํ)ํ
Open | a | b | c | d | e | f | g |
Close | a ํ์ฅ | b ํ์ฅ | c ํ์ฅ | d ํ์ฅ | e ํ์ฅ | f ํ์ฅ | g ํ์ฅ |
DFS ํ์
-> ์๋ํํ๋ก ๊ฐ์ฅ ๋ง์ง๋ง์ ๋ค์ด์จ ๊ฒ๋ถํฐ ์งํ
Stack(์คํ)ํ
Open | a | b | d | e | c | f | g |
Close | a ํ์ฅ | b ํ์ฅ | d ํ์ฅ | e ํ์ฅ | c ํ์ฅ | f ํ์ฅ | g ํ์ฅ |
๋ ๊ธฐ๋ฒ์ ์ฐจ์ด์ ์ ์ดํด๊ฐ ๋์ จ๋์?
๋ง์ ๋์ ๋์ จ๋ค๋ฉดโค์ ๊ตฌ๋ ๋ถํ๋๋ฆด๊ฒ์!
:)
'IT > ์ธ๊ณต์ง๋ฅ(AI)' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์ธ๊ณต์ง๋ฅ] Uninformed Search - UCS List๋ก ๋ถ์ (0) | 2022.01.05 |
---|---|
[์ธ๊ณต์ง๋ฅ] Uninformed Search - UCS(๊ท ์ผ๋น์ฉํ์) (3) | 2022.01.04 |
[์ธ๊ณต์ง๋ฅ] Uninformed Search - DFS(๊น์ด์ฐ์ ํ์) (0) | 2021.12.30 |
[์ธ๊ณต์ง๋ฅ] Uninformed Search - BFS(๋๋น์ฐ์ ํ์) (0) | 2021.12.29 |
[์ธ๊ณต์ง๋ฅ] Uninformed Search (0) | 2021.12.28 |
๋๊ธ