問題および回答ページはこちら

下記はネタバレになります。

 

 

 

 

 

全体解説

今回の問題は、どちらも探索問題と呼ばれる問題になります。探索問題は問題ごとに様々な解き方があるため、一般的に論じることは難しいのですが、今回はその中でも深さ優先探索 (Depth First Search, DFS)で解答可能な問題を作成しました。LL Diverらしく、深く潜りながら探索していただきたいとの思いでした(もちろん、他の解法もあります)。
なおこのページでは、簡易的に C/C++/Java に似た記法を使って解答例を記述しています。

問題1

概要解説

巡回セールスマン問題 (Travelling Salesperson Problem, TSP) と呼ばれる問題です。この問題はチューリング困難問題(「多項式時間での解法はほぼ無い」と思われている問題) であり、全探索が有効に働く問題です。
ここでは2種類の解法を紹介しますが、どちらの場合も10! (10の階乗, 3628800)程度の計算量がかかります。一般的に、10!程度であれば大抵の言語・大抵のパソコンで1秒以内で答えを得ることが出来ます。

解法1

単純に、深さ優先探索を行います。
深さ優先探索の場合、アルゴリズムは大体次のようになります。

int calculateMin(
    Node currentNode, // 現在の都市
    Set notVisitedNode, // まだ訪れてない都市
    int pathLength) { // スタート地点から
                      // 現在の都市までの距離
  int minLength = MAX_INTEGER;
  for (Node nextNode : notVisitedNode) {
     // 次にnextNodeを選択したと仮定して、
     // その際の最短距離を求める
    int length = calculateMin(
        nextNode,
        // すでにnextNodeには付いているので、
        // notVisitedNodeからは取り除いて
        // もう一度訪れないようにする
        notVisitedNode - nextNode,
        // スタート地点から
        // nextNodeまでの距離を計算する。
        pathLength + distance(currentNode, nextNode));
    if (length < minLength) {
      minLength = length;
    }
  }
  return minLength;
}

calculateMin(0, {1,2,3,4,5,6,7,8,9}, 0);

解法2

permutationを使える言語の場合、もう少し簡単に書くことができます。

// 最初は順番に訪れる
int[] order = [1,2,3,4,5,6,7,8,9];
int minLength = MAX_INTEGER;
do {
  // 一番最初は必ず0から始める
  int[] fullOrder = [0] + order;
  int length = 0;
  for (int i = 0; i < fullOrder.size() - 2; i++) {
    length += distance(fullOrder[i], fullOrder[i+1];
  }
  if (length < minLength) {
    minLength = length;
  }
} while (hasNext(initialOrder))

答え

答えは、PALINDROME (回文)となります。
なお、その場合の距離は1991となりますが、これは回文数 (数字を後ろから見ても同じ値)であり、さらにこれを16進数表記にした場合も7C7 (0x7C7 == 1991)という回文数となります。

問題2

概要解説

探索問題として有名なn-Queen問題を少し変え、Queenの代わりにKingを配置する問題としました。n-Queen問題の場合は回転を同一視するなどの難しさがありますが、この問題ではもっとシンプルにしています。

解法1

全探索解法です。

int counter = 0;
int count(
  // すでに置かれた場所
  Set kings,
  // 置こうとする場所
  Cell putCell) {
  // さらにその次のcellを計算する
  nextCell = calculateNext(putCell);
  // putCellに置けるかどうかチェック
  if (canPut(kings, putCell)) {
    // putCellにおける場合は、とりあえず置いた場合を計算
    if (nextCell == null) {
      counter++;
    } else {
      count(kings + putCell, nextCell);
    }
  }
  // putCellに置かない場合も計算
  if (nextCell == null) {
    counter++;
  } else {
    count(kings, nextCell);
  }
}
count(kings, Cell(0, 0));

解法2

より計算量を減らす方法です。n-Queen問題と異なり、n-Kingの場合にはm行目のおき方はm+2行目に全く影響を与えないため、動的計画法を使うことが出来ます。

(擬似コードについては後日追加します)

答え

答えは9720になります。