Добавлен: 05.12.2023
Просмотров: 63
Скачиваний: 1
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Обзор и сравнительный анализ алгоритмов решения задачи коммивояжера
Приближенный параллельный алгоритм
Описание приближенного параллельного алгоритма
Анализ преимуществ и недостатков алгоритма по сравнению с другими алгоритмами решения задачи
Описание алгоритмов в коде на языке программирования C#
Описание эксперимента и методики проведения тестирования алгоритмов
Описание процесса распараллеливания алгоритма
Результаты тестирования алгоритмов на различных наборах данных
Приближенный параллельный алгоритм
Описание приближенного параллельного алгоритма
Анализ преимуществ и недостатков алгоритма по сравнению с другими алгоритмами решения задачи
Практическая часть
Описание алгоритмов в коде на языке программирования C#
Полный перебор
Для реализации алгоритма полного перебора в коде на языке C# с графическим интерфейсом можно использовать Windows Forms. Ниже приведен пример реализации алгоритма полного перебора для решения задачи коммивояжера:
namespace TSP
{
public partial class Form1 : Form
{
private int[] bestPath;
private int bestLength = int.MaxValue;
private List
cities = new List
();
private Pen pen = new Pen(Color.Red, 2);
private Random rnd = new Random();
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
int n = cities.Count;
int[] path = Enumerable.Range(0, n).ToArray(); // исходный путь
do
{
int length = GetPathLength(path);
if (length < bestLength) // если найден более короткий путь
{
bestLength = length;
bestPath = (int[])path.Clone();
label1.Text = $"Длина: {bestLength}";
pictureBox1.Invalidate();
Application.DoEvents();
}
} while (NextPermutation(path)); // генерируем следующую перестановку
}
// функция получения длины пути
private int GetPathLength(int[] path)
{
int sum = 0;
for (int i = 1; i < path.Length; i++)
{
Point p1 = cities[path[i - 1]];
Point p2 = cities[path[i]];
sum += (int)Math.Round(Math.Sqrt(Math.Pow(p2.X - p1.X, 2) + Math.Pow(p2.Y - p1.Y, 2)));
}
return sum;
}
// функция генерации следующей перестановки
private bool NextPermutation(int[] a)
{
int i = a.Length - 2;
while (i >= 0 && a[i] >= a[i + 1]) i--;
if (i < 0)
return false;
int j = a.Length - 1;
while (a[j] <= a[i]) j--;
int temp = a[i];
a[i] = a[j];
a[j] = temp;
Array.Reverse(a, i + 1, a.Length - i - 1);
return true;
}
private void pictureBox1_Paint(object sender, PaintEventArgs e)
{
e.Graphics.Clear(Color.White);
foreach (var city in cities)
{
e.Graphics.DrawEllipse(pen, city.X - 5, city.Y - 5, 10, 10);
}
if (bestPath != null)
{
for (int i = 1; i < bestPath.Length; i++)
{
Point p1 = cities[bestPath[i - 1]];
Point p2 = cities[bestPath[i]];
e.Graphics.DrawLine(pen, p1, p2);
}
}
}
private void pictureBox1_MouseClick(object sender, MouseEventArgs e)
{
cities.Add(e.Location);
pictureBox1.Invalidate();
}
}
}.
Метод ближайшего соседа
Ниже представлен пример кода на языке программирования C# с использованием Visual Studio 2019 для реализации алгоритма Метода ближайшего соседа с графическим интерфейсом:
namespace TSP
{
public partial class MainForm : Form
{
private List
points;
private List
public MainForm()
{
InitializeComponent();
points = new List
();
path = new List
}
private void drawPanel_MouseClick(object sender, MouseEventArgs e)
{
points.Add(e.Location);
drawPanel.Refresh();
}
private void drawPanel_Paint(object sender, PaintEventArgs e)
{
// Отрисовка точек
foreach (PointF point in points)
{
e.Graphics.FillEllipse(Brushes.Black, point.X - 5, point.Y - 5, 10, 10);
}
// Отрисовка пути
if (path.Count > 1)
{
Pen pen = new Pen(Color.Red, 2);
for (int i = 0; i < path.Count - 1; i++)
{
e.Graphics.DrawLine(pen, points[path[i]], points[path[i + 1]]);
}
pen.Dispose();
}
}
private void solveButton_Click(object sender, EventArgs e)
{
// Получение матрицы расстояний
int n = points.Count;
double[,] dist = new double[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
dist[i, j] = (i == j) ? 0 : Math.Sqrt(Math.Pow(points[i].X - points[j].X, 2) + Math.Pow(points[i].Y - points[j].Y, 2));
}
}
// Инициализация пути
path.Clear();
path.Add(0);
// Пока есть неиспользованные вершины
while (path.Count < n)
{
int last = path.Last();
double minDist = double.MaxValue;
int next = -1;
// Поиск ближайшей вершины
for (int i = 0; i < n; i++)
{
if (!path.Contains(i))
{
double d = dist[last, i];
if (d < minDist)
{
minDist = d;
next = i;
}
}
}
// Добавление ближайшей вершины в путь
path.Add(next);
}
// Добавление начальной вершины в конец пути
path.Add(0);
drawPanel.Refresh();
}
}
}:
Метод вставки
using System;
using System.Collections.Generic;
using System.Drawing;
using System.Windows.Forms;
namespace TSP
{
public partial class Form1 : Form
{
private int[,] matrix;
private int numberOfCities;
private List
cities;
private List
private int tourLength;
public Form1()
{
InitializeComponent();
cities = new List
();
tour = new List
tourLength = 0;
}
private void Form1_Paint(object sender, PaintEventArgs e)
{
if (cities.Count == 0)
{
return;
}
Graphics g = e.Graphics;
Pen p = new Pen(Color.Black);
foreach (Point city in cities)
{
g.DrawEllipse(p, city.X - 5, city.Y - 5, 10, 10);
}
if (tour.Count > 1)
{
for (int i = 0; i < tour.Count - 1; i++)
{
Point city1 = cities[tour[i]];
Point city2 = cities[tour[i + 1]];
g.DrawLine(p, city1, city2);
}
}
}
private void generateCitiesButton_Click(object sender, EventArgs e)
{
Random r = new Random();
numberOfCities = Convert.ToInt32(numberOfCitiesTextBox.Text);
cities.Clear();
tour.Clear();
tourLength = 0;
for (int i = 0; i < numberOfCities; i++)
{
Point city = new Point(r.Next(20, this.Width - 40), r.Next(20, this.Height - 60));
cities.Add(city);
}
matrix = new int[numberOfCities, numberOfCities];
for (int i = 0; i < numberOfCities; i++)
{
for (int j = 0; j < numberOfCities; j++)
{
if (i == j)
{
matrix[i, j] = 0;
}
else
{
int distance = (int)Math.Sqrt(Math.Pow(cities[i].X - cities[j].X, 2) + Math.Pow(cities[i].Y - cities[j].Y, 2));
matrix[i, j] = distance;
matrix[j, i] = distance;
}
}
}
this.Invalidate();
}
private void solveButton_Click(object sender, EventArgs e)
{
if (cities.Count == 0)
{
return;
}
tour.Clear();
tourLength = 0;
int[] visitedCities = new int[numberOfCities];
for (int i = 0; i < numberOfCities; i++)
{
visitedCities[i] = 0;
}
int currentCity = 0;
visitedCities[currentCity] = 1;
tour.Add(currentCity);
for (int i = 1; i < numberOfCities; i++)
{
int nearestNeighbor = -1;
int shortestDistance = int.MaxValue;
for (int j = 0; j < numberOfCities; j++)
{
if (visitedCities[j] == 0 && matrix[currentCity, j] < shortestDistance)
{
nearestNeighbor = j;
shortestDistance = matrix[currentCity, j];
}
}
private void HeldKarpAlgorithm()
{
int n = graph.GetLength(0);
int[,] dp = new int[n, (1 << n) - 1];
int[,] path = new int[n, (1 << n) - 1];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < (1 << n) - 1; j++)
{
dp[i, j] = int.MaxValue / 2;
path[i, j] = -1;
}
}
dp[0, 1] = 0;
for (int mask = 0; mask < (1 << n) - 1; mask += 2)
{
for (int i = 0; i < n; i++)
{
if ((mask & (1 << i)) == 0)
{
continue;
}
for (int j = 0; j < n; j++)
{
if ((mask & (1 << j)) == 0 || i == j)
{
continue;
}
int prevMask = mask ^ (1 << j);
if (dp[i, mask] > dp[j, prevMask] + graph[i, j])
{
dp[i, mask] = dp[j, prevMask] + graph[i, j];
path[i, mask] = j;
}
}
}
}
int curVertex = 0;
int curMask = (1 << n) - 1;
List
while (curVertex != -1)
{
tour.Add(curVertex);
int nextVertex = path[curVertex, curMask];
curMask ^= (1 << curVertex);
curVertex = nextVertex;
}
double totalDistance = 0;
for (int i = 0; i < tour.Count - 1; i++)
{
totalDistance += graph[tour[i], tour[i + 1]];
}
totalDistance += graph[tour[tour.Count - 1], tour[0]];
Console.WriteLine("Held-Karp algorithm:");
Console.WriteLine("Tour: " + string.Join(" -> ", tour));
Console.WriteLine("Total distance: " + totalDistance);
}
Алгоритм Хелда-Карпа
namespace TSP
{
public partial class Form1 : Form
{
private Point[] cities;
private int[] bestPath;
private double bestDistance = double.PositiveInfinity;
private int generation = 1;
private int populationSize = 100;
private double mutationRate = 0.015;
private List
public Form1()
{
InitializeComponent();
cities = GenerateCities();
population = GeneratePopulation();
bestPath = new int[cities.Length];
for (int i = 0; i < cities.Length; i++)
{
bestPath[i] = i;
}
}
private void DrawCities(Graphics g)
{
g.Clear(Color.White);
Brush brush = new SolidBrush(Color.Black);
for (int i = 0; i < cities.Length; i++)
{
g.FillEllipse(brush, cities[i].X - 2, cities[i].Y - 2, 5, 5);
}
}
private void DrawPath(Graphics g, int[] path, Color color)
{
Pen pen = new Pen(color);
for (int i = 0; i < path.Length - 1; i++)
{
g.DrawLine(pen, cities[path[i]], cities[path[i + 1]]);
}
g.DrawLine(pen, cities[path[path.Length - 1]], cities[path[0]]);
}
private void btnGenerate_Click(object sender, EventArgs e)
{
cities = GenerateCities();
population = GeneratePopulation();
bestDistance = double.PositiveInfinity;
generation = 1;
pbTSP.Invalidate();
}
private void pbTSP_Paint(object sender, PaintEventArgs e)
{
DrawCities(e.Graphics);
DrawPath(e.Graphics, bestPath, Color.Green);
}
private Point[] GenerateCities()
{
Random rnd = new Random();
Point[] result = new Point[50];
for (int i = 0; i < result.Length; i++)
{
result[i] = new Point(rnd.Next(0, pbTSP.Width - 1), rnd.Next(0, pbTSP.Height - 1));
}
return result;
}
private List
{
List
Random rnd = new Random();
int[] path = new int[cities.Length];
for (int i = 0; i < populationSize; i++)
{
for (int j = 0; j < path.Length; j++)
{
path[j] = j;
}
for (int j = 0; j < path.Length; j++)
{
int k = rnd.Next(j, path.Length);
int temp = path[j];
path[j] = path[k];
path[k] = temp;
}
result.Add(path);
}
return result;
}