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

поиск длины пути - C++

Восстановить пароль Регистрация
 
Surf_Rider
0 / 0 / 0
Регистрация: 15.05.2011
Сообщений: 22
13.09.2012, 08:32     поиск длины пути #1
Всем доброго утра
Ребята подскажите пожалуйста алгоритм
дана матрица расстояний n*n, в ячейках расположены расстояний между i и j объектами
нужно сформировать массив который будет хранить сумму расстояний между всеми возможными путями
например, даны 3 объекта(1,2,3), расстояния между ними, нужен массив который хранит пути 123, 132, 231, 213, 312, 321

Заранее благодарю
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.09.2012, 08:32     поиск длины пути
Посмотрите здесь:

C++ Поиск пути
C++ Поиск пути в лабиринте
C++ Поиск пути
C++ Поиск оптимального пути в графе
Нахождение в орграфе пути максимальной длины от 1-ой вершины до последней C++
Поиск кратчайшего пути в графе C++
Поиск пути C++
C++ Поиск пути

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
zitxbit
Master C/C++
 Аватар для zitxbit
86 / 738 / 75
Регистрация: 11.04.2012
Сообщений: 971
14.09.2012, 10:30     поиск длины пути #2
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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <stdio.h>
#include <conio.h>
#include <memory.h>
 
#include <iostream>
 
#define MAX 10
 
typedef struct Route
{
    int* p;
    int count;
    int length;
} ROUTE;
 
using namespace std;
 
ROUTE& addtop(ROUTE* route, int top)
{
    ROUTE* rdest = new ROUTE;
    int *p = new int[MAX], pos = route->count;
    memcpy((void*)p, (void*)route->p, sizeof(int) * pos);
    p[pos] = top; rdest->p = p; rdest->count = pos+1;
 
    return *rdest;
}
 
int gettop(ROUTE* route)
{
    int len = route->count, top = 0;
    return len > 0 && ((top =
        route->p[len-1]) >= 0) ? top : -1;
}
 
bool visited(ROUTE* route, int top)
{
    for (int i = 0; route->p[i] >= 0; i++)
         if (route->p[i] == top) return true;
    return false;
}
 
const int M[MAX][MAX] = { { 0, 0, 2, 0, 0, 7, 0, 0, 0, 0 },
                          { 8, 0, 0, 0, 0, 4, 6, 0, 0, 0 },
                          { 0, 0, 0, 6, 9, 0, 0, 0, 0, 0 },
                          { 0, 0, 0, 0, 0, 0, 0, 5, 0, 5 },
                          { 0, 0, 0, 1, 0, 2, 0, 0, 0, 0 },
                          { 6, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
                          { 0, 0, 0, 0, 0, 0, 0, 0, 3, 0 },
                          { 0, 0, 0, 0, 8, 0, 4, 0, 0, 0 },
                          { 0, 0, 0, 0, 0, 0, 0, 9, 0, 7 },
                          { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 } };
 
int main()
{
    int start = 1, finish = 2;
 
    ROUTE* routes = new ROUTE[256];
    memset((void*)routes, 0x00, sizeof(ROUTE) * 256);
 
    routes[0].p = new int[MAX];
    routes[0].p[0] = start; routes[0].count = 1;
 
    for (int i = 0, r = 1; routes[i].count > 0; i++)
    {
        int top = gettop(&routes[i]);
        if (top >= 0 && top != finish)
        {
            for (int j = 0; j < MAX; j++)
                 if (M[top][j] > 0 && !visited(&routes[i],j))
                 {
                     ROUTE target = addtop(&routes[i], j);
                     if (target.p != NULL) routes[r++] = target;
                 }
        }
 
        else {
            for (int q = 0; routes[i].p[q] >= 0; q++)
                 cout << routes[i].p[q] << " ";
            
            int len = 0;
            for (int t = 1; routes[i].p[t] >= 0; t++)
                len+=M[routes[i].p[t-1]][routes[i].p[t]];
 
            routes[i].length = len;
            cout << "len = " << routes[i].length << endl;
        }
    }
 
    _getch();
 
    return 0;
}
Миниатюры
поиск длины пути  
Surf_Rider
0 / 0 / 0
Регистрация: 15.05.2011
Сообщений: 22
17.09.2012, 16:45  [ТС]     поиск длины пути #3
Спасибо, с этим я разобрался, я генерирую все возможные перестановки, потом считаю длины
но этот алгоритм не устраивает, потому что конечное число перестановок n!, приемлимо только для n<12

Моя конечная цель - найти кратчайший
сейчас разбираюсь с генетическим алгоритмом
Yandex
Объявления
17.09.2012, 16:45     поиск длины пути
Ответ Создать тему
Опции темы

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