Исследование алгоритмов поиска с возвращением

исследование алгоритмов поиска с возвращением

1.Анализ индивидуального задания поиск возвращение программный алгоритм

Итак, задача состоит в нахождении такого размещения компонент в ячейках, которое минимизирует общую длину использованного провода. Число ячеек на плате — п. Очевидно, что если число компонент k больше п, то решения не существует, а при k? п, то k компонент всегда можно разместить в п ячейках. Эффективность вычислений при решении задачи зависит от характера расположения ячеек на плате. Если расположение ячеек симметричное, то можно предложить некоторые способы повышения эффективности вычислений, которые связаны с эквивалентностью решений. Чем больше осей симметрии имеет плата, тем больше существует эквивалентных решений и значит тем больше можно сократить время перебора. Эквивалентные решения можно найти и в случае ассиметричной схемы, если имеются компоненты с одинаковым числом соединений с другими компонентами. Пример такого решения рассмотрим на следующем рисунке (компонента обозначена парой чисел (l, m), где l — номер компоненты, а m — порядковый номер некоторого способа соединения компоненты с остальными компонентами):

Рисунок 1. Пример эквивалентного решения для задачи о платах

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

Очевидно, что для решения поставленной задачи можно применить метод поиска с возвращением, а точнее его разновидность метод ветвей и границ.

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

Имеются компоненты, которые нужно расположить в n ячейках на плате. Число соединений между парами компонент задается матрицей C, в которой C (i, j) — число связей между i-й и j-й компонентами. Расстояние между парами мест задается матрицей D, в которой D (k, l) — расстояние между k-й и l-й ячейками. Таким образом, в терминах общей длины использованного провода размещение i-й компоненты в k-й ячейке и j-й компоненты в l-й ячейке стоит C (i, j) D (k, l). В каждой ячейке можно поместить только одну компоненту, и каждая компонента может находиться только в одной ячейке. Найдите размещение компонент в ячейках, минимизирующее общую длину использованного провода.

Как видно из постановки задачи, задание на курсовую работу практически уже формализовано. С математической точки зрения необходимо минимизировать функцию стоимости F = C (i, j) D (k, l), где ij и i, j K (множество K — множество компонент), k l и k, l Y (множество Y — множество ячеек). Эта задача эквивалентна другой задаче: нужно найти такое множество двоек S = {p, q}, p K, q Y', Y' Y, которое минимизирует F= C (i, j) D (k, l), и где двойки (i, k) и (j, l) принадлежат множеству S ((i, k), (j, l) S).

2.1 Структуры данных для представления объектов задачи

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

Решим вопрос о представлении вектора решений. Если m — это число компонент, которые нужно расположить в n ячейках на плате и m< n, то решение можно представить вектором (а₁,…, а _m), в котором а_i — есть двойка чисел (j, l), где j — номер компоненты, а l — номер ячейки, в которой располагается данная компонента. Очевидно, что при заданном числе компонент m все решения имеет одну и ту же длину m. Множества значений элементов вектора решений для i-ой компоненты имеют вид А_k = (i, 1…, r ,… n). Аналогичную структуру имеют и множества кандидатов S_k для решения, за исключением одного отличия: допустим если S₁ = (i, 1…, r ,… n) и если r-ая ячейка, i-ая компонента уже выбраны, то S₂ = (j, 1… n).

2.2 Анализ ограничений и усовершенствований. Аналитические и/или экспериментальные оценки

Будем считать, что матрицы C (i, j) и D (k, l) задаются случайным образом и число способов соединения компонент с остальными компонентами достаточно велико.

Рассмотрим ограничения свойственные данной задаче: в каждой ячейке можно поместить только одну компоненту, и каждая компонента может находиться только в одной ячейке, следовательно, для любых двух элементов вектора решений, которые можно представить двойками чисел (i, k) и (j, l) ij, k l. Так как эффективность вычислений при решении задачи зависит от характера расположения ячеек на плате, то для того, чтобы у нас были возможности для повышения эффективности и быстродействия вычислений, будем считать, что плата симметричная и конкретно имеет ровно одну ось симметрии. При этом ячейка с номером 1 симметрична ячейке с номером n, ячейка с номером 1 симметрична ячейке с номером n-1 и т. д.

