지금 지평선 위로 노란 해가 떠 올라 있어요~^^*
들판에 은은하게 퍼져나가는 노란빛 주황빛^^*
네~^^* 아침입니다~^^*
지금 저는 이동을 하고 있습니다~^^* 그래서요~^^*
우리 아침엔 음악만 함께 듣고~^^* 오후에 다시 만날까요~^^*
네~^^* 고마워요~^^*
지금 어느 곳은 저녁 어둠이 내리고 있겠네요^^* 네, 지구는 둥그니까요~^^*
피아노 건반을 콕콕콕 누르면~^^* 동글동글한 공들이 퐁퐁 튀어오르는 것 같아요^^*
피아노가 쏘아올린 작은 공들로 저글링도 하면서~^^* 노란 아침 여유를 누리시기 바래요~^^*
조용한 곳에서 튕겨지는 기타의 현은 작은 웃음소리를 닮은 것 같아요~^^*
저는 차창 밖을 바라보며 마음의 기지개를 켤게요~^^*
조용하고 아늑한 집 안에서 두 팔을 펴고 기지개를 부드럽게 주욱~^^* 켜 보시겠어요~^^*
Good Morning~^^*
오늘도 멋진 아침 보내시고요~^^*
저는 오후에 다시 돌아올게요~^^* 또 만나요~~^^* 쓩~~^^*
네~^^*
멋진 하루를 보내고 계신가요^^*
노랗던 아침 해는~^^*
이제 회색 빛이 더해진 맑은 하얀 빛 융단을 하늘 위에 펼쳐 놓고 자신의 얼굴을 그 안에 가리고 있어요.
네~^^* 쌀 씻어 밥 짓기 딱 좋은 시간입니다~^^*
저녁 맛있게 드시고 다시 만나요, 우리~~^^* 쓩~^^*
네~^^*
오늘은 Travelling Salesman의 여정의 총 거리의 합이 가장 짧은 기록 recordDistance가 갱신될 때마다, 그 여정 경로를 보여주는 코딩작업을 해 볼게요~^^*
여정 경로는 배열 구조로 되어 있었지요~^^*?
여정의 최단거리 기록 recordDistance가 갱신될 때마다, 그 여정 배열을 복사하여 좀 더 진하고 굵은 선으로 표현해 보도록 하면 어떨까요?
배열을 복사하는 함수 slice()를 사용해 보겠습니다~^^*
하나. 현재기준으로 가장 좋은 경로를 담을 변수 bestEver를 준비하겠습니다.
둘. 맨 처음 만들어진 여행경로 cities 배열을 복사하여 bestEver에 저장하겠습니다~
var bestEver;
function setup() {
createCanvas(400, 400);
for( var i = 0; i < totalCities; i++ ) {
var v = createVector(random(width), random(height));
cities[i] = v;
}
var d = calcDistance(cities);
recordDistance = d;
bestEver = cities.slice();
}셋. 여정의 최단거리 기록 recordDistance가 갱신될 때마다, 그때의 cities 배열을 복사하여 bestEver에 저장하겠습니다.
function draw() {
.
.
.
var d = calcDistance(cities);
if (d < recordDistance) {
recordDistance = d;
bestEver = cities.slice();
console.log(recordDistance);
}
}넷. 현재기준 최단경로의 여정인 bestEver을 Hot Pink 굵은 선으로 그려보겠습니다.
function draw() {
.
.
.
stroke(255, 0, 255);
strokeWeight(4);
noFill();
beginShape();
for( var i = 0; i < bestEver.length; i++ ) {
vertex(bestEver[i].x, bestEver[i].y);
}
endShape();
.
.
.
}자 그럼 우리 전체 코드를 한 번 살펴 볼까요~^^*
var cities = [];
var totalCities = 10;
var recordDistance;
var bestEver;
//여행경로 최단거리 신기록을 기록해 보고자 합니다.
//최단거리 경로를 함께 나타내 보겠습니다. 핫! 핑크! 어때요~^^*
function setup() {
createCanvas(400, 400);
for( var i = 0; i < totalCities; i++ ) {
var v = createVector(random(width), random(height));
cities[i] = v;
}
var d = calcDistance(cities);
recordDistance = d;
bestEver = cities.slice();
}
//다양한 좌표위치를 가진 벡터를 생성하여, 도시들을 담는 배열 cities[]에 저장하겠습니다.
// 첫 번째로 구성된 도시 배열의 거리 총합을 구해서 변수 d에 담습니다.
// 이 d의 값이 첫 번째 최단 이동 거리의 신기록 recordDistance가 되겠네요^^*
// 첫 번째 cities[]이 맨 최단거리경로 bestEver가 되겠네요^^*
function draw() {
background(0);
fill(255);
for( var i = 0; i < cities.length; i++ ) {
ellipse(cities[i].x, cities[i].y, 8, 8);
}
//도시들을 담는 배열 cities[]의 구성요소들의 위치좌표에 지름 8의 원을 그리겠습니다.
stroke(255);
strokeWeight(2);
noFill();
beginShape();
for( var i = 0; i < cities.length; i++ ) {
vertex(cities[i].x, cities[i].y);
}
endShape();
//도시들의 위치좌표를 꼭지점으로 하여, 꼭지점들을 연결해 보겠습니다.
//beginShape() - vertex() - endShape() 구조를 복습하고 가실게요~^^*
stroke(255, 0, 255);
strokeWeight(4);
noFill();
beginShape();
for( var i = 0; i < bestEver.length; i++ ) {
vertex(bestEver[i].x, bestEver[i].y);
}
endShape();
//핫핑크 굵은 선으로 현재기준 최단거리 경로 bestEver를 그려보겠습니다~^^*
//신선한 핑크 빛 혈액이 흐르는 믿음직한 굵은 핏줄이 보이겠네요^^*
var i = floor(random(cities.length));
var j = floor(random(cities.length));
swap(cities, i, j);
//도시들을 담은 배열 cities[]의 구성원을 무작위로 두 개 선정하여, 서로의 정보를 맞바꾸겠습니다.
//간혹 이 두 도시가 우연히 동일할 수도 있겠지만, 무작위 선택을 계속 무한반복 하기 때문에 큰 문제는 없을 것 같아요...
var d = calcDistance(cities);
if (d < recordDistance) {
recordDistance = d;
bestEver = cities.slice();
console.log(recordDistance);
}
}
//도시가 무작위 swap()되어 새롭게 된 도시 이동경로의 거리 총합 d가
//최단거리 신기록 recordDistance보다 작다면
//신기록 갱신~~^^*!!!
//신기록이 갱신되었으니, 이때의 cities[]를 복사하여 최단거리 경로 bestEver에 저장하겠습니다.
//콘솔창에 현재의 최단거리 신기록을 보여주도록 하겠습니다~^^*
function swap( a, i, j) {
var temp;
temp = a[i];
a[i] = a[j];
a[j] = temp;
}
function calcDistance(points) {
var sum = 0;
for (var i = 0 ; i < points.length - 1; i++) {
var d = dist(points[i].x, points[i].y, points[i+1].x, points[i+1].y);
sum += d;
}
return sum;
}
//도시배열 마지막 바로 앞 도시 point.length - 2까지 반복한다는 것에 우리 주의를 기울여 볼까요?
//도시 배열은, [0] ~ [point.length - 1]까지의 구성요소를 가지고 있지요?
//배열 length 길이가 3이면, 구성요소는 [0], [1], [ 2 (= length-1) ]가 있겠네요?
//이때 배열 마지막 바로 앞의 구성요소는 [ 1 (= length -2) ]가 되겠네요?
//그래서, 도시 배열 마지막 바로 앞 도시와 그 다음 도시(마지막 도시) 사이의 거리를 구하기 위해서는~^^*
//i가 point.length -1 보다 작을 때까지만,
// 즉, i가 point.length - 2가 될 때까지만
// for 구문을 안의 작업문을 반복해 보면 어떨까요?~~^^*
도시 10개를 잇는 최단거리 경로 bestEver를 보러 가실까요~~^^*
10개의 경우 컴퓨터가 최단거리를 찾아내기 위해 살펴봐야 할 경우의 수가 3,628,800개라서, 우리 눈으로 볼 떄 금방 찾아볼 수 있는 효율적인 경로를 컴퓨터가 찾아내기까지는 시간이 많이 걸릴 것 같네요.
4개의 도시의 경우는 금방 잘 찾아낼 것 같은데요~^^*
네~^^* 오늘 저와 함께 Travelling Salesman Problem 코드를 완성해 주셔서 감사합니다!
네~^^* 저와 함께 Brute Force Solution <<모든 경우의 수를 다 시도해 보기>> 방법을 통해 Travelling Salesman Problem을 해결해 주셔서 감사합니다!!!
Travelling Salesman! 소중한 보부상!
첫 번째 방법도 시간이 좀 걸려서 그렇지 참 재미있었죠~~^^*
내일부터는 새로운 방법으로 최.적.경.로.를 또 찾아 볼게요! YEAH~~^^*
오늘도 따뜻하고 뿌듯한 밤 코~^^* 하시고요~^^*
내일 우리 또 만나서 새로운 도전 이어가 보기로 해요~~^^*
네~~^^* 꿈은 이루어 집니다~~^^*
Silverback9 
댓글 남기기