Графы. Нахождение максимального пути

@El HaZaRD · Регистрация: 08.02.2012

Author24 — интернет-сервис помощи студентам

Добрый день.
Пытаюсь написать программу для помощи в криптоанализе методом двойной перестановки и столкнулся с проблемой. Изложу суть задачи:
Перехвачено сообщение АЗЮЖЕ_СШГТООИПЕР
16 символов, загоняем в матрицу 4х4.
Получилось 4 столбца, переставленных в неизвестном порядке:
А З Ю Ж
Е _ С Ш
Г Т О О
И П Е Р

Метод «вскрытия» шифров двойной перестановки основан на определении маловероятных сочетаний букв и нахождении на их основе истинной последовательности столбцов в шифровальной таблице.

При решении получаем матрицу из сумм логарифмов сочетаний:

0 21 30 27
23 0 26 24
19 22 0 20
28 17 14 0

Таким образом теперь нам надо определить порядок следования столбцов. Впринципе похоже на задачу коммивояжера, только наоборот. Надо найти путь с максимальной суммой (максимальной длины), при этом побывав в каждом столбце один раз. Найдя путь, можно будет расставить столбцы и прочесть сообщение.
Вот здесь то я и не пойму как это сделать..
Может быть кто-нибудь сможет подсказать?
С программированием на Вы, поэтому прошу строго не судить.

Текст программы:

C++

#include <iostream>
#include <locale.h>
#include <stdio.h>
#include <fstream>
#include <string.h>
using namespace std;
 
void Rus(char* in, char* out)
{
    int len = strlen(in);
    for(int i = 0; i < len; i++)
    {
        unsigned char simb = (*in);
        if((simb>=128)&&(simb<=175))
            simb += 64;
        else
        if((simb>=224)&&(simb<=239))
            simb += 16;
        *out = simb;
        out++;
        in++;
    }
}
 
void main()
{
setlocale(LC_ALL,"Russian");
int i,j,num[4][4],per[4][4];
char mas[4][4],head[33];
int log[33][33];
 
 
 
 
    cout<<"введите сообщение:"<<endl;
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            cin>>mas[i][j];
        }
        Rus(mas[i],mas[i]);
    }
    
 
    cout<<endl<<"получилась таблица:"<<endl;
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            cout<<mas[i][j]<<" ";
        }
        cout<<endl;
    }
 
//считываем таблицу логарифмов
    ifstream f("nums.txt");
    for(i=0;i<33;i++) 
    {
        for(j=0;j<33;j++) 
        {
            f>>log[i][j];
        }
    }
    ifstream e("head.txt");
    for(i=0;i<33;i++) 
        {
            e>>head[i];
        }
//получаем таблицу из указателей на строки и столбцы в таблице логарифмов
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            for (int k=0;k<33;k++)
            {
                if (strncmp(&mas[i][j],&head[k],1)==0) num[i][j]=k;
            }
        }
    }
//получаем таблицу переходов
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            per[i][j]=0;
            if (i!=j) 
            {   
                for (int k=0;k<4;k++)
                {
                    per[i][j]=per[i][j]+log[num[k][i]][num[k][j]];
                }
            }
        }
    }
 
cout<<endl<<"получилась таблица переходов:"<<endl;
    for (i=0;i<4;i++)
    {
        for (j=0;j<4;j++)
        {
            cout<<per[i][j]<<" ";
        }
        cout<<endl;
    }
 
//ищем маршрут
    
 
cout<<endl<<endl;
system("pause");
}

@El HaZaRD · 10.05.2012, 20:33 **[ТС]**

Появилась идея реализации.
Так как для меня главное найти только правильный порядок следования столбцов друг за другом, то пришла в голову следующая мысль.
Берем за точку отсчета столбец 1.
Веса переходов из столбца 1 в остальные 3 столбца указан в первой строке массива per[4][4].
Делаем цикл.
Берем первую строку и ищем в ней максимальный элемент. Найдя его запоминаем номер его столбца (обозначим его stnum).
Номеру следующей строки для поиска максимума присваиваем значение stnum.
Затем обнуляем весь столбец с номером stnum. Таким образом мы исключим возможность перехода в этот столбец (нам ведь надо во все по одному разу зайти).
И далее опять ищем максимум в следующей строке.

Для того чтобы запомнить маршрут нам надо будет куда то записывать все значения stnum по порядку, а первым значением в этом списке будет 0 (или 1, т.к. первый столбец).

Помогите, пожалуйста, кто-нибудь воплотить это в коде.

Добавлено через 24 минуты
Сам вопрос задал, сам на него и ответил =)

Для удобства была создана функция для поиска максимума в одномерном массиве, куда будет передаваться строка из таблицы переходов.

C++

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++

//ищем маршрут
    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<<" ";
    }

Добавлено через 12 минут
Небольшой косячек.. забыл обнулить первый столбец в массиве переходов после того, как i=0.

Получится в итоге так:

C++

//ищем маршрут
    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<<" ";
    }

	10.05.2012, 20:33