Pull to refresh
  • by relevance
  • by date
  • by rating

Поиск гамильтонова цикла в большом графе (задача коммивояжера).Часть 1

Programming *
Sandbox

1. Постановка задачи


Полный взвешенный граф из 500 вершин задан матрицей смежности.
Необходимо найти гамильтонов цикл в этом графе как можно меньшей суммарной стоимости.
Читать дальше →
Total votes 35: ↑30 and ↓5 +25
Views 70K
Comments 20

Поиск гамильтонова цикла в большом графе (задача коммивояжера).Часть 2

Programming *
В продолжение к моей первой статье решил написать эту, в которой расскажу про более продвинутые алгоритмы поиска гамильтонова цикла в большом полном графе
Читать дальше →
Total votes 16: ↑15 and ↓1 +14
Views 23K
Comments 3

Молчание — золото: доказательство существования Гамильтонова цикла в графе

Cryptography *Algorithms *
Sandbox

Ульям Гамильтон придумал множество игр, одна из них - задача «кругосветного путешествия» по додекаэдру. В ней вершины додекаэдра носили названия известных городов, а рёбрами были  соединяющие их дороги. Игрок должен был совершить путешествие «вокруг света», найдя дорогу, которая проходит через все вершины ровно один раз. 

Заменив такую сложную конструкцию плоским графом, изоморфным исходному, получим задачу, которую далее используем в системе протоколов с нулевым разглашением.

Read more
Total votes 26: ↑23 and ↓3 +20
Views 4.2K
Comments 13

Применение алгоритма Гровера для поиска гамильтоновых циклов в графе

Algorithms *Quantum technologies
Sandbox
Tutorial

Вариант применения квантового алгоритма Гровера для решения задачи поиска гамильтоновых циклов в графе. Вариант является учебным, он не даст так называемого «квантового превосходства», но возможно вдохновит кого-либо на поиск более оптимального решения задачи.

Читать далее
Total votes 21: ↑21 and ↓0 +21
Views 2.5K
Comments 4

Теория графов в криптографии. Обзор основных подходов

Cryptography *Algorithms *
Sandbox

Теория графов - один из основных инструментов математики, который используется для представления множеств и связей между ними. Любая сфера науки, в том числе криптография, включает в себя анализ данных, поэтому модель имеет широкое практическое применение. В данной статье рассматриваются задачи из теории графов, которые лежат в основе современных криптографических протоколов.

Читать далее
Total votes 23: ↑22 and ↓1 +21
Views 3.2K
Comments 1