Silverback9

네~^^* 어제 우리는 Lexicographic Order Algorithm 코드를 완성해 보았는데요~^^*

우리~^^* 복습으로~^^* 동영상 강의를 편안한 시청자 모드로 한 번 보고 다음 도전에 나서면 어떨까요~^^*

네~^^* 새로운 도전에 앞서, 아침을 음악과 함께 열고 계시겠어요? 코딩 공부 정리해서 돌아올게요~^^* 쓩~^^*

우리는 다시 Travelling Salesman Problem을 다루어 보는 거예요~^^* 긴 길을 길게 걸어가는 긴 시선으로 우리 다시 TSP를 함께 풀어 보는 거예요~^^*

우리는 모두 자신의 길을 나름으로 걸어가는 여행자의 운명을 가지고 있으니까요~^^* 함께 가요, 우리~^^* 함께 풀어봐요, Travelling Salesman Problem~^^*

마음의 준비를 하고 계시겠어요~^^* 코딩 공부 정리해서 돌아올게요~^^* TSP!! 쓩~^^*

네~^^*

사전식 배열 알고리즘으로 도시 경로를 만들어 보려니….

음…

어떻게…?

살짝 막막해지는 느낌이 있죠….

네…저도 그래요….^^* 음…^^* 하…^^*

이전에는 무작위로 맞바꿈을 하며 무한 반복을 하며 모든 경우를 다루어 보려고 했는데요..

이번에는 사전식 배열로 모든 경우를 다루어야 하잖아요…

아!!! 좋은 생각이 났어요…!!!

함께 코딩 공부하고 있는 우리 생각요~^^*

사전식으로 배열된 숫자들을, 도시들을 담은 배열의 인덱스로 사용해 보는 거예요!!!

그러면, 도시들을 담은 배열의 순서를 바꾸지 않아도 될 것 같아요.

사고 실험을 먼저 해 볼까요~,우리~^^*

도시 배열 cities = {마카오, 서울, 오사카}

현재 도시 배열 구성요소 : 
 cities[0] = 마카오, 
 cities[1] = 서울, 
 cities[2] = 오사카

도시 배열의 인덱스 배열 order = {0, 1, 2} 

도시 배열의 구성요소를 가리키는 인덱스를 담은 배열에 Lexicographic Order를 적용하여 발생하는 모든 경우를 다루어 보겠습니다. 

<<경우 1>>
 (1) 도시 인덱스 order = {0, 1, 2}
 (2) 도시 경로 = 
    cities[0] 마카오 =>
    cities[1] 서울 =>
    cities[2] 오사카

<<경우 2>>
 (1) 도시 인덱스 order = {0, 2, 1}
 (2) 도시 경로 = 
    cities[0] 마카오 =>
    cities[2] 오사카 =>
    cities[1] 서울

<<경우 3>>
 (1) 도시 인덱스 order = {1, 0, 2}
 (2) 도시 경로 = 
    cities[1] 서울 =>
    cities[0] 마카오 =>
    cities[2] 오사카

<<경우 4>>
 (1) 도시 인덱스 order = {1, 2, 0}
 (2) 도시 경로 =
    cities[1] 서울 =>
    cities[2] 오사카 =>
    cities[0] 마카오

<<경우 5>>
 (1) 도시 인덱스 order = {2, 0,1}
 (2) 도시 경로 =
    cities[2] 오사카 =>
    cities[0] 마카오 =>
    cities[1] 서울

<<경우 6>>
 (1) 도시 인덱스 order = {2, 1, 0}
 (2) 도시 경로 =
    cities[2] 오사카 =>
    cities[1] 서울 =>
    cities[0] 마카오

네~^^* 도시 배열 자체는 가만히 두었는데요. 도시를 가리키는 인덱스를 담은 배열에 Lexicographic Order를 적용하였더니, 6가지의 도시 이동 경로가 생겨나네요^^*

