Главная      Лекции     Лекции (разные) - часть 9

 

поиск по сайту           правообладателям

 

 

 

 

 

 

 

 

 

содержание   ..  263  264  265   ..

 

 

работа по дисциплине «Технологии программирования» на тему: «Фибоначчиевы кучи»

работа по дисциплине «Технологии программирования» на тему: «Фибоначчиевы кучи»

Оглавление


Процедура

Двоичные кучи
(в худшем случае)

Биномиальные кучи
(в худшем случае)

Фибоначчиевы кучи
(учётная стоимость)

Создание

Q

Q

Q

Вставка

Q

O(log n)

Q

Найти мин.

Q

O(log n)

Q

Удалить мин.

Q

Q

O(log n)

Слить

Q

O(log n)

Q

Уменьшить ключ

Q

Q

Q

Удалить

Q

Q

O(log n)



Приложение

Приложение 1. Листинг программы «Алгоритм Дейкстры».

{************************************************************}

{ }

{ Алгоритм Дейкстры }

{ Copyright (c) 2008 ТГИМЭУиП }

{ Факультет управления/ 461 группа }

{ }

{ Разработчик: Долганова Анастасия }

{ Модифицирован: май 2008 }

{ }

{************************************************************}

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, jpeg, ExtCtrls;

const

MAX = 200; // максимальная длина пути между двумя вершинами

CHCOUNT = 6; // количество частей

type

TForm1 = class(TForm)

StringGrid1: TStringGrid;

Label1: TLabel;

Memo1: TMemo;

Button4: TButton;

Button6: TButton;

ListBox1: TListBox;

Label2: TLabel;

Button1: TButton;

procedure Button4Click(Sender: TObject);

procedure Button6Click(Sender: TObject);

procedure FormCreate(Sender: TObject);

procedure Button1Click(Sender: TObject);

private

// матрица весов (расстояний между частями)

Weights: array [0..CHCOUNT-1, 0..CHCOUNT-1] of integer;

// индекс части- пункта отправления

first: integer;

procedure GetWeightsMatrix;

procedure FirstCountStep;

procedure GoCount;

procedure StraightWay;

public

{ Public declarations }

end;

var

Form1: TForm1;

implementation

{$R *.dfm}

const CH: array [1..6] of string[3]=

('1-я', '2-я', '3-я',

'4-я', '5-я', '6-я');

procedure TForm1.Button4Click(Sender: TObject); // задает пути между частями случайным образом

var

i, j: integer;

flag: real; // существует ли путь

begin

for i:=1 to StringGrid1.ColCount-1 do

begin

for j:=i+1 to StringGrid1.RowCount-1 do

begin

flag := random;

if (flag>0.5) then

begin

StringGrid1.Cells[i,j] := IntToStr(random(MAX));

StringGrid1.Cells[j,i] := StringGrid1.Cells[i,j];// заполняет таблицу

end;

end;

end;

end;

procedure TForm1.GetWeightsMatrix; // заполняет матрицу весов Weights

var

i, j: integer;

begin

for i:=0 to CHCount-1 do

Weights[i,i] := 0; // из части в саму себя

for i:=0 to CHCount-1 do

for j:=0 to CHCount-1 do

begin

if (StringGrid1.Cells[i + 1, j + 1] <> '') then

Weights[i, j] := StrToInt(StringGrid1.Cells[i + 1, j + 1]);

end;

end;

procedure TForm1.Button6Click(Sender: TObject); вызывает процедуры для расчета

begin

Memo1.Lines.Clear;

GetWeightsMatrix; // перебрасывает пути в матрицу

FirstCountStep; // инициализирует расчет

StraightWay; // находит прямые пути

GoCount; // запускает расчет

end;

procedure TForm1.FirstCountStep; // проверяет, выбрана ли часть из списка

var

i: integer;

begin

first := -1;

for i := 0 to CHCount - 1 do

begin

if ListBox1.Selected[i] then

first := i;

end;

if (first = -1) then

begin

MessageDlg(‘ ошибка: вы не выбрали начальную часть в списке!',

mtError, [mbOK], 0);

exit;

end;

end;

procedure TForm1.FormCreate(Sender: TObject); // задает части в интерфейсе

var

i: integer;

