работа на тему: Алгоритм Фаулкса и его приложения (стр. 1 из 3)

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

на тему: Алгоритм Фаулкса и его приложения

Семестр № 7

Преподаватель: Александров О. Е.

Студент: Поляков А. Ю.

Гр. ДО ИСТ 43017д

№ зачетной книжки 17321626

Серов 2007

Содержание:

Введение……………………………………………………………….3

Глава 1

«Новый Фреголли»……………………………………………………4

Алгоритм Фаулкса……………………………………………………9

Замечание……………………………………………………………..13

Глава 2

(Гамильтоновы циклы)

Основные понятия и определения …………………….……………15

Условия существования гамильтонова цикла………………….…..16

Задачи связанные с поиском гамильтоновых циклов……………...17

Методы построения гамильтоновых циклов в графе…………..…..21

Алгебраический метод построения гамильтоновых циклов……... 21

Введение

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

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

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

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

«Новый Фреголли»

На днях мы посетили нашего друга Фреголи, хорошо известного в Мексике, и спросили у него, не мог бы он раскрыть , который сделал его замечательным циркачом, неизменно любимым детьми и даже взрослыми. В самом деле, известно, что Фреголи может полностью сменить одежду за рекордное время. «Речь идет не о секрете, - сказал он нам, - а в логическом методе одевания и раздевания, переданном мне моими предками». И как хорошо воспитанный человек он счел возможным добавить: «Несомненно, математика, которая является вашей профессией, позволила бы вам представить себе усилия, которых потребовало от моего прадеда решение подобных задач».

Математика прошлого действительно позволяла подсчитать количество комбинаций, которые нужно использовать для того, чтобы одеться или раздеться по возможности наиболее удобным способом, то математика сегодняшнего дня позволяет определить лучшую (или лучшие) среди этих комбинаций. Предположим для простоты, что, когда наш друг Фреголи собирается сменить одежду, он не снимет белья – ни рубашки, ни кальсон. Тем не менее, что бы предстать в обличье денди, ему все еще остается напялить на себя целую форму, содержащую брюки, жилет, пиджак, галстук, пальто, носки, ботинки, перчатки, а затем взять в руку трость с серебряным набалдашником.

Посмотрим, что он может сделать по крайней мере в восемью первыми предметами; при этом любой согласится с тем, что:

1) взять свою трость он сможет в последнюю очередь,

2) ему остается исследовать самое большее

81=8*7*6*5*4*3*2*1=40320

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

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

Для простоты записи мы обозначим их буквами:

А – брюки, В – жилет, С – пиджак, D – галстук, Е – пальто, F – носки, G – обувь, H – перчатки.

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

В < C

(что можно читать как «В предшествует С»). Зато ему безразлично, надеть ли прежде жилет или галстук, что запишется в виде

В >< D

Наконец, мы считаем почти немыслимым, чтобы он не обулся немедленно после того, как надел носки; отсюда напрашиваются общие обозначения

F /< G

(F непосредственно предшествует G).

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

А < B,D,C; B<C; B><D,F;

C<E; D<C,E,H; F/<G; G<C,H.

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

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

Чтобы справиться с этой задачей, выполним довольно специфическую операцию – умножением матрицы М (матрица 1) на себя, заменяя, однако обычную арифметическую сумму булевой суммой элементов.

Мы не будем останавливаться на обсуждении по поводу булевой суммы, таблицу которой мы приводим ниже и которая была предметом специального исследования.

Таким образом, члены произведения, расположенные в третьей клетке первой строки, является произведением строки А на столбец С и равен одному, если рассматривать булеву сумму элементов.

Мы видим, что полученная матрица, которую мы обозначим через М^[2] , будет содержать только ноли и единицы. Также будет обстоять дело и с М^[4] .

Единицы, обозначенные (1), не входили в М и составляют часть М^[2] .

Из матрицы М^[4] видно, что А является элементом, за которым может следовать (прямо или косвенно) любой другой, но которому ни какой элемент не может предшествовать.

Для вычисления М^[8] нет надобности сохранять столбец и строку А в М^[4] ; мы получаем М ^1[8] , относительно которой легко заметить, что она в точности равна соответствующей части М^[4].

В этих условиях мы должны, согласно алгоритму Фаулкса, прекратить наши операции. Перестановкой строк и столбцов матрицу М^[4] можно представить в форме М^[4]; это означает, что задача порождает пять упорядоченных подграфов.

Это множество обладает одним и только одним гамильтоновым путем, которым является путь FDBFGCEH. Последнее означает, что наш друг Фреголи обладает одним и только одним способом одеться, как денди. Этот способ состоит в том, чтобы одеваться в таком порядке: галстук, жилет, носки, ботинки, пиджак, пальто, перчатки.

Некоторые аналогичные задачи могут привести к нескольким решениям; так, если бы в приведенном примере мы имели D><F, то существовало бы дополнительное решение ABDFGCEH.

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

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

Алгорифм Фаулкса

Рассмотрим шесть операций: A, B, C, D, E, F, между которыми суцществуют следующие соотношения:

А<B B/<C C<D E<D F<D

A<D B<D F<E

A><F B><E

B><F

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

Исследование графа, изображенного на рис. 16.4, показывает, что точка D есть безусловно конечная точка каждого гамильтонова пути (если таковой существует), ибо никакая дуга не имеет эту точку своим началом, тогда как дуга, исходящая из любой другой точки, достигает точки D.