На нашем сайте вы можете читать онлайн «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина». Эта электронная книга доступна бесплатно и представляет собой целую полную версию без сокращений. Кроме того, доступна возможность слушать аудиокнигу, скачать её через торрент в формате fb2 или ознакомиться с кратким содержанием. Жанр книги — Знания и навыки, Компьютерная литература, Книги о компьютерах. Кроме того, ниже доступно описание произведения, предисловие и отзывы читателей. Регулярные обновления библиотеки и улучшения функционала делают наше сообщество идеальным местом для любителей книг.
Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина
0 баллов
0 мнений
0 чтений
Автор
Дата выхода
09 декабря 2020
Краткое содержание книги Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина, аннотация автора и описание
Прежде чем читать книгу целиком, ознакомьтесь с предисловием, аннотацией, описанием или кратким содержанием к произведению Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина. Предисловие указано в том виде, в котором его написал автор (Геннадий Степанов) в своем труде. Если нужная информация отсутствует, оставьте комментарий, и мы постараемся найти её для вас. Обратите внимание: Читатели могут делиться своими отзывами и обсуждениями, что поможет вам глубже понять книгу. Не забудьте и вы оставить свое впечатие о книге в комментариях внизу страницы.
Описание книги
В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач. В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP-задач. Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения как приближённых, так и оптимальных решений NP-задач без зацикливания.
Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина читать онлайн полную книгу - весь текст целиком бесплатно
Перед вами текст книги, разбитый на страницы для удобства чтения. Благодаря системе сохранения последней прочитанной страницы, вы можете бесплатно читать онлайн книгу Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина без необходимости искать место, на котором остановились. А еще, у нас можно настроить шрифт и фон для комфортного чтения. Наслаждайтесь любимыми книгами в любое время и в любом месте.
Текст книги
Иначе переходим к следующему этапу.
Этап11.
Данную процедуру повторяем, пока число вершин в подмножествах не сравняются с числом вершин графа. Так, как осуществляется эта процедура, примерно, в задаче коммивояжера русским методом.
Определим
N уг = N макс.
Если равен то переходим к этапу 12.
Иначе увеличиваем N уг, допустим, на 1 и переходим к этапу 3.
Этап12.
Анализ полученного результата.
Оценка полученного решения.
Если не удовлетворяет то уточняем N уг и N макс.
Переходим к этапу 2.
Иначе заканчиваем работу.
Задача о доминирующем множестве
В теории графов (https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2) доминирующее множество для графа (https://ru.wikipedia.org/wiki/%D0%93%D1%80%D0%B0%D1%84_(%D0%BC%D0%B0%D1%82%D0%B5%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0))G = (V, E) – это подмножество (https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B4%D0%BC%D0%BD%D0%BE%D0%B6%D0%B5%D1%81%D1%82%D0%B2%D0%BE) D множества вершин V, такое, что любая вершина не из D смежна хотя бы одному элементу из D.
Число доминирования ? (G) – это число вершин в наименьшем доминирующем множестве G.
Задача о доминирующем множестве заключается в проверке, верно ли неравенство ? (G) ? K для заданного графа G и числа K.
Задача является классической NP- полной (https://ru.wikipedia.org/wiki/NP-%D0%BF%D0%BE%D0%BB%D0%BD%D0%B0%D1%8F_%D0%B7%D0%B0%D0%B4%D0%B0%D1%87%D0%B0) проблемой разрешимости (https://ru.
Таким образом, в настоящее время полагают, что не существует эффективного алгоритма (https://ru.wikipedia.org/wiki/%D0%92%D1%80%D0%B5%D0%BC%D0%B5%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%B0) для нахождения наименьшего доминирующего множества для заданного графа.
Точные алгоритмы
Минимальное доминирующее множество графа с nвершинами может быть найдено за время O (2nn) путём просмотра всех подмножеств вершин.
Конец ознакомительного фрагмента.
Текст предоставлен ООО «ЛитРес».
Мнения
Еще нет комментариев о книге Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина, и ваше мнение может быть первым и самым ценным! Расскажите о своих впечатлениях, поделитесь мыслями и отзывами. Ваш отзыв поможет другим читателям сделать правильный выбор. Не стесняйтесь делиться своим мнением!
Другие книги автора
Понравилась эта книга? Познакомьтесь с другими произведениями автора Геннадий Степанов! В этом разделе мы собрали для вас другие книги, написанные вашим любимым писателем.
Похожие книги
