回文子序列与欧几里德旅行商

回文子序列

最长回文子序列是正序与逆序相同的非空字符串。例如,所有长度为1的字符串,civic,racecar,aibobphobia都是回文。设计算法,求给定输入字符串的最长回文子序列。例如,给定输入character,算法应该返回carac。算法的运行时间是怎么样的?

算法设计与分析:

注意这里是回文子序列,而不是回文子串。求子串和子序列有一些不同,这里的方法用于求子序列。
字串的意义是:aaabbb,需要连续的字符相同。

而子序列,是字母按照一定的排列顺序,保持回文的一致性就可以。

实现过程:将原字符串反转,然后用LCS_length(),Print_LCS()计算出最长公共子序列即可。

palidrome_longest.h

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
#include <iostream>
#include <string>
#include <locale>
using namespace std;
#define N 9 //输入您要判断的字符串的字符数
wchar_t b[N+1][N+1]={'S'}; //表示起点start
int c[N+1][N+1]={0};
wchar_t northwest=L'\\', up=L'|', leftway=L'-';
void LCS_length(char *x,char *y)
{
for(int i1=0;i1<N;i1++)
b[i1][0]='S';
for(int j1=0;j1<N;j1++)
b[0][j1]='S';
for(int i=0;i<N;i++)
{
for(int j=0;j<N;j++)
{
if(x[i]==y[j])
{
c[i+1][j+1]=c[i][j]+1;
b[i+1][j+1]=northwest; //Northwest往左上
}
else
{
if(c[i][j+1]>=c[i+1][j])
//c[i-1][j-1] 过渡到 c[i][j],需要将c[i-1][j]和c[i][j-1]比较大小
//取较大的那一个值
{
c[i+1][j+1]=c[i][j+1];
b[i+1][j+1]=up; //Up往上
}
else
{
c[i+1][j+1]=c[i+1][j];
b[i+1][j+1]=leftway; //Left往左
}
}
}
}
}
void Print_lcs(char *x,int i,int j)
{
if(i==0||j==0)
return;
if(b[i][j]==northwest)
{
Print_lcs(x,i-1,j-1);
cout<<x[i-1]<<" "; //当然,按y[j]输出也没有问题,因为是公共序列嘛!
} //这里的下标是从i=0开始的,所以输出x[i-1]
else
{
if(b[i][j]==up)
Print_lcs(x,i-1,j);
else
Print_lcs(x,i,j-1);
}
}
char *strReverse(char *str)
{
for(int i=0;i<N/2;i++)
{
swap(str[i],str[N-1-i]);
}
return str;
}

palidrome_longest.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include "palidrome_longest.h"
int main()
{
char x[N+1]={0};
char y[N+1]={0};
char c;
cout<<"get the string you need to judge: "<<endl;
int i;
for(i=1;i<=N;i++) //默认的字符串是从下标1开始的,这里我们可以让它从0开始
{
cin>>c;
y[i]=x[i]=c;
}
x[i]='\0';y[i]='\0';
cout<<y<<endl;
cout<<"x="<<y<<endl;
strReverse(y); //反转字符串
cout<<"y="<<y<<endl;
LCS_length(x,y);
Print_lcs(x,N,N);
return 0;
}

实现结果

01

欧几里德旅行商问题

算法分析图

02

03

Eucilid_travel.h

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
#include <iostream>
#include <cmath>
using namespace std;
#define N 7 //确定有几个点?
struct travelnode
{
double x;
double y;
}T[N];
//计算两个点之间的直线距离
double distance(travelnode T[],int i,int j) //T[]的下标,第几个数?1,2....N
{
return sqrt((T[i].x-T[j].x)*(T[i].x-T[j].x)+(T[i].y-T[j].y)*(T[i].y-T[j].y));
}
double Bitonic_Eucilid(travelnode T[])
{
double b[N+1][N+1]={0};
//初始化b[1][2],注意初始下标从1开始,1,2.....N
b[1][2]=distance(T,1,2);
for(int j=3;j<=N;j++)
{
for(int i=1;i<j-1;i++) //注意1<=i<=j-2
{
b[i][j]=b[i][j-1]+distance(T,j-1,j); //巡路系统的初始化,递归求解
//length((start->j-1)+(start->i)+length(j-1,j))
//即b[i][j]=b[i][j-1]+distance(T,j-1,j) 这里distance(T,j-1,j)封闭了路径
}
//注意:这里递归求解所得到的路径,b[i][j]不一定就是最短的欧几里德旅行商
//必须用min()维护旅行商信息
//用min()维护每一条线段[j-1,j],保证从length(start->j-1)+length(start->k)+length(k,j)均是最小的
//如图所示:对每一个线段[j-1,j]的两端进行维护,保证最短的Eucilid巡回,即维护b[j-1][j]
//在维护的过程中b[j-1][j]=min(b[k][j-1]+distance(k,j)),封闭了[k,j]就获取了最佳路径
//因为j是在最远端,1<=k<=j-1<j,j-1和k一定在回路的不同方向。由递归求解,已知b[k][j-1]
//最后封闭[k,j]即可年少有你
//这一步确定了从start->i+start->j的路径,但是巡路并不是封闭的
//最后确定b[j-1][j],即确定线段[j-1,j],完成巡路封闭。
//这里b[j-1][j]要保证遍历1<=k<j-1中的最小路径,如图中所示
b[j-1][j]=INFINITY;
//对每一条线段[j-1,j]两端维护Eucilid巡回路径性质
for(int k=1;k<j-1;k++)
{
double q=b[k][j-1]+distance(T,k,j); //最后封闭的线段长度[j-1,j]是固定的
//(start->j-1)+(start->k)+length(k,j)
//由于1<=k<j-1,k和j-1一定是分居在Eucilid旅行图的线段[j-1,j]的两侧
if(q<b[j-1][j])
b[j-1][j]=q;
}
}
b[N][N]=b[N-1][N]+distance(T,N-1,N);
return b[N][N];
}

