Хостинг портала RFpro.ru:
Московский хостер
Профессиональный ХОСТИНГ на базе Linux x64 и Windows x64

РАССЫЛКИ ПОРТАЛА RFPRO.RU

Лучшие эксперты по данной тематике

Асмик Гаряка Статус: Академик Рейтинг: 8743 ∙ повысить рейтинг »

Коцюрбенко Алексей aka Жерар Статус: Профессор Рейтинг: 3219 ∙ повысить рейтинг »

Boriss Статус: Академик Рейтинг: 2596 ∙ повысить рейтинг »

/ КОМПЬЮТЕРЫ И СОФТ / Программирование / C/C++

Номер выпуска:	1709
Дата выхода:	17.12.2011, 19:30
Администратор рассылки:	Киселёва Алёна aka Verena (Профессор)
Подписчиков / экспертов:	277 / 163
Вопросов / ответов:	2 / 2

Консультация # 184726: Уважаемые эксперты! Пожалуйста, ответьте на вопрос: надо реализовать простой вариант метода ветвей и границ для задачи коммивояжёра. Требования к программе: - в списке хранить под-задания - точнее указатели на них и упорядочивать эти подзадачи по значению границы - каждый раз выбирать из списка "самую потенциально лучшую" подз...

Консультация # 184726:

Уважаемые эксперты! Пожалуйста, ответьте на вопрос:
надо реализовать простой вариант метода ветвей и границ для задачи коммивояжёра. Требования к программе:
- в списке хранить под-задания - точнее указатели на них и упорядочивать эти подзадачи по значению границы
- каждый раз выбирать из списка "самую потенциально лучшую" подзадачу - и делить её ровно на две
- при этом разделяющий элемент выбирать по какому либо самому простому (и быстрому) но жадному" алгоритму
- в "правой" задаче он войдёт в СПИСОК таких ВЫБРАННЫХ элементов (добавится к уже имеющемуся такому списку у задачи-родителя), а в "левой" - добавится к списку табулированных элементов
- генерация входов - это так называемая геометрическая ЗКВ( где точки равномерно разбрасываются в N-мерный куб ([0,1])^N(интересны значения N от 3 до скажем 11))
- подсчитать "количественные характеристики выполнения программы";

Дата отправки: 10.12.2011, 09:59
Вопрос задал: Yulesik (2-й класс)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Киселёва Алёна aka Verena (Профессор):

Здравствуйте, Yulesik!
Вот, перевела из этого алгорима. Если будут вопросы, пишите.
Результат проверила, с паскалевской программой совпадает.
Компилировалось под MS VS 2010.
Удачи!

