WWW.REFERATCENTRAL.ORG.UA - Я ТУТ НАВЧАЮСЬ

... відкритий, безкоштовний архів рефератів, курсових, дипломних робіт

ГоловнаІнформатика, Компютерні науки → Задача комівояжера - Реферат

Задача комівояжера - Реферат

15. Символ 'L' на карті тільки один.
Вихід. Для кожного тесту вивести мінімальне число кроків, яке варто пройти Лари, щоб зібрати всі горіхи і повернутися на вихідне місце.
Приклад входу
5 5
L....
#....
#....
.....
#....
5 5
L....
#....
#....
.....
#....
Приклад виходу
8
8
РІШЕННЯ
задача комівояжера, NP повнота, динамічне програмування
Аналіз алгоритму
Класична задача комівояжера. Варто знайти цикл мінімальної довжини, що проходить по усіх вершинах графа. Чи те ж саме що знайти гамильтонов цикл мінімальної довжини. Задача є NP повної і вимагає експонентного часу для її рішення щодо числа вершин у графі.
Нехай n - число вершин у графі. Кожному горіху і початковому місцеві розташування Лари поставимо у відповідність вершину графа. З умови задачі випливає, що n 16. Усі вершини графабудуть попарно з'єднані (зважується евклидова задача комівояжера). Довжина ребра, що з'єднує вершини яким відповідають координати (a, b) і (c, d), дорівнює max( |a - c|, |b - d| ). Матрицю суміжності побудованого графа зберігаємо в двовимірному масиві m.
Можна згенерувати за допомогою функції next_permutation усі можливі перестановки чисел від 1 до n, кожній перестановці буде відповідати гамильтонов цикл. Шукаємо мінімальне значення серед усіх довжин таких циклів. Приведений алгоритм вимагає n! часу, що для n = 16 занадто багато (варто перебрати 16! = 20922789888000 варіантів).
Використовуючи метод динамічного програмування, можна вирішити задачу з оцінкою O(2n) по використовуваній пам'яті і O(n2 * 2n) за часом роботи алгоритму. При n = 16 варто перебрати 16777216 варіантів, що реально за часом.
Для непорожньої підмножини S {1, 2, …, n} і кожної вершини i S визначимо dp(S, i) як довжину найкоротшого шляху, що починається в першій (початкової) вершині, що проходить по усіх вершинах з безлічі S {i} у довільному порядку і закінчується у вершині i. Тоді мають місце рівності:
dp({1, i}, i) = m[1][i],
dp(S, i) = (dp(S {i}, j) + m[j, i] )
Значення dp(S, i) перераховуємо динамічно, запам'ятовуючи їх у масиві dp. Гамильтонов цикл мінімальної довжини дорівнює
(dp({1, 2, ..., n}, j) + m[j, 1] )
Приклад
У першому тесті досить пройти вниз острова (4 кроки), зібравши по шляху всі горіхи, і піднятися нагору до вихідного місця (ще 4 кроки).
Реалізація алгоритму
Визначимо перемінну INF, умовно рівну нескінченності, максимально можливе число вершин у графі MAX і масив dp, у якому будемо зберігати динамічно перелічувані значення dp(S, i). Кожна підмножина S будемо зберігати у виді числа, у якому i - ий біт дорівнює 1, якщо вершина з номером i в ньому є присутнім, і нулю інакше. Наприклад, при n = 5 підмножина {1, 4, 5} кодується числом 110012 = 25.
#define INF 100000000
#define MAX 16
int dp[1<Карту острова зберігаємо в символьному масиві mas, координати горіхів і початкового положення Лари - у масивах x і y, матрицю суміжності графа - у масиві m.
char mas[21][21];
int x[21],y[21], m[21][21];
Функція solve обчислює значення dp(S, last), де безліч S кодується цілим числом mask. При цьому S {last} дорівнює mask ^ 1<<(last - 1). Далі перебираємо всі i, i S {last} і шукаємо мінімальне значення res серед dp(S {last}, i) + m[i, last]. Перемінна res указує на осередок dp[mask][last], так що зі зміною res змінюється і саме значення dp[mask][last].
int solve(int mask,int last)
{
int i,cr;
int &res=dp[mask][last];
if(res < 0)
{
mask^=1<<(last-1);
res=INF;
for(i=1; i<=nuts; ++i)
if(mask&(1<<(i-1)))
{
cr=solve(mask,i)+m[i][last];
if(cr}
}
return res;
}
Основний цикл програми. Читаємо дані острови в масив mas, заносимо координати горіхів у масиви x і y. Початкове місце розташування Лари зберігаємо в (x[1], y[1]).
while(scanf("%d %dn",&xx,&yy) == 2)
{
for(i=0;inuts=1;
for(i=0;ifor(j=0;jif (mas[i][j] == 'L')
{
x[1] = i; y[1] = j;
} else
if (mas[i][j] == '#')
{
x[++nuts] = i; y[nuts] = j;
}
Число вершин графа, рівне кількості горіхів на острові плюс один (початковий стан Лари), зберігається в перемінної nuts. Якщо горіхів на острові ні, то виводимо 0.
if (nuts == 1)
{
printf("0n"); continue;
}
Будуємо матрицю суміжності графа m. Обчислюємо довжини ребер.
memset(m,0x3F,sizeof(m));
for(i=1;ifor(j=i+1;j<=nuts;j++)
m[i][j] = m[j][i] = max(abs(x[i] - x[j]), abs(y[i] - y[j]));
Споконвічно значення dp(S, i) невідомі, покладемо їх рівними деякому негативному числу. При цьому dp({1}, 1) = 0 (мінімальний шлях з першої вершини в неї ж без відвідування інших вершин дорівнює нулю). У перемінної total зберігаємо шукану мінімальну довжину циклу.
memset(dp,-1,sizeof(dp));
dp[1][1] = 0;
total = INF;
n2 = 1<Обчислюємо гамильтонов цикл мінімальної довжини і друкуємо результат. Значення n2 - 1 відповідає безлічі {1, 2, 3, ..., nuts}. Обчислюємо мінімум серед усіх значень dp({1, 2, ..., nuts}, i) + m[i, 1], 2 i nuts.
for(i=2;i<=nuts;i++)
{
temp = solve(n2-1,i) + m[i][1];
if(temp < total) total = temp;
}
printf("%dn",total);
}
Використана література
1. Кузнецов О.П., Адельсон-Вельский Г.М. Дискретная математика для инженера. - М.: Энергоатомиздат, 1988. - 480с.
2. Грэй П. Алгебра, логика и базы данных: Пер. с англ. - М.: Машиностроение, 1989. - 260 с.
3. Оре О. Теория графов: Пер. с англ. - М.: Наука, 1968. - 310 с.
4. Форд Л., Фалкерсон Д. Потоки в сетях: Пер. с англ. - М.: Мир, 1966.-288 с.
5. Марков А.А., Нагорный Н.И. Теория алгоритмов. - М.: Наука, 1984.-300 с.
6. Лавров И.А., Максимова Л.Л. Задачи по теории множеств, математической логике и теории алгоритмов. - М.: Наука, 1975.- 240 c.
7. Кэррол Л. История с узелками: Пер. с англ. - М.: Мир, 1973. - 408 c.
Loading...

 
 

Цікаве