📄Работа №143629
Тема: Квантовый алгоритм поиска кратчайшего пути на графе
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Математика
Объем:
19 листов
Год:
2023
Просмотров:
57
4600
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
Введение 3
Глава 1. Обзорный раздел по предметной области 4
1.1. Квантовые подходы 4
1.1.1 Hop-based подход 4
1.1.2 Edge-based 6
1.2. TTopt 8
1.3. Постановка задачи 9
Глава 2. Проведенные эксперименты 10
2.1. Малый граф 11
2.2. Граф 3 х 3 12
2.3. Граф 5 х 5 14
2.4. Граф 7 х 7 16
Глава 3. Выводы 18
Список литературы 19
Глава 1. Обзорный раздел по предметной области 4
1.1. Квантовые подходы 4
1.1.1 Hop-based подход 4
1.1.2 Edge-based 6
1.2. TTopt 8
1.3. Постановка задачи 9
Глава 2. Проведенные эксперименты 10
2.1. Малый граф 11
2.2. Граф 3 х 3 12
2.3. Граф 5 х 5 14
2.4. Граф 7 х 7 16
Глава 3. Выводы 18
Список литературы 19
📖 Введение
Проблема нахождения кратчайшего пути является хорошо изученной областью в теории графов. Самый простой для описания вариант этой задачи включает наличие одного источника и одного пункта назначения: необходимо найти путь с минимальной стоимостью между заданными начальной и конечной вершинами в графе с учетом стоимости переходов по ребрам. Эта задача является центральной для широкого круга практических приложений, таких как навигация, планирование маршрутов для автономных транспортных средств и анализ социальных сетей.
Квантовый отжиг — это метод оптимизации системы из N кубитов с использованием зависящего от времени гамильтониана путем постепенного уменьшения квантовых флуктуаций [1]. Гамильтониан представляет собой функцию энергии, которая начинается в полностью запутанном, случайном состоянии и постепенно превращается в гамильтониан, связанный с задачей оптимизации. Медленное развитие квантового энергетического состояния позволяет системе кубитов преодолевать энергетические барьеры и находить глобальный минимум многомерной энергетической функции. Процесс отжига начинается, когда все кубиты находятся в состоянии суперпозиции. Когда процесс завершен, кубиты находятся в основном состоянии искомого гамильтониана задачи и, следовательно, представляют собой глобальный оптимум [2]-[4]. Затем считывается и возвращается вектор решения значений кубитов. Функция энергии обычно выражается в виде модели Изинга или связанной с ней квадратичной неограниченной бинарной оптимизации (QUBO).
В данной работе исследуется QUBO постановка задачи и сравниваются методы квантового отжига и алгоритма Tensor train optimization (TTopt) [5] на данных постановках. TTopt представляет собой метод, используемый для эффективного представления многомерных тензоров (многомерных массивов) со значительно уменьшенным количеством параметров. Этот метод особенно полезен в областях машинного обучения, сжатия данных и численного моделирования, где тензоры с большим количеством измерений и элементов трудно хранить, обрабатывать и вычислять.
Квантовый отжиг — это метод оптимизации системы из N кубитов с использованием зависящего от времени гамильтониана путем постепенного уменьшения квантовых флуктуаций [1]. Гамильтониан представляет собой функцию энергии, которая начинается в полностью запутанном, случайном состоянии и постепенно превращается в гамильтониан, связанный с задачей оптимизации. Медленное развитие квантового энергетического состояния позволяет системе кубитов преодолевать энергетические барьеры и находить глобальный минимум многомерной энергетической функции. Процесс отжига начинается, когда все кубиты находятся в состоянии суперпозиции. Когда процесс завершен, кубиты находятся в основном состоянии искомого гамильтониана задачи и, следовательно, представляют собой глобальный оптимум [2]-[4]. Затем считывается и возвращается вектор решения значений кубитов. Функция энергии обычно выражается в виде модели Изинга или связанной с ней квадратичной неограниченной бинарной оптимизации (QUBO).
В данной работе исследуется QUBO постановка задачи и сравниваются методы квантового отжига и алгоритма Tensor train optimization (TTopt) [5] на данных постановках. TTopt представляет собой метод, используемый для эффективного представления многомерных тензоров (многомерных массивов) со значительно уменьшенным количеством параметров. Этот метод особенно полезен в областях машинного обучения, сжатия данных и численного моделирования, где тензоры с большим количеством измерений и элементов трудно хранить, обрабатывать и вычислять.
✅ Заключение
По результатам работы, реализованы 2 QUBO подхода для решения задачи поиска кратчайшего пути на графе, проведены сравнения работы данных подходов с помощью квантового отжига и алгоритма TTopt
Если говорить об алгоритмах, TTopt алгоритм хорошо работает на малых графах (для edge-based и hop-based подходов), в том числе, TTopt для hop-based на графе 3 х 3 отработал лучше, чем квантовый отжиг на hop-based подходе. На больших графах, TTopt-у необходимо большое число обращений к функции для качественного поиска экстремума, из-за чего метод квантового отжига для больших графов является более предпочтительным.
Если сравнивать подходы, edge-based тоже хорошо подходит только для решения задачи на малых графах. На графе 5 х 5 все методы решения для edge-based подхода ни разу не нашли кратчайшего пути. На больших графах наилучший результат показывает hop-based подход. Единственный недостаток подхода - он использует сильно больше переменных (кубическая зависимость от размера графа), чем edge-based подход (квадратическая зависимость). Более того, hop-based подход с симуляцией квантового отжига не только не работает хуже с увеличением размера графа, он почти с одной и той же вероятностью возвращает кратчайший путь.
Идея инициализировать квантовый отжиг результатом TTopt к особым результатам не привела, квантовый отжиг с инициализацией работает не лучше, чем квантовый отжиг с рандомной инициализацией переменных. Вероятнее всего, это связано с имплеминтацией симуляции квантового отжига на обычном компьютере.
Отдельное внимание стоит обратить на метрику Equal vertices в сводных табличках. Во всех случаях, hop based подход на квантовом отжиге всегда выбирает те вершины, которые лежат на кратчайшем пути. Условие правильности пути в постановке hop-based сильно упирается в допустимость, однако, в исследуемых графах восстановить кратчайший путь можно однозначно по выданным вершинам. Таким образом, для графов, с которыми мы работаем, можно всегда восстановить кратчайший путь, используя hop-based подход.
Если говорить об алгоритмах, TTopt алгоритм хорошо работает на малых графах (для edge-based и hop-based подходов), в том числе, TTopt для hop-based на графе 3 х 3 отработал лучше, чем квантовый отжиг на hop-based подходе. На больших графах, TTopt-у необходимо большое число обращений к функции для качественного поиска экстремума, из-за чего метод квантового отжига для больших графов является более предпочтительным.
Если сравнивать подходы, edge-based тоже хорошо подходит только для решения задачи на малых графах. На графе 5 х 5 все методы решения для edge-based подхода ни разу не нашли кратчайшего пути. На больших графах наилучший результат показывает hop-based подход. Единственный недостаток подхода - он использует сильно больше переменных (кубическая зависимость от размера графа), чем edge-based подход (квадратическая зависимость). Более того, hop-based подход с симуляцией квантового отжига не только не работает хуже с увеличением размера графа, он почти с одной и той же вероятностью возвращает кратчайший путь.
Идея инициализировать квантовый отжиг результатом TTopt к особым результатам не привела, квантовый отжиг с инициализацией работает не лучше, чем квантовый отжиг с рандомной инициализацией переменных. Вероятнее всего, это связано с имплеминтацией симуляции квантового отжига на обычном компьютере.
Отдельное внимание стоит обратить на метрику Equal vertices в сводных табличках. Во всех случаях, hop based подход на квантовом отжиге всегда выбирает те вершины, которые лежат на кратчайшем пути. Условие правильности пути в постановке hop-based сильно упирается в допустимость, однако, в исследуемых графах восстановить кратчайший путь можно однозначно по выданным вершинам. Таким образом, для графов, с которыми мы работаем, можно всегда восстановить кратчайший путь, используя hop-based подход.
ИЛИ
Поиск аналога
📕 Список литературы
🖼 Скриншоты
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.