Приложение:
#include <iostream> #include <conio.h> using namespace std; const int COUNT_POINTS =6; void FITSP (int N, int S, int INF, int W [COUNT_POINTS+1][COUNT_POINTS+1], int ROUTE [COUNT_POINTS+1], int &PATH_WEIGHT) { int END1,END2,FARTHEST,I,INDEX, INSCOST,J,MAXDIST,NEWCOST,NEXTINDEX; int CYCLE [COUNT_POINTS+1], DIST[COUNT_POINTS+1]; for (I=1; I<=N; I++) CYCLE[I]=0; CYCLE[S]=S; for (I=1; I<=N; I++) DIST[I]=W[S][I]; PATH_WEIGHT=0; for (I=1; I<=N-1; I++) { MAXDIST=-INF; for (J=1; J<=N; J++) if (CYCLE[J] == 0) if (DIST[J] > MAXDIST) { MAXDIST=DIST[J]; FARTHEST=J; } INSCOST=INF; INDEX=S; for (J=1; J<=I; J++) { NEXTINDEX=CYCLE[INDEX]; NEWCOST=W[INDEX][FARTHEST]+W[FARTHEST][NEXTINDEX]- W[INDEX][NEXTINDEX]; if (NEWCOST < INSCOST) { INSCOST=NEWCOST; END1=INDEX; END2=NEXTINDEX; } INDEX=NEXTINDEX; } CYCLE[FARTHEST]=END2; CYCLE[END1]=FARTHEST; PATH_WEIGHT=PATH_WEIGHT+INSCOST; for (J=1; J<=N; J++) if (CYCLE[J] == 0) if (W[FARTHEST][J] < DIST[J]) DIST[J]=W[FARTHEST][J]; } INDEX=S; for (int I=1; I<=N; I++) { ROUTE[I]=INDEX; INDEX=CYCLE[INDEX]; } } enum SWAPTYPE { ASYMMETRIC, SYMMETRIC }; struct SWAPRECORD { int X1,X2,Y1,Y2,Z1,Z2,GAIN; SWAPTYPE CHOICE; }; void SWAPCHECK(SWAPRECORD SWAP, int W[COUNT_POINTS+1][COUNT_POINTS+1]) { int DELWEIGHT,MAX; SWAP.GAIN=0; DELWEIGHT=W[SWAP.X1][SWAP.X2]+W[SWAP.Y1][SWAP.Y2]+W[SWAP.Z1][SWAP.Z2]; MAX=DELWEIGHT-(W[SWAP.Y1][SWAP.X1]+W[SWAP.Z1][SWAP.X2]+W[SWAP.Z2][SWAP.Y2]); if (MAX > SWAP.GAIN) { SWAP.GAIN=MAX; SWAP.CHOICE=ASYMMETRIC; } MAX=DELWEIGHT-(W[SWAP.X1][SWAP.Y2]+W[SWAP.Z1][SWAP.X2]+W[SWAP.Y1][SWAP.Z2]); if (MAX > SWAP.GAIN) { SWAP.GAIN=MAX; SWAP.CHOICE =SYMMETRIC; } } void REVERSE (int START, int FINISH, int PTR [COUNT_POINTS+1]) { int AHEAD,LAST,NEXT; if (START != FINISH) { LAST=START; NEXT=PTR[LAST]; do { AHEAD=PTR[NEXT]; PTR[NEXT]=LAST; LAST=NEXT; NEXT=AHEAD; } while (LAST != FINISH); } } void THREEOPT (int N, int W[COUNT_POINTS+1][COUNT_POINTS+1], int ROUTE [COUNT_POINTS+1]) { SWAPRECORD BESTSWAP,SWAP; int I,INDEX,J,K; int PTR [COUNT_POINTS+1]; for (I=1; I<=N-1; I++) PTR[ROUTE[I]]=ROUTE[I+1]; PTR[ROUTE[N]]=ROUTE[1]; SWAP.GAIN = 0; do { BESTSWAP.GAIN=0; SWAP.X1=1; for (I=1; I<=N; I++) { SWAP.X2=PTR[SWAP.X1]; SWAP.Y1=SWAP.X2; for (J=2; J<=N-3; J++) { SWAP.Y2=PTR[SWAP.Y1]; SWAP.Z1=PTR[SWAP.Y2]; for (K=J+2;K<=N-1; K++) { SWAP.Z2=PTR[SWAP.Z1]; SWAPCHECK(SWAP, W); if (SWAP.GAIN > BESTSWAP.GAIN) BESTSWAP=SWAP; SWAP.Z1=SWAP.Z2; } SWAP.Y1=SWAP.Y2; } SWAP.X1=SWAP.X2; } if (BESTSWAP.GAIN > 0) { if (BESTSWAP.CHOICE == ASYMMETRIC) { REVERSE(BESTSWAP.Z2,BESTSWAP.X1, PTR); PTR[BESTSWAP.Y1]=BESTSWAP.X1; PTR[BESTSWAP.Z2]=BESTSWAP.Y2; } else { PTR[BESTSWAP.X1]=BESTSWAP.Y2; PTR[BESTSWAP.Y1]=BESTSWAP.Z2; } PTR[BESTSWAP.Z1]=BESTSWAP.X2; } } while (BESTSWAP.GAIN != 0); INDEX=1; for (I=1; I<=N; I++) { ROUTE[I]=INDEX; INDEX=PTR[INDEX]; } } void TWOOPT(int N, int W [COUNT_POINTS+1][COUNT_POINTS+1], int ROUTE [COUNT_POINTS+1], int &PATH_WEIGHT) { int AHEAD,I,I1,I2,INDEX,J,J1,J2,LAST,LIMIT,MAX,MAX1,NEXT,S1,S2,T1,T2; int PTR [COUNT_POINTS+1]; for (I=1; I<=N-1; I++) PTR[ROUTE[I]]=ROUTE[I+1]; PTR[ROUTE[N]]=ROUTE[1]; do { MAX=0; I1=1; for (I=1; I<=N-2; I++) { if (I == 1) LIMIT=N-1; else LIMIT=N; I2=PTR[I1]; J1=PTR[I2]; for (J=I+2; J<=LIMIT; J++) { J2=PTR[J1]; MAX1=W[I1][I2]+W[J1][J2]-(W[I1][J1]+W[I2][J2]); if (MAX1 > MAX ) { S1=I1; S2=I2; T1=J1; T2=J2; MAX=MAX1; } J1=J2; } I1=I2; } if (MAX > 0 ) { PTR[S1]=T1; NEXT=S2; LAST=T2; do { AHEAD=PTR[NEXT]; PTR[NEXT]=LAST; LAST=NEXT; NEXT=AHEAD; } while (NEXT != T2); PATH_WEIGHT=PATH_WEIGHT-MAX; } } while (MAX != 0); INDEX=1; for (I=1; I<=N; I++) { ROUTE[I]=INDEX; INDEX=PTR[INDEX]; } } int _tmain(int argc, _TCHAR* argv[]) { int W [COUNT_POINTS+1][COUNT_POINTS+1] = {{-1, -1, -1, -1, -1, -1, -1}, {-1, 0, 0, 0, 3, 3, 6}, {-1, 0, 0, 1, 4, 1, 0}, {-1, 1, 2, 0, 0, 0, 3}, {-1, 4, 5, 0, 0, 0, 3}, {-1, 4, 2, 0, 0, 0, 0}, {-1, 7, 1, 3, 3, 0, 0} }; int PATH_WEIGHT; int ROUTE [COUNT_POINTS+1]; int i; PATH_WEIGHT=0; for (i=1; i<=COUNT_POINTS; i++) ROUTE[i]=i; FITSP(COUNT_POINTS,1,999999,W,ROUTE,PATH_WEIGHT); TWOOPT(COUNT_POINTS,W,ROUTE,PATH_WEIGHT); THREEOPT(COUNT_POINTS,W,ROUTE); for (i=1; i<=COUNT_POINTS; i++) cout << ROUTE[i] << "->"; cout << 1 << " = " << PATH_WEIGHT; _getch(); return 0; }

Консультировал: Киселёва Алёна aka Verena (Профессор) Дата отправки: 16.12.2011, 15:09

Рейтинг ответа: 0 поблагодарить эксперта

Консультация # 184731:

Здравствуйте! У меня возникли сложности с таким вопросом:
Необходимо Разработать программу, которая создает в отдельном потоке случайный массив А из N целых чисел в диапазоне от -999 до 999 выводит на экран эти числа. Создание и вывод элементов массива производится через заданное время T, N и T вводятся пользователем до запуска процесса. Массив обрабатывается двумя другими потоками В и С, работающими параллельно с потоком, создающим массив. Все потоки выводят результаты своей работы в текстовые окна, каждый поток в свое окно.
А)Определение длины пространственной ломаной линии, соединяющей точки, координаты которых заданы каждой тройкой чисел
Б)Вычисление отклонений всех чисел от округленного среднего арифметического

Можете назначить свою цену если в этом есть необходимость.

Дата отправки: 10.12.2011, 20:28
Вопрос задал: MishaSurgut (Посетитель)
Всего ответов: 1
Страница онлайн-консультации »

Консультирует Киселёва Алёна aka Verena (Профессор):

Здравствуйте, MishaSurgut!
Вот пример такой программы. Правда, тут всё выводится в одну

консоль, чтобы выводить в разные окна надо делать оконное приложение и в каждом потоке

вместо cout выводить на какой-нибудь свой контрол.
В программе создаётся по три потока на

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

линии, третий ищет отклонения. Для синхронизации потоков используются события (event) -

одно для потока создания и одно для потоков обработки.
Используемые WinAPI функции:


CreateEvent
Эта функция создаёт или открывает существующее событие, возвращаемым

значением является его описатель.

HANDLE CreateEvent(
    LPSECURITY_ATTRIBUTES 

lpEventAttributes, //Аттрибуты защиты
    BOOL bManualReset, //Ручной сброс
    BOOL 

bInitialState, //Состояние при создании
    LPCTSTR lpName //Имя (если необходимо)
 );

typedef struct _SECURITY_ATTRIBUTES {
    DWORD nLength; //Размер 

структуры (как правило, берётся sizeof)
    LPVOID lpSecurityDescriptor; //Указатель на 

дескриптор, контролирующий совместное                                        

//использование объекта
   BOOL bInheritHandle; //Флаг, разрешающий наследование объекта 

дочерним процессом
} SECURITY_ATTRIBUTES, *PSECURITY_ATTRIBUTES; 

DWORD WaitForSingleObject(
    HANDLE 

hHandle, //Описатель объекта ядра, сигнальное состояние которого нас интересует 
   DWORD 

dwMilliseconds //Таймаут, по истечению которого прервать ожидание 
);

HANDLE CreateThread(
    LPSECURITY_ATTRIBUTES lpThreadAttributes, //Аттрибуты защиты 
 

  SIZE_T dwStackSize, //Размер стека потока (если указать 0, то берётся по умолчанию) 
   

LPTHREAD_START_ROUTINE lpStartAddress, //Адрес стартовой функции 
   LPVOID lpParameter, 

//Параметр для передачи потоку 
   DWORD dwCreationFlags, //Служебные флаги 
   LPDWORD 

lpThreadId //ID потока 
); 

DWORD WINAPI 

ThreadProc( //Имя функции может быть произвольным 
   LPVOID lpParameter
 ); 

Приложение:
#include <Windows.h> #include <iostream> #include <math.h> #include <time.h> #include <string> using namespace std; int* A; //глобальный массив int N, T; //число элементов, время HANDLE g_BusyEvent[2]; //события int Random (int min, int max) //рандом от min до max { return rand()%(max-min) + min ; } double Length (int x1, int y1, int z1, int x2, int y2, int z2) //вычисление длины линии между пространственными точками { double val = (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1) + (z2-z1)*(z2-z1); return sqrt (val); } DWORD WINAPI CreateArrayThread(void *pParam) //Поток формирования массива { WaitForSingleObject (g_BusyEvent[0], INFINITE); //ждём допуска ResetEvent (g_BusyEvent[1]); //запрещаем обработки cout << "\nNew array: "; srand (time(NULL)); for (int i=0; i<N; i++) { A[i] = Random (-999, 999); //заполняем массив cout << A[i] << \' \'; } SetEvent(g_BusyEvent[0]); SetEvent(g_BusyEvent[1]); return 0; } DWORD WINAPI LengthThread(void *pParam) //Рабочий поток { WaitForSingleObject (g_BusyEvent[1], INFINITE); //ждём разрешение на обработку SetEvent(g_BusyEvent[1]); //разрешаем параллельную обработку ResetEvent (g_BusyEvent[0]); //запрещаем переформирование массива cout << "\nLength of line: "; double s = 0; for (int i=0; i<N-6;) { //считаем длину s+=Length(A[i++], A[i++], A[i++], A[i++], A[i++], A[i++]); } cout << s; SetEvent(g_BusyEvent[0]); //разрешаем переформирование return 0; } DWORD WINAPI AverageThread(void *pParam) //Рабочий поток { //аналогично предыдущему WaitForSingleObject (g_BusyEvent[1], INFINITE); SetEvent(g_BusyEvent[1]); ResetEvent (g_BusyEvent[0]); cout << "\nDisplacement: "; int s = 0; for (int i=0; i<N; i++) s+=A[i]; s/=N; for (int i=0; i<N; i++) cout << s-A[i] << \' \'; SetEvent(g_BusyEvent[0]); return 0; } int _tmain(int argc, _TCHAR* argv[]) { cout << "Enter count: "; cin >> N; cout << "Enter time (seconds): "; cin >> T; A = new int [N]; g_BusyEvent[0] = CreateEvent(NULL, FALSE, FALSE, NULL); //Создаём событие g_BusyEvent[1] = CreateEvent(NULL, FALSE, TRUE, NULL); //Создаём событие DWORD dwID; while (true) { SetEvent (g_BusyEvent [0]); //разрешаем формирование ResetEvent (g_BusyEvent[1]); //запрещаем обработки CloseHandle (CreateThread(NULL, 0, CreateArrayThread, NULL, 0, &dwID)); //Создаём поток CloseHandle (CreateThread(NULL, 0, LengthThread, NULL, 0, &dwID)); //Создаём поток CloseHandle (CreateThread(NULL, 0, AverageThread, NULL, 0, &dwID)); //Создаём поток Sleep (T*1000); //выжидаем заданное время //system("pause"); //если хотите успеть смотреть результат на каждой итерации } return 0; }

Консультировал: Киселёва Алёна aka Verena (Профессор) Дата отправки: 16.12.2011, 13:47

Рейтинг ответа: 0 поблагодарить эксперта

Оценить выпуск | Задать вопрос экспертам

главная страница  |  стать участником  |  получить консультацию
техническая поддержка  |  восстановить логин/пароль