Это мне нужно для написания эвристик для решения транспортной задачи. Ниже я привел код своей программы (из него убраны нерелевантные участки). Не обращайте внимания на некоторые, казалось бы, ненужные функции; дело в том, что я буду их "зашивать" в DLL. Я написал пояснения к строкам, так, Вам будет много легче разбирать этот код. Программа должна оптимизировать путь через семь городов известной эвристикой 2-OPT. Проблема этой программы заключается в том же самом: цепочка, в которой уже присутствует другая инверсированная цепочка, будет инверсирована неправильно.
| Цитата |
#include <iostream.h>
// Задает указатель на матрицу расстояний
void SetDistancesMatrix(unsigned long *M);
// Задает начальную последовательность городов, которую нужно оптимизировать
void SetData(unsigned int *CitiesData, unsigned int N);
// Возвращает оптимизированную последовательность городов
int GetData(unsigned int *CitiesData);
// Собственно эвристическая процедура 2-OPT пользуется указателями, которые задали в вышеуказанных функциях
bool Perform2OPT();
// Структура, характеризующая город. Включает в себя все поля, которые были оговорены в описании алгоритма.
typedef struct City {
unsigned int Data;
struct City *Link[2];
bool Direction;
} TCity;
// Указатель на начало и на конец дву-связного списка, вспомогательный указатель.
TCity *Head=NULL, *Tail=NULL, *Last;
// Указатель на матрицу расстояний между городами.
unsigned long *Distance;
// Количество городов в последовательности
int Num;
// Это пример использования всех этих функций. Представим себе, что они в DLL
void main(void) {
const n=7; // Количество городов
// Текущая матрица расстояний между городами. Она имеет вид: D[C1][C2] - расстояние от города С1, до города С2;
unsigned long D[n*n] ={6,3,8,2,6,4,9,
/**/ 3,2,7,1,7,2,5,
/**/ 8,7,5,4,9,3,1,
/**/ 2,1,4,9,8,2,4,
/**/ 6,7,9,8,1,5,7,
/**/ 4,2,3,2,5,3,9,
/**/ 9,5,1,4,7,9,4};
unsigned int Cities[n]={0,1,2,3,4,5,6}; // Сама последовательность городов.
SetDistancesMatrix(D); // Задаем указатель на матрицу расстояний
SetData(Cities, n); // Задаем последовательность городов и их количество
Perform2OPT(); // Выполняем оптимизацию
GetData(Cities); // Возвращаем значения и выводим их на экран
for (int i=0;i<n; i++) {
cout<<" "<<Cities[i];
} cout<<endl;
}
void SetDistancesMatrix(unsigned long *M) {
Distance=M;
}
// Процедура для создания духсвязного списка в памяти для переданной последовательности
void SetData(unsigned int *CitiesData, unsigned int N) {
TCity *C; Num=N; // Временная переменная, для обхода списка. Сохранение количества городов
// Создание первого элемента и последнего. Эти элементы не включаются в последовательность.
// Таким образом, количество элементов в дву-связном списке будет Num+2
Head=new TCity; Tail=new TCity; Last=Head;
Head->Data=0; Tail->Data=0; // Обнуление номера города (не имеет значения)
// Установка направления: указатель в массиве :Link с индексом 0 указывает вперед, а с 1 - назад
Head->Direction=0; Tail->Direction=0;
// Предыдущий элемент для начального не существует. Предыдущий для последнего есть первый.
Head->Link[1]=NULL; Tail->Link[1]=Head;
// Следующий у первого есть последний. Следующего элемента у последнего не существует.
Head->Link[0]=Tail; Tail->Link[0]=NULL;
for (int i=0; i<Num; i++) { // Цикл для вставки элементов в двусвязный список.
C=new TCity; // Создание нового элемента в списке
C->Data=CitiesData[i]; // Запись номера города в элемент
// Задание направления: 0 означает, что указаель с индексом 0 - указывает на следующий и наоборот.
C->Direction=0;
C->Link[1]=Last; // Предыдущий элемент от нового
Last->Link[0]=C; // Следующий элемент от предыдущего - это новый элемент
Last=C; // Продвижение указателя для добавления большего числа элементов
}
// "Приклеивание" последнего элемента.
Tail->Link[1]=Last; Last->Link[0]=Tail;
}
// Функция для возврата информации (оптимизированная последовательность)
int GetData(unsigned int *CitiesData) {
int Idx=0; bool Direction=0; // Индекс города в массиве и начальное направление
// Временный указатель для обхода списка инициализируется первым элементом с городом
TCity *C=Head->Link[0];
while (C!=Tail) { // Пока не дошли до последнего элемента
// Обход списка по алгоритму, указанному выше.
CitiesData[Idx++]=C->Data; // Передача номера города в массив
Direction^=C->Direction; // Одновление бита направления
C=C->Link[Direction]; // Продолжить обход
}
return Idx-1; // возвратить количество городов, которые были записаны.
}
// Функция оптимизации по 2-OPT алгоритму
bool Perform2OPT() {
TCity *I1, *I2, *J1, *J2; // Указатели вместо А1, А2, А3, А4 (как было описано в алгоритме)
bool D=0, Result=false; // Бит направления и результат была ли оптимизирована последовательность или нет.
Next:
I1=Head->Link[0]; // I1 указывает на первый элемент в списке
do {
D^=I1->Direction; // Обновление направления
I2=I1->Link[D]; // I2 указывает на следующий от I1
D^=I2->Direction; // Обновление направления
J1=I2->Link[D]; // J1 указывает на следующий от I2
do {
D^=J1->Direction; // Обновление направления
J2=J1->Link[D]; // J2 указывает на следующий от J1
// Следующее условие выполняется тогда, когда расстояние между городами I1-J1 в сумме
// с расстоянием между городами I2-J2 меньше чем расстояние I1-I2 + J1-J2 (текущее),
// то необходимо поменять местами все города между I2 и J1, включая их самих.
if ((Distance[I1->Data*Num+J1->Data]+Distance[I2->Data*Num+J2->Data])<
(Distance[I1->Data*Num+I2->Data]+Distance[J1->Data*Num+J2->Data]))
{
// Вот тут то и начинается мой алгоритм...
// Поясню сначала, как вычисляется индекс внутри квадратных скобок. Если элемент,
// на который указывает I2, не находится на следующем указателе (с индексом 0) у
// I1, значит элемент, на который указывает I1 - перевернут. Т.е. на I2 у него
// указывает предыдущий указатель (с индексом 1). Значит именно его мы меняем:
// записываем в него адрес J1. Во всем остальном эта строка соответствует первому
// пункту моего алгоритма.
I1->Link[I1->Link[0]!=I2]=J1;
J1->Link[J1->Link[0]!=J2]=I1; // То же самое и для этого переназначения. Соответствует второму пункту
J1->Direction=~J1->Direction; // Инверсия флага направления у J1. Пункт 5 (порядок их неважен)
I2->Link[I2->Link[1]==I1]=J2; // Пункт 3
J2->Link[J2->Link[1]==J1]=I2; // Пункт 4
J2->Direction=~J2->Direction; // Пункт 6
Result=true; // Последовательность была оптимизирована
goto Next; // Здесь лучше плюнуть в лицо модульному программированию и использовать
// старые методы, т.к. эффективность повышается.
}
J1=J2; // Продвижение указателей J
} while (J1!=Tail->Link[1]); // Пока J1 не дошел до предпоследнего
I1=I2; // Продвижение указателей I
} while (I1==Tail->Link[1]->Link[~Tail->Link[1]->Direction]); // Немного сложновато и неэффективно, но если
// разобраться, то это условие означает - пока I1 не дошел до
// предпоследнего элемента. Я подумаю, как можно это покороче записать.
return Result; // Вернуть результат.
}
|
З.Ы. Чингачгук, извиняй, что раньше не написал пояснения. Просто перевод их на русский заняло время. |
(Зачем?)
). Ну, например, почему просто не держать номер, ссылку, на первый (последний) "типа" инвертированный элемент. Ну короче: Программа = Данные + Логика + Интерпретатор, и надо думать не только о данных, но и о логике их интерпретации.