ЗЫ Мне посоветовали читать книжки по теории графов
| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Задача коммивояжера |
| Автор: Graf Zeppelin 19.4.2004, 14:49 |
| На практике столкнулся с такой проблемой: есть сверлильный станок для него существуе задание просверлить N дырок и вернутся в исходную позицию. Координаты дырок известны, нужно минимизировать пройденный путь. ЗЫ Мне посоветовали читать книжки по теории графов |
| Автор: Alex101 19.4.2004, 16:27 |
| Если на плоскости, то это типичная задача коммивояжера. Оптимизировать можно, отсекая лишние ветви, если уже на i-том шаге путь станка больше какого-то полученного. А вообще посмотри метод Литтла. Вроде как он позволяет решать задачу для N (кол-ва городов) в районе 30-50... |
| Автор: Graf Zeppelin 25.4.2004, 11:01 |
| Плиз дайте ссылку. |
| Автор: Maverick 6.5.2004, 08:52 |
| http://alglib.manual.ru/ Там только блок-схема была в прошлый раз.... но на безрыбье.... |
| Автор: Lem03 6.5.2004, 13:45 |
| Можно использовать генетический алгоритм. Поищи "Konstantin Boukreev" , он написал программу на эту тему и выложил исходник. Правда генетические алгоритмы довольно медленные. |
| Автор: Graf Zeppelin 7.5.2004, 23:32 |
| http://www.codeproject.com/cpp/tspapp.asp Буду разбириться |
| Автор: Golod 8.5.2004, 08:54 |
| Алгоритм решения задачи комивояжера: (алгоритм жадный, так что он может давать оптимальное решение, а может и не давать, но не жадного алгоритма нет т.к. задача NP-полна) 1)Начинаем строить цикл, включив в него ребро наименьшего веса; 2)Среди рёбер, инцедентных концам нашего ребра, находится ребро наименьшего веса(весом будет расстояние между дырками) и тоже включается в цикл; 3)Если построили цепь, то просматриваем рёбра, инцедентные концам цепи, и не образующие цикл с уже включёнными рёбрами, выбираем наименьшее и включаем; 4)Пункт 3 повторяем, пока не закончатся вершины, а потом соединяем последнюю и первую вершины. Вот и весь алгоритм. Его удобнее всего реализовать методом расстановки меток. |
| Автор: Crot 13.5.2004, 05:59 |
| А скажите, задача коммивояжёра определена для полного графа, или для любого? |
| Автор: Guest 13.5.2004, 10:20 |
| Hello, ALL ! Если путь замкнутый, то видимо для любого. В случае с печ-ми платми, прирост производит-ти станка при замене пути, может достичь ~30 % (где вычитал не помню, давно это было) Реальный экономический эффект, без "большого" напряга :-) Когда-то я пробовал решать эту задачу по алгоритму, схожему с предложенным Golod-ом, но с некоторым отличием. Внедрить, увы не удалось, т к на тот момент все производства "дохли" ... :-( Попробуйте, может у вас что-то получится. Итак, алгоритм: 1) в составленной матрице из _расстояний_ между точками выбираем самую "дальнюю" точку (можно по макс расст или по сумме всех расст. Я брал 1-й вар ) 2) вкл в маршрут _две_ ближайшие точки 3) добавить в маршрут точку с наименьшей ценой, т е включение которой даёт _наименьшее_ приращение длинны маршрута. Включение этой точки производится перебором включением во все рёбра уже имеющегося маршрута. Есс-но выбирается вставка в то ребро, где приращение маршрута наименьше. 4) ... и так далее, пока не будут вставлены в маршрут все точки. Была и вторая часть, оптимизатор, но сейчас точно я его не помню :-( Если найду, кину. Эх, давно это было ... :-( Удачи ! |
| Автор: maxim1000 13.5.2004, 11:37 |
| кстати, а сколько отверстий? (приблизительно) |
| Автор: Graf Zeppelin 14.5.2004, 11:22 | ||
~100 в худшем случае p.s. уже потихоньку врубаюсь в книжку Кристофидеса "Графы. Алгоритмический подход" |
| Автор: Гость_Eugene 14.5.2004, 11:29 |
В догонку  Как вариант: п 2 можно изменить на включение 2-х или 3-х самых дальних точек, что-бы охватить сразу _весь_ периметр печатной платы. Этот вариант у меня тоже был. Экспериментируйте... Удачи ! |
| Автор: LSD 14.5.2004, 20:07 | ||
Решение есть если граф Гамильтонов, задача определения являеся ли граф Гамильтоновым NP полная, но полный граф всегда Гамильтонов. |
| Автор: achmed 14.5.2004, 20:18 |
| в догонку могу посоветовать книгу Мину, тоже по графам. |
| Автор: HalkaR 17.5.2004, 20:57 |
| http://algolist.manual.ru Вобщем там есть достаточно простые методы. Хотя там нет методов ветвей и границ. |
| Автор: Ruff18 11.6.2004, 17:15 |
| [color=darkblue][/color] А где можно качнуть решение задачи о комивояжёре на С++ или Paskale ?  |
| Автор: Graf Zeppelin 25.6.2004, 23:06 |
| /* Решение Задачи Коммивояжера методом Монте-Карло Лебедев Сергей 21.06.2004 */ #include <string.h> #include <stdlib.h> #include <conio.h> #include <stdio.h> #include <time.h> #include <math.h> #include <alloc.h> #include <graphics.h> int x[255],y[255]; int minimum(long dis[1000],int n) { unsigned long i,tmp,f; tmp=800; for (i=0;i<n;i++) { if (dis[i]<=tmp) { f=i; tmp=dis[f]; } } return(f); } long viability(char *string,char n) { char i; long viability=0; viability=max(abs(x[string[0]]-x[string[n-1]]),abs(y[string[0]]-y[string[n-1]])); for (i=0;i<n-1;i++) { viability+=max(abs(x[string[i]]-x[string[i+1]]),abs(y[string[i]]-y[string[i+1]])); } return(viability); } void inversion(char *string, char n) { char i,j,k,*tmp; i=random(n); j=random(n); tmp=malloc((abs(i-j)+1)*sizeof(char)); for (k=min(i,j);k<=max(i,j);k++) { *(tmp+k-min(i,j))=*(string+k); } for (k=min(i,j);k<=max(i,j);k++) { *(string+k)=*(tmp+max(i,j)-k); } free(tmp); } void main(void) { long dis[255]; char string[255],elite[255],chk[255]; char i,j,k,l,n=100; unsigned int s=0; int graphdriver,graphmode; detectgraph(&graphdriver,&graphmode); initgraph(&graphdriver,&graphmode,"C:\\TC\\BGI"); randomize(); clrscr(); cleardevice(); for (i=0;i<n;i++) { x[i]=random(getmaxx()); y[i]=random(getmaxy()); } for (l=0;l<n;l++) { chk[l]=0; } l=0; //LazyFrog-algorithm for (j=1;j<n;j++) { for (i=0;i<n;i++) { if ((chk[i]!=1)&&(i!=l)) { dis[i]=max(abs(x[i]-x[l]),abs(y[i]-y[l])); } else { dis[i]=2000; } } chk[l]=1; k=minimum(dis,n); setcolor(RED); string[j]=k; l=k; } string[0]=0; for (i=0;i<n;i++) { putpixel(x[i],y[i],GREEN); } for (i=0;i<n;i++) { // string[i]=i; elite[i]=string[i]; } do { for (i=0;i<n;i++) { string[i]=elite[i]; } inversion(&string,n); if (viability(&string,n)<viability(&elite,n)) { for (i=0;i<n;i++) { elite[i]=string[i]; // printf("%3d",elite[i]); } // printf(": Elite\n"); s=0; } s++; }while (s<pow(2,15)); printf("%d \nPress Any Key",viability(&elite,n)); getch(); cleardevice(); for (i=0;i<n-1;i++) { setcolor(BLUE); line(x[elite[i]],y[elite[i]],x[elite[i+1]],y[elite[i+1]]); } line(x[elite[0]],y[elite[0]],x[elite[n-1]],y[elite[n-1]]); for (i=0;i<n;i++) { putpixel(x[i],y[i],GREEN); } getch(); closegraph(); } |
| Автор: neutrino 31.7.2004, 20:46 |
| Я писал прогу для генетиков, как раз решение той же задачи, только на генах в ДНК. |
| Автор: IgorMAN 14.8.2006, 09:09 |
| Добрый день уважаемые програмисты!!! А есть у кого-нибудь решение задачи коммивояжера методом ГА в ручную(на бумаге), с 4 или 5 городами??? Если есть то скиньте на [email protected] Пожалуйсто не игнорируйте мое сообщение, от него может зависеть будущее моего обучения. |
| Автор: Magister Y0da 12.1.2007, 22:46 |
| Graf Zeppelin, а можешь выложить скаченное http://www.codeproject.com/cpp/tspapp.asp? |
| Автор: DAGON 17.5.2007, 14:12 |
| Народ плиз есть у когонить листинг жадного алгоритма на паскеле или ВБ если есть плиз скиньте на мыло [email protected] Буду очень благодарен |