NP-Hard 등의 문제를 풀 때, 가지치기를 효과적으로 하며 최적의 해를 탐색하는 기법 중 하나. Branch별로 Bound와 탐색 중에 발견된 Maxprofit을 비교하여 Prunning을 하는 기법이다. 즉, branch별로 선택하는 경우에 대한 Bound (주어진 상황에서 예상되는 최대의 결과)를 계산하여 이를 선택의 제외의 기준으로 삼는 방법이다.
처음에 이해하기는 조금 헷갈리는 개념이지만, 실제로 그림을 그리면서 진행해보면 생각만큼 이해하기는 어렵지 않은 주제이다.
TSP를 예를 들어서, 남은 선택 중에서 모두 최선의 선택을 한다고 가정할 경우에 나오는 예상 값을 각각 bound로 계산한다. TSP의 목표는 탐색비용의 최소화이므로, bound는 lower bound가 될 것이다. 탐색을 하면서 각 branch별로 bound를 먼저 계산하고 가장 bound가 낮은 것부터 탐색한다.
순회를 계속해 진행하면서 maxprofit을 갱신해 나간다. maxprofit보다 bound가 높은 node의 경우는 더 이상 진행할 필요가 없으므로 추가로 탐색하지 않는 것을 반복한다. 끝.
간단하면서도 효과가 뛰어난 NP-Hard 해결 방법 중 하나이다.
best-first search 방법을 섞어서 사용하면 조금 더 탐색의 효율이 개선될 것으로 보인다. 검증할 필요는 있어 보이지만..
사용에 제한이 없는 web-based coding open source툴. 간단한 C++는 잘 돌아가는 것을 확인헀는데, python은 동작이 제대로 안 돌아가는 것 같다. 아직 구현이 덜된건가? 여튼 C, C++를 간단히 테스트하기에는 무척이나 유용한 툴 http://melpon.org/wandbox
coderpad
깔끔하고 사용하기 좋아보이는 coderpad. 상용 툴이라서 제한은 좀 있지만 정말 간단하게 코드를 웹에서 테스트해보기 딱 좋다. 다만, 로그인하지 않으면 곧 expire되므로, 유료사용자가 될 것이 아니면 제약이 많다. https://coderpad.io/
지원 가능 언어들 : 거의 모든 언어가 다 된다고 보면 된다.
C C# C++ Clojure CoffeeScript Erlang F# Go Haskell Java JavaScript Markdown MySQL Objective-C PHP Perl Plain Text Python 2 Python 3 R Ruby Rust Scala SwiftVisual Basic
There are five well-known software design principles from the book “Head First, Design Patterns”. Nothing’s absolute, but classical things are great enough to know and have a look on it.
S : Single responsibility
O : OCP, Open / Close Principles
Objects should be open for extension, but closed for modification.
클래스(객체)는 확장에 대해서는 열려있어야 한다. 하지만, 코드 변경에 대해서는 닫혀 있어야 한다.
L
I
D : Dependency Inversion Principles
if you want an easier life as a coder, “depend on abstractions, not concretions”
추가로 path를 추가해야 한다. 다음과 같이 export로 실행파일들이 있는 user의 실행파일 폴더를 추가하자. tensorflow virtualenv를 실행하면 자동으로 추가하기 위해서는 해당 activate script 중간에 추가하자.
1
$ export PATH="$PATH:/Users/huklee/.local/bin"
scikit-learn 설치 추가로 scikit-learn을 아래와 같이 설치하자. 마찬가지로 virtualenv로 들어와 있는 상태에서 진행해야 제대로 tensorflow 환경이 반영될 수 있다.
1
(tensorflow) $ pip3 install -U scikit-learn
jupyter notebook 실행 jupyter notebook을 실행하자. 마찬가지로 tensorflow virtualenv를 실행시킨 상태에서 실행이 되어야 한다. 그리고 나서는 브라우저(chrome)으로 http://localhost:8888/ 에 접속하면 된다.
1
(tensorflow) $ jupyter notebook
DONE
여기까지 하면 jupyter에서 tensorflow 및 scikit-learn, numpy, scipy, pandas 몽땅 잘 작동하는 것을 확인할 수 있다.
쭉 yes / enter를 해 주면 설치가 5~10분 정도 걸린다. 다운로드 및 설치 당시 파일 기준의 버전은 아래와 같다.
1
2
3
4
$ python -V
Python 3.6.0 :: Anaconda 4.3.0 (x86_64)
$ conda -V
conda 4.3.8
다음과 같이 conda envinronment에 텐서플로우를 추가하자.
1
$ conda create -n tensorflow python=3.4
추가된 conda environment를 사용하기 위해서는 source activate [env_name] 을 사용해서 접속하면 된다. 활성화된 conda env에서 실제로 python 버전을 찍어보면 다른 버전이 나오는 것을 확인할 수 있다. 반대로 env를 나오기 위해서는 source deactivate로 나오면 된다.
1
2
3
4
5
$ python -V
Python 3.6.0 :: Anaconda 4.3.0 (x86_64)
$ source activate tensorflow
$ (tensorflow) python -V
Python 3.4.5 :: Continuum Analytics, Inc.
2. install tensorflow
본격적으로 tensorflow를 설치하자. 위에서 바로 실행된 conda env가 activate된 상태에서 진행하면 된다. pip