Данное ограничение способствует тому, что у нас появляются эквивалентные решения, которые можно исключить для просмотра и тем самым увеличить быстродействие. Эквивалентные решения можно найти и в случае ассиметричной схемы, если имеются компоненты с одинаковым числом соединений с другими компонентами. Пример такого решения уже был рассмотрен в разделе № 2. Рассмотрим данный способ нахождения эквивалентных решений. Пусть s — число способов соединения компонент с остальными компонентами, п — число ячеек на плате, т — число компонент (s достаточно велико по сравнению с т). Так как матрицы C (i, j) и D (k, l) задаются случайным образом, то определим вероятность того, что хотя бы две компоненты из т будут иметь одинаковые способы соединения с остальными компонентами.

p₀ — вероятность того, что не будет ни одного совпадения способов соединения с остальными компонентами.

p₁ — вероятность того, что будет одно совпадение способов соединения с остальными компонентами.

где — вероятность того, что у двух компонент совпадут количества соединений к какому-нибудь третьему компоненту,

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

Так как p₁ = 1 — p₀, то окончательная формула имеет вид .

Даже для простой задачи, где число способов соединения компонент с остальными компонентами s = 5 и число компонент т = 10 такая вероятность примерно равна 0,46, то есть настолько мала, поиск таких эквивалентных решений только понизит быстродействие алгоритма. Следовательно, такие эквивалентные решения при дальнейшей разработке алгоритмов учитываться не будут.

Если не использовать никаких усовершенствований, то дерево поиска для задачи размерностью т=4 и п=4 имеет около 1312 узлов. Использование ограничения, касающегося симметрии платы даёт оценку около 656 узлов.

Таблица 1. Оценки усовершенствований

3.3 Разработка алгоритмов решения задачи (итерационный и рекурсивный варианты)

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

Для применения метода ветвей и границ стоимость должна быть четко определена для частичных решений. Кроме того, для всех частичных решений и для всех расширений должно выполнятся соотношение:

cost? cost (1).

В нашем случае стоимость частичных решений уже определена в задании на курсовую работу: в терминах общей длины использованного провода размещение i-й компоненты в k-й ячейке и j-й компоненты в l-й ячейке стоит C (i, j) D (k, l), где C — матрица числа связей между компонентами, а D — матрица расстояний между ячейками. Если у нас имеется частичное решение ((i₁, j₁), (i₂, j₂),…,(i_m, j_m)), в котором i₁ компонента размещается в j₁ ячейке и т. д., то его стоимость вычисляется по следующему алгоритму:

cost := 0;

for k :=2 to m do

for l:=1 to (k-1) do cost := cost + C (i_k, i_l)*D (j_k, j_l)

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

Алгоритм 1. Итерационный вариант решения задачи

Данный алгоритм очень похож на общий алгоритм метода ветвей и границ, но в нём всё же есть свои отличия, так как он применён для решения конкретной задачи. Например, на первом шаге в множество кандидатов S₁ выбиралось всё множество А₁, в нашем же алгоритме с учётом симметричности платы в множество S₁ выбираются только те элементы А_1, которые не являются симметричными друг к другу, т. е. множество. Это позволит нам не просматривать эквивалентные решения. Другое отличие алгоритма — вектор решения считается искомым решением, если k равно числу компонент. Это связано с тем, что все решения имеют фиксированную длину.

Данный итерационный алгоритм можно преобразовать в рекурсивный; после преобразования он будет выглядеть следующим образом:

Алгоритм 2. Рекурсивный вариант решения задачи

3. Оценка асимптотической временной сложности алгоритма (метод Монте-Карло) Вычисление по методу Монте-Карло можно использовать для оценки эффективности алгоритма поиска с возвращением путём сравнения его с эталоном, полученным для задачи с меньшей размерностью. В данной курсовой работе этот метод будет использован для исследования асимптотической временной сложности решения задачи в зависимости от количества ячеек п на плате.

Алгоритм Монте-Карло для исследования деревьев поиска методом ветвей и границ, который использовался в данной курсовой работе, имеет следующий вид:

Алгоритм 3. Исследование дерева поиска методом Монте-Карло

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

1). Количество компонент не изменяется.

Таблица 2. Исследование решения задачи при постоянном количестве компонент

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

Проведём аналогичное исследование для случая, когда количество компонент изменяется пропорционально количеству ячеек.

