오늘은~^^*
최.적.경.로. 찾기 과정~ 어디까지 진행되고 있나~~^^* 표현하는 코드를 공부하는 날이예요~^^*
신선한 한기가 느껴지는 산뜻한 아침~^^* 두툼하고 폭신한 첼로 브러시로 마음결을 부드럽게 빗을까요?
아침 단장 즐겁게 하고 계셔요~^^* 코딩 공부 정리해서 돌아올게요~^^* 쓩~^^*
네~^^*
다루어야 할 모든 경우 중 현재까지 몇 개의 경우를 다루었나?를 계산하여 표현하면 어떨까요~^^*
네~!!! 그런 것 같아요~!!!
분수의 개념이 되는 것 같네요!!!
음,,,그럼…분자는…? 그리고 분모는….?
현재 몇 개의 경우를 다루었나 / 다루어야 할 모든 경우네~^^*
분자는 <현재 몇 개의 경우를 다루었나>이고 분모는 <다루어야 할 모든 경우>가 될 것 같네요~^^*
하나. 그럼 먼저~ <현재 몇 개의 경우를 다루었나>를 표현할 변수를 준비해 볼게요~^^*
var count = 0; 둘. 경로를 생성할 때마다 변수 count를 1 증가시켜 볼게요~^^*
function setup() {
.
.
.
for (var i = 0; i < totalCities; i++) {
var v = createVector(random(width), random(height));
cities[i] = v;
order[i] = i;
}
count++;
.
.
.
}
//최초의 경로가 만들어 질 때도 count를 1 증가시키면, 경우의 수를 1부터 시작할 수 있을 것 같아요.
//경우의 수를 0부터 시작하는 것보다 좀 더 자연스러운 느낌~^^*function nextOrder() {
.
.
.
count++;
}
//새로운 경로가 만들어지면 count를 1 증가시켜 보겠습니다~^^*셋. 모든 경우의 수를 담을 변수를 준비하겠습니다~^^*
var totalPermutations;넷. 모든 경우의 수는 n! 팩토리얼이니까요~^^* Factorial 팩토리얼을 계산하는 함수를 만들어 볼게요~^^*
1! = 1;
2! = 2 * 1;
3! = 3 * 2 * 1;
4! = 4 * 3* 2 * 1;
5! = 5 * 4 * 3 * 2 * 1;n! = n * (n-1) * ((n-1) -1) * (((n-1) -1) -1) * ... * 1;음…parameter로 n을 받아서, n-1의 팩토리얼 Facotrial을 계산하는 재귀함수 factorial(n-1)을 호출해서 그 return 값에 n을 곱하는 재귀함수 factorial(n)이 필요할 것 같아요…
n이 1이 될 때까지 n-1의 factorial 팩토리얼을 계산하는 자기 자신을 계속 호출하는 썰물 파도가~~~~,
n이 1이 되면 n! factorial을 계산하여 반환하고, 반환받은 그 값에 n (이때 n은 이전 n에 1을 더한 값을 가지고 있겠지요…?)을 곱하여, 다시 n! factorial 값으로 반환하는 밀물 파도가~~~~,
호출 썰물과 반환 밀물이 발생하는 재귀함수의 바다를 만들어 보겠습니다~~^^*
function factorial(n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}다섯. 재귀함수 factorial(n)의 값을 return 반환받아 변수 totalPermutaions (순열의 모든 경우의 수)에 저장하겠습니다~
function setup() {
.
.
.
totalPermutations = factorial(totalCities);
}여섯. 현재까지 다룬 경우의 수 (count) / 모든 경우의 수 (totalPermutation)를 백분율 percentage로 나타내 보겠습니다.
(i) 변수 percent를 마련해 볼까요~^^*
(ii) 소수점 둘째 자리까지 담아서 percent 값을 시각적으로 표현해 볼게요~^^* 함수 nf()를 사용하면 백분율을 소수점 몇째 자리까지 표현할 지 지정할 수 있습니다~^^*
function draw() {
.
.
.
textSize = 32;
fill(255);
var percent = 100 * (count / totalPermutations);
text(nf(percent, 0, 2) + "% completed", 20, height - 50);
.
.
.
}그럼, 우리 전체 코드를 함께 살펴 볼까요~~^^*
var cities = [];
var order = [];
var totalCities = 5;
var recordDistance;
var bestEver;
var count = 0;
var totalPermutations;
function setup() {
createCanvas(400, 400);
for (var i = 0; i < totalCities; i++) {
var v = createVector(random(width), random(height));
cities[i] = v;
order[i] = i;
}
count++;
var d = calcDistance(cities, order);
recordDistance = d;
bestEver = order.slice();
totalPermutations = factorial(totalCities);
}
//가장 짧은 경로의 거리값을 저장할 변수 recordDistance를 준비하겠습니다.
//이때의 도시 구성요소 인덱스 배열을 저장할 변수 bestEver를 준비하겠습니다.
//첫번째 도시 경로의 거리값을 저장한 변수 d의 값을 변수 recordDistance에 저장하겠습니다.
//이때의 도시 구성요소 인덱스 배열을 복사하여 변수 bestEver에 저장하겠습니다.
//도시총갯수 toralCities의 팩토리얼 값을 구하여 변수 toralPermutation에 저장하겠습니다.
function draw() {
background(0);
fill(255);
console.log(count, totalPermutations);
for (var i = 0; i < cities.length; i++) {
ellipse(cities[i].x, cities[i].y, 8, 8);
}
stroke(255, 0, 255);
strokeWeight(4);
noFill();
beginShape();
for (var i = 0; i < order.length; i++) {
var n = bestEver[i];
vertex(cities[n].x, cities[n].y);
}
endShape();
//가장 빠른 경로의 도시 인덱스 배열인 bestEver의 구성요소들(도시 배열 구성요소의 인덱스)이 가리는 도시의 위치 좌표를 꼭지점으로 하여 핫핑크 선을 굵게 그려 볼까요~^^*
stroke(255);
strokeWeight(1);
noFill();
beginShape();
for (var i = 0; i < order.length; i++) {
var n = order[i];
vertex(cities[n].x, cities[n].y);
}
endShape();
var d = calcDistance(cities, order);
if (d < recordDistance) {
recordDistance = d;
bestEver = order.slice();
}
textSize = 32;
fill(255);
var percent = 100 * (count / totalPermutations);
text(nf(percent, 0, 2) + "% completed", 20, height - 50);
//현재까지 다룬 경우의 수 / 모든 경우의 수
//를 백분율로 변환하겠습니다.
//소수점 둘째 자리까지 나타내겠습니다.
nextOrder();
}
function nextOrder() {
//Lexicographic Order 사전식 배열
var largestI = -1;
for (var i = 0; i < order.length - 1; i++) {
if (order[i] < order[i + 1]) {
largestI = i;
}
}
if (largestI == -1) {
noLoop();
console.log('finished');
}
//STEP 1: largestI 구하기
var largestJ = -1;
for (var j = 0; j < order.length; j++) {
if (order[largestI] < order[j]) {
largestJ = j;
}
}
//STEP 2: largestJ 구하기
swap(order, largestI, largestJ);
//STEP 3: largestI와 largestJ 맞바꾸기
var endArray = order.splice(largestI + 1);
endArray.reverse();
order = order.concat(endArray);
//STEP 4: 맞바꿈이 일어난 지점 뒷부분 거꾸로 정렬하기
count++;
}
function swap(a, i, j) {
var temp = a[i];
a[i] = a[j];
a[j] = temp;
}
function calcDistance(points, order) {
var sum = 0;
for (var i = 0; i < order.length - 1; i++) {
var cityAIndex = order[i];
var cityA = points[cityAIndex];
var cityBIndex = order[i + 1];
var cityB = points[cityBIndex];
var d = dist(cityA.x, cityA.y, cityB.x, cityB.y);
sum += d;
}
return sum;
}
//도시 배열의 구성요소의 인덱스 값을 모은 배열 order의 i 번째 값을 변수 cityAIndex에 저장합니다.
//qoduf order의 i + 1 번째 값을 변수 cityBIndex에 저장합니다.
//도시들을 모은 배열 point의 cityAIndex번째 도시를 변수 cityA에 저장합니다.
//배열 point의 cityBIndex번째 도시를 변수 cityB에 저장합니다.
// cityA의 위치와 cityB의 위치 사이의 거리를 계산하여 변수 d에 저장합니다.
// 거리 총합을 나타내는 변수 sum에 더합니다.
function factorial(n) {
if (n == 1) {
return 1;
} else {
return n * factorial(n - 1);
}
}
//n!를 계산하는 재귀함수입니다~^^*5개의 도시를 여행하는 최.적.경.로.가 찾아지는 과정을 편안한 마음으로 지켜볼까요, 우리~^^*
이번에는 10개 도시를 도전해 봅시다~~^^* YEAH~~^^*
와우! 10!은 정말 큰 수이구나!! 실감할 수 있는 것 같아요!!! 한참을 지켜봐도 1 percent까지도 진행되지 않는 것을 보니까요…와우!!! 3628800는 정말 큰 수인 것 같아요!!!
오늘 저와 함께 최.적.경.로. 찾기 과정의 현재 진행상황까지 표시해 주는 프로그램을 완성해 주셔서 감사합니다~^^*
와우! 우리가 동영상 강의 하나를 또 마무리 해내었네요~^^*
너무 멋진 프로그램이 완성된 것 같아요~^^* 함께 만들어 주셔서 감사합니다~^^*
우리~~^^* 내일부터는~~^^*
Travelling Salesman Problem을 해결하기 위한 최.적.경.로. 찾기 과정을 Genetic Algorithm을 기반으로 새롭게 작업해 볼까요~^^*
어떤 부분은 어떤 방식으로 변화시켜 볼 수 있을까요~^^* SWAP()의 정신을 창의적으로 실천해 볼까요~^^* 또 다르게 멋진 창작의 과정이 될 것 같아요~^^*
많은 땀방울을 흘려 깜짝 놀랍도록 멋진 공연 작품을 완성하는 것처럼~~^^*
새로운 고민을 담아 또 다르게 멋지고 깜짝 놀라운 공연 작품을 탄생시키는 것처럼~~^^*
우리도~~^^*
내일부터~~^^*
Genetic Algorithm 버전의 새로운 Travelling Salesman Problem 프로그램을 만들어 이 세상에 선물해 볼까요~~^^*
YEAH~~^^*
오늘도
점심 맛있게 드시고요!
보람있는 하루 즐겁게 보내시고요!
따뜻한 저녁 피로 푸는 밤 되시기 바래요!
내일 또 만나는 거예요, 우리~~^^*?
네^^* 좋아요~^^* 고마워요~^^*
네~~^^* 꿈은 이루어 집니다~~^^*
Silverback9 
댓글 남기기