Материал: Программирование на языке С#

Рассмотрим сам алгоритм:

. Увеличивается количество активных потоков.

. В локальный стек вершин помещается текущая вершина.

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

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

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

3.5 Пример работы алгоритма

Рассмотрим небольшой пример. Пусть необходимо найти путь из вершины A в вершину H. При двух разрешённых пересадках оптимальный путь (представленный на верхнем рисунке) состоит из четырёх рёбер и имеет вес равный 13. При трёх разрешённых пересадках оптимальный путь (представленный на нижнем рисунке) состоит из одиннадцати рёбер и имеет вес равный 11. Подобный результат обеспечивают все разработанные алгоритмы.

Заключение

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

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

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

В качестве среды разработки был выбран пакет Visual Studio 2008. Реализация велась с использованием языка программирования высокого уровня C#. Для хранения транспортной сети использовались принципы сериализации объектов и формат XML. Были выявлены отличительные особенности и положительные стороны данной среды программирования.

На основе разработанного модифицированного алгоритма и модели внутреннего представления данных был создан программный комплекс, обладающий следующими возможностями:

. Создание, модификация, загрузка, сохранение транспортной сети.

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

. Задание условий поиска и критериев оптимальности поиска маршрута.

. Осуществление поиска маршрутов с учётом заданных ограничений.

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

Список используемых источников и литературы

1. Задачи по программированию. / С.А. Абрамов, Г.Г. Гнездилова, Е.Н. Капустина, М.И. Селюн. - Москва: Наука, 1988. - 234 с.

. Вентцель, С.Е. Исследование операций: задачи, принципы, методология. / С.Е. Вентцель. - Москва. : Наука, 1980. - 304 с.

. Вирт, Н. Алгоритмы и структуры данных. / Н. Вирт. - Москва: Мир, 1989. - 340 с.

. Демидович, Е.М. Основы алгоритмизации и программирования. Язык СИ. / Е.М. Демидович. - Мосвка: "Бестпринт" 2003. - 403 с.

. Дейтл, Х. C#. / Х. Дейтл. - Санкт Петербург. : БХВ-Петербург, 2006.- 542 с.

. Лекции по теории графов. / В.А. Емеличев, О.И. Мельников, В.И. Сарванов, Р.И. Тышкевич. - Москва: Наука, 1990. - 674 с.

. Кормен, М.Т. Часть VI. Алгоритмы для работы с графами // Алгоритмы: построение и анализ. - Москва: "Вильямс", 2006. - 345 с.

. Кнут, Д.Э. Искусство программирования, том 3. Сортировка и поиск, 2-е изд. / Д.Э. Кнут. - Москва.: ООО "И.Д. Вильямс", 2007. - 832с.

. Культин, Н.Б. Microsoft Visual C# в задачах и примерах. / Н.Б. Культин. - Санкт Петербург: БХВ-Петербург, 2009. - 289 с.

. Лахатин, А.С. Языки программирования. Учеб. пособие. / А.С. Лахатин, Л.Ю. Искакова. - Екатеринбург, 1998. - 548 с.: ил.

. Левитин, А.В. Алгоритмы: введение в разработку и анализ. / А.В. Левитин. - Москва : "Вильямс", 2006. - 430 с.

. Меньшиков, Ф. Олимпиадные задачи по программированию. / Ф. Меньшиков. - Санкт Петербург. : "Питер", 2006. - 386 с.

. Мудров, В.И. Задача о коммивояжере. / В.И. Мудров. - Москва: "Знание", 1969. - 254 с.

Муртаф, Б. Современное линейное программирование. / Б. Муртаф. - Москва: Мир, 1984. - 630 с.

. C# 2005 и платформа .NET 3.0 для профессионалов. / К. Нейгл, Б. Ивьен, Д. Глинн и др. - Москва: ООО "И.Д. Вильямс", 2008. - 765 с.

. Оре, О. Теория графов. / О. Оре. - Москва: Наука, 1968. - 380 с.

. Павловская, Т.А. C#. Программирование на языке высокого уровня. / Т.А. Павловская. - Санкт Петербург: "Питер", 2007. - 544 с.

. Поляков, А. Программирование на языке Си. / А. Поляков. - Москва: Наука,. 2012. - 460 с.

. Сербин, Д.В. Основы логистики. / Д.В. Сербин. - Таганрог: ТРТУ, 2004. - 420 с.

. Сток, Р.Д. Стратегическое управление логистикой. / Р.Д. Сток. - Москва: Инфра-М, 2005. - 512 с.

. Стивен, С. Олимпиадные задачи по программированию. / С. Стивен, М.А. Скиена. - Москва: ИД Кудиц-образ, 2005. - 340 с.