Таблица 3. Исследование решения задачи при изменяющемся количестве компонент

Из таблицы 3 видно, что во втором случае, когда количество компонент изменяется пропорционально количеству ячеек, при увеличении размера задачи на единицу, время поиска увеличивается не в полтора раза, как в первом случае, а примерно в 40−50 раз. При размерности задачи 7*7 фактическое время вычислений составляет примерно 6,5 минут, фактическое число исследованных узлов — 48 841 193. Зная это, можно предположить примерное время поиска решения задачи размерностью 8*8: так как количество узлов в дереве поиска найденное методом Монте-Карло для задачи данной размерности составляет 1 558 443 648 узлов, т. е. в 32 раза больше, чем для задачи размерностью 7*7, то ожидаемое время поиска будет больше примерно в столько же раз и составит около 3,5 часов.

4. Программная реализация алгоритмов

4.1 Реализация данных

Для начала определимся с представлением a_k — k-го элемента вектора решения. В пункте 3 (формализация задачи) условились, что а_k есть двойка чисел (j, l), где j — номер компоненты, а l — номер ячейки, в которой располагается данная компонента. Логичнее всего данный элемент представить как запись с двумя полями целочисленного типа, в котором одно поле есть номер компоненты, а другой — номер ячейки, в которую помещается данная компонента:

TElement = record

i, j: byte;

end;

Вектор решения будет представлен соответственно линейным массивом данных записей, а множество кандидатов в решение S_k представим прямоугольным массивом переменных булевского типа. В последнем случае в массиве на пересечении i-ой строки и j-го столбца будет находиться значение TRUE если двойка (i, j) входит в множество кандидатов в решение, и FALSE в противном случае. Множество S_k будет считаться пустым, если на пересечении всех строк и всех столбцов будут находиться значения FALSE.

4.2 Реализация алгоритмов

Программная реализация алгоритма метода ветвей и границ включает реализацию таких важных моментов алгоритма как

1) Проверка множества кандидатов в решение S_k на пустоту

2) Выбор элемента a_k из множества S_k в качестве следующего элемента вектора решения

3) Удаление элемента a_k из множества S_k

4) Определение стоимости частичного решения

5) Определение следующего множества S_k

1. Проверка множества кандидатов в решение S_k на пустоту. Осуществляется следующим образом: в массиве множества кандидатов последовательно проверяется каждый элемент до тех пор, пока не будет найден первый элемент со значением TRUE. Если такой элемент не найден, то множество кандидатов в решение пусто.

2. Выбор элемента a_k из множества S_k в качестве следующего элемента вектора решения. Осуществляется таким же образом, как и пункт 1, но номер строки элемента со значением TRUE записывается в поле i элемента вектора решения, а номер строки в поле j.

3. Удаление элемента a_k из множества S_k: в массиве S_k элемент стоящий на пересечении соответствующей строки столбца принимает значение FALSE.

4. Определение стоимости частичного решения. Пуст, А — переменная типа TElement, параметр k — длина вектора решения, то стоимость частичного решения вычисляется следующей функцией:

functuion SolCost (k: byte):word;

var i, j: byte;

cost: word;

begin

cost := 0;

for i:=2 to k do

for j:=1 to (i-1) do begin

cost := cost + (C[A[i]. j][A[j].j]*D[A[i].i][A[j].i]);

end;

SolCost := cost;

end;

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

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

4.3 Исследование способов программирования. Характеристики программ

Программа полностью написана на Borland Delphi 7.0 и оформлена в виде отдельных модулей предназначенных для решения конкретных задач. Список модулей программы приведён ниже:

Таблица 4. Список модулей программы

Общий размер exe-кода программы — 448 512 байт. Время выполнения подпрограмм измерялось на задаче размером 6 компонент на 6 ячеек.

заключение

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

Таблица 5. Характеристики программной реализации алгоритмов

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

Если предположить, что плата, на которой размещаются ячейки, симметрична, то существуют эквивалентные решения, которые можно исключить из процесса поиска. Аналогичные характеристики программной реализации алгоритма в данном случае выглядят следующим образом: размер исполняемого кода 1137 байт, время выполнения задачи размером 6 компонент на 6 ячеек — 3188 мс.

