В посте С# реализация расширенного алгоритма Эвклида я опубликовала метод, производящий вычисления ...
Понадобилась мне самописная реализация алгоритма шифрования RSA (шифрование с открытым ключом, когда ...
Понадобилась мне самописная реализация алгоритма шифрования RSA (шифрование с открытым ключом, когда для зашифровки и расшифровки используются разные ключи). В этом алгоритме один из ключей вычисляется как обратный к а, например, по модулю b. Для вычисления такого обратного числа применяется расширенный алгоритм Эвклида, суть которого описывается выражением: x * a + y * b = d, где d - НОД [...]
Понадобилась мне самописная реализация алгоритма шифрования RSA (шифрование с открытым ключом, когда ...
Бродил я по хабрахабру и наткнулся на статью Алгоритм Дейкстры. Поиск ...
Предисловие
Бродил я по хабрахабру и наткнулся на статью Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе, и вспомнил как в студенческие годы писал прогу на С++ для этого алгоритма. Решил поделится одной интересной темой — решением задачи коммивояжера (TSP), алгоритмом муравьиной колонии (ACS) и реализацией этого алгоритма при помощи
Google Maps.
Пол года назад у меня была задача написать сервис для поиска оптимального пути с использованием Google Maps Api и я использовал
задачу коммивояжера с
алгоритмом муравьиной колонии. Описание задачи коммивояжера найдёте можете найти в Википедии.
Приведу и опишу сам алгоритм и в конце ссылка где я выложил демо-версию реализации алгоритма.
Алгоритм
Общая
задача коммивояжера (traveling salesmen problem, TSP состоит в следующем: используя заданную систему транспортных соединений (дорог и т.п.) между пунктами (городами, фирмами и т.п.) в конкретной зоне обслуживания, посетить все пункты в такой последовательности, чтобы пройденный путь был минимальным.
Читать дальше →
На данный момент не известно полиномиальных по времени алгоритмов точного ...
Введение.
На данный момент не известно полиномиальных по времени алгоритмов точного решения NP-трудных задач. Более того, специалисты по теории сложности склоняются к варианту, что таких алгоритмов не существует. Однако, NP-трудные задачи часто встречаются в жизни. Одним из способов борьбы с NP-трудными задачами на практике является применение приближенных алгоритмов.
Рассмотрим лучший известный приближенный алгоритм решения
задачи о вершинном покрытии.
Читать дальше →