Eucilid_travel.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
#include "Eucilid_travel.h"
int main()
{
travelnode T[N+1]={0};
cout<<"Input the numbers in order : "<<endl;
for(int i=1;i<=N;i++)
{
cin>>T[i].x>>T[i].y;
}
cout<<Bitonic_Eucilid(T)<<endl;
}

旅行商的重构解

Print函数的递归分析

04

05

特别注意:

1
2
if(s<k)
print_eucilid(solution,s,val);

或者是:

1
2
if(s>k)
print_eucilid(solution,val,k);

如图中绿色线条所示:递归的过程,无论是$s->val$还是$val->s$,均是由较大坐标的点转向较小坐标的点。
二者的区别在于:s<k的时候直接取得val=solution[s][k]的值,先输出val,再递归;

而s>k的时候,则先递归输出顺时针方向其余的点,再输出val=solution[k][s]的值。
注意这里是solution[k][s]

当然递归和$val$的输出的先后顺序,取决于你是按顺时针还是逆时针输出。

Eucilid_travel_constitute.h

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
#include <iostream>
#include <cmath>
using namespace std;
#define N 7 //确定有几个点?
struct travelnode
{
double x;
double y;
}T[N];
//计算两个点之间的直线距离
double distance(travelnode T[],int i,int j) //T[]的下标,第几个数?1,2....N
{
return sqrt((T[i].x-T[j].x)*(T[i].x-T[j].x)+(T[i].y-T[j].y)*(T[i].y-T[j].y));
}
double Bitonic_Eucilid(travelnode T[],int solution[][N+1])
{
double b[N+1][N+1]={0};
//初始化b[1][2],注意初始下标从1开始,1,2.....N
b[1][2]=distance(T,1,2);
for(int j=3;j<=N;j++)
{
for(int i=1;i<j-1;i++) //注意1<=i<=j-2
{
b[i][j]=b[i][j-1]+distance(T,j-1,j); //巡路系统的初始化,递归求解
//length((start->j-1)+(start->i)+length(j-1,j))
//即b[i][j]=b[i][j-1]+distance(T,j-1,j) 这里distance(T,j-1,j)封闭了路径
solution[i][j]=j-1;
}
//注意:这里递归求解所得到的路径,b[i][j]不一定就是最短的欧几里德旅行商
//必须用min()维护旅行商信息
//用min()维护每一条线段[j-1,j],保证从length(start->j-1)+length(start->k)+length(k,j)均是最小的
//如图所示:对每一个线段[j-1,j]的两端进行维护,保证最短的Eucilid巡回,即维护b[j-1][j]
//在维护的过程中b[j-1][j]=min(b[k][j-1]+distance(k,j)),封闭了[k,j]就获取了最佳路径
//因为j是在最远端,1<=k<=j-1<j,j-1和k一定在回路的不同方向。由递归求解,已知b[k][j-1]
//最后封闭[k,j]即可
//这一步确定了从start->i+start->j的路径,但是巡路并不是封闭的
//最后确定b[j-1][j],即确定线段[j-1,j],完成巡路封闭。
//这里b[j-1][j]要保证遍历1<=k<j-1中的最小路径,如图中所示
b[j-1][j]=INFINITY;
//对每一条线段[j-1,j]两端维护Eucilid巡回路径性质
for(int k=1;k<j-1;k++)
{
double q=b[k][j-1]+distance(T,k,j); //最后封闭的线段长度[j-1,j]是固定的
//(start->j-1)+(start->k)+length(k,j)
//由于1<=k<j-1,k和j-1一定是分居在Eucilid旅行图的线段[j-1,j]的两侧
if(q<b[j-1][j])
{
b[j-1][j]=q;
solution[j-1][j]=k;
}
}
}
b[N][N]=b[N-1][N]+distance(T,N-1,N);
solution[N][N]=N-1;
return b[N][N];
}
void print_eucilid(int solution[][N+1],int s,int k)
{
if(s<k)
{
int val=solution[s][k];
cout<<val<<" ";
if(val>1)
print_eucilid(solution,s,val);
}
else
{
int val=solution[k][s];
if(val>1)
{
print_eucilid(solution,val,k);
}
cout<<val<<" ";
}
}

Eucilid_travel_constitute.cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include "Eucilid_travel_constitute.h"
int main()
{
travelnode T[N+1]={0};
int solution[N+1][N+1]={0};
cout<<"Input the numbers in order : "<<endl;
for(int i=1;i<=N;i++)
{
cin>>T[i].x>>T[i].y;
}
cout<<Bitonic_Eucilid(T,solution)<<endl;
cout<<"The Eucilid travel is :"<<endl;
cout<<N<<" ";
print_eucilid(solution,N-1,N);
cout<<N-1<<" ";
}

算法运行结果

06

原创技术分享,您的支持鼓励我继续创作