Creative Coding 독학 제300일 2025년01월21일(화)

2025년 1월 21일

오늘 다시 Travelling Salesman Problem을 Lexicographic Order Algorithm으로 풀어내는 코드 작업을 해나갈텐데요~^^*

제가 마법의 양탄자를 타고 이동을 해야 해서요~^^*

우리 밤에 다시 만날까요~^^*

네~^^* 좋아요~^^* 고마워요~^^*

멋진 아침과 맛있는 점심과 보람찬 하루 보내시고요!

밤에 다시 만나요~^^* 쓩~^^*

네~^^* 마법에 양탄자에서 사뿐히 내렸습니다~^^*

지구는 둥글어서 어느 곳은 이른 저녁이겠지요~^^* 그래서 지금부터 오늘의 코딩 공부를 해 보겠습니다~^^*

부지런했던 오늘 하루 끝, 수고한 마음과 몸 토닥이며 재즈 편안히 듣고 계시겠어요^^* 공부 정리해서 돌아올게요~^^* 쓩~^^*

음악이 녹진해서 잠들어도 괜찮아요~^^*. 이미 12시 06분. 이미 22일이네요. 코~^^* 잠들었다 아침에 깨어나서 천천히 보셔도 괜찮아요~^^*

네~^^* 오늘은 경로의 거리를 계산하여 가장 짧은 경로를 찾아내 보겠습니다~^^*

하나. 도시 경로의 거리값을 계산해 보겠습니다.

도시들을 담은 배열과 도시 배열의 구성요소의 인덱스를 담은 배열의 정보가 필요하겠네요~^^*

인덱스 < i >가 가리키는 도시의 위치, 그리고 인덱스 < i + 1 >가 가리키는 도시의 위치 사이의 거리를 구하고, 거리의 총합에 더하면 될 것 같아요~^^*

그럼 우리~~^^* 거리 계산 함수 calcDistance()를 준비해 볼까요~~^^*

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에 더합니다.

둘. 필요한 변수와 맨 첫번째 경로에 관련된 값들을 계산해 보겠습니다.

var recordDistance;
var bestEver;

function setup() {
   .
   .
   .
  var d = calcDistance(cities, order);
  recordDistance = d;
  bestEver = order.slice();
}
//가장 짧은 경로의 거리값을 저장할 변수 recordDistance를 준비하겠습니다.
//이때의 도시 구성요소 인덱스 배열을 저장할 변수 bestEver를 준비하겠습니다.
//첫번째 도시 경로의 거리값을 저장한 변수 d의 값을 변수 recordDistance에 저장하겠습니다. 
//이때의 도시 구성요소 인덱스 배열을 복사하여 변수 bestEver에 저장하겠습니다.

셋. 두번째 경로부터는 무한 반복 함수 draw() 안에서, 기록 갱신을 하면 어떨까요~^^*

function draw() {
   .
   .
   .
  var d = calcDistance(cities, order);
  if (d < recordDistance) {
    recordDistance = d;
    bestEver = order.slice();
  }
   .
   .
   .
}

넷. 가장 빠른 경로 기록이 갱신될 때마다 핫핑크 선으로 새롭게 표현해 보겠습니다~^^*

function draw() {
   .
   .
   .
  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의 구성요소들(도시 배열 구성요소의 인덱스)이 가리키는 도시의 위치 좌표를 꼭지점으로 하여 핫핑크 선을 굵게 그려 볼까요~^^*

그럼 우리 전체 코드를 함께 살펴 볼까요~~^^*

var cities = [];
var order = [];
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;
      order[i] = i;
  }
  
  var d = calcDistance(cities, order);
  recordDistance = d;
  bestEver = order.slice();
}
//가장 짧은 경로의 거리값을 저장할 변수 recordDistance를 준비하겠습니다.
//이때의 도시 구성요소 인덱스 배열을 저장할 변수 bestEver를 준비하겠습니다.
//첫번째 도시 경로의 거리값을 저장한 변수 d의 값을 변수 recordDistance에 저장하겠습니다. 
//이때의 도시 구성요소 인덱스 배열을 복사하여 변수 bestEver에 저장하겠습니다. 


function draw() {
  background(0);
  fill(255);
  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();
  }

  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: 맞바꿈이 일어난 지점 뒷부분 거꾸로 정렬하기 
}

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에 더합니다.

먼저, 가벼운 마음으로 ~^^* 5개의 도시들의 최.적.경.로.가 찾아지는 과정을 우리 함께 지켜볼까요~^^*

이제 10개의 도시 도전!!!

오늘 저와 함께 최.적.경.로. 찾기 과정을 완성해 주셔서 감사합니다!

아…네~^^* 저도 그렇게 느껴져요…

뭔가 좀 더 짧은 경로가 열심히 꾸준히 찾아지고 있다는 느낌은 있는데….최.적.경.로. 찾기 과정이 어느 정도까지 진행되고 있는지는 느껴지지는 않는 것 같아요. 10!….너~~무 많은 경우를 다루고 있다 보니까요…

그럼 우리 내일은, 지금 모든 경우 중 어느 정도까지를 살펴보았는지를 표시하는 기능을 추가해 보면 어떨까요~^^*