Классификация переборных алгоритмов

Во многих прикладных задачах требуется найти оптимальное решение среди очень большого конечного числа вариантов. Иногда удается построить это решение сразу, но в большинстве случаев единственный способ его отыскать состоит в переборе ВСЕХ возможных вариантов и сравнении их между собой [12, c.17-19].

В переборе различают общие и частные решения задач. К общим задачам относятся те задачи, которые ищут все переборные решения задачи то, как частное решение находит решение, которое встретится первым.

Поэтому так важно для нас научиться строить алгоритмы ПЕРЕБОРА различных комбинаторных объектов - последовательностей, перестановок, подмножеств и т.д.

Схема перебора всегда будет одинакова:

· во-первых, надо установить ПОРЯДОК на элементах, подлежащих перечислению (в частности, определить, какой из них будет первым, а какой последним);

· во-вторых, научиться переходить от произвольного элемента к HЕПОСРЕДСТВЕHHО СЛЕДУЮЩЕМУ за ним (т.е. для заданного элемента x1 строить такой элемент x2, что x1 Наиболее естественным способом упорядочения составных объектов является лексикографический порядок, принятый в любом словаре (сначала сравниваются первые буквы слов, потом вторые и т.д.).

При переборе важным методом является рекурсия. Рекурсия «позволяет очень компактно (без использования циклов) программировать вычисление функций, заданных рекуррентно» [10, c.7], например факториала.

Оказывается, рекурсивные процедуры являются удобным способом порождения многих комбинаторных объектов что запись многих алгоритмов значительно упростится благодаря использованию рекурсии.

Можно перечислить несколько переборных алгоритмов:

· Перебор с возвратом;

· Перестановки;

· Последовательности;

На примерах можно составить блок – схему для каждого случая:

Перестановки:

Просматривается массив на совпадение со всеми ключами поиска. Если не будет совпадения хотя бы одним ключом, то решения нет (рис. 1).

Рис. 1. Блок-схема переборного алгоритма
Последовательности:

Последовательно просматривается массив до совпадения с ключом поиска.

Частное решение: найдено одно решение или сообщение “Решений нет”.

Общее решение: найти все решения или сообщение “Решений нет” (рис. 2).

Рис. 2. Поиск общего и частного решений
Глава 2 Разработка программы решения задачи о расстановки ферзей на шахматной доске

Дата добавления: 2015-11-26