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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
*krIsTiNa*
0 / 0 / 0
Регистрация: 19.01.2011
Сообщений: 46
#1

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

01.11.2011, 11:02. Просмотров 450. Ответов 0
Метки нет (Все метки)

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++
Задана окружность, с помощью координат центра и радиуса. Определить, лежит ли она полностью в первой четверти. 1вывожу окружность и ...

Как процедуру в Паскале реализовать, как функцию в с++? - C++
Здравствуйте! Есть код на Паскале. Нужно процедуру реализовать в С++ как функцию. Возможно ли в моем случае? Попробовал по-всякому, но у...

Как реализовать? - C++
добрый вечер, прораммисты! Помогите, пожалуйста, советом. Есть таблица в excel, которая содержит информацию о ТО транспорта(водитель,...

как реализовать!!!! - C++
Комендант крепости выходит из центрального помещения и проверяет как солдаты дежурят на постах. При этом он, проходя все посты, не проходит...

Как реализовать в c++ - C++
// ConsoleApplication2.cpp : Defines the entry point for the console application. // #include &quot;stdafx.h&quot; #include &quot;math.h&quot; ...

Как реализовать структуру - C++
Доброго времени суток. Никак не могу скомпиллировать эту структуру. struct tree{ char inf; list&lt;tree*&gt; lt;}; Выдает вот эти ошибки ...

Как реализовать цикл - C++
Посчитать сумму s=cos(x+2*k)/(pow(k,3)) если x меряется от-1 до 1 с шагом 0.1(к=8)

Как реализовать таблицу? - C++
Всем Доброго времени суток. Как сделать таблицу в с++ ? Заранее спасибо!)

Многопоточность на C++. Как реализовать? - C++
Здравствуйте! Имеется такая задача: Написать программу на С/С++, которая после запуска считает в отдельном потоке от 0 до 100, при этом...

Не знаю как реализовать - C++
Итак, пользователь может ввести, а может и ничего не вводить, но програма выводит число через каждые sleep(500) как реализировать...

Как можно реализовать ? - C++
У меня есть код на С++ для ввода и вывода комплексных чисел #include &lt;cstdlib&gt; #include &lt;iostream&gt; #include &lt;math.h&gt; using namespace...

Как реализовать tolower()? - C++
Подскажите, пожалуйста, как применить функцию tolower() к переменной типа vector&lt;int&gt;::size_type Вот фрагмент кода, приводящий к ошибке:...


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

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

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