그럼 이 부분을 코드로 만들어 볼까요~^^*

하나. 먼저 도시들을 무작위로 생성하여 배열 cities[]에 담겠습니다. 그리고 그 배열의 인덱스를 담은 또다른 배열 order[]를 만들겠습니다.

var cities = [];
var order = [];
var totalCities = 3;

function setup() {
   .
   .
   .
  for (var i = 0; i < totalCities; i++) {
      var v = createVector(random(width), random(height / 2));
      cities[i] = v;
      order[i] = i;
  }
   .
   .
   .
}

둘. 도시들을 담은 배열 cities[]의 구성요소들의 인덱스를 담은 배열 order[]의 다음 순열을 생성하는 함수 nextOrder()를 Lexicographic Oder Algorithm을 바탕으로 준비해 보겠습니다.

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;
}

셋. 도시들을 담은 배열 cities[]의 구성요소의 인덱스를 담은 배열 order의 구성요소의 내용을 변수 n에 저장하고, 도시들을 담은 배열 cities[]의 n번째 구성요소를 찾아서, 이것을 꼭지점으로 삼아 선을 그려보겠습니다. 음…도시 경로가 그려지겠네요~^^*

function draw() {
  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();
}

넷. 경로가 완성되고 나면, nextOrder함수를 호출하여, Order[]의 다음 순열을 생성하겠습니다. 함수 draw()는 무한반복 함수이기 때문에, Order[]의 모든 경우의 순열이 생성되고, 이때마다 도시 경로도 바뀌게 되겠네요^^*

function draw() {
   .
   .
   .
  nextOrder();
}

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

var cities = [];
var order = [];
var totalCities = 3;

function setup() {
  createCanvas(400, 400);
   
  for (var i = 0; i < totalCities; i++) {
      var v = createVector(random(width), random(height / 2));
      cities[i] = v;
      order[i] = i;
  }
}

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);
  strokeWeight(1);
  noFill();
  beginShape();
  for (var i = 0; i < order.length; i++) {
    var n = order[i];
    vertex(cities[n].x, cities[n].y);
  }
  endShape();

  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;
}

그럼 도시들을 담은 배열 cities[]의 구성요소의 순서를 바꾸지 않아도, 도시들을 담은 배열 cities[]의 구성요소의 인덱스을 담은 배열 Order[]의 구성요소의 순서만 바꾸어도, 도시 연결 경로가 바뀌어지는 모습, 저와 함께 보러 가실까요? 경로 변화를 잘 볼 수 있도록 무한 반복 함수 draw()를 천천히 반복해 보겠습니다~^^*

오늘 저와 함께~^^* Lexicographic Order Algorithm 사전식 배열 알고리즘을 Travelling Salesman Problem 여행하는 외판원 문제에 적용하는 작업을 시작해 주셔서 감사합니다~^^*

내일은요~^^*, Travelling Salesman~^^*

음악 함께 들으며 편하게 쉬구요~^^*, 소중한 보부상~^^*

화요일부터 다시 코딩 공부 시작할까요~^^*

경로 변화는 해내었으니, 최.적.경.로. 계산도 해낼 수 있을 것 같아요! YEAH!!!

작은 성공이 우리에게 선사하는 <<용기 뿜뿜 좋은 기분>> 이 느낌~~^^*

오늘도 점심 맛있게 드시고요~^^*

즐거운 기차 여행처럼 편안하고도 보람찬 하루 보내시고요~^^*

밤이라는 정착역에 내리면~^^*

감사와 뿌듯함 속에서 코~^^* 하시기 바래요~~^^*

멋진 한 주를 살아내기 시작할 내일이 또 우리를 기다리고 있으니까요~^^*

Legend 전설을 써 내려갈 또 다른 멋진 한 주가 우리를 기다리고 있으니까요~^^* YEAH!!!

네~^^* 꿈은 이루어 집니다~^^*