Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.67/30: Рейтинг темы: голосов - 30, средняя оценка - 4.67
0 / 0 / 1
Регистрация: 31.03.2014
Сообщений: 26
1

Задача коммивояжера методом динамического программирования

01.10.2014, 10:20. Просмотров 6025. Ответов 5
Метки нет (Все метки)

Помогите пожалуйста переделать коммивояжера методом динамического программирования.
Пусть n - это количество вершин графа. Тогда в цикле n-1 выбирается самое короткое еще не выбранное ребро при условии, что оно не образует цикла с уже выбранным. Для проверки того, что новое ребро не образует цикла с уже выбранными, каждую вершину i окрашивают в отличный от других цвет i. При выборе очередного ребра, скажем (i, j), где i и j имеют разные цвета, вершина j и все, окрашенные в ее цвет (т. е. ранее с ней соединенные) перекрашиваются в цвет i. Таким образом после выбора n-1 ребер все вершины получают один цвет.
Алгоритм Прима:
1. (ввод). Ввести матрицу расстояний D={dij}, i,j=1,…,n.
2. (инициализация). Приписать разные цвета всем вершинам: coli:=i; длина дерева L:=0.
3. (общий шаг). В цикле по k:=1 to n-1 do найти ребро минимальной длины между вершинами разного цвета: пусть это ребро (i,j).
Запомнить результат: res1[k]:=i; res2[k]:=j;
Перекрасить вершины: I1:=col[i]; j1:=col[j].
В цикле по m:=1 to n do
If col[m]=j1 then col[m]:=i1;
Нарастить длину дерева: L:=L+d[i,j].
Конец цикла по k.
4.(вывод). Вывести res1, res2.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#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();
}
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
01.10.2014, 10:20
Ответы с готовыми решениями:

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

Задача коммивояжера методом локального поиска
Всем доброго времени суток, кто обратил внимание на сия сообщение) Возникла необходимость...

Игра Ним методом динамического программирования
добрый день помогите решить задачу методом динамического программирования. Игра Ним с одной кучей...

Задача коммивояжера
Всем привет! Необходимо решить задачу коммивояжера с помощью жадных алгоритмов. Разбирался вообще...

5
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
01.10.2014, 22:44 2
алгоритм Прима строит минимальное остовное дерево, а не кратчайший гамильтонов цикл. Т.е. алгоритм Прима не имеет никакого отношения к задаче коммивояжера. Поэтому непонятно как переделывать
0
0 / 0 / 1
Регистрация: 31.03.2014
Сообщений: 26
03.10.2014, 09:47  [ТС] 3
А вот это? (паскаль)

{Программа решения задачи коммивояжера методом лексического перебора.}
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
Uses CRT;
Label Out;
Const
N=8;
Var
C: array [1..N,1..N] of word; {Матрица расстояний}
Tour, P: array [1..N] of word; {Оптимальный и текущие туры}
l, s: word;
i, j, k, min, ind: byte;
All: boolean; {Признак окончания перебора}
Graph: text;
Begin
ClrScr;
{Ввод данных}
Assign(Graph,'D:\matr.in');
Reset(Graph);
TextColor(14);
WriteLn('=========================ЗАДАЧА КОММИВОЯЖЕРА (Перебор)=========================');
WriteLn('Матрица смежности:');
WriteLn('========================================= ======================================');
For i:=1 To N Do For j:=1 To N Do Read(Graph, C[i,j]);
For i:=1 To N Do
Begin
For j:=1 To N Do Write(C[i,j],' ');
WriteLn;
End;
{Инициализация}
All:=False; {Перебраны не все варианты}
l:=MaxInt; {Оптимальный тур неизвестен}
For i:=1 To N Do P:=i; {Строим первый тур}
Repeat
{Вычисляем его длину}
s:=0;
For i:=1 To N-1 Do s:=s+C[P,P[i+1]];
s:=s+C[P[n],P[1]];
{Полагаем первый тур текущим}
If l>s Then
Begin
Tour:=P;
l:=s;
End;
{Генерируем все (N-1)! перестановок}
For i:=N DownTo 3 do
Begin
If P<P[i-1] Then continue;
min:=N+1;
k:=P[i-1];
{Ищем миним. число из тех, что больше k и правее}
For j:=i To N Do If (P[j]>k) and (P[j]<min) Then
Begin
min:=P[j];
ind:=j;
End;
{Рокировка min и k}
P[i-1]:=min;
P[ind]:=k;
{Элементы на местах от i до N упорядочиваем по возрастанию}
For j:=i To N-1 Do
Begin
min:=N+1;
For k:=j To N Do If min > P[k] Then
Begin
min:=P[k];
ind:=k;
End;
k:=P[j];
P[j]:=min;
P[ind]:=k;
End;
GoTo out;
End;
{Проверяем перебраны ли все перестановки}
All:=true;
Out:
Until All;
{Если перебраны все перестановки, то выдаем оптимальный тур}
WriteLn('========================================= ======================================');
Write('Минимальный тур: ');
For i:=1 To N Do Write(Tour,'-');
Write('1');
WriteLn(' имеет длину ',l);
WriteLn('========================================= ======================================');
Close(Graph);
ReadKey;
END.
0
Мой лучший друг-отладчик!
165 / 165 / 30
Регистрация: 24.06.2012
Сообщений: 662
Записей в блоге: 5
03.10.2014, 10:39 4
Прим никак не подходит для задачи коммивояжера. Вообще, нужно находить Гамильтонов цикл, что в настоящее время найти ТОЧНЫЙ ответ за полиномиальное время никому не удалось. Есть конечно метод перебора, но это есть беда. Есть перебор с использованием битовых масок, но это тоже перебор. Ну и есть всякие оптимизации-эвристики, которые не дают точный ответ: жадняк какой-нибудь, метод отжига например неплохие результаты.
0
0 / 0 / 1
Регистрация: 31.03.2014
Сообщений: 26
09.10.2014, 01:42  [ТС] 5
Так как же сделать через Гамильтоновй цикл?
0
219 / 164 / 47
Регистрация: 17.07.2012
Сообщений: 587
09.10.2014, 02:09 6
Shelby_ph, динамикой dp[mask][last] - кратчайшее расстояние чтобы побывать в городах, которые есть в маске mask и при этом находиться в городе last. переход - перебираешь в какой город идешь. если ты не слышал про ДП, то ниче не поймешь xD.
0
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
09.10.2014, 02:09

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

Основы динамического программирования
Добрый день! Я начал изучать динамическое программирование, но что-то не особо получается. В общем...

Задача коммивояжера - выход за пределы массива
Бьет ошибку! Я так понимаю где-то выход за пределы массива! Народ гляньте кто, а то я уже ничего не...

Задача коммивояжера (метод ветвей и границ)
Написать программу для решения задачи коммивояжёра с помощью метода ветвей и границ. Интерфейс...

Как считать а степени н применяя принцип динамического программирования?
Как считать а^n применяя принцип динамического программирования?


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
6
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.