На нашем сайте вы можете читать онлайн «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина». Эта электронная книга доступна бесплатно и представляет собой целую полную версию без сокращений. Кроме того, доступна возможность слушать аудиокнигу, скачать её через торрент в формате fb2 или ознакомиться с кратким содержанием. Жанр книги — Знания и навыки, Компьютерная литература, Книги о компьютерах. Кроме того, ниже доступно описание произведения, предисловие и отзывы читателей. Регулярные обновления библиотеки и улучшения функционала делают наше сообщество идеальным местом для любителей книг.
Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина
0 баллов
0 мнений
0 чтений
Автор
Дата выхода
09 декабря 2020
Краткое содержание книги Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина, аннотация автора и описание
Прежде чем читать книгу целиком, ознакомьтесь с предисловием, аннотацией, описанием или кратким содержанием к произведению Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина. Предисловие указано в том виде, в котором его написал автор (Геннадий Степанов) в своем труде. Если нужная информация отсутствует, оставьте комментарий, и мы постараемся найти её для вас. Обратите внимание: Читатели могут делиться своими отзывами и обсуждениями, что поможет вам глубже понять книгу. Не забудьте и вы оставить свое впечатие о книге в комментариях внизу страницы.
Описание книги
В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач. В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP-задач. Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения как приближённых, так и оптимальных решений NP-задач без зацикливания.
Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина читать онлайн полную книгу - весь текст целиком бесплатно
Перед вами текст книги, разбитый на страницы для удобства чтения. Благодаря системе сохранения последней прочитанной страницы, вы можете бесплатно читать онлайн книгу Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина без необходимости искать место, на котором остановились. А еще, у нас можно настроить шрифт и фон для комфортного чтения. Наслаждайтесь любимыми книгами в любое время и в любом месте.
Текст книги
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.wikipedia.org/wiki/%D0%98%D0%BD%D1%84%D0%BE%D1%80%D0%BC%D0%B0%D1%82%D0%B8%D0%BA%D0%B0) в области теории графов (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%A2%D0%B5%D0%BE%D1%80%D0%B8%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D0%B8_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D0%B9) для доказательства NP-полноты более сложных задач.
Вершинное покрытие для неориентированного графа G = (V,E) – это множество его вершин S, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из S.
Размером (size) вершинного покрытия называется число входящих в него вершин.
Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия (https://ru.
NP-полнота задачи о вершинном покрытии.
Поскольку задача о вершинном покрытии является 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), то, в настоящее время считается, что неизвестны алгоритмы для её решения за полиномиальное время.
Однако существуют алгоритмы, дающие«приближённое» решение этой задачи за полиномиальное время.
С их помощью можно найти, например, вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.
Безпереборный метод (русский метод) решения задачи о вершинном покрытии графа.
Мной предлагается следующий способ решения задачи о вершинном покрытии:
Этап1.
Выберем интервал изменения числа угадывания (N уг) для данной конкретной задачи.
Он изменяется от 1 до определённого, предварительно, для этой задачи значения (N макс).
Процесс изменения можно осуществлять, например, путём прибавления 1 к значению N уг.
Это не является принципиально важным.
Этап2.
Осуществим сортировку вершин графа, в соответствии с числом входов в вершину графа рёбер графа.
Этап3.
Мнения
Еще нет комментариев о книге Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина, и ваше мнение может быть первым и самым ценным! Расскажите о своих впечатлениях, поделитесь мыслями и отзывами. Ваш отзыв поможет другим читателям сделать правильный выбор. Не стесняйтесь делиться своим мнением!
Другие книги автора
Понравилась эта книга? Познакомьтесь с другими произведениями автора Геннадий Степанов! В этом разделе мы собрали для вас другие книги, написанные вашим любимым писателем.
Похожие книги
