русс | укр

Языки программирования

ПаскальСиАссемблерJavaMatlabPhpHtmlJavaScriptCSSC#DelphiТурбо Пролог

Компьютерные сетиСистемное программное обеспечениеИнформационные технологииПрограммирование

Все о программировании


Linux Unix Алгоритмические языки Аналоговые и гибридные вычислительные устройства Архитектура микроконтроллеров Введение в разработку распределенных информационных систем Введение в численные методы Дискретная математика Информационное обслуживание пользователей Информация и моделирование в управлении производством Компьютерная графика Математическое и компьютерное моделирование Моделирование Нейрокомпьютеры Проектирование программ диагностики компьютерных систем и сетей Проектирование системных программ Системы счисления Теория статистики Теория оптимизации Уроки AutoCAD 3D Уроки базы данных Access Уроки Orcad Цифровые автоматы Шпаргалки по компьютеру Шпаргалки по программированию Экспертные системы Элементы теории информации

Решение NР-полной задачи


Дата добавления: 2013-12-23; просмотров: 1221; Нарушение авторских прав


Для решения новой задачи всегда хочется придумать точный эффективный алгоритм. В книге Гэри и Джонсона приведен список известных -полных задач и может так оказаться, что наша задача есть в этом списке Что делать в этом случае? Или нашей задачи нет в списке, но мы думаем что она могла бы там быть. Доказательство того, что наша задача NP-полна не решает проблемы. С практической точки зрения мы должны изобрести новый алгоритм или использовать старый, даже если задача NP-полна. Если алгоритм полиномиален, но степень полинома больше 3, то этот алгоритм скорее всего, не достаточно эффективен. Дадим несколько советов.

1. Придумать новый алгоритм. Один из лучших примеров такого подхода симплекс-метод линейного программирования. Хотя симплекс-метод не является полиномиальным в худшем случае, он работает. Одной из главных проблем линейного программирования является вопрос: «Почему симплекс-метод работает так хорошо?» В формулировке задачи линейного программирования значения элементов матрицы А и векторов b и с произвольны Вероятно, в реальных задачах А, b, с удовлетворяют некоторым условия делающим симплекс-метод эффективным. '

2. Рассмотреть специальные случаи задачи. Для любой нерешенной задачи полезно сначала рассмотреть специальные или крайние случаи а затем постепенно обобщать результат. Обычно новую задачу сводят к известной, пытаясь, тем не менее, не потерять специфики задачи. Великое множество комбинаторных задач можно свести к задачам целочисленного линейного программирования и решать общими методами. Однако для реальных задач эти общие методы, как правило, приводят к весьма медленным на практике алгоритмам. Общий алгоритм подобен одежд ходового размера: она подойдет всем, но не будет слишком удобна.

3. Эвристический подход. Чтобы сформулировать эвристический подход для решения конкретной задачи, обычно испытывают несколько числовых примеров, на которых тренируют интуицию. Если эвристический алгоритм приводит к успеху только в некоторых случаях, мы должны описать эти случаи.



4. Декомпозиция задачи. Если задача большая и сложная, то ее возможно удастся разложить на несколько подзадач и решать отдельно каждую. После этого необходимо как-то из частных решений составить общее решение исходной задачи. Подход декомпозиции был проиллюстрирован на задаче нахождения кратчайших путей между всеми парами вершин большой сети.

5. Использовать общие методы. Если у нас нет времени, и мы не хотим заниматься настоящими исследованиями, можно использовать общие подходы. Вот некоторые из них:

(1) поиск с возвращением,

(2) динамическое программирование,

(3) методы отсечений Гомори.

Специальные модификации даже таких методов, как поиск с возвращением, могут существенно повысить эффективность алгоритма, например, в игре на дереве. Метод отсечений Гомори предназначен для решения задач целочисленного линейного программирования. В некоторых случаях он хорошо зарекомендовал себя, но при решении многих других задач ведет себя крайне плохо.

Вообще говоря, нет систематического метода для создания новых комбинаторных алгоритмов.

 

 



<== предыдущая лекция | следующая лекция ==>
NP-полные задачи | МЕТОДЫ МАТЕМАТИЧЕСКОГО МОДЕЛИРОВАНИЯ ПРОЦЕССОВ В МАШИНОСТРОЕНИИ


Карта сайта Карта сайта укр


Уроки php mysql Программирование

Онлайн система счисления Калькулятор онлайн обычный Инженерный калькулятор онлайн Замена русских букв на английские для вебмастеров Замена русских букв на английские

Аппаратное и программное обеспечение Графика и компьютерная сфера Интегрированная геоинформационная система Интернет Компьютер Комплектующие компьютера Лекции Методы и средства измерений неэлектрических величин Обслуживание компьютерных и периферийных устройств Операционные системы Параллельное программирование Проектирование электронных средств Периферийные устройства Полезные ресурсы для программистов Программы для программистов Статьи для программистов Cтруктура и организация данных


 


Не нашли то, что искали? Google вам в помощь!

 
 

© life-prog.ru При использовании материалов прямая ссылка на сайт обязательна.

Генерация страницы за: 0.004 сек.