47597 (Механизм бектрекинга)

2016-07-31СтудИзба

Описание файла

Документ из архива "Механизм бектрекинга", который расположен в категории "". Всё это находится в предмете "информатика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "47597"

Текст из документа "47597"

Министерство образования Республики Беларусь

Учреждение образования

"Гомельский государственный университет им.Ф. Скорины"

Математический факультет

Кафедра МПУ

Курсовая работа

Бектрекинг

Исполнитель:

Студентка группы М-41

Кравченко А.Ю.

Научный руководитель:

Канд. физ-мат. наук, доцент

Морозова Т.Е.

Гомель 2005

Содержание

Введение

1. Важное свойство этой задачи

2. Условие задачи

3. Решение полным перебором

3. Бектрекинг

Заключение

Литература


Введение

Существуют задачи для которых нет хорошего метода решения, ответ на них нельзя получить вычислением по формулам. Это как поиск клада без карты. Надо все честно перекопать. Такие задачи называются задачами полного перебора или комбинаторными задачами. Но перебор перебору рознь. Очевидно, что нет смысла копать скальную породу, могут быть и другие разумные ограничения на действия кладоискателя. То есть все возможные ситуации можно разделить на два класса: могущие содержать решение и не могущие содержать решения. Конечно это грубое разбиение, но для нас этого достаточно.

Это очень простая и понятная идея не искать там, где решения нет, но вот в чём проблема, как определить отсутствие клада не копая?

Пример 1.

Дано множество чисел. Составить из них подмножество такое что сумма его элементов будет в точности равна заданному числу А.

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

Кстати давайте оценим количество отсекаемых вариантов. Пусть в исходном множестве M элементов и мы для множества из N - элементов установили, что его элементы в сумме дают больше чем А. Это означает, что M-N элементов могут не участвовать в дальнейших построениях. То есть необходимо отказаться от добавления к нашему плохому подмножеству всех подмножеств построенных на M-N элементах.

Комбинаторика говорит, что из К элементов можно построить 2К множеств, следовательно в нашем случае мы отбрасываем 2M-N вариантов. Даже при не очень больших числах выигрыш получится солидный, потому как экспоненциальная функция обладает очень высокой скоростью роста.

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


1. Важное свойство этой задачи

Всё множество решений этой задачи можно выстроить в виде дерева вариантов. Причём для любого решения (подмножества чисел которое предполагается решением) кроме минимального найдётся решение из которого его можно построить. Пусть например в задаче предложенной выше дано множество из трёх чисел А, В, С. Построим два уровня дерева решений.



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

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

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

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

Среди ветвей ведущих вниз есть не пройденные. Найдём среди них самую левую и пойдём по ней.

Сформулированное правило никак не учитывает события происходящие в вершинах дерева. Между тем вершина от вершины может отличаться и не только положением в дереве. Например, в рассмотренной выше задаче при переходе вниз нарастает сумма, а при переходе вверх та сумма уменьшается. Таким образом, существует класс задач, для которых к дереву комбинаций данных может быть привязана некоторая величина изменяющаяся закономерным образом. Конечно, это не обязательно увеличение. Попробуем описать поведение этой величины в общем виде. Назовём её характеристикой дерева.

Характеристика изменяется внутри некоторого числового интервала.

Это изменение обладает свойством монотонности при движении по дереву вниз.

Существует критическое значение (левая или правая граница интервала), такое, что если характеристика достигает этого критического значения, то дальнейший поиск решения теряет смысл.

С учётом таковой характеристики описанное выше правило обхода дерева немного изменяется и теперь выглядит вот так:

Все ветви уходящие вниз уже пройдены. Тогда необходимо идти по ветви идущей вверх и пометить её как пройденную.

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

Среди ветвей ведущих вниз есть не пройденные и характеристика не достигла критического значения. Найдём среди них самую левую и пойдём по ней.

Обход дерева комбинаций в соответствии с описанным выше правилом и есть метод бектрекинга (BackTracking - обратный ход). Сформулированное правило достаточно общее и под него подходит довольно много задач, но всё-таки это не самая общая формулировка. Думаю, существует много возможностей расширить правило. Например, можно положить, что характеристик несколько и они зависят друг от друга сложным образом. Можно как-то изменить понятие характеристики. Но мы сейчас заниматься этим не будем, Если есть желание попробуйте самостоятельно сформулировать более широкое правило. А мы сейчас рассмотрим пример применения Бектрекинга.

