В этой статье я хотел бы представить свой топ-10 алгоритмов, которые могут помочь вам в работе. Бонусом покажу на примерах, как ими пользоваться.
Сам список включает в себя следующие алгоритмы:
QuickSort - алгоритм разделения и покорения, который рекурсивно разбивает массив на более мелкие подмассивы и сортирует их.
MergeSort — алгоритм «разделяй и властвуй», который рекурсивно делит массив пополам, сортирует половинки, а затем объединяет их обратно.
Бинарный поиск - алгоритм поиска, который многократно делит интервал поиска пополам, ища определенное значение в отсортированном массиве.
Поиск в глубину (DFS) — алгоритм обхода графа, который исследует как можно дальше по каждой ветви, прежде чем вернуться назад.
Breadth-first Search (BFS) — алгоритм обхода графа, который исследует все вершины графа или все узлы дерева уровень за уровнем.
Динамическое программирование - метод решения проблем путем разбиения их на более мелкие подпроблемы и хранения решений этих подпроблем, чтобы избежать лишней работы.
Алгоритм Беллмана-Форда — алгоритм кратчайшего пути с одним источником, который также может обнаруживать отрицательные циклы в графе.
Алгоритм Дейкстры — алгоритм кратчайшего пути с одним источником, который работает путем многократного ослабления оценок расстояния между вершинами.
Алгоритм поиска A* - алгоритм поиска, который использует эвристику для направления поиска и обычно используется для поиска пути и решения задач обхода графа.
Knapsack Problem — задача комбинаторной оптимизации, целью которой является максимизация общей стоимости предметов в рюкзаке без превышения его вместимости.
Для примерах реализации я буду использовать Typescript, так как это ЯП с сильной типизацией, но в тоже время достаточно простой для понимания.
Заметка: все вышеперечисленные алгоритмы реализованы с помощью Typescript и могут быть найдены в менеджере пакетов npm.
Реализацию QuickSort, MergeSort, Бинарного поиска, Поиска в глубину (DFS) мы можете найти в первой части.
Сегодня мы разберем Breadth-first Search (BFS), Динамическое программирование и Алгоритм Беллмана-Форда
Пример алгоритма поиска в ширину (BFS), реализованного на TypeScript:
class Graph {
constructor(private numOfVertices: number) {
this.adjList = new Map<number, number[]>();
}
private adjList: Map<number, number[]>;
addVertex(v: number) {
this.adjList.set(v, []);
}
addEdge(v: number, w: number) {
this.adjList.get(v).push(w);
this.adjList.get(w).push(v);
}
bfs(start: number) {
let visited: boolean[] = new Array(this.numOfVertices).fill(false);
let queue: number[] = [];
visited[start] = true;
queue.push(start);
while (queue.length !== 0) {
let vertex = queue.shift();
console.log(vertex);
let neighbours = this.adjList.get(vertex);
for (let i = 0; i < neighbours.length; i++) {
let neighbour = neighbours[i];
if (!visited[neighbour]) {
visited[neighbour] = true;
queue.push(neighbour);
}
}
}
}
}
let g = new Graph(6);
let vertices = [0, 1, 2, 3, 4, 5];
for (let i = 0; i < vertices.length; i++) {
g.addVertex(vertices[i]);
}
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 4);
g.addEdge(3, 5);
console.log('BFS:');
g.bfs(0);
Данная реализация BFS использует представление графа в виде списка смежности, где каждая вершина представлена ключом в карте, а ее значение — массив соседних вершин.
Функция bfs начинает работу с инициализации очереди, добавления в нее начальной вершины и пометки ее как посещенной. Затем с помощью цикла while выполняется итерация по очереди, удаление первой вершины, ее печать, добавление в очередь всех ее непосещенных соседей и пометка их как посещенных.
Стоит отметить, что в данном примере показан обход BFS, начиная с вершины 0, но его можно начать с любой вершины, и для реализации BFS полезно использовать структуру данных очереди.
Кроме того, это базовая реализация BFS, и ее можно использовать для различных целей, таких как поиск кратчайшего пути между двумя вершинами, проверка существования пути между двумя вершинами и решение таких задач, как обход лабиринта и поиск кратчайшего пути в сетке.
Детальное объяснение можете найти тут
Динамическое программирование
Динамическое программирование (ДП) — это метод решения проблем путем разбиения их на более мелкие подпроблемы и хранения решений этих подпроблем, чтобы избежать лишней работы. Этот подход особенно полезен для решения, которые имеют перекрывающиеся подпроблемы, т.е. одни и те же подпроблемы решаются несколько раз.
Существует две основные техники, используемые в динамическом программировании:
— Мемоизация: Этот метод предполагает хранение решений подпроблем в кэше или таблице, чтобы их можно было использовать в дальнейшем. — Табулирование: Эта техника предполагает заполнение таблицы снизу вверх, начиная с наименьших подпроблем и доводя до окончательного решения.
Вот пример использования динамического программирования для решения проблемы последовательности Фибоначчи:
function fibonacci(n: number, memo: number[]): number {
if (n <= 0) return 0;
if (n === 1) return 1;
if (memo[n] !== undefined) return memo[n];
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
return memo[n];
}
let memo = new Array(10);
let result = fibonacci(8, memo);
console.log(result);
В этом примере функция fibonacci принимает на вход число n и массив memo и возвращает n-е число последовательности Фибоначчи, используя мемоизацию. Функция проверяет, хранится ли уже результат для текущего n в массиве memo, если да, то возвращает его, в противном случае вычисляет результат путем сложения результатов (n-1)-го и (n-2)-го чисел Фибоначчи и сохраняет его в массиве memo для дальнейшего использования.
Этот подход имеет временную сложность O(n), поскольку мы вычисляем каждое число последовательности Фибоначчи только один раз и можем повторно использовать результаты предыдущих вычислений.
Динамическое программирование может быть применено ко многим проблемам, таким как проблема кратчайшего пути, проблема ранца и некоторые проблемы оптимизации. Важно понять суть проблемы, прежде чем применять динамическое программирование, так как некоторые проблемы не могут быть решены с помощью этого метода. Также важно понимать временную и пространственную сложность решения.
Алгоритм Беллмана-Форда
Алгоритм Форда-Беллмана позволяет найти кратчайшие пути из одной вершины графа до всех остальных, даже для графов, в которых веса ребер могут быть отрицательными. Тем не менее, в графе не должно быть циклов отрицательного веса, достижимых из начальной вершины, иначе вопрос о кратчайших путях является бессмысленным. При этом алгоритм Форда-Беллмана позволяет определить наличие циклов отрицательного веса, достижимых из начальной вершины.
Алгоритм Форда-Беллмана использует динамическое программирование. Введем функцию динамического программирования:
— F[k][i] — длина кратчайшего пути из начальной вершины до вершины i, содержащего не более k ребер.
Начальные значения зададим для случая k=0. В этом случае F[0][start] = 0, а для всех остальных вершин i F[0][i] = INF, то есть путь, состоящий из нуля ребер существует только от вершины start до вершины start, а до остальных вершин пути из нуля ребер не существует, что будем отмечать значением INF.
Далее будем вычислять значения функции F увеличивая число ребер в пути k, то есть вычислим кратчайшие пути, содержащие не более 1 ребра, кратчайшие пути, содержащие не более 2 ребер и т. д. Если в графе нет циклов отрицательного веса, то кратчайший путь между любыми двумя вершинами содержит не более ребра ( - число вершин в графе), поэтому нужно вычислить значения F[n-1][i], которые и будут длинами кратчайших путей от вершины start до вершины i).
Рассмотрим, как вычисляется значение F[k][i]. Пусть есть кратчайший маршрут из вершины start до вершины i, содержащий не более k ребер. Пусть последнее ребро этого маршрута есть ребро j-i. Тогда путь до вершины j содержит не более k-1 ребра и является кратчайшим путем из всех таких путей, значит, его длина равна F[k-1][j], а длина пути до вершины i равна F[k-1][j] + W[j][i], где W[j][i] есть вес ребра j-i. Дальше необходимо перебрать все вершины j, которые могут выступать в качестве предыдущих, и выбрать минимальное значение F[k-1][j] + W[j][i].
Получаем следующий алгоритм:
/// <reference path="q.module.d.ts" />
import q = module('q');
export interface IList {
forEach(op: () => void ): void;
toArray(): any[];
}
export interface INode {
id: number;
}
interface INodeHash {
[id: number]: INode;
}
interface ResultMap {
[id: number]: DistanceResult;
}
var id = 0;
export class Node implements INode {
private _id = id++;
public get id(): number {
return this._id;
}
}
export class NodeList implements IList {
private _nodes = <INodeHash>{};
private _length = 0;
public getNode(id: string): INode;
public getNode(id: number): INode;
public getNode(id: any): INode {
if (!this._nodes[id]) return null;
else return this._nodes[id];
}
public addNode(node: INode): void {
this._nodes[node.id] = node;
this._length++;
}
public removeNode(node: INode): void {
this._nodes[node.id] = undefined;
this._length--;
}
public forEach(op: (u: INode, list?: NodeList) => void ) {
for (var id in this._nodes) {
op(this._nodes[id], this);
}
}
public toArray(): INode[] {
var nodeArray: INode[] = [];
this.forEach((node) => nodeArray.push(node));
return nodeArray;
}
public get length(): number { return this._length; }
}
export class EdgeMap {
private _edges = {};
public setEdge(one: INode, two: INode, distance: number) {
if (!this._edges[one.id]) this._edges[one.id] = {};
if (!this._edges[two.id]) this._edges[two.id] = {};
this._edges[one.id][two.id] = distance;
this._edges[two.id][one.id] = distance;
}
public getEdge(one: INode, two: INode): number {
if (this._edges[one.id] === undefined || this._edges[one.id][two.id] === undefined) return Number.POSITIVE_INFINITY;
else return this._edges[one.id][two.id];
}
public forEach(op: (u: INode, v: INode, distance: number) => void ) {
var _this = this;
_this.nodes.forEach(function (node1) {
for (var n2id in _this._edges[node1.id]) {
var node2 = _this.nodes.getNode(n2id);
op(node1, node2, _this._edges[node1.id][node2.id]);
}
});
}
constructor(public nodes: NodeList) {
}
}
export class DistanceResult {
public toString() {
return "{via:" + ((this.via) ? this.via.id.toString() : '-') + ",distance:" + this.distance + "}";
}
constructor(public distance: number, public via: INode) {
}
}
export class DistanceResultList {
private _distances = <ResultMap>{};
public forEach(op: (distance: number, id: number, iteration: number) => void ) {
var i = 0;
for (var key in this._distances) {
op(this._distances[key], Number(key), i++);
}
}
public getDistanceFrom(source: INode): DistanceResult {
if (!this._distances[source.id]) return this._distances[source.id] = new DistanceResult(Number.POSITIVE_INFINITY, null);
return this._distances[source.id];
}
public copy() {
var c = new DistanceResultList(this.destination);
var distances = <ResultMap>{};
for (var key in this._distances) {
distances[key] = this._distances[key];
}
c._distances = distances;
return c;
}
public toString() {
var out = "{";
this.forEach(function (distance, id, i) {
if (i > 0) out += ',';
out += id.toString() + ":" + distance.toString();
});
out += "}";
return out;
}
constructor(public destination: INode) {
this._distances[destination.id] = new DistanceResult(0, null);
}
}
export class Graph {
public addNode(node: INode): void {
this.nodes.addNode(node);
}
constructor(public nodes: NodeList, public edges: EdgeMap) {
}
private updatePaths(paths: DistanceResultList) {
this.edges.forEach(function (u, v, w) {
var uPath = paths.getDistanceFrom(u);
var vPath = paths.getDistanceFrom(v);
if (uPath.distance + w < vPath.distance) {
vPath.distance = uPath.distance + w;
vPath.via = u;
}
});
return paths;
}
private negativeCycleExists(paths: DistanceResultList) {
var failure = false;
this.edges.forEach((u, v, w) =>
{
if (paths.getDistanceFrom(u).distance + w < paths.getDistanceFrom(v).distance)
failure = true;
});
return failure;
}
public getShortestPathsAsync(destination: INode): Qpromise {
var _this = this,
d = q.defer();
var shortestPaths = new DistanceResultList(destination);
var request = q(shortestPaths);
for (var i = 0; i < this.nodes.length - 1; i++) {
request = request.then(function (paths: DistanceResultList) {
d.notify(paths.copy());
return _this.updatePaths(paths);
});
}
request.then(function (paths) {
d.notify(paths.copy());
if (_this.negativeCycleExists(paths)) {
d.reject(new Error("negative cycle"));
} else {
d.resolve(paths.copy());
}
});
return d.promise;
}
public getShortestPathsSync(destination: INode): DistanceResultList {
var shortestPaths = new DistanceResultList(destination);
for (var i = 0; i < this.nodes.length - 1; i++) {
this.updatePaths(shortestPaths);
}
if (this.negativeCycleExists(shortestPaths)) throw new Error("negative cycle");
return shortestPaths.copy();
}
}
Реализацию на других языках можно найти тут и тут
Спасибо за ваше внимание. В следующей части реализуем такие алгоритмы как Knapsack Problem и Алгоритм поиска A*.