Comments (3)
선생님 ! 블로그 글 너무 잘봤습니다. 그런데 제가 헷갈리는 부분이 있어서 여쭤보고 싶습니다. 다른 블로그에서는 <그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, >라고 되어있는데 선생님 블로그에서는 <해가 될 가능성이 있으면 유망하다>라고 되어있습니다. 유망하다(promising)라는 표현이 정확히 어떤 뜻인지 설명해주실 수 있을까요? 전체 알고리즘의 효율성측면에서 긍정적인 표현인건지, 부정적인 표현인건지 잘 모르겠습니다!
from chanhuiseok.github.io.
@haeni0117
안녕하세요 :)
보통 유망하다(promising)는 표현은 코드를 통해 이해하면 더 와닿을 수 있을 것 같습니다.
위의 N-queen 문제(https://chanhuiseok.github.io/posts/baek-1/) 를 예로 들어 보면,
유망함의 판단 조건이 '퀸이 놓였을 때 퀸 자신을 기준으로 일직선상(가로 및 세로)과 대각선 방향에는 아무것도 놓여있으면 안 된다' 입니다.
퀸을 놓을 때 위 조건에 어긋나면, 거기에는 퀸을 놓지 않고 다른 경로를 다시 탐색하는데요.
이 때 조건에 어긋났던 그 길은 해답이 될 수 없으므로 유망하지 않다고 말할 수 있습니다.
반대로 위 조건에 어긋나지 않다면 해가 될 가능성이 있으므로 유망하기(promising) 때문에 그 자리에 퀸을 놓을 수 있습니다.
조건에 어긋나서(유망하지 않아서) 그 경로로 갈 시도를 하지 않는 것을 가지치기라고 합니다.
이렇듯 모든 경로를 다 탐색하지 않기 때문에 효율성을 높일 수 있는 것입니다!
from chanhuiseok.github.io.
덕분에 좋은 내용 잘 보고 갑니다.
정말 감사합니다.
from chanhuiseok.github.io.
Related Issues (20)
- posts/algo-33/ HOT 2
- posts/improve-6/ HOT 4
- posts/electron-1/ HOT 1
- posts/baek-19/ HOT 1
- posts/ds-4/ HOT 1
- posts/react-4/ HOT 1
- posts/baek-26/ HOT 2
- posts/js-10/ HOT 1
- posts/git-4/ HOT 1
- posts/algo-14/ HOT 3
- posts/baek-33/ HOT 1
- posts/baek-16/ HOT 1
- posts/algo-42/ HOT 3
- posts/algo-26/ HOT 1
- posts/algo-54/ HOT 2
- posts/baek-34/ HOT 2
- posts/algo-34/ HOT 1
- posts/algo-32/ HOT 1
- posts/algo-50/ HOT 1
- posts/ds-3/ HOT 1
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from chanhuiseok.github.io.