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

Поиск минимального гамильтонова цикла в матрице - C++

Восстановить пароль Регистрация
 
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
09.01.2010, 01:06     Поиск минимального гамильтонова цикла в матрице #1
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
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
    #include <iostream>
    using namespace std;
    #define n 10
    int c[n] ; // номер хода, на котором посещается вершина
    int path[n]; // номера посещаемых вершин
    int v0=2; // начальная вершина
    //Матрица смежности
    int a[n][n]=
    {
 
            0,0,0,0,0,7,0,0,0,0,
 
            0,0,2,0,0,0,5,0,0,0,
 
            0,4,0,11,0,0,0,9,0,0,
 
            0,0,8,0,9,0,0,0,6,0,
 
            3,0,0,6,0,0,0,0,0,9,
 
            0,0,0,0,0,0,4,0,0,2,
 
            0,0,0,9,0,0,0,6,0,0,
 
            0,0,0,0,3,0,0,0,0,0,
 
            0,0,0,0,0,0,0,0,0,6,
 
            0,0,0,0,0,0,0,0,0,0
 
    };
    void prnt(void)
    {
        int p;
        for ( p = 0 ; p<n ; p++)
        printf("%d ", path[p] ) ;
        printf("%d ", path[0] ) ;
        printf("\n") ;
    }
    //подпрограмма нахождения гамильтонова цикла
    int gamilton ( int k)
    {
        int v,q1=0;
        for(v=0; v<n && !q1; v++)
        {
            if(a[v][path[k-1]]||a[path[k-1]][v])
            {
                if (k==n && v==v0 ) q1=1;
                else if (c[v]==-1)
                {
                    c[v] = k ; path[k]=v;
                    q1=gamilton (k+1) ;
                    if (!q1) c[v]=-1;
                } else continue;
            }
        } return q1;
    }
    int main()
    {
        setlocale (LC_ALL, "Russian");
    int j;
    printf("Гамильтонов цикл:\n");
    for(j=0;j<n;j++) c[j]=-1;
    path[0]=v0 ;
    c[v0]=v0;
    if(gamilton (1)) prnt(); else printf("Нет решений\n");
    system ("pause");
    }
Эта программа ищет гамельтонов цикл в матрице. Помогите сделать так чтобы прога искала минимальный гамельтонов цикл...
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
09.01.2010, 01:06     Поиск минимального гамильтонова цикла в матрице
Посмотрите здесь:

Поиск минимального значения C++
C++ Поиск максимального и минимального значения в матрице
Поиск минимального элемента в массиве C++
C++ Поиск минимального элемента в матрице
C++ Поиск максимального и минимального элементов в матрице
Поиск минимального элемента C++
C++ Поиск минимального цикла
C++ В квадратной матрице найти сумму минимального и максимального элементов главной диагонали

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
mikhail2704
39 / 39 / 8
Регистрация: 18.11.2009
Сообщений: 115
09.01.2010, 14:09     Поиск минимального гамильтонова цикла в матрице #2
А почему двумерный массив a[n][n] заполняется как одномерный и нет объявления функций. К тому же использовать глобальные переменнын нежелательно.
Kemsit
 Аватар для Kemsit
4 / 4 / 1
Регистрация: 07.06.2009
Сообщений: 62
09.01.2010, 14:55  [ТС]     Поиск минимального гамильтонова цикла в матрице #3
Цитата Сообщение от mikhail2704 Посмотреть сообщение
А почему двумерный массив a[n][n] заполняется как одномерный и нет объявления функций. К тому же использовать глобальные переменнын нежелательно.
Спасибо за помощь, задача уже решена.
Yandex
Объявления
09.01.2010, 14:55     Поиск минимального гамильтонова цикла в матрице
Ответ Создать тему
Опции темы

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