коммивояжера. Содержание введение 2 теоретическая часть 3

• Название: Содержание введение 2 теоретическая часть 3
• Дата: 09.05.2023
• Размер: 99.67 Kb.
• Имя файла: коммивояжера.docx
• Тип: Задача; #1117133
• страница: 3 из 4

Приближенный параллельный алгоритм

Описание приближенного параллельного алгоритма

Анализ преимуществ и недостатков алгоритма по сравнению с другими алгоритмами решения задачи

Практическая часть

Описание алгоритмов в коде на языке программирования 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 path;

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 tour;

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 tour = new 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 population;
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 GeneratePopulation()

{

List result = new 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;

}