. Стэкер, М.А. Разработка клиентских Windows-приложений на платформе Microsoft .NET Framework. / М.А. Стэкер, С.Д. Стэйн, Т. Нортроп. - Санкт Петербург: "Питер", 2008. - 580 с.

. Таха, Х.А. Введение в исследование операций. / Х.А. Таха. - Москва: "Вильямс", 2007. - 374 с.

. Уилсон, Р. Введение в теорию графов. Пер с англ. / Р. Уилсон. - Москва: Мир, 1977. - 286 с.

. Уэйт, М. Язык С. Руководство для начинающих. / М. Уэйт, С. Прага, Д. Мартин. - Москва: Мир, 1995. - 521с.: ил.

. Харари, Ф. Теория графов / Ф.Харари. - Москва: Мир, 1973. - 420 с.

. Богатырев, А. Язык программирования С [Электронный ресурс] / А. Богатырев.- электр. дан. - Режим доступа: http://www.refby.com. - Загл. с экрана.

. программное Обеспечение и Интернет ресурсы: http://lib.mexmat.ru/

Приложение

Функция отрисовки транспортной сети

public void Draw(bool showInvisible, bool showDeleted) {

//отрисовать граф

//перо для отрисовкиdcPen = new Pen(Color.Black, 1); //кисть для отрисовки

Brush dcBrush = new SolidBrush(Color.White);

//если необходимо изменить размер компонента перед отрисовкой

if (this.pb.Width != this.width || this.pb.Height != this.height) {.pb.Width = this.width; this.pb.Height = this.height;.pb.Image = new Bitmap(this.width, this.height); this.dc = Graphics.FromImage(this.pb.Image);

}

//отрисовка ведѐтся в высоком качестве.SmoothingMode = System.Drawing.Drawing2D.SmoothingMode.HighQuality; dc.TextRenderingHint = System.Drawing.Text.TextRenderingHint.SingleBitPerPixel;

//заливаем всю картинку белым цветом this.dc.FillRectangle(dcBrush, 0, 0, this.width, this.height);

//перед тем как отрисовывать вершины, нужно отрисовать рѐбра for (int i = 0; i < aEdge.Count; i++)

{

//отрисовываем только видимые и не помеченные как удалѐнные рѐбра

if ((aEdge[i].Visible == true || (aEdge[i].Visible == false && showInvisible == true)) && (aEdge[i].Deleted == false || (aEdge[i].Deleted == true && showDeleted == true)))

{x1 = aVertex[aEdge[i].srcVertex].X; int y1 = aVertex[aEdge[i].srcVertex].Y; int x2 = aVertex[aEdge[i].destVertex].X; int y2 = aVertex[aEdge[i].destVertex].Y; int xm = (x1 + x2) / 2;

int ym = (y1 + y2) / 2;

//цвет исходящий от первой вершины dcPen.Width = 4;

dcPen.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color; dc.DrawLine(dcPen, x1, y1, xm, ym);.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color; dc.DrawLine(dcPen, x2, y2, xm, ym);.Width = 2;.Color = aEdge[i].Color; dc.DrawLine(dcPen, x1, y1, x2, y2);

((SolidBrush)dcBrush).Color = aEdge[i].Color;suffix = ""; string prefix = "";(aEdge[i].Enabled == false) suffix += "Ч"; if (aEdge[i].Visible == false) suffix += "°"; if (aEdge[i].Deleted == true) suffix += "†";(aEdge[i].IsPartOfPath == true) {

//suffix += " ="; //prefix = "= ";

((SolidBrush)dcBrush).Color = Color.FromArgb(200, 200, 200); }(aEdge[i].Selected == true) {

dcPen.Width = 2;

//рисуем кружочек за который можно таскать ребро

dc.FillEllipse(dcBrush, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color; dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dot; dcPen.DashOffset = 0;.DrawEllipse(dcPen, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color; dcPen.DashOffset = 1;.DrawEllipse(dcPen, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid;

//надпись на ребре int x = xm;

int y = ym;textSize = TextRenderer.MeasureText(prefix + aEdge[i].Weight.ToString() + suffix, textFontBold);-= textSize.Width / 2; y -= textSize.Height / 2;textRect = new Rectangle(x, y, textSize.Width, textSize.Height);.DrawText(this.dc, prefix + aEdge[i].Weight.ToString() + suffix, textFontBold, textRect, Color.Black);

} else {.Width = 1;

//рисуем кружочек за который можно таскать ребро dc.FillEllipse(dcBrush, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);.Color = aGraph[aVertex[aEdge[i].srcVertex].iGraph].Color; dcPen.DashStyle = System.Drawing.Drawing2D.DashStyle.Dot; dcPen.DashOffset = 0;.DrawEllipse(dcPen, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);.Color = aGraph[aVertex[aEdge[i].destVertex].iGraph].Color; dcPen.DashOffset = 1;.DrawEllipse(dcPen, xm - rSize, ym - rSize, 2 * rSize, 2 * rSize);.DashStyle = System.Drawing.Drawing2D.DashStyle.Solid;

//надпись на ребре int x = xm;

int y = ym;textSize = TextRenderer.MeasureText(prefix + aEdge[i].Weight.ToString() + suffix, textFontNormal);-= textSize.Width / 2; y -= textSize.Height / 2;textRect = new Rectangle(x, y, textSize.Width, textSize.Height);.DrawText(this.dc, prefix + aEdge[i].Weight.ToString() + suffix, textFontNormal, textRect, Color.Black);

} }

}

//теперь необходимо отрисовать вершины for (int i = 0; i < aVertex.Count; i++) {

//отрисовываем только видимые и не помеченные как удалѐнные вершины

if ((aVertex[i].Visible == true || (aVertex[i].Visible == false && showInvisible == true))

&& (aVertex[i].Deleted == false || (aVertex[i].Deleted == true && showDeleted == true)))

{

//цвет границы.Color = aGraph[aVertex[i].iGraph].Color; //цвет заполнения

((SolidBrush)dcBrush).Color = aVertex[i].Color;suffix = "";(aVertex[i].Enabled == false) suffix += "Ч"; if (aVertex[i].Visible == false) suffix += "°"; if (aVertex[i].Deleted == true) suffix += "†";(aVertex[i].IsStart == true) suffix += " ""; if (aVertex[i].IsFinish == true) suffix += " "";(aVertex[i].IsPartOfPath == true) {

((SolidBrush)dcBrush).Color = Color.FromArgb(200, 200, 200); }(aVertex[i].Selected == true) {.Width = 2;

* dSize);

* dSize););

//рисуем квадратик за который можно таскать вершину

dc.FillRectangle(dcBrush, aVertex[i].X - dSize, aVertex[i].Y - dSize, 2 * dSize,.DrawRectangle(dcPen, aVertex[i].X - dSize, aVertex[i].Y - dSize, 2 * dSize, 2

//надпись на вершине int x = aVertex[i].X; int y = aVertex[i].Y;textSize = TextRenderer.MeasureText(aVertex[i].Title + suffix,-= textSize.Width / 2; y -= textSize.Height / 2;textRect = new Rectangle(x, y, textSize.Width, textSize.Height); dc.FillRectangle(dcBrush, textRect);.DrawRectangle(dcPen, textRect);.DrawText(this.dc, aVertex[i].Title + suffix, textFontBold, textRect, Color.Black);

} else {.Width = 1;

* dSize);

* dSize);

//рисуем квадратик за который можно таскать вершину

dc.FillRectangle(dcBrush, aVertex[i].X - dSize, aVertex[i].Y - dSize, 2 * dSize,.DrawRectangle(dcPen, aVertex[i].X - dSize, aVertex[i].Y - dSize, 2 * dSize, 2

//надпись на вершине int x = aVertex[i].X; int y = aVertex[i].Y;textSize = TextRenderer.MeasureText(aVertex[i].Title + suffix, textFontNormal);-= textSize.Width / 2; y -= textSize.Height / 2;textRect = new Rectangle(x, y, textSize.Width, textSize.Height); dc.FillRectangle(dcBrush, textRect);.DrawRectangle(dcPen, textRect);.DrawText(this.dc, aVertex[i].Title + suffix, textFontNormal, textRect, Color.Black);

} }

}

//обновляем картинку т.к. перерисовали this.pb.Refresh();

}

Свойство, реализующее признак видимости графа

new public bool Visible {{base.Visible; }{.Visible = value;

//наследовать свойство видимости всем принадлежащим графу вершинам for (int i = 0; i < this.iVertex.Count; i++)

{.aVertex[this.iVertex[i]].Visible = value; }

} }

Свойство, реализующее признак видимости вершины

new public bool Visible {

get {base.Visible; }{.Visible = value;

//наследовать свойство видимости смежным рѐбрам for (int i = 0; i < this.iEdge.Count; i++)

{.aEdge[this.iEdge[i]].Visible = value; }

} }

Свойство базового класса, реализующее свойство видимости

public bool Visible {{this.visible; }

set {.visible = value; }

}

Функции для сохранения/загрузки транспортной сети

private void menuItemСохранить_Click(object sender, EventArgs e) {(saveFileDialogTN.ShowDialog() == DialogResult.OK) {

//экземпляр xmlSer класса XmlSerializer нужен для сериализацииxmlSer = new XmlSerializer(typeof(TransportNetworkSerialization)); //имя файла в который будет сохраняться результат сериализации

//string fileName = System.Environment.CurrentDirectory + "\\tst.xml"; string fileName = saveFileDialogTN.FileName;

//поток fileStream для создания XML-файла

FileStream fileStream = new FileStream(fileName, FileMode.Create);tns = new TransportNetworkSerialization(); tn.PreSerialize(tns);

//сериализация xmlSer.Serialize(fileStream, tns); //закрываем поток fileStream.Close();

} }void menuItemЗагрузить_Click(object sender, EventArgs e) {(openFileDialogTN.ShowDialog() == DialogResult.OK) {

//экземпляр xmlSer класса XmlSerializer нужен для десериализацииxmlSer = new XmlSerializer(typeof(TransportNetworkSerialization)); //имя файла из которого будет осуществляться десериализации

//string fileName = System.Environment.CurrentDirectory + "\\tst.xml"; string fileName = openFileDialogTN.FileName;

//поток fileStream для чтения XML-файла

FileStream fileStream = new FileStream(fileName, FileMode.Open);tns = new TransportNetworkSerialization();

//десериализация= (TransportNetworkSerialization)xmlSer.Deserialize(fileStream); //закрываем поток

fileStream.Close();

//теперь нужно развернуть транспортную сеть

//нужно очистить все списки tn.aEdge.Clear(); tn.aVertex.Clear(); tn.aGraph.Clear();

//и визуальные списки тоже необходимо очистить comboBoxEdge.Items.Clear(); comboBoxVertex.Items.Clear(); comboBoxGraph.Items.Clear();

//и поля ввода тоже необходимо очистить textBoxGraphTitle.Text = ""; textBoxGraphDescription.Text = ""; checkBoxGraphDeleted.Checked = false; checkBoxGraphEnabled.Checked = true; checkBoxGraphVisible.Checked = true; panelGraph.BackColor = Color.Black;

textBoxVertexTitle.Text = ""; textBoxVertexDescription.Text = ""; checkBoxVertexDeleted.Checked = false; checkBoxVertexEnabled.Checked = true; checkBoxVertexVisible.Checked = true; panelVertex.BackColor = Color.White;.Text = ""; textBoxEdgeDescription.Text = ""; checkBoxEdgeDeleted.Checked = false; checkBoxEdgeEnabled.Checked = true; checkBoxEdgeVisible.Checked = true; panelEdge.BackColor = Color.White; numericUpDownEdge.Value = 0;

//а теперь в списки нужно добавлять значения

//сначала будем добавлять графы(int i = 0; i < tns.aGraph.Length; i++) {_Click(sender, e); textBoxGraphTitle.Text = tns.aGraph[i].title;.Text = tns.aGraph[i].description; checkBoxGraphDeleted.Checked = tns.aGraph[i].deleted; checkBoxGraphEnabled.Checked = tns.aGraph[i].enabled; checkBoxGraphVisible.Checked = tns.aGraph[i].visible;.BackColor = Color.FromArgb(tns.aGraph[i].colorR, tns.aGraph[i].colorG, tns.aGraph[i].colorB);.aGraph[i].Color = panelGraph.BackColor; }

//теперь необходимо добавить вершины

for (int i = 0; i < tns.aVertex.Length; i++) {.SelectedIndex = tns.aVertex[i].iGraph; buttonVertexAdd_Click(sender, e); textBoxVertexTitle.Text = tns.aVertex[i].title;.Text = tns.aVertex[i].description; checkBoxVertexDeleted.Checked = tns.aVertex[i].deleted; checkBoxVertexEnabled.Checked = tns.aVertex[i].enabled; checkBoxVertexVisible.Checked = tns.aVertex[i].visible;.BackColor = Color.FromArgb(tns.aVertex[i].colorR, tns.aVertex[i].colorG, tns.aVertex[i].colorB);.aVertex[i].Color = panelVertex.BackColor; tn.aVertex[i].X = tns.aVertex[i].x; tn.aVertex[i].Y = tns.aVertex[i].y;

}

//и, наконец необходимо добавить рѐбра(int i = 0; i < tns.aEdge.Length; i++) {

if (tn.AddEdge(tns.aEdge[i].srcvertex, tns.aEdge[i].destvertex) == true) {

//его имя записываем в список comboBoxEdge.Items.Add(tn.aEdge[tn.aEdge.Count - 1].Title); //и оно становится текущим.SelectedIndex = tn.aEdge.Count - 1; }.Text = tns.aEdge[i].title; textBoxEdgeDescription.Text = tns.aEdge[i].description; checkBoxEdgeDeleted.Checked = tns.aEdge[i].deleted; checkBoxEdgeEnabled.Checked = tns.aEdge[i].enabled; checkBoxEdgeVisible.Checked = tns.aEdge[i].visible;.BackColor = Color.FromArgb(tns.aEdge[i].colorR, tns.aEdge[i].colorG, tns.aEdge[i].colorB);.aEdge[i].Color = panelEdge.BackColor; numericUpDownEdge.Value = tns.aEdge[i].weight;