Возможно ли использовать глубокое обучение для получения приближенных решений задач теории графов, являющихся NP-трудными? Задать вопрос

Задано 4 года, 10 месяцев назад Изменено сегодня Просмотрено 207 раз

Задано 4 года, 10 месяцев назад

6 $\begingroup$ Возможно ли использовать глубокое обучение для получения приближенных решений задач теории графов, являющихся NP-трудными? Если мы возьмем, к примеру, задачу коммивояжера (или задачу о доминирующем множестве). Предположим, у меня есть набор небольших примеров, где я вычисляю оптимальные значения путем проверки всех возможностей, может ли это быть использовано для более крупных задач? В частности, предположим, что я беру большой граф и просто оптимизирую подграфы этого большого графа. Это, возможно, более общий вопрос: Мой опыт работы с глубоким обучением (TensorFlow/Keras) заключается в прогнозировании значений. Как мне получить изоморфизм графов и/или список локальных ходов на графе, чтобы получить лучшее решение? Может ли ML/DL предоставить вам список ходов или локальных изменений для приближения к оптимальному значению, или оно просто возвращает предсказанное оптимальное значение? нейронные сети глубокое обучение tensorflow keras теория графов Поделиться Улучшить вопрос Подписаться отредактировано 10 марта 2021 г. в 23:15 nbro 43,2 тыс. 14 14 золотые значки 121 121 серебряные значки 222 222 бронзовые значки задано 10 марта 2021 г. в 20:58 Jake B. 181 1 1 бронзовая значка $\endgroup$ 1 2 $\begingroup$ Возможно, эта статья решает ваш вопрос: Универсальная аппроксимация функций на графах . $\endgroup$ Vahid Shams – Vahid Shams 2021-03-10 21:13:43 +00:00 Комментировано 10 марта 2021 г. в 21:13 Добавить комментарий | 1 Ответ 1 Отсортировано по: Сбросить до значения по умолчанию Наивысший рейтинг (по умолчанию) Измененная дата (от новых к старым) Созданная дата (от старых к новым) 0 $\begingroup$ Да, действительно возможно использовать глубокое обучение для предоставления приближенных решений задач теории графов, являющихся NP-трудными. Хотя решение NP-трудных задач точно за полиномиальное время обычно считается вычислительно невозможным, методы глубокого обучения можно применять для получения приближенных решений с впечатзательными результатами в некоторых случаях. Вот как это может работать: Кодирование Графов: Модели глубокого обучения могут принимать структуры графов в качестве входных данных. Графовые сверточные сети (GCN), графовые сети внимания (GAT) и графовые нейронные сети (GNN) – это архитектуры, специально разработанные для работы с графовыми данными. Обучение на основе Данных: Модели обучаются на наборе данных, который включает экземпляры графов и их соответствующие оптимальные или близкие к оптимальным решения. Эти решения могут быть получены с помощью эвристик, метаэвристик или других методов оптимизации. Функция потерь: Функция потерь, используемая во время обучения, сравнивает прогнозы модели с известными решениями. Цель состоит в том, чтобы минимизировать разницу между предсказанным и фактическим решением. Приближенное решение: После обучения модель можно использовать для прогнозирования решений для новых экземпляров графов. Эти решения могут не быть оптимальными, но они могут быть очень близки к оптимальным и получены гораздо быстрее, чем традиционные точные методы. Торговля между точностью и эффективностью: Баланс между качеством решения и вычислительной эффективностью можно регулировать путем управления сложностью модели, объемом данных обучения и самим процессом обучения. Перенос обучения: Предварительно обученные модели на одной проблеме могут быть настроены на связанных проблемах. Это перенос обучения может помочь ускорить обучение и улучшить качество решения. Настройка гиперпараметров: Как и в других задачах глубокого обучения, производительность модели может быть чувствительна к гиперпараметрам. Поиск правильной комбинации может существенно повлиять на качество полученных приближенных решений. Оценка: Качество приблизительных решений, сгенерированных моделью, можно оценить по сравнению с известными оптимальными решениями или по сравнению с решениями, полученными другими алгоритмами аппроксимации. Важно отметить, что успех использования глубокого обучения для NP-трудных задач теории графов может сильно варьироваться в зависимости от таких факторов, как сама проблема, наличие подходящих данных для обучения, архитектура нейронной сети и эффективность процесса обучения.