работа по дисциплине «Технологии программирования» на тему: «Фибоначчиевы кучи» (стр. 3 из 4)
Описание
В простейшей реализации для хранения чисел d [ i ] можно использовать массив чисел, а для хранения принадлежности элемента множеству U — массив булевских переменных.
В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (большим максимального возможного пути в графе ). Массив флагов заполняется нулями. Затем запускается основной цикл.
На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0
. Последний случай возможен, если и только если граф G несвязан.В разработанном приложении рассчитывается расстояние от выбранной пожарной части до всех остальных города N.
Технические задачи:
1. разработка интерфейса;
2. реализация ввода данных пользователем;
3. осуществление расчета расстояния;
4. организация вывода результата пользователю.
2.2. Интерфейс
Интерфейс программы включает в себя окно ввода информации, окно выбора начальной пожарной части, три кнопки: очистка, ввод данных и расчет, а так же окно вывода результата.
При нажатии на кнопку «задать расстояние случайно» задается расстояние при помощи random из максимально допустимой длины MAXPATH.
При нажатии кнопки «рассчитать расстояние» программа сначала заполняет матрицу весов, т.е. перебрасывает пути из таблицы в матрицу, потом проверяет, выбрана ли начальная часть. Если начало выбрано пользователем, то вначале находится прямой путь между частями, а после не прямой. И в конце работы программы выводится результат- все допустимые пути.
Если начальная пожарная часть не выбрана, то об этом сообщается пользователю в виде сообщения.
При нажатии «очистить» происходит очистка таблицы значений и окна вывода результатов.
2.3. Кодовая реализация
Первая процедура TForm1.Button4Click задает пути случайным образом.
Листинг 1:
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));// значения из const
StringGrid1.Cells[j,i] := StringGrid1.Cells[i,j];// заполняет таблицу
end;
end;
end;
После этого происходит заполнение матрицы весов.
Листинг 2:
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; // Если индекс ячейки не относится к шапке, то происходит заполнение
Далее при нажатии кнопки «Рассчитать» происходит вызов процедуры для расчета, которая состоит из четырех различных процедур.
Листинг 3:
GetWeightsMatrix; // перебрасываем пути в матрицу
FirstCountStep; // инициализируем расчет
StraightWay; // находим прямые пути
GoCount; // запускаем расчет
Процедура TForm1.FirstCountStep проверяет выбрана ли начальная часть, и если нужно, то сообщает об ошибке.
Листинг 4:
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); // то выходит сообщение об ошибке
Процедура TForm1.FormCreate задает части в интетрфейсе.
Листинг 5:
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];
Процедура TForm1.StraightWay находит прямой путь между частями.
Листинг 6:
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]) + ')'); // выводится в компоненте Memo1 путь
Процедура TForm1.GoCount находит непрямой путь между частями.
Листинг 7:
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)+')') // выводится результат
Процедура TForm1.Button1Click производит очистку.
Листинг 8:
for i:= 1 to CHCount do // счетчик
for j:= 1 to CHCount do // счетчик
begin
StringGrid1.Cells[j, i] := ''; // очистка
end;
Memo1.Lines.Clear; // очистка
Заключение
В первой главе данной курсовой работы было рассмотрено понятие фибоначчиевы кучи, их основные свойства и операции над ними.
Фибоначчиева куча является структурой данных для хранения данных позволяющей быстро производить следующие операции: добавление элемента, получение минимального элемента, удаление минимального элемента, уменьшение ключа по ссылке и удаление по ссылке.
Во второй главе был реализован алгоритм Дейкстры на примере задачи о пожарных частях.
Сложность алгоритма Дейкстры зависит от способа нахождения вершины v , а также способа хранения множества непосещенных вершин и способа обновления меток. Обозначим через n количество вершин, а через m — количество ребер в графе G .
- В простейшем случае, когда для поиска вершины с минимальным d [ v ] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть O ( n 2 + m ) . Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе.
- Для разреженных графов (то есть таких,для которых m много меньше n²) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d [ i ], то время извлечения вершины из
станет log n , при том, что время модификации d [ i ] возрастет до log n . Т.к. цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации O ( n log n + m log n )
- Если для хранения непосещенных вершин использовать фибоначчиевы кучи, у которых удаление происходит за O (log n ) , а уменьшение значения за O (1) , то время работы алгоритма составит O ( n log n + m )
Нетрудно показать, что скорость работы алгоритма при использовании фибоначчиевых куч является асимптотически оптимальной и улучшить её нельзя. Так, с одной стороны, задачу сортировки массива из n элементов можно свести к задаче о поиске кратчайших путей на графе из n вершин; с другой стороны, алгоритму требуется просмотреть все ребра графа, хотя бы по одному разу.
Литература
1. Ананий В. Левитин Глава 9. Жадные методы: Алгоритм Дейкстры // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: «Вильямс» , 2006. — С. 189-195. — ISBN 0-201-74395-7
2. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2001.
3. Статьи «Фибоначчиевы кучи» и «Алгоритм Дейкстры» сайта www.wikipedia.org.
4. Э. Рейнгольд, Ю. Нивергельд, Н. Део. Комбинаторные алгоритмы. Теория и практика. Пер. с англ. – М., Мир, 1980.
5. Ульман Д.Д.Алгоритм Дейкстры. – «Intertera», апр. 2007.
Приложение
Приложение 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}