Я пытаюсь реализовать TSP-решатель, используя метод ветвей и границ и алгоритм Литтла. Само программное обеспечение должно использоваться в демонстрационных целях для чтения лекций по дискретной математике.
С помощью алгоритма Литтла я нахожу тур-кандидат, который затем должен сравниваться с другими турами-кандидатами. Но еще до того, как перейти к ветвлению и привязке, у меня возникает проблема с результатами реализации алгоритма моего Литтла.
Я использую double.positiveinfinity для удаления маршрутов, которые я уже проверил, и маршрутизации и маршрутов из точки x в точку x.
Сам алгоритм выглядит следующим образом:
- Получить матрицу расстояний всех возможных маршрутов
- Найти минимальный элемент для каждой строки
- Для всех строк вычесть минимальный элемент соответствующей строки из каждого элемента в этой строке, кроме бесконечных
- Найти минимальный элемент для каждого столбца
- Для всех столбцов вычесть минимальный элемент соответствующего столбца из каждого элемента в этом столбце, кроме бесконечных
Мы получим как минимум 1 ноль в каждой строке и столбце.
- Для каждого нулевого элемента в матрице вычислить значение как сумму минимального элемента соответствующей строки и минимального элемента соответствующего col (исключая сам этот нулевой элемент)
- Найти нулевой элемент с наибольшим вычисленным значением. Это маршрут, который мы включим в наш тур
- Удалить из строки и столбца матрицы этот нулевой элемент. Также удалите из учета "элемент обратного маршрута" (например, мы нашли маршрут 3> 4, это означает, что мы больше не будем идти 4> 3 в этом туре, и поэтому мы удаляем элемент (4,3)). Это делается путем присвоения double.positiveinfinity элементам этой строки, этого столбца и элемента обратного маршрута
- Если мы не получили полный тур, мы переходим к шагу 2 для нашей новой матрицы
Ниже приведены функции, которые я написал.
//find minimum element in row i of matrix m excluding element with number exc
private double GetRowMin(double[,] m, int i, int exc = -1)
{
double[] SubRow = new double[m.GetLength(1)];
Buffer.BlockCopy(m, 8 * m.GetLength(1) * i, SubRow, 0, 8 * m.GetLength(1));
if (exc != -1)
SubRow[exc] = Double.PositiveInfinity;
return SubRow.Min();
}
//find minimum element in col j of matrix m excluding element with number exc
private double GetColMin(double[,] m, int j, int exc = -1)
{
double[] SubCol = new double[m.GetLength(0)];
SubCol = Enumerable.Range(0, m.GetLength(0)).Select(xr => m[xr, j]).ToArray();
if (exc != -1)
SubCol[exc] = Double.PositiveInfinity;
return SubCol.Min();
}
//reduce matrix m by subtracting minimum for every row and col
private double[,] MReduce(double[,] m)
{
double[,] resm = new double[m.GetLength(0), m.GetLength(1)];
for (int i = 0; i < m.GetLength(0); i++)
for (int j = 0; j < m.GetLength(1); j++)
if (m[i, j] < Double.PositiveInfinity)
resm[i, j] = m[i, j] - GetRowMin(m, i, i);
else
resm[i, j] = Double.PositiveInfinity;
for (int i = 0; i < m.GetLength(0); i++)
for (int j = 0; j < m.GetLength(1); j++)
if (m[i, j] < Double.PositiveInfinity)
resm[i, j] = m[i, j] - GetColMin(m, j, j);
else
resm[i, j] = Double.PositiveInfinity;
return resm;
}
//find zero element with maximum value
private Point FindMaxVElem(double[,] m)
{
double MaxV = Double.MinValue;
Point MaxP = new Point();
for (int i = 0; i < m.GetLength(0); i++)
for (int j = 0; j < m.GetLength(1); j++)
if (m[i, j] == 0)
{
double s = 0;
if (!Double.IsInfinity(GetRowMin(m, i, j)))
s += GetRowMin(m, i, j);
if (!Double.IsInfinity(GetColMin(m, j, i)))
s += GetColMin(m, j, i);
if (Double.IsInfinity(s))
s = 0;
if (s > MaxV)
{
MaxV = s;
MaxP.X = i;
MaxP.Y = j;
}
}
return MaxP;
}
//delete row/col and backroute from accounting
private double[,] RCSubtract(double[,] m, int l, int n)
{
double[,] resm = new double[m.GetLength(0), m.GetLength(1)];
for (int i = 0; i < m.GetLength(0); i++)
for (int j = 0; j < m.GetLength(1); j++)
{
if (i == l || j == n)
resm[i, j] = Double.PositiveInfinity;
else
resm[i, j] = m[i, j];
}
resm[n, l] = Double.PositiveInfinity;
return resm;
}
Код драйвера выглядит примерно так:
public List<PointD> PList; //list for storing coordinates of all points
double[,] AdjM; //distance matrix
List<Point> path; //here will be unordered subroutes of the tour
...
for (int i = 0; i < PList.Count; i++)
{
AdjM = MReduce(AdjM);
path.Add(FindMaxVElem(AdjM));
AdjM = RCSubtract(AdjM, path.Last().X, path.Last().Y);
}
В большинстве случаев (простых и сложных) все в порядке, и тур найден. Проблема заключается в том, что вместо полного обхода всех точек реализация моего алгоритма Литтла на нескольких отдельных группах строго локализованных точек возвращает нескольких отдельных закрытых туров , например:
(думаю, у меня недостаточно репутации для публикации изображения, извините) https://pp.userapi.com/c849236/v849236895/174a46/ASAPt1F8zs4.jpg
Пошаговая матрица решается так:
0 1 2 3 4 5 Min
--------------------------------------------
0: нет 25,4 31,5 146,3 159,6 140,2 25,4
1: 25,4 нет 24,8 160,3 176,3 159,3 24,8
2: 31,5 24,8 нет 138,3 155,9 141,2 24,8
3: 146,3 160,3 138,3 нет 26,3 40,8 26,3
4: 159,6 176,3 155,9 26,3 нет 27,9 26,3
5: 140,2 159,3 141,2 40,8 27,9 нет 27,9
Min 25,4 24,8 24,8 26,3 26,3 27,9 310,9
0 1 2 3 4 5 Min
--------------------------------------------
0: нет 0,5 6,7 120,1 нет 112,4 0,5
1: 0 нет 0 134,1 нет 131,5 0
2: 6,2 0 нет 112 нет 113,3 0
3: нет нет нет нет нет нет нет
4: 134,2 151,5 131 нет нет 0 0
5: 114,9 134,5 116,3 14,6 нет нет 14,6
Min 0 0 0 14,6 нет 0 29,7
0 1 2 3 4 5 Min
--------------------------------------------
0: нет 0,5 6,7 105,5 нет нет 0,5
1: 0 нет 0 119,5 нет нет 0
2: 6,2 0 нет 97,4 нет нет 0
3: нет нет нет нет нет нет нет
4: нет нет нет нет нет нет нет
5: 114,9 134,5 116,3 0 нет нет 0
Min 0 0 0 0 нет нет 0,5
0 1 2 3 4 5 Min
--------------------------------------------
0: нет 0,5 6,7 нет нет нет 0,5
1: 0 нет 0 нет нет нет 0
2: 6,2 0 нет нет нет нет 0
3: нет нет нет нет нет нет нет
4: нет нет нет нет нет нет нет
5: нет нет нет нет нет нет нет
Min 0 0 0 нет нет нет 0,5
0 1 2 3 4 5 Min
--------------------------------------------
0: нет 0,5 нет нет нет нет 0,5
1: нет нет нет нет нет нет нет
2: 6,2 нет нет нет нет нет 6,2
3: нет нет нет нет нет нет нет
4: нет нет нет нет нет нет нет
5: нет нет нет нет нет нет нет
Min 6,2 0,5 нет нет нет нет 13,4
0 1 2 3 4 5 Min
--------------------------------------------
0: нет нет нет нет нет нет нет
1: нет нет нет нет нет нет нет
2: 0 нет нет нет нет нет 0
3: нет нет нет нет нет нет нет
4: нет нет нет нет нет нет нет
5: нет нет нет нет нет нет нет
Min 0 нет нет нет нет нет 0
Так что я знаю, что сделал что-то не так (возможно, запутался в обработке бесконечности), так как уже первая итерация для отдельно локализованных групп точек возвращает несколько закрытых обходов вместо одного. Но я не могу понять, что именно идет не так. У кого-нибудь есть идеи?