Цель задания для данной курсовой работы — исследование асимптотической временной сложности решения в зависимости от количества ячеек на плате. Исследование данной асимптотической временной сложности решения проводилось для двух случаев: когда число компонент постоянно и в случае, когда оно изменяется пропорционально числу ячеек. Результаты данных исследований приведены в таблицах 2 и 3. В обоих случаях мы получили экспонентациальную временную сложность — О (с^п), (при этом коэффициент с₁ для первого случая гораздо меньше с₂). Построим графики зависимостей времени решения от размера задачи.

Рисунок 2. Графики зависимостей времени решения от размера задачи

Приложение

В данном приложении приведен текст программы по решению исходной задачи. Программа полностью написана на Borland Delphi 7.0 и оформлена в виде отдельных модулей, предназначенных для решения конкретных задач.

unit KR_mainu;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms, Dialogs, StdCtrls, KR_treeb, ExtCtrls, ComCtrls, XPMan, Spin, KR_data, KR_proc, KR_recurs, KR_Btreeb, KR_near;

type

TForm1 = class (TForm)

Matrix_D: TGroupBox;

Memo1: TMemo;

GroupBox1: TGroupBox;

Memo2: TMemo;

Label1: TLabel;

Label2: TLabel;

GroupBox2: TGroupBox;

Label3: TLabel;

Button2: TButton;

Label4: TLabel;

RadioButton1: TRadioButton;

RadioButton2: TRadioButton;

Button3: TButton;

GroupBox3: TGroupBox;

Button1: TButton;

RichEdit1: TRichEdit;

SpinEdit1: TSpinEdit;

Label8: TLabel;

SpinEdit2: TSpinEdit;

RadioButton3: TRadioButton;

RadioButton4: TRadioButton;

Button4: TButton;

procedure Button2Click (Sender: TObject);

procedure Button3Click (Sender: TObject);

procedure Button1Click (Sender: TObject);

procedure Button4Click (Sender: TObject);

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

procedure TForm1. Button2Click (Sender: TObject);

var int: integer;

begin

int := SpinEdit1. Value;

InitD (int);

int := SpinEdit2. Value;

if (SpinEdit2.Value>SpinEdit1.Value) then begin

SpinEdit2.Value := SpinEdit1. Value;

int := SpinEdit1. Value;

end;

InitC (int);

Button3.Enabled := TRUE;

Memo1.Lines.Text := Cstr;

Memo2.Lines.Text := Dstr;

end;

procedure TForm1. Button3Click (Sender: TObject);

const wait = 'Ждите. Идёт поиск…';

name = '" Электорнные платы" ';

var int: integer;

begin

Form1.Caption := wait;

int := SpinEdit2. Value;

if (Form1.RadioButton1.Checked) then TreeBench (int, SpinEdit1. Value);

if (Form1.RadioButton2.Checked) then NearMethod (int);

if (Form1.RadioButton3.Checked) then BT. InitBackTrack (int, SpinEdit1. Value);

if (Form1.RadioButton4.Checked) then TreeBenchB (int, SpinEdit1. Value);

Form1.Caption := name;

RichEdit1.Text := answer;

end;

procedure TForm1. Button1Click (Sender: TObject);

const mess =

' Данная программа решает следующую задачу:'+^M^J+^M^J+

' Имеются компоненты, которые нужно расположить в n' + ^M^J+

'ячейках на плате. Число соединений между парами компо'+^M^J+

'нент задается матрицей C, в которой C (i, j) — число св'+^M^J+

'язей между i-й и j-й компонентами. Расстояние между па'+^M^J+

'рами мест задается матрицей D, в которой D (k, l) — рас-'+^M^J+

'стояние между k-й и l-й ячейками.' +^M^J+

' Таким образом, в терминах общей длины использован-'+^M^J+

'ного провода раз-мещение i-й компоненты в k-й ячейке и'+^M^J+

'j-й компоненты в l-й ячейке стоит C (i, j) D (k, l).'+^M^J+

' В каждой ячейке можно поместить только одну компон'+^M^J+

'енту, и каждая компонента может находиться только в од'+^M^J+

'ной ячейке. Найти размещение компонент в ячейках, мини'+^M^J+

'мизирующее общую длину использованного провода.';

begin

Application.MessageBox (mess, 'Справка', MB_OKCANCEL) = IDOK;

end;

procedure TForm1. Button4Click (Sender: TObject);

