Shortest Path Problem
Weight graph๋ Node ์ Edge ๊ทธ๋ฆฌ๊ณ weight๊ฐ ์๋ ๊ทธ๋ํ๋ฅผ ์๋ฏธํ๋ค.
(V, E, W) Node ๊ฐ์ ์ฐ๊ฒฐ์ฑ๊ณผ ํน์ง์ ๋ณด์ฌ์ฃผ๋ ๊ฒ์ด W์ด๋ค.
Path = sequence of edge
length of path ๋ number of edge ๊ฐ ๋๋ค.
Q) What is shortest path?
Boston ์์ LA๋ก ๊ฐ๋ ๊ฐ์ฅ ์งง์ ๊ธธ์ ์ด๋ค ์กฐํฉ์ด ๋ ๊น..?
Positive weight๋ฅผ ๊ฐ์ง๊ณ ์์์ ๊ฐ์ ํ๋ค.
a์์ z ๋ก ๊ฐ๋ Shortest Path๋ฅผ ์ฐพ๋๋ค.
: ํด๋น ๋ ธ๋์ ์ฃผ๋ณ๋ง์ ํ์ธํ๋ฉด์ ์์ ๋ ธ๋๋ก ๋ถํฐ ์ด๋ ๊ธธ์ด ๊ฐ์ฅ ์งง์ ๊ธธ์ด ๋๋์ง๋ฅผ ํ์ธํ๋ค.
๋ชจ๋ ๊ณผ์ ์ ํ ํ์์์ด ์ด์์ผ๋ก ๋ถํฐ Path์ ๊ธธ์ด๊ฐ ์ผ๋ง์๋์ง๋ง ๊ธฐ์ตํ๊ณ ์๋ค๋ฉด ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ฐพ์ ์ ์๋ค.
Start Vertex์ Ending Vertex๋ ์๋ ค์ฃผ๊ณ ์์ํด์ผ ํ๋ค.
Weigth ๋ ํญ์ Positive weight๊ฐ ์์์ ๊ฐ์ ํด์ผ ํ๋ค.
(์์๊ฐ ์๊ณ Cycle์ด ์กด์ฌํ๋ฉด ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ์ ์ํ ์ ์๋ค.)
L: V -> R (Vertex ์ ๋ํ ๋ด์ฉ์ ๊ฐ์ง๊ณ ์๋ ํจ์)
L(v)๊ฐ ํํํ๊ณ ์ ํ๋ ๊ฒ์ a์์ ์ถ๋ฐํด์ v๊น์ง ๊ฐ๋๋ฐ shortest Path๋ฅผ ์๋ฏธํ๋ค.
์ฒ์ L(v)๋ ์ผ๋ง๋ ๊ฑธ๋ฆฌ๋ ์ง ์์ง ๋ชปํ๋ค. ์ฐ๊ฒฐ์ด ์๋์์ ๊ฐ๋ฅ์ฑ๋ ์กด์ฌํ๋ค.
S ๋ ๊ณ์ฐ์ด ๋๋ ๊ฒ๋ค์ ๋ชจ์๊ฐ๋ Vertex
๋ฃจํ๊ฐ ์์ํ๊ณ
S์ z๊ฐ ์ํ์ง ์์ ๋๊น์ง ๋ฐ๋ณต์ ํ๊ณ S์ ์ํ์ง ์๋ V ๋ง๋ค L(u) + w(u,v) < L(v) ๋ผ๋ฉด
L(v) ์ L(u) + w(u,v) ๋ฅผ ํ ๋นํด์ ํด๋น V ๋ ธ๋๋ก ๊ฐ๋ ์ต๋จ ๊ฑฐ๋ฆฌ์ ๋ํ ์ ๋ณด๋ฅผ ์ต์ ํํด์ค๋ค.
S์ ์์ญ์ ํ ์นธ์ฉ ํค์ฐ๊ณ ์ถ์ ๊ฒ.
S๋ ์ด๋ฏธ ํต๊ณผํ Vertex๋ก ์ด๋ฃจ์ด์ ธ ์๊ณ S์ ์ํ์ง ์์ ๊ทธ ๋ค์ Vertex ์ค ์ต๋จ ๊ฑฐ๋ฆฌ๋ฅผ ๋ง์กฑํ๋
L(u) + w(u,v) < L(v) ๋ฅผ ๋ง์กฑํ๋ค๋ฉด ์ต๋จ ๊ฑฐ๋ฆฌ์ ๋ํ ๊ฐ์ ์๋ก ์ต์ ํ ํด์ค๋ค.
์ฌ๊ธฐ์ L(v) ๋ ์ง๊ธ๊น์ง ์๋ ค์ง ์์ ๋ ธ๋ a์์ ์ถ๋ฐํด์ v ๋ ธ๋๊น์ง ๋์ฐฉํ๊ธฐ ์ํด ๊ฑธ๋ฆฌ๋ path๊ฐ ๋๋ค.
S๋ฅผ ํตํด์ ์ฐพ์์ง ๊ฒฝ๋ก ์ค ์ต๋จ ๊ฑฐ๋ฆฌ๋ง์ ์ ํํ๋ค๋ ๊ฒ์ด Inductive Hypotheses
๊ฐ์ ์ ๋ฐ๋ฅด๋ฉด S์ ์ํ์ง ์์ V' ์ ํตํด์ U ๋ก ๊ฐ๋ ์ต๋จ ๊ฑฐ๋ฆฌ ๋ฐฉ๋ฒ์ด ์กด์ฌํด์ผ ํ๋ค.
ํ์ง๋ง V'์ ํญ์ S ์์ ์ํ ๊ฒ์ด ๋๋ ๋ชจ์์ด ๋ฐ์ํ๋ค.
์๋ํ๋ฉด ํ์ฌ ๊ฐ์ฅ ์งง์ ๊ธธ๋ก ๊ฐ๋ ๋ฐฉ๋ฒ์ด ์กด์ฌํ๋ ๊ฒฝ๋ก๋ ํญ์ S๋ฅผ ํตํ ์ ๋ฐ์ ์์์ด ์ ์ ๊ฐ ๋๊ธฐ ๋๋ฌธ์ด๋ค.
N x N ๋งํผ์ Time์ด ๊ฑธ๋ฆฐ๋ค. ํ๋์ Vertex ๋น ๋ชจ๋ Vertex๋ฅผ ํ์ํ๋ฏ๋ก
Find a circuit์ ํ๋ ๊ฒ์ ๋ค๋ฅธ ๋ฌธ์ ์ด๋ค. (TSP ๋ฌธ์ )
Hemilton Circuit์ ์๊ธฐํ ๋ ์ธ๊ธํ ์ ์์
ํด๋น ๋์๋ฅผ ํ ๋ฒ ์ฉ๋ง ๋ฐฉ๋ฌธํ๊ณ ์ถ์๋ฐ ๊ทธ ์ค ๊ฐ์ฅ ์งง์ ๊ธธ๋ก ๋ค๋ ์ ์๋ ๋ฐฉ๋ฒ์ ๋ํ ์๊ณ ๋ฆฌ์ฆ
๋ชจ๋ ๊ฒฝ๋ก๋ฅผ ํ์ํ๋ ๊ฒ๋ณด๋ค ๋ ์ข์ ์๊ณ ๋ฆฌ์ฆ์ด ์กด์ฌํ์ง ์๋๋ค.
๋ชจ๋ ๊ฒฝ๋ก๋ฅผ ๋ค ๋ณด์ง ์๊ณ ํ์ํ ์ ์๋ ๋ฐฉ๋ฒ์ ๋ํ ์๊ณ ๋ฆฌ์ฆ์ ์กด์ฌํ์ง ์๋๋ค.
Arbitrary graph ์ฆ, ์ผ๋ฐ์ ์ธ Solution์ ์์ง๋ง Efficient ํ Common Case ์ ๋ํ Solution์ ์กด์ฌํ๋ค.
Common ์ด๋ผ๋ ๊ฒ์ ์์ฃผ ๋์ค๊ณ , Popular ํ ๊ฒ๋ค, ์ผ์ ์กฐ๊ฑด์ ๋ํด ๋ง์กฑํ๋ Graph์ ๋ํด์
efficient ํ๊ฒ ๋์๊ฐ๋ ์๊ณ ๋ฆฌ์ฆ์ด ์กด์ฌํ๋ค.
Sequence๋ฅผ ์ฃผ๋ฉด ํด๋น Path์ Weight๋ฅผ ์ฐพ์ ์๋ ์๋ค.
Weight๋ฅผ ๊ตฌํ๋ ๊ฒ์ ํ๊ธฐ ์ฝ๋ค. ํ์ฌ ์์ ์์ Evaluation์ ํ ์ ์๋ค.
Random ํ Sequence๋ฅผ ์ฃผ๊ณ ์ด๋ค ๊ฐ์ด ๊ฐ์ฅ ์ข์์ง๋ฅผ ์ ์ ์๋ค.
Trial Error๋ฅผ ํ๋ฉด์ ๋ฐ์ํ Information์ ์ Search๋ฅผ ํ๋ค.
๊ทธ๋์ ํด๋น Sequence์ ๋น์ทํ Sequence๋ฅผ ๋ง๋ค์ด๋ณด์๋ผ๋ ๊ด์ ์ผ๋ก Problem Solving์ ์งํํ๋ค.
ํด๋น Sequence์ ๋ํ ๊ท์น์ ์ด์ง ์ด์ง์ ๋ฐ๊ฟ์ฃผ๋ฉด์ ์ฐพ์๋๊ฐ๋ค.
์ํ์ ์ฆ๋ช ์ ์ํ์ ์ฌ์ค์ Subset ๊ด๊ณ๋ฅผ ๊ฐ์ง๋ค.
์ฆ๋ช ์ ์๋์ง๋ง ์ฌ์ค์ด๋ค.
'๐ Major Study (Bachelor) > ๐ข Discrete Mathematics' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
HW4 (Drawing "Hasse Diagram") (0) | 2022.01.02 |
---|---|
HW3 (Implementation with Recursive) (0) | 2022.01.02 |
์ค์ผ๋ฌ ํ๋ก (Euler's Path), ์ค์ผ๋ฌ ์ํท(Euler's Circuit) (0) | 2021.12.07 |
Hall's Marriage Theorem, Isomorphism of Graph (0) | 2021.12.03 |
Discrete Mathematics (0) | 2021.11.02 |