//图的遍历算法程序
//图的遍历是指按某条搜索路径访问图中每个结点，使得每个结点均被访问一次，而且仅被访问一次。图的遍历有深度遍历算法和广度遍历算法，程序如下：
#include <iostream>
//#include <malloch>
#define INFINITY 32767
#define MAX_VEX 20 //最大顶点个数
#define QUEUE_SIZE (MAX_VEX+1) //队列长度
using namespace std;
bool visited; //访问标志数组
//图的邻接矩阵存储结构
typedef struct{
char vexs; //顶点向量
int arcs[MAX_VEX][MAX_VEX]; //邻接矩阵
int vexnum,arcnum; //图的当前顶点数和弧数
}Graph;
//队列类
class Queue{
public:
void InitQueue(){
base=(int )malloc(QUEUE_SIZEsizeof(int));
front=rear=0;
}
void EnQueue(int e){
base[rear]=e;
rear=(rear+1)%QUEUE_SIZE;
}
void DeQueue(int &e){
e=base[front];
front=(front+1)%QUEUE_SIZE;
}
public:
int base;
int front;
int rear;
};
//图G中查找元素c的位置
int Locate(Graph G,char c){
for(int i=0;i<Gvexnum;i++)
if(Gvexs[i]==c) return i;
return -1;
}
//创建无向网
void CreateUDN(Graph &G){
int i,j,w,s1,s2;
char a,b,temp;
printf("输入顶点数和弧数:");
scanf("%d%d",&Gvexnum,&Garcnum);
temp=getchar(); //接收回车
Gvexs=(char )malloc(Gvexnumsizeof(char)); //分配顶点数目
printf("输入%d个顶点\n",Gvexnum);
for(i=0;i<Gvexnum;i++){ //初始化顶点
printf("输入顶点%d:",i);
scanf("%c",&Gvexs[i]);
temp=getchar(); //接收回车
}
for(i=0;i<Gvexnum;i++) //初始化邻接矩阵
for(j=0;j<Gvexnum;j++)
Garcs[i][j]=INFINITY;
printf("输入%d条弧\n",Garcnum);
for(i=0;i<Garcnum;i++){ //初始化弧
printf("输入弧%d:",i);
scanf("%c %c %d",&a,&b,&w); //输入一条边依附的顶点和权值
temp=getchar(); //接收回车
s1=Locate(G,a);
s2=Locate(G,b);
Garcs[s1][s2]=Garcs[s2][s1]=w;
}
}
//图G中顶点k的第一个邻接顶点
int FirstVex(Graph G,int k){
if(k>=0 && k<Gvexnum){ //k合理
for(int i=0;i<Gvexnum;i++)
if(Garcs[k][i]!=INFINITY) return i;
}
return -1;
}
//图G中顶点i的第j个邻接顶点的下一个邻接顶点
int NextVex(Graph G,int i,int j){
if(i>=0 && i<Gvexnum && j>=0 && j<Gvexnum){ //i,j合理
for(int k=j+1;k<Gvexnum;k++)
if(Garcs[i][k]!=INFINITY) return k;
}
return -1;
}
//深度优先遍历
void DFS(Graph G,int k){
int i;
if(k==-1){ //第一次执行DFS时,k为-1
for(i=0;i<Gvexnum;i++)
if(!visited[i]) DFS(G,i); //对尚未访问的顶点调用DFS
}
else{
visited[k]=true;
printf("%c ",Gvexs[k]); //访问第k个顶点
for(i=FirstVex(G,k);i>=0;i=NextVex(G,k,i))
if(!visited[i]) DFS(G,i); //对k的尚未访问的邻接顶点i递归调用DFS
}
}
//广度优先遍历
void BFS(Graph G){
int k;
Queue Q; //辅助队列Q
QInitQueue();
for(int i=0;i<Gvexnum;i++)
if(!visited[i]){ //i尚未访问
visited[i]=true;
printf("%c ",Gvexs[i]);
QEnQueue(i); //i入列
while(Qfront!=Qrear){
QDeQueue(k); //队头元素出列并置为k
for(int w=FirstVex(G,k);w>=0;w=NextVex(G,k,w))
if(!visited[w]){ //w为k的尚未访问的邻接顶点
visited[w]=true;
printf("%c ",Gvexs[w]);
QEnQueue(w);
}
}
}
}
//主函数
void main(){
int i;
Graph G;
CreateUDN(G);
visited=(bool )malloc(Gvexnumsizeof(bool));
printf("\n广度优先遍历: ");
for(i=0;i<Gvexnum;i++)
visited[i]=false;
DFS(G,-1);
printf("\n深度优先遍历: ");
for(i=0;i<Gvexnum;i++)
visited[i]=false;
BFS(G);
printf("\n程序结束\n");
}
输出结果为（红色为键盘输入的数据，权值都置为1）：
输入顶点数和弧数:8 9
输入8个顶点
输入顶点0:a
输入顶点1:b
输入顶点2:c
输入顶点3:d
输入顶点4:e
输入顶点5:f
输入顶点6:g
输入顶点7:h
输入9条弧
输入弧0:a b 1
输入弧1:b d 1
输入弧2:b e 1
输入弧3:d h 1
输入弧4:e h 1
输入弧5:a c 1
输入弧6:c f 1
输入弧7:c g 1
输入弧8:f g 1
广度优先遍历: a b d h e c f g
深度优先遍历: a b c d e f g h
程序结束
已经在vc++内运行通过，这个程序已经达到要求了呀~
Q-learning算法的过程可以根据下面的步骤：
首先，我们会初始化一个Q-table，可以是全0或者是其他的数值，一般都是全0，然后我们设定训练的轮数episodes，这里从初始状态直到终止状态算作一轮。那么在每一轮中，我们会有一个初始状态，然后会不断的采取动作，这里每一个动作叫做一个step。在每一个step中，我们根据当前的状态通过一定的策略选择动作A，这里的策略可能是以09的概率选择Q-table中当前状态对应的q值最大的动作，以01的概率选择随机动作。然后在选择动作A之后，我们可以得到奖励值R和新的状态S，那么当前q值的更新基于下面的公式：
其中alpha是学习率，表示保留之前训练效果的多少，学习速率α越大，保留之前训练的效果就越少，如果学习率是1的话，完全用新学到的q值替换掉了原来的q值。R是从环境获得的奖励，而gamma是折现系数，我们会选择到新状态之后能够得到的最大的Q值来更新当前的Q值。
对于Q-learning来说，
1在状态s'时，只是计算了 在s'时要采取哪个a'可以得到更大的Q值，并没有真的采取这个动作a'。
2动作a的选取是根据当前Q网络以及策略（e-greedy），即每一步都会根据当前的状况选择一个动作A，目标Q值的计算是根据Q值最大的动作a'计算得来，因此为off-policy学习。
SARSA算法根Q-learning很像，也是基于Q-table，但是不同的是，在每一个episode的每一个step，我们会确定下一步采取的动作，而不是在下一个step开始时动态的确定step，算法步骤看下面的图示。
因此对于SARSA来说
1在状态s'时，就知道了要采取哪个a'，并真的采取了这个动作。
2动作a的选取遵循e-greedy策略，目标Q值的计算也是根据（e-greedy）策略得到的动作a'计算得来，因此为on-policy学习。
SoftQ是一个深度强化学习算法，用于解决决策问题。在实际应用中，连续动作导致了探索难度的增加，因此需要对连续动作进行抽象表示。SoftQ算法使用Q函数的软化版来计算连续动作。每个时间步，SoftQ算法根据当前状态和动作，计算出一个Q函数值，该值表示在当前时间步采取该动作可以获得的回报总和。SoftQ算法随后将该Q函数值与一个“软化”系数相乘，该系数控制了SoftQ算法在当前状态和动作上的探索程度。本质上，SoftQ算法计算的是一个行动价值函数，该函数描述了智能体在当前状态下，任何动作可以带来的可能回报总和。通过以这种方式计算连续动作，SoftQ算法可以实现更有效的强化学习。
cls
input
"diyigeshu=";a
input
"diergeshu=";b
input
"disangeshu=";c
以上语句是输入三个数
max=-999
if
a>max
then
max=a
if
b>max
then
max=b
if
c>max
then
max=c
以上语句是找出最大数：先设最大数是max,设最大数的值为-999，当a,b,c中的任意一个比最大数大，就让最大数max等于它。
"zuidashu=";max
以上语句输出最大数
end
void ReverseString(char a,int lenth) //逆转函数
{
int i;
char c;
initstack(&s);
for(i=0;i<lenth;i++) Push(&s,a[i]);
for(i=0;i<lenth;i++) {Pop(&s,&c);a[i]=c;}
}
---------------------------------------------------------------------
typedef struct //循环队列定义
{
int data[4];
int front;
int rear;
}SeqQueue;
void InitQueue(SeqQueue Q) //初始化函数
{
Q->front=Q->rear=0;
}
int EnterQueue(SeqQueue Q,int x) //入队函数
{
if((Q->rear+1)%4==Q->front) return 0;
Q->data[Q->rear]=x;
Q->rear=(Q->rear+1)%4
return 1;
}
写个main函数调用两次入队即可！
求解算法的时间复杂度的具体步骤是：⑴找出算法中的基本语句；算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。⑵计算基本语句的执行次数的数量级；只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次
查找算法集：顺序查找、二分查找、插值查找、动态查找(数组实现、链表实现)
// searchcpp : Defines the entry point for the console application
//
#include "stdafxh"
#include "LinkTableh"
#define MAX_KEY 500
//------------------------------数组实现部分----------------------------------
///
无序数组顺序查找算法函数nsq_Order_Search<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: nsq_Order_Search = -1
否则: nsq_Order_Search = key数组下标
/
int nsq_Order_Search(int array[],int n,int key)
{
int i;
array[n] = key;
///for循环后面的分号必不可少/
for(i=0;key!=array[i];i++);
return(i<ni:-1);
}
///
有序数组顺序查找算法函数sq_Order_Search<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Order_Search = -1
否则: sq_Order_Search = key数组下标
/
int sq_Order_Search(int array[],int n,int key)
{
int i;
array[n] = MAX_KEY;
///for循环后面的分号必不可少/
for(i=0;key>array[i];i++);
if(i<n && array[i] == key)
return(i);
else
return(-1);
}
///
有序数组二分查找算法函数sq_Dichotomy_Search0<用数组实现>
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Dichotomy_Search0 = -1
否则: sq_Dichotomy_Search0 = key数组下标
/
int sq_Dichotomy_Search0(int array[],int n,int key)
{
int low,high,mid;
low = 0;
high = n - 1;
while(low<=high)
{
mid = (high+low)/2;
if(array[mid] == key)
return(mid);
///key>array[mid] 表明要求查找的值在[mid+1,high]/
///否则,在[low,mid-1]/
if(key > array[mid])
low = mid + 1;
else
high = mid - 1;
}
return(-1);
}
///
有序数组插值查找算法函数sq_Dichotomy_Search1<用数组实现>
(插值查找算法是二分查找算法的改进)
参数描述：
int array[] :被查找数组
int n :被查找数组元素个数
int key :被查找的关键值
返回值:
如果没有找到: sq_Dichotomy_Search1 = -1
否则: sq_Dichotomy_Search1 = key数组下标
/
int sq_Dichotomy_Search1(int array[],int n,int key)
{
int low,high, //二分数组的上,下标
pos; //查找码的大致(估算)位置
low = 0;
high = n-1;
while(low <= high)
{
pos = (key-array[low])/(array[high]-array[low])(high-low)+low;
///找到关键值,中途退出/
if(key == array[pos])
return(pos);
if(key > array[pos])
low = pos + 1;
else
high = pos - 1;
}
///没有找到,返回-1/
return(-1);
}
//------------------------------数组实现部分----------------------------------
//------------------------------链表实现部分----------------------------------
///
无序链表顺序查找算法函数nlk_Order_Serach<用链表实现>
[查找思想:遍历链表的所有节点]
参数描述：
Node head :被查找链表的首指针
int key :被查找的关键值
返回值:
如果没有找到: nlk_Order_Serach = NULL
否则: nlk_Order_Serach = 键值为key的节点的指针
/
Node nlk_Order_Serach(Node head,int key)
{
for(;head!=NULL && head->data != key;head = head->link);
return(head);
}
///
有序链表顺序查找算法函数lk_Order_Serach<用链表实现>
[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]
参数描述：
Node head :被查找链表的首指针
int key :被查找的关键值
返回值:
如果没有找到: lk_Order_Serach = NULL
否则: lk_Order_Serach = 键值为key的节点的指针
/
Node lk_Order_Search(Node head,int key)
{
for(;head!=NULL && head->data < key;head=head->link);
///当遍历指针为NULL或没有找到键值为key的节点,返回NULL(表明没有找到)/
///否则,返回head(表明已经找到)/
return(head==NULL || head->data != key NULL : head);
}
///
有序链表动态查找算法函数lk_Dynamic_Search<用链表实现>
[查找思想:依次遍历链表的节点,发现节点不在key的范围时提前结束查找]
参数描述：
Node head: 被查找链表的首指针
Node p; 键值为key的节点的前驱指针(回传参数)
Node q: 键值为key的节点指针(回传参数)
int key : 被查找的关键值
注意:
当 p == NULL 且 q != NULL,链表的首节点键值为key
当 p != NULL 且 q != NULL,链表的中间(非首,尾)节点键值为key
当 p != NULL 且 q == NULL,链表的尾节点键值为key
当 p == NULL 且 q == NULL,链表是空链表
/
void lk_Dynamic_Search(Node head,Node p,Node q,int key)
{
Node pre,cur;
pre = NULL;
cur = head;
for(;cur != NULL && cur->data < key;pre = cur,cur = cur->link)
p = pre;
q = cur;
}
///
有序链表动态插入算法函数lk_Dynamic_Insert<用链表实现>
参数描述：
Node head: 被插入链表的首指针
int key : 被插入的关键值
返回值:
lk_Dynamic_Search = 插入键值为key的节点后的链表首指针
/
Node lk_Dynamic_Insert(Node head,int key)
{
Node
x, //插入节点的前驱节点
y, //插入节点的后续节点
p; //插入的节点
p = (Node )malloc(sizeof(Node));
p->data = key;
p->link = NULL;
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
{
p->link = x;
head = p;
}
else
{
p->link = x->link;
x->link = p;
}
ListLinkTable(head,"插入节点");
return(head);
}
///
有序链表动态删除算法函数lk_Dynamic_Delete<用链表实现>
参数描述：
Node head: 被删除链表的首指针
int key : 被删除的关键值
返回值:
lk_Dynamic_Delete = 删除键值为key的节点后的链表首指针
/
Node lk_Dynamic_Delete(Node head,int key)
{
Node x, //删除节点的前驱节点
y; //删除的节点
lk_Dynamic_Search(head,&x,&y,key);
if(x==NULL)
///因为x=NLLL时,y指向首指针/
head = y->link;
else
x->link = y->link;
free(y);
ListLinkTable(head,"删除节点");
return(head);
}
//------------------------------链表实现部分----------------------------------
int main(int argc, char argv[])
{
Node head;
//Node p,x,y;
int KEY;
int count,i;
//int result;
KEY = 11;
//PrintArrayValue(TestArray2,DEFAULT_ARRAY_SIZE,"原始");
//result = sq_Dichotomy_Search1(TestArray2,DEFAULT_ARRAY_SIZE,KEY);
//printf("查找结果是：数组[%d] = %d ",result,TestArray2[result]);
head = CreateLinkTable(DEFAULT_ARRAY_SIZE,TestArray2);
ListLinkTable(head,"原始");
///
p = lk_Order_Search(head,KEY);
if(p==NULL)
printf(" 查找结果是：指定链表中没有[数据域 = %d]的节点! ",KEY);
else
printf(" 查找结果是：节点Data = %d 节点Link = %d 节点Addr = %d ",p->data,p->link,p);
/
printf("输入插入节点的个数： ");
scanf("%d",&count);
for(i=0;i<count;i++)
{
printf("输入插入节点的数据域： ");
scanf("%d",&KEY);
lk_Dynamic_Insert(head,KEY);
}
do
{
printf("输入删除节点的数据域： ");
scanf("%d",&KEY);
lk_Dynamic_Delete(head,KEY);
}while(head!=NULL);
printf(" 应用程序正在运行 ");
return 0;
}
唯一区别就是 Q学习算法有个最大Q值的采用 而sarsa木有
Q算法是当选择下一步的时候 会找最好的一个走（选最大Q值的） 而sarsa是当选择下一步的时候 运用和上一步一样/想等的Q值 但是最后都会更新之前的一步从而达到学习的效果~
java代码就算了吧 其实都大同小异
以上就是关于图的遍历（c语言）完整上机代码全部的内容，包括:图的遍历（c语言）完整上机代码、Q-Learning 和 SARSA 算法对比、softq怎么计算连续动作等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）