VPF::[Delphi] Задача коммивояжера - Форум программистов

batraz

Дата 2.5.2013, 08:23 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 2.5.2013

Репутация: нет
Всего: нет

Помогите, пожалуйста, с задачей.
Найти на взвешенном ориентированном графе локально оптимальное решение разомкнутой задачи коммивояжера методом Монте-Карло.

Poseidon

Дата 6.5.2013, 11:47 (ссылка)

(нет голосов)

Загрузка ...

Delphi developer

Профиль
Группа: Комодератор
Сообщений: 5273
Регистрация: 4.2.2005
Где: Гомель, Беларусь

Репутация: 5
Всего: 133

Если это у тебя курсовая (что очень похоже), то обратись в Центр помощи либо на фриланс
Если решить эту задачу тебе нужно для своего проекта, то выкладывай что уже сделано и рассказывай что не получается. Писать тебе все с 0 тут никто не будет.

--------------------

Если хочешь, что бы что-то работало - используй написанное,
если хочешь что-то понять - пиши сам...

MetalFan

Дата 7.5.2013, 10:25 (ссылка)

(нет голосов)

Загрузка ...

Аццкий Сотона

Профиль
Группа: Комодератор
Сообщений: 3815
Регистрация: 2.10.2006
Где: Moscow

Репутация: нет
Всего: 128

Для домашних заданий, курсовых, существует "Центр Помощи".

Тема перенесена!

--------------------

There are always someone smarter than you...

Governor

Дата 19.2.2015, 19:15 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 45
Регистрация: 13.4.2005
Где: Москва

Репутация: нет
Всего: нет

Решение методом Монте-Карло:

1. Матрицу весов графа загнать в массив matrix
2. Вывод результатов в Memo1

Код


procedure TForm1.Button6Click(Sender: TObject);
var bestplancost: double; // стоимость оптимального маршрута

     ss:string;  // оптимальный маршрут (для вывода)
     pln,optplan:array[1..5] of byte; // тестовый и оптимальный маршруты

    i,j,k,l,m: byte; // счётчики
    s: array [1..5] of double; // массив случайных чисел
    nn:longint; // число испытаний
    bf:double; buf: byte; // буферные переменные

begin
  reloadmatrix; // загрузка матрицы связей
  nn:=StrToInt(Edit1.text); // число испытаний
  bestplancost:=1e10; // стоимость оптимального плана - первое приближение        
 Ti1:=Time; // засекаем время счёта
  randomize; // перезапуск генератора случайных чисел
 for j:=1 to 5 do pln[j]:=j; // первое приближение маршрута
  for i:=1 to nn do
        begin
        for j:=1 to 5 do s[j]:=random;  // генерируем случайные маршруты
        for j:=1 to 5-1 do
         for k:=j+1 to 5 do
          if s[j]>s[k] then
          begin
           bf:=s[j]; s[j]:=s[k]; s[k]:=bf;
           buf:=pln[j]; pln[j]:=pln[k]; pln[k]:=buf;
          end;


        cost:=0;  // подсчёт стоимости случайного маршрута
        for m:=1 to 5 do cost:=cost+matrix[pln[m],pln[m+1]];
        if cost<bestplancost then  // запоминаем лучший случайный маршрут
        begin
         bestplancost:=cost;
         for m:=1 to 5 do optplan[m]:=pln[m];
        end;
       end;

        Ti2:=Time;  // останавливаем секундомер
        tt:=(Ti2-Ti1)*86400; // считаем время
      Memo1.Lines.Add('Обработано вариантов: '+floattostr(nn));
      Memo1.Lines.Add('Время счёта: '+floattostr(tt));
      Memo1.Lines.Add('Стоимость оптимального маршрута (по Монте-Карло): '+floattostr(bestplancost));
      Memo1.Lines.Add('Оптимальный план');  ss:='';
      for m:=1 to 5 do
      begin
       ss:=ss+inttostr(optplan[m])+'>';
      end;
      Memo1.Lines.Add(ss); // выводим оптимальный маршрут


end;

Народ! А кто поделится решением для метода ветвей и границ?

Это сообщение отредактировал(а) Governor - 19.2.2015, 19:33

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Центр помощи \| Следующая тема »