Mod: Coding Challenge #35.1 + 35.2 : Traveling Salesperson

トラベルサラリーマンじゃなくて，巡回セールスパーソン問題ってやつ．イメージはセールスパーソンが幾つかの都市に出張営業する経路を考える時に，移動距離が一番短くなる経路を導き出すというもの．総当りで出すけど経路の組み合わせと計算をシリーズで考えてみる．5個あるシリーズのうち，今回は前半の2つをやってみた．

2個目は辞書式順序（Lexicographic Order），辞書の並びのようにアルファベットや五十音で順序を並べていくためのアルゴリズム．textを含めたプログラムを実行するのにProcessingのPDEだといちいち時間が掛かるのでOpenProcessingで書いてたんだけど，結果OpenProcessingでは動くけどPDEでは動かないものになってしまった…．原因は配列の連結やスプライスの書き方な気がするけど，ちょっと今は追えないのでまたやる．

先行きの内容を見ると，p5.jsちょっと本腰入れてやらないとダメな気がしてきた．

コード（35.1）

int totalCities = 10;
PVector[] cities = new PVector[totalCities];
PVector[] citiesOrdered = new PVector[totalCities];
float offset = 50;
float recordDistance = 0;
float hue1, hue2;
void setup() {
  fullScreen();
  colorMode(HSB, 360, 100, 100);
  init();
}

void init(){
  for (int i = 0; i < totalCities; i++) {
    PVector city = new PVector(random(offset, width-offset), random(offset, height-offset));
    cities[i] = city;
    citiesOrdered[i] = city;
  }
  recordDistance = calDistance(cities);
  hue1 = random(360);
  hue2 = (hue1 + 180)%360;
}

void draw() {
  background(hue2, 40, 40);
  
  fill(hue1, 100, 100);
  noStroke();
  for (PVector city : cities) {
    ellipse(city.x, city.y, 15, 15);
  }
  stroke(0, 0, 100);
  strokeWeight(1);
  noFill();
  beginShape();
  for (PVector city : cities) {
    vertex(city.x, city.y);
  }
  endShape();

  int i = floor(random(cities.length));
  int j = floor(random(cities.length));
  cities = swap(cities, i, j);

  float currentDistance = calDistance(cities);
  if (currentDistance < recordDistance) {
    recordDistance = currentDistance;
    arrayCopy(cities, citiesOrdered);
  }
  
  if (citiesOrdered != null) {
    stroke(hue1, 100, 100);
    strokeWeight(3);
    strokeJoin(ROUND);
    noFill();
    beginShape();
    for (PVector city : citiesOrdered) {
      vertex(city.x, city.y);
    }
    endShape();
  }
  fill(0,0,100);
  noStroke();
  text("Min Distance : "+ recordDistance,40,height-40);
}

PVector[] swap(PVector[] array, int a, int b) {
  PVector temp = array[a];
  array[a] = array[b];
  array[b] = temp;
  return array;
}

float calDistance(PVector[] array) {
  float sum = 0;
  for (int i = 0; i < cities.length-1; i++) {
    PVector cityA = cities[i];
    PVector cityB = cities[i+1];
    float dist = PVector.dist(cityA,cityB);
    sum += dist;
  }
  return sum;
}

void keyPressed(){
    init();
}

void mousePressed(){
    init();
}

コード（35.2）

int[] vals = {0,1,2,3,4,5,6,7,8,9};
void setup(){
    size(600,600);
}

void draw(){
  // step 1 
  int largestI = -1;
  for(int i = 0; i < vals.length - 1; i++){
    if(vals[i] < vals[i + 1]){
      largestI = i;
    }
  }
  if(largestI == -1){
    noLoop();
  }
  
  // step 2
  int largestJ = -1;
  for(int j = 0; j < vals.length; j++){
    if(vals[largestI] < vals[j]){
      largestJ = j;
    } 
  }
  
  // step3
  swap(vals, largestI, largestJ);
  
  // step4
  int n = 0;
  int[] endArray = new int[vals.length - largestI -1];
  for(int i = largestI+1; i < vals.length; i++){
    endArray[n] = vals[i];
    n++;
  }
  reverse(endArray);
  int m= 0;
  for(int i = largestI+1; i < vals.length; i++){
    vals[i] = endArray[m];
    m++;
  }
    
  background(0);
  textSize(64);
  String s = "";
  for(int i = 0; i < vals.length; i++){
    s += vals[i];
  }
  fill(255);
  text(s, 20, height/2);
}

void swap(int[] array, int i, int j){
  int temp = array[i];
  array[i] = array[j];
  array[j] = temp;
}

リファレンス