Форум программистов, компьютерный форум CyberForum.ru

как реализовать на с++ - C++

Восстановить пароль Регистрация
 
*krIsTiNa*
0 / 0 / 0
Регистрация: 19.01.2011
Сообщений: 46
01.11.2011, 11:02     как реализовать на с++ #1
Pascal
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
procedure KOMMI(i);
 begin
  for y Є ЗАПИСЬ[X[i-1]] do
  if cost + A[X[i-1], y] < OptCost then
   if (i = n+1) AND (y = k) then
    begin OptX:=X; OptCost:= cost + A[X[i-1],y] end
   else if DOP[y] then
    begin 
     X[i]:=y; DOP[y]:= ложь;
     cost:=cost + A[X[i-1], y];
     KOMMI(i+1);
     DOP[y]:= истина; cost:=cost — A[X[i-1], y];
    end;
 end; {KOMMI }
 
 
begin { основная программа }
 for v Є V do DOP[v]:=истина;
 X[1]:=k; { k — произвольная }
 DOP[k]:= ложь;
 cost:=0; OptCost:= +бесконечность(большое число);;
 KOMMI(2);
end.
ЗАДАЧА КОММИВОЯЖЕРА
Пусть заданы конечное множество C городов, целые положительные расстояния A(c1,c2) для каждой пары городов c1,c2.
Требуется найти маршрут минимальной длины, проходящий через все города ровно один раз и возвращающийся в исходный пункт.
Это — задача на минимум. Карта представляется графом, ребрам которого приписаны веса. Из всех гамильтоновых циклов (это полный граф, в нем существуют гамильтоновы циклы) в этом графе нужно выбрать цикл минимальной длины. Длина определяется естественным образом — как сумма расстояний между городами, входящими в маршрут. Можно поступить просто — сгенерировать алгоритмом с возвратом все циклы и среди них выбрать минимальный. Однако немного изменив общую схему алгоритма с возвратом, можно добиться того, что возвраты будут происходить значительно раньше, и решение будет найдено быстрее.
Итак, задача на минимум — среди всех допустимых объектов ищется минимальный.
Каждому решению( и полному, и частичному ) приписывается стоимость — ее еще называют целевой функцией. Будем обозначать ее cost.
При продолжении решения стоимость может только увеличиваться:
cost(< X(1), … , X(i-1) >)<= cost(< X(1), … , X(i-1), X(i)>).
Для задачи коммивояжера целевой функцией, удовлетворяющей такому условию, будет
cost(< X(1), … , X(i)>)=A(X(1), X(2))+…+ A(X(i-1), X(i)).
Очевидно, что ее значение будет увеличиваться при удлинении маршрута.
Идея алгоритма:
1. Находим первое решение и запоминаем его стоимость в OptCost.
2. Пусть < X(1), … , X(i)> — текущее частичное решение. Прежде, чем пытаться продолжать его дальше, проверим, имеет ли смысл это делать. Если cost(< X(1), … , X(i)>) >= OptCost,
то любое его продолжение будет заведомо больше текущего минимального решения. Производим возврат к предыдущему частичному решению < X(1), … , X(i-1)>.
Таким образом, произведя «досрочный» возврат, мы избавляем себя от генерации всех заведомо неоптимальных продолжений, т.е. обрубаем целое поддерево на дереве поиска.
АЛГОРИТМ. {Нахождение гамильтоновых цикла min длины}
Данные: Граф G=<V,E>, представленный списками ЗАПИСЬ[v], матрица весов A[u,v].
Результаты: Печать min гамильтонова цикла.
Переменные ЗАПИСЬ, X, cost, OptX, OptCost, DOP — глобальные.

Добавлено через 16 минут
вот мой алгоритм на паскале
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
const
 n0=100; {вершины}
 inf=32000;{бесконечность}
var
 m:integer; {рёбра}
 n:byte; {вершины}
 A:array[1..n0,1..n0] of real; {матрица весов}
 DOP:array[1..n0] of boolean; {допустимость вершины}
 X,OptX:array[1..n0] of byte; {маршруты}
 Cost,OptCost:real; {стоимости}
 r:real;
 i,j,k:byte;
 
procedure path(i:byte);
var u,j,v:byte;
begin
  for u:=1 to n do
    if (A[X[i-1],u]<inf) AND (Cost+A[X[i-1],u] < OptCost) then
      begin
        if (i=n+1) AND (u=1) then {новый минимум}
          begin
            for j:=1 to n do OptX[j]:=X[j];
            OptCost:=Cost+A[X[i-1],u];
          end
        else if DOP[u] then {продолжаем текущий маршрут}
          begin
            X[i]:=u; DOP[u]:=false;
            Cost:=Cost+A[X[i-1],u];
            path(i+1);
            {возврат, удаляем u из текущего маршрута}
            DOP[u]:=true;
            Cost:=Cost-A[X[i-1],u];
          end;
      end;
end;
 
BEGIN {main}
  for i:=1 to n0 do
  for j:=1 to n0 do
    A[i,j]:=inf;
 
  for i:=1 to n0 do
    begin
      DOP[i]:=true;
      X[i]:=0;
      OptX[i]:=0;
    end;
  Cost:=0; OptCost:=inf;
 
  Write('Vvedite kolvo vershin n= '); readln(n);
  Write('Vvedite kolvo reber m= '); readln(m);
  for i:=1 to m do
  begin
    Write('Vvedit cherez probil vershini i ves ',i,' rebra: '); Readln(j,k,r);
    A[j,k]:=r;
    A[k,j]:=r;
  end;
  X[1]:=1; DOP[1]:=false;
  path(2);
  if OptCost< inf then
  begin
    Writeln('OptCost', OptCost:5:2);
    for i:=1 to n do
      write(OptX[i],' ');
    writeln;
  end
  else
    writeln('No solution');
 readln;
END.
В программе граф неориентированный неполный. Заодно проверяется существование гамильтонова цикла.
Если граф полный, то число ребер m=n*(n-1)/2 и убирается проверка на существование ребра (A[X[i-1],u]<inf).
inf -бесконечность - число, большее длины самого дорогого пути.
Cost, OptCost - стоимости текущего и оптимального маршрута,
X, OptX - текущий и оптимальный маршрут.
DOP - допустимость вершины. Если вершина включена в текущий маршрут, то false.
path - рекурсия, которая осуществляет ветвление.

 Комментарий модератора 
Используйте теги форматирования кода
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2011, 11:02     как реализовать на с++
Посмотрите здесь:

C++ как реализовать!!!!
C++ Как реализовать?
Как такое реализовать? C++
незнаю как вывести полное решение для задачки.смысл улавливаю, а как реализовать - туплю C++
Не знаю как реализовать C++
C++ Указатель на имя файла как аргумент функции. Как реализовать?
Как можно реализовать ? C++
C++ Необходимо реализовать шаблонный класс Array, и грамотно реализовать push_back

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 05:27. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru