/* NAME: Ivan Anev SCHOOL: SMG ID: A5 PROG: travel ЕСЕНЕН ТУРНИР ПО ИНФОРМАТИКА ШУМЕН’02 - 16 ноември 2002 ТЕМА ЗА 11-12 КЛАС (ГРУПА A) Задача 1. ОБИКОЛКА Хора от различни професии (пощальони, разносвачи на стоки по домовете, търговци и т.н.) често са изправени пред следната задача: те трябва да тръгнат от точка, съответна на работното им място (пощенска станция, магазин, склад или офис на фирмата), да посетят няколко други точки, където са разположени клиентите им и да се върнат в началната точка на обиколката. Нека точките, през които трябва да мине обиколката са означени с числата от 1 до N, като началната точка е означена с 1. За всеки две точки, които трябва да бъдат посетени (включително и началната точка на обиколката) е известно цяло число – разстояние между двете точки (време за изминаване на това разстояние или някаква друга цена за изминаването му). Няма съмнение, че колкото по-кратка (по-бърза, по-евтина) е обиколката, толкова по-добре. За съжаление, добре известно е, че да се намери най-добрата възможна обиколка не е никак лесно, ако броят на местата, които трябва да бъдат посетени е достатъчно голям. Вашата задача е да напишете програма TRAVEL.EXE, която да опита да намери за отпуснатото й време колкото може по-добро решение. Данните ще бъдат зададени в текстов файл, който вашата програма ще прочете от стандартния си вход. В първия ред на входния файл ще бъде зададено цялото число N (3 < N < 200) – броят на точките, които трябва да бъдат посетени, включително началната. Всеки от следващите N реда ще съдържа целочислените координати (разделени с интервал) на една от точките – в реда на номерата им. Разстоянието между две точки е т.н. манхатънско разстояние. За точките с координати (x1,y1) и (x2,y2) то се пресмята по формулата |x1–x2| + |y1–y2|. Всички координати са неотрицателни цели числа, не надхвърлящи 10000. Изходният файл трябва да бъде изведен на стандартния изход. Той трябва да съдържа един ред с пермутацията на числата от 1 до N, разделени с по един интервал – намерена от програмата обиколка. Оценката на резултата от работата на Вашата програмата върху всеки тест ще бъде извършена след сравняване с резултатите на другите състезатели. Програмите построили най-добра обиколка ще получат пълния брой точки за теста, а всяка останала програма – част от пълния брой, пропорционална на дължината на намереното решение. Пример Вход Изход (един от възможните) 6 1 4 6 5 3 2 0 0 40 0 25 5 20 10 40 20 10 20 РЕШЕНИЕ: Задача 1 е известна под името “задача за търговския пътник”. Също така е известно, че не е намерено решение различно от пълното изчерпване, което да решава задачата. На състезанието се искаше да се намери колкото се може по-добро решение в рамките на 5 секунди. Към задачата има няколко подхода. Има няколко известни приближени решения наречени апроксимации, който намират решение с някакъв коефициент k по-лошо от най-доброто, като някой от състезателите реализираха някои от тях. Едно от тях е да се направи обхождане в дълбочина на минимално обхващащо дърво на точките, което ще ни даде ред за посещаване на точките; за това решение е вярно, че коефициентът k винаги е не по-голям от 2 и обикновено е в интервала [1.15, 1.20]. Също така, много участници написаха много лесен greedy алгоритъм, който на всяка стъпка от текущия връх отива във най-близкия не посетен връх. Друг подход (реализиран от мен) е пълното изчерпване, като трябва да се вземат под внимание няколко момента. Алгоритъмът пробва от текущия връх да отиде във всеки връх който не е посетен и от този, в който е отишъл отново пробва да отиде във всеки не посетен и т.н. Също така обхождането на съседните върхове става в ред на отдалеченост от него, като пръв се посещава този, който е най-близо. Макар последното да дава доста добро подобрение като цяло пълното изчерпване има един голям недостатък. При голям брой върхове алгоритъмът ще направи всички възможни обхождания на последните 20-30 върха, но при лош избор в началото това няма да намери много по-добро решение. В такива случай се използва лесен за реализиране подход (не реализиран от мен по време на състезанието поради липса на желание), при който след определен период от време (например 0.1 сек) алгоритъма се връща (1/2*N) стъпки назад, а след всяка една секунда се връща до първия връх. Така може да се поправи лош избор в началото. Не реализирането на последния подход за голям брой върхове не дава много по-добро решение от посочения по-горе greedy алгоритъм. */ #include <stdio.h> #include <stdlib.h> #include <math.h> #include <limits.h> #include <time.h> #define MAXN 256 typedef struct Point TPoint; struct Point { int x, y; }; typedef struct Vex TVex; typedef struct Edge TEdge; struct Vex { int v, b; TEdge *edges; }; struct Edge { int v, w; TEdge *next; }; int n; TPoint pt[MAXN]; TVex vs[MAXN]; clock_t s; int bp; int path[MAXN]; void readf(void); void solve(void); void writef(void); int main(void) { readf(); solve(); writef(); return 0; } void readf(void) { /* FILE *fin; */ int i; /* fin = fopen("travel.in", "r"); fscanf(fin, "%d", &n); for (i = 0; i < n; ++i) fscanf(fin, "%d %d\n", &pt[i].x, &pt[i].y); fclose(fin); */ scanf("%d", &n); for (i = 0; i < n; ++i) scanf("%d%d", &pt[i].x, &pt[i].y); } void solve(void) { int i, j; void add_edge(int a, int b); int dfs(int v, int cp, int len); s = clock(); for (i = 0; i < n; ++i) for (j = 0; j < n; ++j) if (i != j) add_edge(i, j); bp = INT_MAX; dfs(0, 0, 1); } void writef(void) { int i; printf("%d", path[0]+1); for (i = 1; i < n; ++i) printf(" %d", path[i]+1); printf("\n"); } void add_edge(int a, int b) { TEdge *e, **se; e = (TEdge*)malloc(sizeof(TEdge)); e->v = b; e->w = abs(pt[a].x - pt[b].x) + abs(pt[a].y - pt[b].y); for (se = &vs[a].edges; *se && (*se)->w < e->w; se = &(*se)->next) ; e->next = *se; *se = e; } int dfs(int v, int cp, int len) { TEdge *e; int i, u; clock_t c; if (cp < bp) { vs[v].v = 1; for (e = vs[v].edges; e; e = e->next) if (e->v == 0 && len == n) { if (cp + e->w < bp) { bp = cp + e->w; u = v; for (i = n-1; i >= 0; --i) { path[i] = u; u = vs[u].b; } } } else if (vs[e->v].v == 0) { c = clock(); if ((c - s) / 1000.0 > 4.9) return 1; vs[e->v].b = v; if (dfs(e->v, cp + e->w, len+1)) return 1; } vs[v].v = 0; } return 0; }