Появилась идея реализации.
Так как для меня главное найти только правильный порядок следования столбцов друг за другом, то пришла в голову следующая мысль.
Берем за точку отсчета столбец 1.
Веса переходов из столбца 1 в остальные 3 столбца указан в первой строке массива per[4][4].
Делаем цикл.
Берем первую строку и ищем в ней максимальный элемент. Найдя его запоминаем номер его столбца (обозначим его stnum).
Номеру следующей строки для поиска максимума присваиваем значение stnum.
Затем обнуляем весь столбец с номером stnum. Таким образом мы исключим возможность перехода в этот столбец (нам ведь надо во все по одному разу зайти).
И далее опять ищем максимум в следующей строке.
Для того чтобы запомнить маршрут нам надо будет куда то записывать все значения stnum по порядку, а первым значением в этом списке будет 0 (или 1, т.к. первый столбец).
Помогите, пожалуйста, кто-нибудь воплотить это в коде.
Добавлено через 24 минуты
Сам вопрос задал, сам на него и ответил =)
Для удобства была создана функция для поиска максимума в одномерном массиве, куда будет передаваться строка из таблицы переходов.
| C++ |
1
2
3
4
5
6
7
8
9
| int maximum(int mass[4])
{
int maxx=0;
for (int j=0;j<4;j++)
{
if (mass[j]>maxx) maxx=mass[j];
}
return maxx;
} |
|
А вот так я реализовал само решение:
| C++ |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| //ищем маршрут
i=0;
int ans[4]={0,0,0,0};
for(int k=0;k<3;k++)
{
for (j=0;j<4;j++)
{
if (maximum(per[i])==per[i][j]) ans[k+1]=j;
}
i=ans[k+1];
for(j=0;j<4;j++)
{
per[j][i]=0;
}
}
cout<<endl<<"Путь: ";
for (j=0;j<4;j++)
{
cout<<ans[j]+1<<" ";
} |
|
Небольшой косячек.. забыл обнулить первый столбец в массиве переходов после того, как i=0.
Получится в итоге так:
| 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
| //ищем маршрут
i=0;
for(j=0;j<4;j++)
{
per[j][i]=0;
}
int ans[4]={0,0,0,0};
for(int k=0;k<3;k++)
{
for (j=0;j<4;j++)
{
if (maximum(per[i])==per[i][j]) ans[k+1]=j;
}
i=ans[k+1];
for(j=0;j<4;j++)
{
per[j][i]=0;
}
}
cout<<endl<<"Путь: ";
for (j=0;j<4;j++)
{
cout<<ans[j]+1<<" ";
} |
|
