Форум программистов, компьютерный форум, киберфорум
Наши страницы

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 11, средняя оценка - 4.82
kristi1
10 / 10 / 1
Регистрация: 07.03.2010
Сообщений: 465
#1

Муравьиный алгоритм - C++

21.11.2013, 09:25. Просмотров 2046. Ответов 0
Метки нет (Все метки)

Здравствуйте!
Имеется задание:
Решить задачу коммивояджера методом Марко Дориго (3 способ муравьиного алгоритма). Теоретическая часть тут:
http://vuz.exponenta.ru/PDF/MPEI/c1202/8690.pdf
Был написан подобный набросок программы:
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
#include <iostream>
using namespace std;
const int inf=1E9,NMAX=16;
int n,i,j,k,m,temp,ans,d[NMAX][NMAX],t[1<<NMAX][NMAX];
bool get(int nmb,int x)
{ return (x&(1<<nmb))!=0; }
int main()
{
 cin >>n;
 for (i=0;i<n;++i)
  for (j=0;j<n;++j) cin>>d[i][j];
 t[1][0]=0; m=1<<n;
 for (i=1;i<m;i+=2)
  for (j=(i==1)?1:0;j<n;++j)
  {
   t[i][j]=inf;
   if (j>0 && get(j,i))
   {
    temp=i^(1<<j);
    for (k=0;k<n;++k) 
     if (get(k,i) && d[k][j]>0) t[i][j]=min(t[i][j],t[temp][k]+d[k][j]);
   }
  }
 for (j=1,ans=inf;j<n;++j)
  if (d[j][0]>0) ans=min(ans,t[m-1][j]+d[j][0]);
 if (ans==inf) cout<<-1; else cout<<ans;
}
Верно ли сделано?
Есть подозрение, что что-то не так(
Ну либо покажите другие варианты решения. Спасибо
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
21.11.2013, 09:25
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Муравьиный алгоритм (C++):

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i&gt;=0; i--) { str = (x&amp;1 == 1) ? '1' : '0'; x = x &gt;&gt;...

Волновой алгоритм (алгоритм Ли) - C++
Здравствуйте! У кого-нибудь есть реализованный волновой алгоритм (алгоритм Ли) ? Дело в том, что я игрушку захотел написать (что-то...

Муравьиный алгоритм - PHP
У меня стояла задача написать утилиту поиска кратчайшего маршрута проходящего через указанные точки хотя бы по одному разу с последующим...

Муравьиный алгоритм - Алгоритмы
Привет. Реализовываю данный алгоритм. Написал пока часть для одного муравья (обернуть циклом, считающим муравьев, позже не проблема):...

0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
21.11.2013, 09:25
Привет! Вот еще темы с ответами:

Муравьиный алгоритм, ACO - Matlab
Добрый день! Помогите пожалуйста с муравьиным алгоритмом. Есть исходник в с++ надо перегнать его в матлаб или сделать приблизительный. ...

Задача коммивояжера, муравьиный алгоритм - Java SE
Здраствуйте. Написал код для решения задачи комивояджера. в Силу того, что только учусь, пожалуйста укажите на ошибки: import...

Муравьиный алгоритм в задаче Коммивояжера - Delphi
Здравствуйте. Нужна помощь в представлении типов для решения задачи коммивояжера муравьиным алгоритмом. Решаю задачу 2умя...

Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм - Pascal
Линейный алгоритм, Алгоритм с ветвлениями, Циклический алгоритм Линейный алгоритм 1. Объясни, что будет напечатано программой Program...


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

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

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