Читайте также:
|
Во многих задачах из различных областей знания ставятся вопросы – задания вида: “Сколько существуют способов … ”, “Есть ли способ … ”, “Существует ли объект … ” и т.п. Ответы на них, как правило, требуют исчерпывающего поиска в некотором множестве М всех возможных вариантов, среди которых находятся решения конкретной задачи. Есть метод организации исчерпывающего поиска: перебор с возвратом.
Решение методом перебора с возвратом строится конструктивно последовательным расширением частичного решения. Если на конкретном шаге такое расширение провести не удается, то происходит возврат к более короткому частичному решению, и попытки его решить продолжаются. Для ускорения перебора с возвратом вычисления всегда стараются организовать так, чтобы была возможность отметать, как можно раньше и как можно больше заведомо неподходящих вариантов М. Перебор с возвратом практически одновременно и независимо был изобретен многими исследователями еще до его формального описания. Он находит применение при решении различных комбинаторных задач в области искусственного интеллекта.
Метод перебора с возвратом, вообще говоря, не являются ни методам, ни алгоритмом решения задач. На нем следует смотреть лишь как на некоторые общие схемы, которые применяются для решения той или иной задачи. Реализация этой схемы в виде конкретных алгоритмов часто требует значительных дополнительных усилий и большой изобретательности, особенно в представлении данных.
Соединение его с рекурсией определяет специфический способ реализации рекурсивных вычислений и заслуживает своего отдельного названия. Этот союз двух эффективных методов формирования ценнейшего сочетания умений, включающих в себя творчество, способность к анализу и синтезу, это можно назвать возвратной рекурсией.
При использовании возвратной рекурсии отпадает необходимость непосредственно организовывать возвраты и отслеживать правильность их существования. Они, как правило, становится встроенной частью механизма выполнения рекурсивных вызовов. Этот факт наглядно демонстрируется на достаточно известных примерах: расстановка ферзей на шахматной доске, обходы шахматной доски конем, латинские квадраты и т.д.
1. Вычислительная схема перебора с возвратом.
Опишем некоторую совокупность R комбинаторных задач, которых заведомо применим алгоритм перебора с возвратом.
Пусть М0, М1, … Мn-1 – n конечных линейно упорядоченных множеств и G – совокупность ограничений (условий), ставящих в соответствие векторам вида v=(v0, v1, … vn-1)T (vj, j=0,1,…,k;k<=n-1), булево значение G(v) принадлежит {истина,ложь}. Векторы v=(v0, v1, … vn-1)T, для которых G(v) = истина, назовем частыми решениями. Пусть далее существует конкретное правило P, в соответствии с которым некоторые из частных решений могут объявляется полными решениями. Тогда возможна постановка следующих поисковых задач:
· Найти все полные решения или установить отсутствие таковых.
· Найти хотя бы одно полное решение или установить его отсутствие.
Общий метод решения приведенных задач состоит в последовательном покомпонентном наращивании вектора v слева направо, начиная с v0, и последующих испытаниях его ограничениями G и правилом P.
В общем случае этот метод приводит к алгоритмам с экспоненциальной временной сложностью, а применяя он в основном к классу так называемых Np-полных задач (задача коммивояжера, задача о рюкзаке и т.д.). Задачи этого класса эквивалентны друг другу в том смысле, что все они разрешены недетерминированными алгоритмами полиномиальной сложности. Далее, для них известно, что либо все они разрешимы, либо ни одна из них не разрешима детерминированными алгоритмами полиномиальной сложности. Иными словами, если хотя бы для одной из этих задач не существует детерминированного алгоритма, имеющего в худшем случае полиномиальную трудоемкость, то такие алгоритмы не должны существовать и для остальных задач этого класса. Наоборот, если хотя бы для одной из этих задач удалось найти детерминированный алгоритм, имеющий в худшем случае полиномиальную трудоемкость, то подобные алгоритмы существовали бы и для остальных задач этого класса и, более того, их можно было бы построить.
Недетерминированный алгоритм исследует все возможности одновременно, как бы копируя себя для реализации вычислений по всем альтернативам одновременно (оператор выбор). Далее все копии работают независимо друг от друга и по мере необходимости продолжают создавать новые копии. Копия, сделавшая неправильный или безрезультатный выбор прекращает свою работу (оператор неуспех). Копия, нашедшая решение задач, объявляет об этом (оператор успех), давая тем самым сигнал другим копиям о прекращении вычислений. Недетерминированные алгоритмы, являясь весьма полезной и продуктивной абстракцией, рекурсивны по сути, ибо при реализации оператора выбора фактически обращаются сами к себе.
Дидактическая ценность метода перебора с возвратом в соединении с рекурсией неоспорима. Во-первых, программы решения многих задач строятся по единой схеме, а во-вторых, они компактны и тем самым просты для понимания и условия соответствующих идей.
Тестирование - определение одной или более характеристики объекта оценки соответствия согласно процедуре (ГОСТ Р ИСО/МЭК 17000). Тестирование обычно проводят с целью получения информации, необходимой для принятия решения о соответствии заданным требованиям. Также испытания проводят с научными целями, с целью мониторинга объекта, с целью установления цены продукта и др.
Тестирование программного обеспечения — процесс исследования программного обеспечения (ПО) с целью получения информации о качестве продукта.
Цель тестирования - это обнаружение максимального количества ошибок, а не всех ошибок в программе. Обнаружение всех ошибок невозможно. Полное и абсолютное тестирование выглядит скорее мечтой, чем реальностью.
План тестирования – это то, что с помощью чего можно указать, что требуется протестировать и как следует выполнять запланированные тесты. Тестовый плат можно применить к определенной итерации проекта. Можно объединить тестовые случаи в единственный набор тестов, используемый по умолчанию, или создать иерархию наборов тестов.
Цель:
1. Выявить синтаксические ошибки
2. Выявить логические ошибки:
Ø Работа меню
Ø Ввод данных
Ø Вывод в случае отсутствующих решения
Ø Вывод в случае нахождения решения
План тестирования
1. Синтаксические ошибки отсутствуют
Рис. 3. Отсутствие синтаксических ошибок
2. Логические ошибки
2.1 Меню
Ø Корректность данных (1,2,3,4)
Вывести на кран:
Рис. 4.
Записать в файл:
Вывести на кран и Записать в файл:
Вернуться в главное меню:
Ø Некорректные данные (0,5)
2.2 корректность вводимых данных
Ø положительное число (N = 5)
Ø слишком большое число (N = 33000)
Ø символ
2.3 нет решения (N = 2, N = 3)
2.4 есть решение (N = 8)
Заключение
Результатами курсовой работы являются:
1. Изучен теоретический материал, заданный в курсовой работе.
2. Рассмотрены рекурсивные методы в программировании, в частности, перебор с возвратом, использующиеся при создании программы
3. Реализована программа решения задачи о расстановки ферзей на шахматной доске средствами Microsoft Visual Studio
4. Выполнено тестирование программного кода на компьютере
5. Устранены выявленные в ходе тестирования неполадки
Рассмотрим работу программы.
Литература
[1] Термин “статический” означает, что содержимое таблицы остается неизменным и главная задача – уменьшить время поиска без учета времени, необходимого для настройки таблицы
[2] Термин “динамический” означает, что таблица часто изменяется путем вставки (а возможно и удаления) элементов.
Дата добавления: 2015-11-26; просмотров: 381 | Нарушение авторских прав