|
|
Регистрация Восстановить пароль |
Регистрация | Задать вопрос |
Заплачу за решение |
Новые сообщения |
Сообщения за день |
Расширенный поиск |
Правила |
Всё прочитано |
|
|
Опции темы | Поиск в этой теме |
24.12.2010, 16:43 | #1 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 1
|
реализовать задачу китайского почтальона
Очень нужна помощь в реализации "задачи китайского почтальона на Си(Си++)"
Суть задачи в том, что задается граф матрицей смежности, с весами каждого ребра. нужно найти минимальный путь обхода всех ребер графа,по ребрам можно идти по нескольку раз. По примеру...если смотреть в учебнике он состоит из 3 алгоритмов. Алгоритма Дейкстра, алгоритма минимального паросочетания , и алгоритма нахождения Эйлерова цикла. |
24.12.2010, 16:43 | #2 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 1
|
у меня готовые есть Эйлера
Код:
Последний раз редактировалось Stilet; 24.12.2010 в 16:54. |
24.12.2010, 16:44 | #3 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 1
|
и Дейкстра .
Код:
Последний раз редактировалось Stilet; 24.12.2010 в 17:04. |
24.12.2010, 16:58 | #4 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 1
|
если кто-то может помочь написать-помогите.Я в долгу не останусь...в разумных пределах конечно))))
|
24.12.2010, 17:13 | #5 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 1
|
так же есть Венгерский алгоритм...но он не мой...я его не понимаю совсем...и он через вектора решает...что очень печально...но может вам это что то скажет
#include <vector> #include <limits> using namespace std; typedef pair<int, int> PInt; typedef vector<int> VInt; typedef vector<VInt> VVInt; typedef vector<PInt> VPInt; const int inf = numeric_limits<int>::max(); /* * Решает задачу о назначениях Венгерским методом. * matrix: прямоугольная матрица из целых чисел (не обязательно положительных). * Высота матрицы должна быть не больше ширины. * Возвращает: Список выбранных элементов, по одному из каждой строки матрицы. */ VPInt hungarian(const VVInt &matrix) { // Размеры матрицы int height = matrix.size(), width = matrix[0].size(); // Значения, вычитаемые из строк (u) и столбцов (v) VInt u(height, 0), v(width, 0); // Индекс помеченной клетки в каждом столбце VInt markIndices(width, -1); // Будем добавлять строки матрицы одну за другой for(int i = 0; i < height; i++) { VInt links(width, -1); VInt mins(width, inf); VInt visited(width, 0); // Разрешение коллизий (создание "чередующейся цепочки" из нулевых элементов) int markedI = i, markedJ = -1, j; while(markedI != -1) { // Обновим информацию о минимумах в посещенных строках непосещенных столбцов // Заодно поместим в j индекс непосещенного столбца с самым маленьким из них j = -1; for(int j1 = 0; j1 < width; j1++) if(!visited[j1]) { if(matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1]) { mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1]; links[j1] = markedJ; } if(j==-1 || mins[j1] < mins[j]) j = j1; } // Теперь нас интересует элемент с индексами (markIndices[links[j]], j) // Произведем манипуляции со строками и столбцами так, чтобы он обнулился int delta = mins[j]; for(int j1 = 0; j1 < width; j1++) if(visited[j1]) { u[markIndices[j1]] += delta; v[j1] -= delta; } else { mins[j1] -= delta; } u[i] += delta; // Если коллизия не разрешена - перейдем к следующей итерации visited[j] = 1; markedJ = j; markedI = markIndices[j]; } // Пройдем по найденной чередующейся цепочке клеток, снимем отметки с // отмеченных клеток и поставим отметки на неотмеченные for(; links[j] != -1; j = links[j]) markIndices[j] = markIndices[links[j]]; markIndices[j] = i; } // Вернем результат в естественной форме VPInt result; for(int j = 0; j < width; j++) if(markIndices[j] != -1) result.push_back(PInt(markIndices[j], j)); return result; } |
24.12.2010, 17:13 | #6 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 1
|
так же есть Венгерский алгоритм...но он не мой...я его не понимаю совсем...и он через вектора решает...что очень печально...но может вам это что то скажет
#include <vector> #include <limits> using namespace std; typedef pair<int, int> PInt; typedef vector<int> VInt; typedef vector<VInt> VVInt; typedef vector<PInt> VPInt; const int inf = numeric_limits<int>::max(); /* * Решает задачу о назначениях Венгерским методом. * matrix: прямоугольная матрица из целых чисел (не обязательно положительных). * Высота матрицы должна быть не больше ширины. * Возвращает: Список выбранных элементов, по одному из каждой строки матрицы. */ VPInt hungarian(const VVInt &matrix) { // Размеры матрицы int height = matrix.size(), width = matrix[0].size(); // Значения, вычитаемые из строк (u) и столбцов (v) VInt u(height, 0), v(width, 0); // Индекс помеченной клетки в каждом столбце VInt markIndices(width, -1); // Будем добавлять строки матрицы одну за другой for(int i = 0; i < height; i++) { VInt links(width, -1); VInt mins(width, inf); VInt visited(width, 0); // Разрешение коллизий (создание "чередующейся цепочки" из нулевых элементов) int markedI = i, markedJ = -1, j; while(markedI != -1) { // Обновим информацию о минимумах в посещенных строках непосещенных столбцов // Заодно поместим в j индекс непосещенного столбца с самым маленьким из них j = -1; for(int j1 = 0; j1 < width; j1++) if(!visited[j1]) { if(matrix[markedI][j1] - u[markedI] - v[j1] < mins[j1]) { mins[j1] = matrix[markedI][j1] - u[markedI] - v[j1]; links[j1] = markedJ; } if(j==-1 || mins[j1] < mins[j]) j = j1; } // Теперь нас интересует элемент с индексами (markIndices[links[j]], j) // Произведем манипуляции со строками и столбцами так, чтобы он обнулился int delta = mins[j]; for(int j1 = 0; j1 < width; j1++) if(visited[j1]) { u[markIndices[j1]] += delta; v[j1] -= delta; } else { mins[j1] -= delta; } u[i] += delta; // Если коллизия не разрешена - перейдем к следующей итерации visited[j] = 1; markedJ = j; markedI = markIndices[j]; } // Пройдем по найденной чередующейся цепочке клеток, снимем отметки с // отмеченных клеток и поставим отметки на неотмеченные for(; links[j] != -1; j = links[j]) markIndices[j] = markIndices[links[j]]; markIndices[j] = i; } // Вернем результат в естественной форме VPInt result; for(int j = 0; j < width; j++) if(markIndices[j] != -1) result.push_back(PInt(markIndices[j], j)); return result; } |
24.12.2010, 17:17 | #7 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 2
|
Готов решить данную проблему. напиши мне на почту и договоримся обо всем
roman.tarabanov (собака) live.ru |
24.12.2010, 17:23 | #8 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 1
|
474322419
если есть возможность, пишите в ICQ) |
24.12.2010, 17:49 | #9 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 2
|
Решение
Код на C++
#include <stdlib.h> #include <time.h> #include <stdio.h> int wpchk(int w, int *wpts) { int i=0; int flg=0; while(wpts[i]!=-1) { if(wpts[i]==w){flg=1;} i++; } if (flg==0) {return 0;} else return 1; } void main() { srand( (unsigned)time( NULL ) ); //int prices[10][10]; int waypoint[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,1}; int way[11]={-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1}; int start=-1; int end=-1; int min; int imin; */// 0 1 2 3 4 5 6 7 8 9 int prices[10][10]={0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //0 0, 0, 2, 9, 8, 0, 0, 0, 0, 0, //1 0, 2, 0, 3, 0, 20,0, 0, 0, 0, //2 0, 9, 3, 0, 7, 4, 0, 0, 0, 0, //3 0, 8, 0, 7, 0, 11,0, 0, 0, 0, //4 0, 0, 20,4, 11,0, 0, 0, 0, 0, //5 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //6 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //7 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, //8 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};//9 printf("Enter № of start location:"); scanf("%i",&start); printf("Enter № of finish location:"); scanf("%i",&end); waypoint[0]=start; int n=0; int w; while(waypoint[n]!=end) { min=0; w=waypoint[n]; for(int i=0;i<10;i++) { if(((min==0)||((prices[w][i]<min)&&(prices[w][i]>0)))&&wpchk(i,waypoint)==0) {min=prices[w][i];imin=i;} } n++; waypoint[n]=imin; } printf("\nThe way is:\n"); int i=0; while(waypoint[i]!=-1) { printf("%i ",waypoint[i]); i++; } getchar(); getchar(); } |
24.12.2010, 17:56 | #10 |
Новичок
Джуниор
Регистрация: 24.12.2010
Сообщений: 1
|
просьба все еще в силе.
P.S. задача комевояжера и почтальона совершенно разнвые вещи. |
|
Похожие темы | ||||
Тема | Автор | Раздел | Ответов | Последнее сообщение |
Реализовать на assembler | Mr.Steroid | Помощь студентам | 0 | 19.11.2010 21:45 |
Как реализовать | revaldo666 | Microsoft Office Access | 2 | 25.10.2010 12:54 |
Помогите реализовать данную задачу | ==Spider== | Работа с сетью в Delphi | 2 | 15.12.2007 11:25 |