begin

StringGrid1.Cells[0, 0] := 'часть';

for i:= 1 to CHCount do

begin

StringGrid1.Cells[0, i] := CH[i];

StringGrid1.Cells[i, 0] := CH[i];

Listbox1.Items[i-1] := CH[i];

end;

end;

procedure TForm1.StraightWay; // находит прямой путь

var

i : integer;

begin

for i:= 1 to CHCount do

begin

if Weights[first, i] <> 0 then

Memo1.lines.Add(ListBox1.Items[first] + '=>' + INtToStr(i) +

'(' + IntToStr(Weights[first, i]) + ')');

end;

end;

procedure TForm1.GoCount; // находит непрямой путь между частями и вычисляет расстояние

var

i, n, j : integer;

str : string;

begin

n := 0;

str := (ListBox1.Items[first] + '=>');

for j := 1 to CHCount do

begin

for i := 0 to CHCount-1 do

begin

if Weights[first, i] <> 0 then

if Weights[i, j] <> 0 then

begin

n := n + Weights[first, i] + Weights[i, j];

str := str + ListBox1.items[i] + '=>';

end;

end;

Memo1.Lines.Add(str + IntToStr(j) + '('+IntToStr(n)+')')

end;

end;

procedure TForm1.Button1Click(Sender: TObject); // очистка

var

i, j: integer;

begin

for i:= 1 to CHCount do

for j:= 1 to CHCount do

begin

StringGrid1.Cells[j, i] := '';

end;

Memo1.Lines.Clear;

end;

end.

Приложение 2. Тестовое задание.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями — пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» — длина пути. Рядом с каждой вершиной красным обозначена метка — длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг . Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Ее соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 — вершина 2, потому что длина пути до нее минимальна. Длина пути в нее через вершину 1 равна кратчайшему расстоянию до вершины 1 + длина ребра, идущего из 1 в 2, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины — 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и обсуждению не подлежит (то, что это действительно так, впервые доказал Дейкстра ). Вычеркнем её из графа , чтобы отметить, что эта вершина посещена.

Второй шаг' . Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю. Соседями вершины 2 являются 1, 3, 4.

Первый (по порядку) сосед вершины 2 — вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 — вершина 4. Если идти в неё через 2-ю, то длина такого пути будет = кратчайшее расстояние до 2 + расстояние между вершинами 2 и 4 = 7 + 15 = 22. Поскольку 22< , устанавливаем метку вершины 4 равной 22.

Ещё один сосед вершины 2 — вершина 3. Если идти в неё через 2, то длина такого пути будет = 7 + 10 = 17. Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем ее как посещенную.

Третий шаг . Повторяем шаг алгоритма, выбрав вершину 3. После ее «обработки» получим такие результаты:

Дальнейшие шаги . Повторяем шаг алгоритма для оставшихся вершин (Это будут по порядку 6, 4 и 5).

Завершение выполнения алгоритма . Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й — 9, до 4-й — 20, до 5-й — 20, до 6-й — 11.

 

 

 

 

 

 

 

содержание   ..  263  264  265   ..

 

Операция

Binary

Leftist

Top-Down Skew

Bottom-Up Skew

Pairing

Binomial

Fibonacci

2-3

Soft

MAKE

O(1)

O(1)

O(1)

O(1)

O(1)

O(1)

O(1)

O(1)

O(1)

INSERT

O(log N)

O(log N)

O(log N)

O(1)

O(log N) *

O(log N)

O(1)

O(1)

O(log 1/E)

MELD

O(N)

O(log N)

O(log N)

O(1)

O(log N) *

O(log N)

O(1)

O(log N)

O(1)

FIND-MIN

O(1)

O(1)

O(1)

O(1)

O(1)

O(log N)

O(1)

O(1)

O(1)

DELETE-MIN

O(log N)

O(log N)

O(log N)

O(log N)

O(log N)

O(log N)

O(log N)

O(log N)

O(1)

DECREASE

O(log N)

O(log N)

O(log N)

O(log N)

O(log N) *

O(log N)

O(1)

O(1)

O(1)

DELETE

O(log N)

O(log N)

O(log N)

O(log N)

O(log N)

O(log N)

O(log N)

O(log N)

O(1)