Help us understand the problem. What is going on with this article?

jsでアルゴリズム

クイックソート

ピボットを決めて、そのピボットより、小さい値、大きい値でグループ分けする。それを再帰的に繰り返す。
ピボットの値をどこにするかで計算量が変わってくる。

const quickSort = (arr) => {
  if (arr < 2) {
    return arr;
  }
  const pivot = arr[0];

  const minArr = arr.filter(arr => arr < pivot);
  const maxArr = arr.filter(arr => arr > pivot);

  return [...quickSort(minArr), pivot, ...quickSort(maxArr)];
}

const arr = quickSort([8,41,6,4,2,19]);

console.log(arr);
// [ 2, 4, 6, 8, 19, 41 ]

幅優先探索

キューを使うことで現在の頂点に紐づくノードを確認しきってから(幅優先)、次の頂点に映っていく探索ができる。

const graph = {};

graph['START'] = ['alice', 'bob', 'claire'];
graph['bob'] = ['anuj', 'peggy'];
graph['alice'] = ['peggy'];
graph['claire'] = ['TARGET', 'jonny'];
graph['anuj'] = [];
graph['peggy'] = [];
graph['thom'] = [];
graph['jonny'] = [];

const bfs = () => {
  const queue = graph['START'];

  while (queue.length) {
    const person = queue.shift();

    console.log(person);
    if (person === 'TARGET') {
      console.log('見つけた')
      console.log(person)
      return;
    } else {
      queue.push(...graph[person])
    }
  }

  console.log('見つからなかった。')
  return;
}

bfs();

bfs();
// alice
// bob
// claire
// peggy
// anuj
// peggy
// TARGET
// 見つけた
// TARGET

深さ優先探索

スタックを使うことで、後から追加したノードから確認するようになるので、終端まで探索してから(深さ優先)、次の頂点に進んでいく探索ができる。

const graph = {};

graph['START'] = ['alice', 'bob', 'claire'];
graph['bob'] = ['anuj', 'peggy'];
graph['alice'] = ['peggy'];
graph['claire'] = ['TARGET', 'jonny'];
graph['anuj'] = [];
graph['peggy'] = [];
graph['thom'] = [];
graph['jonny'] = [];

const dfs = () => {
  const queue = graph['START'];

  while (queue.length) {
    const person = queue.pop();

    console.log(person);
    if (person === 'TARGET') {
      console.log('見つけた')
      console.log(person)
      return
    } else {
      queue.push(...graph[person])
    }
  }

  console.log('見つからなかった。')
  return
}

dfs();
// claire
// jonny
// TARGET
// 見つけた
// TARGET

ダイクストラ

最短経路を求める。
iOS の画像 (1).jpg

0) それぞれのノードはスタート地点からのコストを持つ。開始時はスタート地点は0、他のノードはコストが不明なのでInfinity
1) 最もコストが低く、まだ確認していないノードを探す
2) そのノードの隣接ノードを探す。
3) 隣接ノードの現在のコストと、今いる場所から隣接ノードへ辿った場合のコストを比較し少ない方で隣接ノードのコストを更新する。
4) 現在のノードを確認済みにし、次のノードへ移動する。
5) 全てのノードが確認済みになるまで続ける。

ダイクストラは負のコストが存在するグラフの場合、正しく計算できなくなる。負の値が存在する場合はベルマンフォードを使う。

const findLowestCostNode = (nodeList) => {
  const unProcessedNodeList = nodeList.filter(node => !node.processd);

  return unProcessedNodeList.reduce((nodeA, nodeB) => {
    if (nodeA.cost <= nodeB.cost) {
      return nodeA;
    } else {
      return nodeB
    }
  }, {});
}

const findNode = (nodeList, targetNodeName) => {
  return nodeList.find(node => node.name === targetNodeName);
}

const _display = (nodeList, node, routes) => {
  if (node.parents.name === 'start') {
    const startNode = findNode(nodeList, 'start');
    routes.push(startNode);

    console.log(routes.reverse()); 
    return;
  }

  const parentsNode = findNode(nodeList, node.parents.name);

  routes.push(parentsNode);

  _display(nodeList, parentsNode, routes);
}

const displayResult = (nodeList) => {
  const finNode = nodeList.find(node => node.name === 'fin');

  _display(nodeList, finNode, [finNode]);
}

const dijkstra = (nodeList) => {
  // 未処理かつ、コストが一番低いノードを取得
  let node = findLowestCostNode(nodeList);

  while (Object.keys(node).length) { // 未処理のノードがある限り続ける
    const neighbors = graph[node.name];

    Object.keys(neighbors).forEach(nodeName => {
      const newCost = node.cost + neighbors[nodeName]; // 経由した場合のコスト

      const neighborNode = findNode(nodeList, nodeName);
      const currentCost = neighborNode.cost; // 現在登録されているコスト

      if (currentCost > newCost) {
        neighborNode.cost = newCost;
        neighborNode.parents = node;
      }
    });

    node.processd = true;
    node = findLowestCostNode(nodeList);    
  }

  displayResult(nodeList);
}

const graph = {
  start: {
    a: 6,
    b: 2
  },
  a: {
    fin: 1,
  },
  b: {
    a: 3,
    fin: 5
  },
  fin: {} // ゴールには隣接ノードはない
}

