Геннадий Степанов - Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина

Здесь есть возможность читать онлайн «Геннадий Степанов - Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина» — ознакомительный отрывок электронной книги совершенно бесплатно, а после прочтения отрывка купить полную версию. В некоторых случаях можно слушать аудио, скачать через торрент в формате fb2 и присутствует краткое содержание. ISBN: , Жанр: Прочая околокомпьтерная литература, на русском языке. Описание произведения, (предисловие) а так же отзывы посетителей доступны на портале библиотеки ЛибКат.

Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина: краткое содержание, описание и аннотация

Предлагаем к чтению аннотацию, описание, краткое содержание или предисловие (зависит от того, что написал сам автор книги «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина»). Если вы не нашли необходимую информацию о книге — напишите в комментариях, мы постараемся отыскать её.

В этой, предлагаемой мной умному, любознательному и доброжелательно настроенному читателю, книге, описываются некоторые примеры решения труднорешаемых задач.В этих примерах показываются возможные, в общем виде, некоторые приёмы применения Русского метода при решении NP-задач.Таких приёмов (вариантов) применения Русского метода может быть неограниченное множество для получения как приближённых, так и оптимальных решений NP-задач без зацикливания.

Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина — читать онлайн ознакомительный отрывок

Ниже представлен текст книги, разбитый по страницам. Система сохранения места последней прочитанной страницы, позволяет с удобством читать онлайн бесплатно книгу «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина», без необходимости каждый раз заново искать на чём Вы остановились. Поставьте закладку, и сможете в любой момент перейти на страницу, на которой закончили чтение.

Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Часто используется в теории сложности для доказательства NP-полноты более сложных задач.

Вершинное покрытие для неориентированного графа G = (V,E) – это множество его вершин S, такое, что, у каждого ребра графа хотя бы один из концов входит в вершину из S.

Размером (size) вершинного покрытия называется число входящих в него вершин.

Задача о вершинном покрытии состоит в поиске вершинного покрытия наименьшего размера для заданного графа (этот размер называется числом вершинного покрытия графа).

NP-полнота задачи о вершинном покрытии.

Поскольку задача о вершинном покрытии является NP-полной, то, в настоящее время считается, что неизвестны алгоритмы для её решения за полиномиальное время.

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

С их помощью можно найти, например, вершинное покрытие, в котором число вершин не более чем вдвое превосходит минимально возможное.

Безпереборный метод (русский метод) решения задачи о вершинном покрытии графа.

Мной предлагается следующий способ решения задачи о вершинном покрытии:

Этап1.

Выберем интервал изменения числа угадывания (N уг) для данной конкретной задачи. Этот интервал зависит от характеристик этой задачи.

Он изменяется от 1 до определённого, предварительно, для этой задачи значения (N макс).

Процесс изменения можно осуществлять, например, путём прибавления 1 к значению N уг.

Это не является принципиально важным.

Этап2.

Осуществим сортировку вершин графа, в соответствии с числом входов в вершину графа рёбер графа.

Этап3.

Выберем из отсортированного множества вершин графа N уг «лучших» вершин (больше количество входов рёбер графа в вершину), в соответствии с числом входов в вершину графа рёбер графа.

Этап4.

Объединим каждую вершину графа с другой каждой вершиной графа во множества по две вершины.

Определим число входов в вершину графа рёбер графа для данного множества по два, которые запомним для этого множества.

Получим множество подмножест по два.

Определим, получен ли искомый результат или нет.

Если получен, то заканчиваем поиск.

Переход к этапу12.

Иначе переходим к следующему этапу.

Этап5.

Осуществим сортировку подмножеств по два, в соответствии с числом входов в вершину графа рёбер графа.

Этап6.

Выберем из отсортированного множества подмножеств по два графа N уг лучших подмножеств, в соответствии с числом входов в вершину графа для этих подмножеств.

Этап7.

Объединим каждое подмножество по два в подмножества по три или четыре в зависимости от условий задачи.

Так, как осуществляется склейка путей графа русским методом в задаче коммивояжера.

Определим число входов в вершину графа рёбер графа для данного множества вершин по три или четыре, которые запомним для этого подмножества.

Получим множество подмножеств по три или четыре.

Если множество подмножеств по три или по четыре оказывается пустым, то увеличиваем N уг, допустим на 1, и переходим к этапу3.

Определим, получен ли искомый результат или нет.

Если получен, то заканчиваем поиск.

Переход к этапу12.

Иначе переходим к следующему этапу.

Этап8.

Осуществим сортировку подмножеств вершин по три или четыре, в соответствии с числом входов в вершину графа рёбер графа, русского метода.

Этап9.

Выберем из отсортированного множества подмножеств вершин по три или четыре N уг лучших подмножеств, в соответствии с числом входов в вершину графа для этих подмножеств.

Этап10.

Объединим каждое подмножество вершин по три в подмножество вершин по шесть или пять.

Или подмножество вершин по четыре во множества подмножеств по восемь или семь.

В полном соответствии с правилами русского метода, указанными в задаче коммивояжера.

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

Определим, получен ли искомый результат или нет.

Если получен, то заканчиваем поиск.

Переход к этапу12.

Иначе переходим к следующему этапу.

Этап11.

Данную процедуру повторяем, пока число вершин в подмножествах не сравняются с числом вершин графа. Так, как осуществляется эта процедура, примерно, в задаче коммивояжера русским методом.

Читать дальше
Тёмная тема
Сбросить

Интервал:

Закладка:

Сделать

Похожие книги на «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина»

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


Отзывы о книге «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина»

Обсуждение, отзывы о книге «Вычислительные машины и труднорешаемые задачи. Русский метод. Русская машина» и просто собственные мнения читателей. Оставьте ваши комментарии, напишите, что Вы думаете о произведении, его смысле или главных героях. Укажите что конкретно понравилось, а что нет, и почему Вы так считаете.

x