2. Условие задачи

Некто, назовём его покупателем, зашел в магазин имея на руках определённую сумму денег. Его цель купить как можно большее количество товара (на вес) в пределах имеющейся суммы денег. Для каждого товара задана цена и вес. Именовать товары будем для простоты номером.

Предварительные замечания.

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

Из сказанного выше следует, что задачу можно решить обычным полным перебором. Так мы и поступим, а затем в переборное решение добавим механизм бектрекинга.

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

3. Решение полным перебором

Думаю, покупатель будет вести себя следующим образом: возьмёт первый товар (а все товары пронумерованы), затем следующий из оставшихся, затем следующий из оставшихся и т.д. пока не заберет все товары.

Затем он выложит последний и снова попытается увеличить количество товаров, но это не имеет смысла, так как последний товар он только что выложил. Тогда он выложит предпоследний и положит в сумку последний, и у него получится новая совокупность товаров.

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

Теперь то же самое но немного более строго.

Предположим, что у покупателя есть сумка в которой столько же отделов сколько товаров и эти отделы пронумерованы. Каждый раз когда покупатель кладет в сумку новый товар, образуется новая совокупность товаров которая может оказаться искомой. Для того, чтобы это выяснить покупатель после того, как положил товар, взвешивает сумку и выясняет две вещи: может ли он это оплатить и если да, то весит ли сумка больше, нежели запомненный вес. А первоначально сумка не весит ничего.

У покупателя две проблемы:

Большая. Как обеспечить полный перебор всех допустимых совокупностей товаров. Маленькая. Как сделать так, чтобы не было повторов. Ведь может так получится, что он возьмёт одни и те же товары, но в разном порядке. Это конечно не беда, но лишняя работа. Я полагаю, что эти две проблемы решаются следующим образом:

В первом отделе должны побывать все товары. В отделе с номером i должны побывать все товары с номерами на меньшим чем i. Таким образом для каждого отдела с номером i будут получены все допустимые комбинации товаров в остальных отделах с номерами большими чем i и соответственно для отдела с номером 1 будут получены вообще все возможные комбинации.

Наверное стоит привести конкретный пример работ алгоритма. Возьмём следующее множество: 1, 2,3. Для этого множества алгоритм даст следующие комбинации:

(1), (1,2), (1, 2,3), (1, 2,3), (1,3)

(2), (2,3)

(3)

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

program example;

uses crt;

var

b,s: array [1. .100] of word;

a: array [1. .100] of record

cost,ves: word;

end; {Массив магазин}

sum_ves,sum_cost,max,money,level, i,n: integer;

function add_element (d: integer): integer;

var

i: integer;

q: boolean;

begin

repeat

{Ищем пока не найдём}

q: =true;

{проверка есть такой товар или нет}

for i: =1 to level do

if s [i] >=d then q: =false;

if q then add_element: =d

else

begin

d: =d+1;

{проверка, не вышли ли мы за допустимые границы}

if d>n then

begin

add_element: =0;

q: =true;

end;

end;

until q

end;

begin

clrscr;

read (n);

for i: =1 to n do

begin

writeln ('Элемент номер - ', i);

write ('Введите его вес - '); read (a [i]. ves);

write ('Введите его цену - '); read (a [i]. cost);

b [i]: =i;

end;

write ('Сколько денег в наличии - '); read (money);

clrscr;

level: =1; max: =0;

while b [1]

begin

{Поиск элемента не использованного на этом уровне}

b [level]: =add_element (b [level]);

if b [level] >0

then

begin

s [level]: =b [level] ;

level: =level+1;

sum_ves: =0; sum_cost: =0;

for i: =1 to n do

if s [i] <>0 then

begin

sum_ves: =sum_ves+a [s [i]]. ves;

sum_cost: =sum_cost+a [s [i]]. cost;

end;