class Node {
  constructor({ name, cost }) {
    this.name = name;
    this.cost = cost;
    this.parents = {};
    this.processd = false;
  }
}

const start = new Node({ name: 'start', cost: 0 })
const a = new Node({ name: 'a', cost: Infinity })
const b = new Node({ name: 'b', cost: Infinity })
const fin = new Node({ name: 'fin', cost: Infinity })

dijkstra([start, a, b, fin]);
// [ Node { name: 'start', cost: 0, parents: {}, processd: true },
//   Node {
//     name: 'b',
//     cost: 2,
//     parents: Node { name: 'start', cost: 0, parents: {}, processd: true },
//     processd: true },
//   Node {
//     name: 'a',
//     cost: 5,
//     parents: Node { name: 'b', cost: 2, parents: [Object], processd: true },
//     processd: true },
//   Node {
//     name: 'fin',
//     cost: 6,
//     parents: Node { name: 'a', cost: 5, parents: [Object], processd: true },
//     processd: true } ]

ナップサック問題

決められた縛りの中で価値を最大化する問題。
重み1,価値1500重み4,価値3000重み3,価値2000
の品物がある。重さ4まで耐えれるナップサックに品物を入れていく。価値の最大値はいくつになるか

const MaxWeight = 4;
const Products = [
  {
    weight: 1,
    value: 1500
  },
  {
    weight: 4,
    value: 3000
  },
  {
    weight: 3,
    value: 2000
  },
];

const dpTable = {};

const dp = () => {
  // 「前の最大値」の初期値を用意
  for (let w = 1;  w <= MaxWeight;  w++) {
    if (!dpTable[0]) {
      dpTable[0] = {};
    }
    dpTable[0][w] = 0;
  }

  Products.forEach((product, index) => {
    const productId = index + 1;
    dpTable[productId] = {};

    for (let weight = 1;  weight <= MaxWeight;  weight++) {
      // 前の最大値
      const prevMaxValue = dpTable[productId - 1][weight];
      // 現在の品物の価値(現在の重みより軽ければ加算)
      const curProductValue = (product.weight <= weight) ? product.value : 0;
      // 残りのスペースの価値(現在の重み - 品物の重さ の位置のデータを取ってくる。負の値になった場合は 0 を入れる)
      const maxValOfRemainingSpace = (dpTable[productId - 1][weight - product.weight] || 0);
      // 現在の品物の価値 + 残りのスペースの価値
      const curMaxValue = curProductValue + maxValOfRemainingSpace;

      // 前の最大値 と (現在の品物の価値 + 残りのスペースの価値) を比較し、大きい方がその時の最適解
      dpTable[productId][weight] = Math.max(prevMaxValue, curMaxValue);
    }
  });

  return dpTable;
}

const result = dp();

console.log(result);
// { '0': { '1': 0, '2': 0, '3': 0, '4': 0 },
//   '1': { '1': 1500, '2': 1500, '3': 1500, '4': 1500 },
//   '2': { '1': 1500, '2': 1500, '3': 1500, '4': 3000 },
//   '3': { '1': 1500, '2': 1500, '3': 2000, '4': 3500 } }

最大ヒープ

親より子供の方が値が小さい完全二分木。

こういう感じの二分木を
iOS の画像 (1) (2).jpg

こんな感じに入れ替える
iOS の画像 (2).jpg

配列で二分木を表した時に、親の配列のindexの値を i とするなら、左の子は 2*i 、右の子は 2*i+1 となる。
最大ヒープは真ん中の値(親)が左右の子供より必ず大きくなるので、親、左の子、右の子の中で最大のものを新しい親とする処理を行なっていく。
真ん中が最大値となったら部分木の根を移動して再度同じ処理を行なっていく。最終的に二分木全体の根で処理を行ったら完成。
親、左の子、右の子の中で最小のものを選ぶようにすれば、最小ヒープになる。

// 配列のindexに使っている値は二分木の位置。二分木の位置は1から始まっているので配列のindexを指定する際、常に-1を指定
const _swap = (arr, index, index2) => {
  const tmp = arr[index - 1];

  arr[index - 1] = arr[index2 - 1];
  arr[index2 - 1] = tmp;

  return arr;
}

const maxHeap = (heapSize, arr, cur) => {
  const left = 2 * cur;
  const right = 2 * cur + 1;
  let lergest;

  if (left <= heapSize && arr[left - 1] > arr[cur - 1]) {
    lergest = left;
  } else {
    lergest = cur;
  }

  if (right <= heapSize && arr[right - 1] > arr[lergest - 1]) {
    lergest = right;
  }

  if (lergest != cur) {
    arr = _swap(arr, cur, lergest)

    maxHeap(heapSize, arr, lergest);
  }
}

const arr = [4,1,3,2,16,9,10,14,8,7];
const heapSize = arr.length;

for (cur = heapSize / 2; cur >= 1; cur--) {
  maxHeap(heapSize, arr, cur);
}
console.log(arr);
// [ 16, 14, 10, 8, 7, 9, 3, 2, 4, 1 ]
Why do not you register as a user and use Qiita more conveniently?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away