var int, check: integer;

begin

check := SpinEdit2. Value;

case check of

1.5: int := 1000;

6: int := 100;

7: int := 25;

else int := 2;

end;

if (Form1.RadioButton1.Checked) then MonteKarlo (int, SpinEdit2. Value, SpinEdit1. Value);

if (Form1.RadioButton4.Checked) then MonteKarloB (100,SpinEdit2.Value, SpinEdit1. Value);

RichEdit1.Text := answer;

end;

end.

unit KR_data;

interface

const Cmaxsize = 15;

inf = 1 000 000;

type TElement = record {запись для элемента вектора решения}

i, j: byte;

end;

Tsquere = array [1.Cmaxsize, 1. Cmaxsize] of boolean;{тип для множества кандидатов в решение}

TSol = array [1.Cmaxsize] of TElement; {тип вектора решения}

var C, D: array [1.Cmaxsize, 1. Cmaxsize] of integer; {массивы C и D}

Cstr, Dstr: string;

S: array [0.Cmaxsize] of Tsquere; {множество множеств кандидаторв в решение}

bestsol, A: TSol; {вектора текущего и лучшего решений}

answer: string;

implementation

end.

unit KR_proc;

interface

uses SysUtils, Windows, Math, KR_data;

var

cost, lowcost: longword;

procedure initC (N: integer);

procedure initD (N: integer);

procedure SetS;

function SNotZero (k, sizeC, sizeD: byte):boolean;

function SNotZeroB (k, size, sizeD: byte):boolean;

function ElementFromSB (k, size, sizeD: byte):word;

function ElementFromS (k, size, sizeD: byte):word;

function SolCost (k: byte):word;

procedure FindNewS (k, size: byte);

procedure RecordAnswer (size: byte; lowcost: word; time: longint; uzels: longword);

function powerS (k, size, sizeD: integer):integer;

function RandomElementFromS (k, size, sizeD: byte):word;

function MonteKarlo (N, size, sizeD: integer):longword;

function powerSB (k, size, sizeD: integer):integer;

function RandomElementFromSB (k, size, sizeD: byte):word;

function MonteKarloB (N, size, sizeD: integer):longword;

implementation

{Процедура формирования матрицы C}

procedure initC (N: integer);

var i, j: byte;

begin

randomize;

for i:=1 to N do begin

for j:=1 to N do begin

if (i <> j) then begin C[i][j]: =random (50)+1;

C[j][i]:= C[i][j];

end

else begin C[i][j]: = inf; end;

end;

end;

Cstr:='';

for i:=1 to N do begin

Cstr := Cstr + ^M^J;

for j:=1 to N do if (i<>j)then

if (C[i][j]>9)then Cstr := Cstr + inttostr (C[i][j])+' '

else Cstr := Cstr + inttostr (C[i][j])+' '

else Cstr := Cstr + ' - ';

end;

end;

{Процедура формирования матрицы D}

procedure initD (N: integer);

var i, j: byte;

begin

randomize;

for i:=1 to N do begin

for j:=1 to N do begin

if (i <> j) then begin D[i][j]: =random (50)+1;

D[j][i]: = D[i][j];

end

else begin D[i][j]: = inf; end;

end;

end;

for j:=1 to N do

for i:=1 to (N-j+1) do D[i][j]: =D[N-j+1][N-i+1];

Dstr:='';

for i:=1 to N do begin

Dstr := Dstr + ^M^J;

for j:=1 to N do if (i<>j)then

if (D[i][j]>9)then Dstr := Dstr + inttostr (D[i][j])+' '

else Dstr := Dstr + inttostr (D[i][j])+' '

else Dstr := Dstr + ' - ';

end;

end;

{Первоначальная установка множеств решений}

procedure SetS;

var i, j: byte;

begin

for i:=1 to Cmaxsize do

for j:=1 to Cmaxsize do begin

S[1][i][j] := TRUE;

end;

S[0] := S[1];

end;

{Проверка на пустоту множества S}

functuion SNotZero (k, sizeC, sizeD: byte):boolean;

var i, j: byte;

begin

SNotZero := FALSE;

if (k > sizeC) then exit;

for j:=1 to sizeC do

for i:=1 to sizeD do

if (S[k][i][j]) then begin

SNotZero := TRUE;

exit;

end;

end;