if (max

end

else

begin

{освобождаем отдел}

s [level]: =0;

b [level]: =level;

level: =level-1;

end;

end;

write ('Наибольший вес - ',max);

end.

3. Бектрекинг

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

{освобождаем отдел}

s [level]: =0;

b [level]: =level;

level: =level-1;

Заметьте, что этой группе операторов абсолютно без разницы причина по которой к неё обращаются. Поэтому добавим в программу ещё одну причину обращения к этой группе. А именно

Если сумма набранного товара больше имеющейся наличности

ТО освобождаем отдел.

Заметим, также, что группа операторов "Освобождаем отдел" повторяется дважды поэтому есть смысл организовать её в виде процедуры. А вот как выглядит теперь программа:

program example;

uses crt;

var

b,s: array [1. .100] of word;

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Да! На равне с готовыми студенческими работами у нас продаются услуги. Цены на услуги видны сразу, то есть Вам нужно только указать параметры и сразу можно оплачивать.
Отзывы студентов
Ставлю 10/10
Все нравится, очень удобный сайт, помогает в учебе. Кроме этого, можно заработать самому, выставляя готовые учебные материалы на продажу здесь. Рейтинги и отзывы на преподавателей очень помогают сориентироваться в начале нового семестра. Спасибо за такую функцию. Ставлю максимальную оценку.
Лучшая платформа для успешной сдачи сессии
Познакомился со СтудИзбой благодаря своему другу, очень нравится интерфейс, количество доступных файлов, цена, в общем, все прекрасно. Даже сам продаю какие-то свои работы.
Студизба ван лав ❤
Очень офигенный сайт для студентов. Много полезных учебных материалов. Пользуюсь студизбой с октября 2021 года. Серьёзных нареканий нет. Хотелось бы, что бы ввели подписочную модель и сделали материалы дешевле 300 рублей в рамках подписки бесплатными.
Отличный сайт
Лично меня всё устраивает - и покупка, и продажа; и цены, и возможность предпросмотра куска файла, и обилие бесплатных файлов (в подборках по авторам, читай, ВУЗам и факультетам). Есть определённые баги, но всё решаемо, да и администраторы реагируют в течение суток.
Маленький отзыв о большом помощнике!
Студизба спасает в те моменты, когда сроки горят, а работ накопилось достаточно. Довольно удобный сайт с простой навигацией и огромным количеством материалов.
Студ. Изба как крупнейший сборник работ для студентов
Тут дофига бывает всего полезного. Печально, что бывают предметы по которым даже одного бесплатного решения нет, но это скорее вопрос к студентам. В остальном всё здорово.
Спасательный островок
Если уже не успеваешь разобраться или застрял на каком-то задание поможет тебе быстро и недорого решить твою проблему.
Всё и так отлично
Всё очень удобно. Особенно круто, что есть система бонусов и можно выводить остатки денег. Очень много качественных бесплатных файлов.
Отзыв о системе "Студизба"
Отличная платформа для распространения работ, востребованных студентами. Хорошо налаженная и качественная работа сайта, огромная база заданий и аудитория.
Отличный помощник
Отличный сайт с кучей полезных файлов, позволяющий найти много методичек / учебников / отзывов о вузах и преподователях.
Отлично помогает студентам в любой момент для решения трудных и незамедлительных задач
Хотелось бы больше конкретной информации о преподавателях. А так в принципе хороший сайт, всегда им пользуюсь и ни разу не было желания прекратить. Хороший сайт для помощи студентам, удобный и приятный интерфейс. Из недостатков можно выделить только отсутствия небольшого количества файлов.
Спасибо за шикарный сайт
Великолепный сайт на котором студент за не большие деньги может найти помощь с дз, проектами курсовыми, лабораторными, а также узнать отзывы на преподавателей и бесплатно скачать пособия.
Популярные преподаватели
Нашёл ошибку?
Или хочешь предложить что-то улучшить на этой странице? Напиши об этом и получи бонус!
Бонус рассчитывается индивидуально в каждом случае и может быть в виде баллов или бесплатной услуги от студизбы.
Предложить исправление
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
5075
Авторов
на СтудИзбе
455
Средний доход
с одного платного файла
Обучение Подробнее