a算法代码

❶ 设计一个算法代码 ，解字谜ABCAB*A=DDDDDD

#include <stdio.h>
int main()
{
int a, b, c, dddddd;
for(a=1; a<=9; a++)
for(b=0; b<=9; b++)
for(c=0; c<=9; c++)
{
dddddd = (a*10000 + b*1000 + c*100 + a*10 + b) * a;
if(dddddd % 111111 == 0)
printf(" %d%d%d%d%d X %d = %d\n", a,b,c,a,b,a,dddddd);
}
return 0;
}

❷ 求一个A*算法的C语言或C++代码，小弟不胜感激，谢谢

1#include <iostream>
2#include <queue>
3usingnamespace std;
4
5struct knight{
6int x,y,step;
7int g,h,f;
8booloperator< (const knight & k) const{ //重载比较运算符
9return f > k.f;
10 }
11}k;
12bool visited[8][8]; //已访问标记(关闭列表)
13int x1,y1,x2,y2,ans; //起点(x1,y1),终点(x2,y2),最少移动次数ans
14int dirs[8][2]={{-2,-1},{-2,1},{2,-1},{2,1},{-1,-2},{-1,2},{1,-2},{1,2}};//8个移动方向
15priority_queue<knight> que; //最小优先级队列(开启列表)
16
17boolin(const knight & a){ //判断knight是否在棋盘内
18if(a.x<0|| a.y<0|| a.x>=8|| a.y>=8)
19returnfalse;
20returntrue;
21}
22int Heuristic(const knight &a){ //manhattan估价函数
23return (abs(a.x-x2)+abs(a.y-y2))*10;
24}
25void Astar(){ //A*算法
26 knight t,s;
27while(!que.empty()){
28 t=que.top(),que.pop(),visited[t.x][t.y]=true;
29if(t.x==x2 && t.y==y2){
30 ans=t.step;
31break;
32 }
33for(int i=0;i<8;i++){
34 s.x=t.x+dirs[i][0],s.y=t.y+dirs[i][1];
35if(in(s) &&!visited[s.x][s.y]){
36 s.g = t.g +23; //23表示根号5乘以10再取其ceil
37 s.h = Heuristic(s);
38 s.f = s.g + s.h;
39 s.step = t.step +1;
40 que.push(s);
41 }
42 }
43 }
44}
45int main(){
46char line[5];
47while(gets(line)){
48 x1=line[0]-'a',y1=line[1]-'1',x2=line[3]-'a',y2=line[4]-'1';
49 memset(visited,false,sizeof(visited));
50 k.x=x1,k.y=y1,k.g=k.step=0,k.h=Heuristic(k),k.f=k.g+k.h;
51while(!que.empty()) que.pop();
52 que.push(k);
53 Astar();
54 printf("To get from %c%c to %c%c takes %d knight moves.\n",line[0],line[1],line[3],line[4],ans);
55 }
56return0;
57}
58

❸ 求用A*算法解01背包问题的C语言编的完整的源代码，在线等，高人们帮帮我，谢谢~

这个算法厉害。

#include "stdafx.h"
#include <iostream>
using namespace std;
#define N 7//物品数量
#define S 20//要求背包重量
int W[N+1]=;//各物品重量，W[0]不使用。。。
int knap(int s,int n)//s为剩余重量，n为剩余可先物品数。。
{
if(s==0)return 1;//return 1 means success..
if(s<0||(s>0&&n<1))return 0;//如果s<0或n<1则不能完成
if(knap(s-W[n],n-1))//从后往前装，如果装满第n个包，剩余的重量仍然可以在剩余的n-1包中放下，那么就将第n个包装满。
{
printf("%4d",W[n]);//打印第n个包的容量，即装进第n个包的重量。
return 1;
}
return knap(s,n-1);//如果装满第n个包后，剩余的重量不能在剩余的n-1包中放下，那么就不用第n个包，考虑能不能用第n-1个包。
}
void main()
{
if(knap(S,N))printf("\nOK!\n");
else printf("Failed!");
}

❹ 游戏中的A星算法怎么写

首先A星算法占内存和CPU简直要命，之前用AS3写的代码90*90格仅6个敌人每次同时寻路都得卡上几秒，还经常找不到路，反正我目前还没想到好的优化方法。

❺ A*搜寻算法的代码实现(C语言实现)

用C语言实现A*最短路径搜索算法，作者 Tittup frog(跳跳蛙)。 #include<stdio.h>#include<math.h>#defineMaxLength100 //用于优先队列（Open表）的数组#defineHeight15 //地图高度#defineWidth20 //地图宽度#defineReachable0 //可以到达的结点#defineBar1 //障碍物#definePass2 //需要走的步数#defineSource3 //起点#defineDestination4 //终点#defineSequential0 //顺序遍历#defineNoSolution2 //无解决方案#defineInfinity0xfffffff#defineEast(1<<0)#defineSouth_East(1<<1)#defineSouth(1<<2)#defineSouth_West(1<<3)#defineWest(1<<4)#defineNorth_West(1<<5)#defineNorth(1<<6)#defineNorth_East(1<<7)typedefstruct{ signedcharx,y;}Point;constPointdir[8]={ {0,1},//East {1,1},//South_East {1,0},//South {1,-1},//South_West {0,-1},//West {-1,-1},//North_West {-1,0},//North {-1,1}//North_East};unsignedcharwithin(intx,inty){ return(x>=0&&y>=0 &&x<Height&&y<Width);}typedefstruct{ intx,y; unsignedcharreachable,sur,value;}MapNode;typedefstructClose{ MapNode*cur; charvis; structClose*from; floatF,G; intH;}Close;typedefstruct//优先队列（Open表）{ intlength; //当前队列的长度 Close*Array[MaxLength]; //评价结点的指针}Open;staticMapNodegraph[Height][Width];staticintsrcX,srcY,dstX,dstY; //起始点、终点staticCloseclose[Height][Width];//优先队列基本操作voidinitOpen(Open*q) //优先队列初始化{ q->length=0; //队内元素数初始为0}voidpush(Open*q,Closecls[Height][Width],intx,inty,floatg){ //向优先队列（Open表）中添加元素 Close*t; inti,mintag; cls[x][y].G=g; //所添加节点的坐标 cls[x][y].F=cls[x][y].G+cls[x][y].H; q->Array[q->length++]=&(cls[x][y]); mintag=q->length-1; for(i=0;i<q->length-1;i++) { if(q->Array[i]->F<q->Array[mintag]->F) { mintag=i; } } t=q->Array[q->length-1]; q->Array[q->length-1]=q->Array[mintag]; q->Array[mintag]=t; //将评价函数值最小节点置于队头}Close*shift(Open*q){ returnq->Array[--q->length];}//地图初始化操作voidinitClose(Closecls[Height][Width],intsx,intsy,intdx,intdy){ //地图Close表初始化配置 inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { cls[i][j].cur=&graph[i][j]; //Close表所指节点 cls[i][j].vis=!graph[i][j].reachable; //是否被访问 cls[i][j].from=NULL; //所来节点 cls[i][j].G=cls[i][j].F=0; cls[i][j].H=abs(dx-i)+abs(dy-j); //评价函数值 } } cls[sx][sy].F=cls[sx][sy].H; //起始点评价初始值 // cls[sy][sy].G=0; //移步花费代价值 cls[dx][dy].G=Infinity;}voidinitGraph(constintmap[Height][Width],intsx,intsy,intdx,intdy){ //地图发生变化时重新构造地 inti,j; srcX=sx; //起点X坐标 srcY=sy; //起点Y坐标 dstX=dx; //终点X坐标 dstY=dy; //终点Y坐标 for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { graph[i][j].x=i;//地图坐标X graph[i][j].y=j;//地图坐标Y graph[i][j].value=map[i][j]; graph[i][j].reachable=(graph[i][j].value==Reachable); //节点可到达性 graph[i][j].sur=0;//邻接节点个数 if(!graph[i][j].reachable) { continue; } if(j>0) { if(graph[i][j-1].reachable) //left节点可以到达 { graph[i][j].sur|=West; graph[i][j-1].sur|=East; } if(i>0) { if(graph[i-1][j-1].reachable &&graph[i-1][j].reachable &&graph[i][j-1].reachable) //up-left节点可以到达 { graph[i][j].sur|=North_West; graph[i-1][j-1].sur|=South_East; } } } if(i>0) { if(graph[i-1][j].reachable) //up节点可以到达 { graph[i][j].sur|=North; graph[i-1][j].sur|=South; } if(j<Width-1) { if(graph[i-1][j+1].reachable &&graph[i-1][j].reachable &&map[i][j+1]==Reachable)//up-right节点可以到达 { graph[i][j].sur|=North_East; graph[i-1][j+1].sur|=South_West; } } } } }}intbfs(){ inttimes=0; inti,curX,curY,surX,surY; unsignedcharf=0,r=1; Close*p; Close*q[MaxLength]={&close[srcX][srcY]}; initClose(close,srcX,srcY,dstX,dstY); close[srcX][srcY].vis=1; while(r!=f) { p=q[f]; f=(f+1)%MaxLength; curX=p->cur->x; curY=p->cur->y; for(i=0;i<8;i++) { if(!(p->cur->sur&(1<<i))) { continue; } surX=curX+dir[i].x; surY=curY+dir[i].y; if(!close[surX][surY].vis) { close[surX][surY].from=p; close[surX][surY].vis=1; close[surX][surY].G=p->G+1; q[r]=&close[surX][surY]; r=(r+1)%MaxLength; } } times++; } returntimes;}intastar(){ //A*算法遍历 //inttimes=0; inti,curX,curY,surX,surY; floatsurG; Openq;//Open表 Close*p; initOpen(&q); initClose(close,srcX,srcY,dstX,dstY); close[srcX][srcY].vis=1; push(&q,close,srcX,srcY,0); while(q.length) { //times++; p=shift(&q); curX=p->cur->x; curY=p->cur->y; if(!p->H) { returnSequential; } for(i=0;i<8;i++) { if(!(p->cur->sur&(1<<i))) { continue; } surX=curX+dir[i].x; surY=curY+dir[i].y; if(!close[surX][surY].vis) { close[surX][surY].vis=1; close[surX][surY].from=p; surG=p->G+sqrt((curX-surX)*(curX-surX)+(curY-surY)*(curY-surY)); push(&q,close,surX,surY,surG); } } } //printf("times:%d ",times); returnNoSolution;//无结果}constintmap[Height][Width]={ {0,0,0,0,0,1,0,0,0,1,0,0,0,0,0,0,0,0,1,1}, {0,0,1,1,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,1}, {0,0,0,0,0,0,1,0,0,0,0,0,0,1,1,0,0,0,0,1}, {0,0,0,0,0,1,0,1,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,1,0,1}, {0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,0,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0}, {0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,1,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0}, {0,0,0,0,1,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,0}, {0,1,0,0,0,0,1,0,0,0,0,0,0,1,0,1,0,0,0,1}, {0,0,0,0,1,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0}};constcharSymbol[5][3]={"□","▓","▽","☆","◎"};voidprintMap(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%s",Symbol[graph[i][j].value]); } puts(""); } puts("");}Close*getShortest(){ //获取最短路径 intresult=astar(); Close*p,*t,*q=NULL; switch(result) { caseSequential: //顺序最近 p=&(close[dstX][dstY]); while(p) //转置路径 { t=p->from; p->from=q; q=p; p=t; } close[srcX][srcY].from=q->from; return&(close[srcX][srcY]); caseNoSolution: returnNULL; } returnNULL;}staticClose*start;staticintshortestep;intprintShortest(){ Close*p; intstep=0; p=getShortest(); start=p; if(!p) { return0; } else { while(p->from) { graph[p->cur->x][p->cur->y].value=Pass; printf("（%d，%d）→ ",p->cur->x,p->cur->y); p=p->from; step++; } printf("（%d，%d） ",p->cur->x,p->cur->y); graph[srcX][srcY].value=Source; graph[dstX][dstY].value=Destination; returnstep; }}voidclearMap(){ //ClearMapMarksofSteps Close*p=start; while(p) { graph[p->cur->x][p->cur->y].value=Reachable; p=p->from; } graph[srcX][srcY].value=map[srcX][srcY]; graph[dstX][dstY].value=map[dstX][dstY];}voidprintDepth(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { if(map[i][j]) { printf("%s",Symbol[graph[i][j].value]); } else { printf("%2.0lf",close[i][j].G); } } puts(""); } puts("");}voidprintSur(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%02x",graph[i][j].sur); } puts(""); } puts("");}voidprintH(){ inti,j; for(i=0;i<Height;i++) { for(j=0;j<Width;j++) { printf("%02d",close[i][j].H); } puts(""); } puts("");}intmain(intargc,constchar**argv){ initGraph(map,0,0,0,0); printMap(); while(scanf("%d%d%d%d",&srcX,&srcY,&dstX,&dstY)!=EOF) { if(within(srcX,srcY)&&within(dstX,dstY)) { if(shortestep=printShortest()) { printf("从（%d，%d）到（%d，%d）的最短步数是:%d ", srcX,srcY,dstX,dstY,shortestep); printMap(); clearMap(); bfs(); //printDepth(); puts((shortestep==close[dstX][dstY].G)?"正确":"错误"); clearMap(); } else { printf("从（%d，%d）不可到达（%d，%d） ", srcX,srcY,dstX,dstY); } } else { puts("输入错误！"); } } return(0);}

❻ A*算法java实现

代码实现(Java)
1. 输入
(1) 代表地图二值二维数组(0表示可通路，1表示路障)
int[][] maps = {
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0 }
};123456789123456789
(2) 按照二维数组的特点，坐标原点在左上角，所以y是高，x是宽，y向下递增，x向右递增，我们将x和y封装成一个类，好传参，重写equals方法比较坐标(x,y)是不是同一个。
public class Coord
{
public int x;
public int y;

public Coord(int x, int y)
{
this.x = x;
this.y = y;
}

@Override
public boolean equals(Object obj)
{
if (obj == null) return false;
if (obj instanceof Coord)
{
Coord c = (Coord) obj;
return x == c.x && y == c.y;
}
return false;
}
}2223
(3) 封装路径结点类，字段包括：坐标、G值、F值、父结点，实现Comparable接口，方便优先队列排序。
public class Node implements Comparable
{

public Coord coord; // 坐标
public Node parent; // 父结点
public int G; // G：是个准确的值，是起点到当前结点的代价
public int H; // H：是个估值，当前结点到目的结点的估计代价

public Node(int x, int y)
{
this.coord = new Coord(x, y);
}

public Node(Coord coord, Node parent, int g, int h)
{
this.coord = coord;
this.parent = parent;
G = g;
H = h;
}

@Override
public int compareTo(Node o)
{
if (o == null) return -1;
if (G + H > o.G + o.H)
return 1;
else if (G + H < o.G + o.H) return -1;
return 0;
}
}
(4) 最后一个数据结构是A星算法输入的所有数据，封装在一起，传参方便。:grin:
public class MapInfo
{
public int[][] maps; // 二维数组的地图
public int width; // 地图的宽
public int hight; // 地图的高
public Node start; // 起始结点
public Node end; // 最终结点

public MapInfo(int[][] maps, int width, int hight, Node start, Node end)
{
this.maps = maps;
this.width = width;
this.hight = hight;
this.start = start;
this.end = end;
}
}
2. 处理
(1) 在算法里需要定义几个常量来确定：二维数组中哪个值表示障碍物、二维数组中绘制路径的代表值、计算G值需要的横纵移动代价和斜移动代价。
public final static int BAR = 1; // 障碍值
public final static int PATH = 2; // 路径
public final static int DIRECT_VALUE = 10; // 横竖移动代价
public final static int OBLIQUE_VALUE = 14; // 斜移动代价12341234
(2) 定义两个辅助表：Open表和Close表。Open表的使用是需要取最小值，在这里我们使用Java工具包中的优先队列PriorityQueue，Close只是用来保存结点，没其他特殊用途，就用ArrayList。
Queue openList = new PriorityQueue(); // 优先队列(升序)
List closeList = new ArrayList();1212
(3) 定义几个布尔判断方法：最终结点的判断、结点能否加入open表的判断、结点是否在Close表中的判断。
/**
* 判断结点是否是最终结点
*/
private boolean isEndNode(Coord end,Coord coord)
{
return coord != null && end.equals(coord);
}

/**
* 判断结点能否放入Open列表
*/
private boolean canAddNodeToOpen(MapInfo mapInfo,int x, int y)
{
// 是否在地图中
if (x 0 || x >= mapInfo.width || y 0 || y >= mapInfo.hight) return false;
// 判断是否是不可通过的结点
if (mapInfo.maps[y][x] == BAR) return false;
// 判断结点是否存在close表
if (isCoordInClose(x, y)) return false;

return true;
}

/**
* 判断坐标是否在close表中
*/
private boolean isCoordInClose(Coord coord)
{
return coord!=null&&isCoordInClose(coord.x, coord.y);
}

/**
* 判断坐标是否在close表中
*/
private boolean isCoordInClose(int x, int y)
{
if (closeList.isEmpty()) return false;
for (Node node : closeList)
{
if (node.coord.x == x && node.coord.y == y)
{
return true;
}
}
return false;
}353637383940414243444546
(4) 计算H值，“曼哈顿” 法，坐标分别取差值相加
private int calcH(Coord end,Coord coord)
{
return Math.abs(end.x - coord.x) + Math.abs(end.y - coord.y);
}12341234
(5) 从Open列表中查找结点
private Node findNodeInOpen(Coord coord)
{
if (coord == null || openList.isEmpty()) return null;
for (Node node : openList)
{
if (node.coord.equals(coord))
{
return node;
}
}
return null;
}
(6) 添加邻结点到Open表
/**
* 添加所有邻结点到open表
*/
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current)
{
int x = current.coord.x;
int y = current.coord.y;
// 左
addNeighborNodeInOpen(mapInfo,current, x - 1, y, DIRECT_VALUE);
// 上
addNeighborNodeInOpen(mapInfo,current, x, y - 1, DIRECT_VALUE);
// 右
addNeighborNodeInOpen(mapInfo,current, x + 1, y, DIRECT_VALUE);
// 下
addNeighborNodeInOpen(mapInfo,current, x, y + 1, DIRECT_VALUE);
// 左上
addNeighborNodeInOpen(mapInfo,current, x - 1, y - 1, OBLIQUE_VALUE);
// 右上
addNeighborNodeInOpen(mapInfo,current, x + 1, y - 1, OBLIQUE_VALUE);
// 右下
addNeighborNodeInOpen(mapInfo,current, x + 1, y + 1, OBLIQUE_VALUE);
// 左下
addNeighborNodeInOpen(mapInfo,current, x - 1, y + 1, OBLIQUE_VALUE);
}

/**
* 添加一个邻结点到open表
*/
private void addNeighborNodeInOpen(MapInfo mapInfo,Node current, int x, int y, int value)
{
if (canAddNodeToOpen(mapInfo,x, y))
{
Node end=mapInfo.end;
Coord coord = new Coord(x, y);
int G = current.G + value; // 计算邻结点的G值
Node child = findNodeInOpen(coord);
if (child == null)
{
int H=calcH(end.coord,coord); // 计算H值
if(isEndNode(end.coord,coord))
{
child=end;
child.parent=current;
child.G=G;
child.H=H;
}
else
{
child = new Node(coord, current, G, H);
}
openList.add(child);
}
else if (child.G > G)
{
child.G = G;
child.parent = current;
// 重新调整堆
openList.add(child);
}
}
}85960618596061
(7) 回溯法绘制路径
private void drawPath(int[][] maps, Node end)
{
if(end==null||maps==null) return;
System.out.println("总代价：" + end.G);
while (end != null)
{
Coord c = end.coord;
maps[c.y][c.x] = PATH;
end = end.parent;
}
}12345678910111234567891011
(8) 开始算法，循环移动结点寻找路径，设定循环结束条件，Open表为空或者最终结点在Close表

public void start(MapInfo mapInfo)
{
if(mapInfo==null) return;
// clean
openList.clear();
closeList.clear();
// 开始搜索
openList.add(mapInfo.start);
moveNodes(mapInfo);
}

/**
* 移动当前结点
*/
private void moveNodes(MapInfo mapInfo)
{
while (!openList.isEmpty())
{
if (isCoordInClose(mapInfo.end.coord))
{
drawPath(mapInfo.maps, mapInfo.end);
break;
}
Node current = openList.poll();
closeList.add(current);
addNeighborNodeInOpen(mapInfo,current);
}
}
单元和区域和数值，，，中的最大

❼ 急求：初识A*算法 这个的源代码！！

#include <iostream>
#include <cmath>
using namespace std;

struct tnode{

int gvalue;//以下3个参数是估计函数
int hvalue;
int fvalue;
tnode* parent;//不是父节点，而是指向当前节点
tnode* next;//指向链表的下一个节点
int pass;
int nodevalue;//唯一标示节点
};

tnode table[5][5];//存储地图5*5
int startx,starty,endx,endy;
tnode openlist,closelist;

void computervalue(const int curx,const int cury);
int intsearch(tnode *plist,int value);//C++需要int
void addopenlist(int hx,int hy);
void handlenode(int hx,int hy,int curx,int cury);

void main()
{
tnode *pp;
int x,y;
int i,j;//要定义
for ( i=0;i<=4;i++)//初始化
for ( j=0;j<=4;j++)
{
table[i][j].gvalue=0;
table[i][j].hvalue=0;
table[i][j].fvalue=0;
table[i][j].parent=0;
table[i][j].next=0;
table[i][j].pass=1;
table[i][j].nodevalue=(i+1)*(j+1);
}
cout<<"输入不可以通过的位置，格式为坐标X 坐标Y"<<endl;
for (i=1;i<=3;i++)
{
cin>>x>>y;
table[x][y].pass=0;
}

cout<<"输入起始的位置，格式为坐标X 坐标Y"<<endl;
cin>>startx>>starty;

cout<<"输入结束的位置，格式为坐标X 坐标Y"<<endl;
cin>>endx>>endy;

for (i=0;i<=4;i++)//打印地图结构
{
cout<<endl;
for (int k=0;k<=4;k++)
cout<<table[i][k].pass;
}

computervalue(startx,starty);

pp=&table[endx][endy];
while(pp->parent)
{
pp=pp->next;
cout<<pp->parent->nodevalue<<"=>";
}
system("pause");

}
//遍历链表，判段是否在列表中，找到返回1，否则返回0

int search(tnode *plist,int value)
{
while( (value!=plist->nodevalue) && plist->next)
plist=plist->next;

if(plist==0)
return 0;
else
return 1;
}

//把table[hx][hy]加入openlist有序链表

void addopenlist(int hx,int hy)
{

tnode *plist,*qlist=0;
plist=openlist.next;

while((plist->next!=0) && plist->nodevalue<(hx+1)*(hy+1) )
{
qlist=plist;
plist=plist->next;
}
table[hx][hy].next=qlist->next;
qlist->next=&table[hx][hy];

}

void handlenode(int hx,int hy,int curx,int cury)
{//对每一个相邻节点执行以下操作

/*1.如果该相邻节点不可通行或者该相邻节点已经在封闭列表中,
则什么操作也不执行,继续检验下一个节点;
2如果该相邻节点不在开放列表中,
则将该节点添加到开放列表中, 并将该相邻节点的父节点设为当前节点,
同时保存该相邻节点的G和F值;
3.如果该相邻节点在开放列表中,
则判断若经由当前节点到达该相邻节点的G值是否小于原来保存的G值,
若小于,则将该相邻节点的父节点设为当前节点,并重新设置该相邻节点的G和F值.
*/

if(!search(&openlist,(hx+1)*(hy+1)) && table[hx][hy].pass!=0)
{//不在openlist中

addopenlist(hx,hy);
table[hx][hy].parent=&table[curx][cury];

if(abs(curx-hx)+abs(cury-hy)==2)//计算gvalue值，因为传过来的hx，hy已经做过处理，这里只是处理+1，+2
table[hx][hy].gvalue+=2;
else table[hx][hy].gvalue+=1;

table[hx][hy].hvalue=(curx-hx)+(cury-hy);//计算hvalue
table[hx][hy].fvalue=table[hx][hy].gvalue+table[hx][hy].hvalue;//计算fvalue

}

else if(search(&openlist,(hx+1)*(hy+1)) && table[hx][hy].pass!=0)
{ //在openlist中
int tempx;//存放比较的中间值
if(abs(curx-hx)+abs(cury-hy)==2)
tempx=table[hx][hy].gvalue+2;
else tempx=table[hx][hy].gvalue+1;

if(tempx<table[hx][hy].gvalue)//判断是否更新
table[hx][hy].gvalue=tempx;

table[hx][hy].hvalue=(curx-hx)+(cury-hy);//计算hvalue

table[hx][hy].fvalue=table[hx][hy].gvalue+table[hx][hy].hvalue;//更新fvalue

}

}

void computervalue(int curx,int cury)
{//对每一个当前节点执行以下操作

if(curx==0)
{
if(cury==0)
{
handlenode(curx,cury+1,curx,cury);

handlenode(curx+1,cury,curx,cury);

handlenode(curx+1,cury+1,curx,cury);

}
else if(cury==4)
{
handlenode(curx-1,cury,curx,cury);

handlenode(curx,cury-1,curx,cury);

handlenode(curx-1,cury-1,curx,cury);

}
else
{
handlenode(curx,cury-1,curx,cury);

handlenode(curx,cury+1,curx,cury);

handlenode(curx+1,cury-1,curx,cury);

handlenode(curx+1,cury,curx,cury);

handlenode(curx+1,cury+1,curx,cury);

}
}

else if(curx==4)
{
if(cury==0)
{
handlenode(curx-1,cury,curx,cury);
//table[curx-1][cury].gvalue+=1;
handlenode(curx,cury+1,curx,cury);

handlenode(curx-1,cury+1,curx,cury);
}

else if(cury==4)
{
handlenode(curx-1,cury-1,curx,cury);

handlenode(curx-1,cury,curx,cury);

handlenode(curx,cury-1,curx,cury);

}
else
{
handlenode(curx,cury-1,curx,cury);

handlenode(curx,cury+1,curx,cury);

handlenode(curx-1,cury-1,curx,cury);

handlenode(curx-1,cury,curx,cury);

handlenode(curx-1,cury+1,curx,cury);

}
}

else if(cury==0)
{
handlenode(curx-1,cury,curx,cury);

handlenode(curx+1,cury,curx,cury);

handlenode(curx-1,cury+1,curx,cury);

handlenode(curx,cury+1,curx,cury);

handlenode(curx+1,cury+1,curx,cury);

}

else if(cury==4)
{
handlenode(curx-1,cury-1,curx,cury);

handlenode(curx,cury-1,curx,cury);

handlenode(curx+1,cury-1,curx,cury);

handlenode(curx-1,cury,curx,cury);

handlenode(curx+1,cury,curx,cury);

}

else
{
handlenode(curx,cury+1,curx,cury);

handlenode(curx+1,cury,curx,cury);

handlenode(curx+1,cury+1,curx,cury);

handlenode(curx-1,cury,curx,cury);

handlenode(curx-1,cury-1,curx,cury);

handlenode(curx-1,cury+1,curx,cury);

handlenode(curx,cury-1,curx,cury);

handlenode(curx+1,cury-1,curx,cury);
}
}

❽ A* 寻路算法

A*算法
�6�1 启发式搜索
– 在搜索中涉及到三个函数
�6�1 g(n) = 从初始结点到结点n的耗费
�6�1 h(n) = 从结点n到目的结点的耗费评估值，启发函数
�6�1 f(n)=g(n)+h(n) 从起始点到目的点的最佳评估值
– 每次都选择f(n)值最小的结点作为下一个结点，
直到最终达到目的结点
– A*算法的成功很大程度依赖于h(n)函数的构建
�6�1 在各种游戏中广泛应用 Open列表和Closed列表
– Open列表
�6�1 包含我们还没有处理到的结点
�6�1 我们最开始将起始结点放入到Open列表中
– Closed列表
�6�1 包含我们已经处理过的结点
�6�1 在算法启动时，Closed列表为空 A* 算法伪代码初始化OPEN列表
初始化CLOSED列表
创建目的结点；称为node_goal
创建起始结点；称为node_start
将node_start添加到OPEN列表
while OPEN列表非空{
从OPEN列表中取出f(n)值最低的结点n
将结点n添加到CLOSED列表中
if 结点n与node_goal相等then 我们找到了路径，程序返回n
else 生成结点n的每一个后继结点n'
foreach 结点n的后继结点n'{
将n’的父结点设置为n
计算启发式评估函数h(n‘)值，评估从n‘到node_goal的费用
计算g(n‘) = g(n) + 从n’到n的开销
计算f(n') = g(n') + h(n')
if n‘位于OPEN或者CLOSED列表and 现有f(n)较优then丢弃n’ ，处理后继n’
将结点n‘从OPEN和CLOSED中删除
添加结点n‘到OPEN列表
}
}
return failure （我们已经搜索了所有的结点，但是仍然没有找到一条路径）

❾ python apriori算法代码怎么实现

classApriori(object):
def__init__(self,filename,min_support,item_start,item_end):
self.filename=filename
self.min_support=min_support#最小支持度
self.min_confidence=50
self.line_num=0#item的行数
self.item_start=item_start#取哪行的item
self.item_end=item_end
self.location=[[i]foriinrange(self.item_end-self.item_start+1)]
self.support=self.sut(self.location)
self.num=list(sorted(set([jforiinself.locationforjini])))#记录item
self.pre_support=[]#保存前一个support,location,num
self.pre_location=[]
self.pre_num=[]
self.item_name=[]#项目名
self.find_item_name()
self.loop()
self.confidence_sup()
defdeal_line(self,line):
"提取出需要的项"
return[i.strip()foriinline.split('')ifi][self.item_start-1:self.item_end]
deffind_item_name(self):
"根据第一行抽取item_name"
withopen(self.filename,'r')asF:
forindex,lineinenumerate(F.readlines()):
ifindex==0:
self.item_name=self.deal_line(line)
break
defsut(self,location):
"""
输入[[1,2,3],[2,3,4],[1,3,5]...]
输出每个位置集的support[123,435,234...]
"""
withopen(self.filename,'r')asF:
support=[0]*len(location)
forindex,lineinenumerate(F.readlines()):
ifindex==0:continue
#提取每信息
item_line=self.deal_line(line)
forindex_num,iinenumerate(location):
flag=0
forjini:
ifitem_line[j]!='T':
flag=1
break
ifnotflag:
support[index_num]+=1
self.line_num=index#一共多少行,出去第一行的item_name
returnsupport
defselect(self,c):
"返回位置"
stack=[]
foriinself.location:
forjinself.num:
ifjini:
iflen(i)==c:
stack.append(i)
else:
stack.append([j]+i)
#多重列表去重
importitertools
s=sorted([sorted(i)foriinstack])
location=list(sfors,_initertools.groupby(s))
returnlocation
defdel_location(self,support,location):
"清除不满足条件的候选集"
#小于最小支持度的剔除
forindex,iinenumerate(support):
ifi<self.line_num*self.min_support/100:
support[index]=0
#apriori第二条规则,剔除
forindex,jinenumerate(location):
sub_location=[j[:index_loc]+j[index_loc+1:]forindex_locinrange(len(j))]
flag=0
forkinsub_location:
ifknotinself.location:
flag=1
break
ifflag:
support[index]=0
#删除没用的位置
location=[ifori,jinzip(location,support)ifj!=0]
support=[iforiinsupportifi!=0]
returnsupport,location
defloop(self):
"s级频繁项级的迭代"
s=2
whileTrue:
print'-'*80
print'The',s-1,'loop'
print'location',self.location
print'support',self.support
print'num',self.num
print'-'*80
#生成下一级候选集
location=self.select(s)
support=self.sut(location)
support,location=self.del_location(support,location)
num=list(sorted(set([jforiinlocationforjini])))
s+=1
iflocationandsupportandnum:
self.pre_num=self.num
self.pre_location=self.location
self.pre_support=self.support
self.num=num
self.location=location
self.support=support
else:
break
defconfidence_sup(self):
"计算confidence"
ifsum(self.pre_support)==0:
print'min_supporterror'#第一次迭代即失败
else:
forindex_location,each_locationinenumerate(self.location):
del_num=[each_location[:index]+each_location[index+1:]forindexinrange(len(each_location))]#生成上一级频繁项级
del_num=[iforiindel_numifiinself.pre_location]#删除不存在上一级频繁项级子集
del_support=[self.pre_support[self.pre_location.index(i)]foriindel_numifiinself.pre_location]#从上一级支持度查找
#printdel_num
#printself.support[index_location]
#printdel_support
forindex,iinenumerate(del_num):#计算每个关联规则支持度和自信度
index_support=0
iflen(self.support)!=1:
index_support=index
support=float(self.support[index_location])/self.line_num*100#支持度
s=[jforindex_item,jinenumerate(self.item_name)ifindex_itemini]
ifdel_support[index]:
confidence=float(self.support[index_location])/del_support[index]*100
ifconfidence>self.min_confidence:
print','.join(s),'->>',self.item_name[each_location[index]],'min_support:',str(support)+'%','min_confidence:',str(confidence)+'%'
defmain():
c=Apriori('basket.txt',14,3,13)
d=Apriori('simple.txt',50,2,6)
if__name__=='__main__':
main()

Apriori(filename, min_support, item_start, item_end)

参数说明

filename:(路径)文件名
min_support:最小支持度
item_start:item起始位置

item_end:item结束位置

importapriori
c=apriori.Apriori('basket.txt',11,3,13)

输出：

❿ 求A* 算法C语言源程序

#include <string.h>
#include <stdio.h>
#include <malloc.h>
#include <time.h>
#define NULL 0

const int nmax = 200;
const int nend = 99; /*终点坐标的代表点*/
static char achar[10][10];
static int npayo = 0; /*0 表示空 1为非空*/
static int npayc = 0; /*0 表示空 1为非空*/
static int npay_x = 0; /*起点*/
static int npay_y = 0;
static int nend_x = 9; /*终点*/
static int nend_y = 9;
static int nnewpay_x;
static int nnewpay_y;
static int ndian = 101;
static int nh;
static long i = 10000000L;

struct Spaydian
{
int ng;
int nf; /*路径评分*/
int nmy_x; /*自己位置*/
int nmy_y;
int nfatherx; /*父节点*/
int nfathery;
int nflag; /* 0 wei O; 1 wei @ */
};
static struct Spaydian spaydian[200];

/* open close list 表 */
typedef struct spaylist
{
int n_f;
int n_x;
int n_y;
int nfather_x;
int nfather_y;
struct spaylist *next;
};
static struct spaylist *open_list, *close_list;

static void smline();
static int sjudge(int nx,int ny,int i); /*判断在第nx列ny行向第i个方向走是否可以,可以返回1否则返回0。
i=1表示向右，2表示向下，3表示向左，4表示向上*/
static void spath();
static void spayshow(int nxx,int nyy);
static int sifopen( int nx,int ny); /*判断点是否在 open 表上*/
static int sifclose(int nx,int ny); /*判断点是否在 close 表上*/
static int snewx(int nx,int i);
static int snewy(int ny,int i);
static spaylist *creat(); /*建立链表*/
static spaylist *del(spaylist *head,int num_x,int num_y); /*删除链表的结点*/
static spaylist *snewdianx(spaylist *head);/*新的点*/
static spaylist *snewdiany(spaylist *head);
static spaylist *insert(spaylist *head,int ndian); /* 点插入链表 */
static spaylist *srebirth(spaylist *head,int ndian); /*更新表*/

int main()
{
FILE *fp ;
char ach ;
int ni = 0 ; /*统计个数*/
int nii = 0; /*achar[nii][njj]*/
int njj = 0;
if ((fp=fopen("route.txt","rt")) == NULL) /* 判断打开文件是否为空 */
{
printf("文件为空！~\n");
return 0;
/* exit(1);*/
}
ach = fgetc(fp);
while(ach != EOF)
{
if(ach == 'O' || ach == '@') /*当值为@或O时候*/
{
spaydian[ni].ng = 0;
spaydian[ni].nf = nmax;
spaydian[ni].nmy_x = njj;
spaydian[ni].nmy_y = nii;
spaydian[ni].nfathery = -1;
spaydian[ni].nfatherx = -1;
if(ach == '@')
{
spaydian[ni].nflag = 1;
}
else if(ach == 'O')
{
spaydian[ni].nflag = 0;
}
ni++;
achar[nii][njj] = ach;
njj++;
if(njj == 10)
{
nii++;
njj = 0;
}
} /*end if*/
ach = fgetc(fp);
}/*end while*/
smline(); /* a*算法 */
fp=fopen("answer.txt","w");
for(int i=0;i<10;i++ )
{ for(int j=0;j<10;j++ )
{
printf("%c",achar[i][j]);
if(j==9)
printf("\n");
fprintf(fp,"%c",achar[i][j]);
if (j==9)
fprintf(fp,"\n");
}
}
fclose(fp);
return 0;
}

/* a* 算法 */
static void smline()
{ close_list = open_list = NULL;
open_list = creat();
while(open_list != NULL) /* 当open 表不为空时 */
{
open_list = del(open_list,npay_x,npay_y); /*删除open 链表的结点*/
if(npay_x == 9 && npay_y == 9)
{

achar[9][9] = '=';
spath(); /*寻找并画出路径*/
break;
}
for (int i=1; i<=4; i++) /*四个方向逐个行走，i=1向右 2向下 3向左 4向上*/
{
if (sjudge(npay_x,npay_y,i))
{

nnewpay_x = snewx(npay_x,i);
nnewpay_y = snewy(npay_y,i);
if(open_list != NULL)
npayo = sifopen(nnewpay_x,nnewpay_y) ; /*判断点是否在 open 表中*/
else
npayo = 0;

if(close_list != NULL)
npayc = sifclose(nnewpay_x,nnewpay_y) ; /*判断点是否在 close 表中*/
else
npayc = 0;
ndian = 10*nnewpay_x+nnewpay_y ;

if (npayo == 0 && npayc == 0 ) /*点不在open表也不在close表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1; /*更新点的基本信息*/
nh = (nend - ndian)/10 + (nend - ndian)%10 ;
spaydian[ndian].nf = spaydian[ndian].ng+nh;
spaydian[ndian].nfathery = npay_y;
spaydian[ndian].nfatherx = npay_x;
spaydian[ndian].nmy_y = nnewpay_y;
spaydian[ndian].nmy_x = nnewpay_x;

open_list = insert(open_list,ndian);/*点插入open 表中*/
}
else if (npayo == 1) /*点在open表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1;
nh = (nend - ndian)/10 + (nend - ndian)%10 ;
if(spaydian[ndian].nf > (spaydian[ndian].ng+nh) && spaydian[ndian].nf != nmax)
{
spaydian[ndian].nf = spaydian[ndian].ng+nh;
open_list = srebirth(open_list,ndian); /*点插入open 表中*/
}
}
else if(npayc == 1) /*新生成的点在close表中*/
{
spaydian[ndian].ng = spaydian[10*npay_x+npay_y].ng + 1;
nh = (nend - ndian)/10 + (nend - ndian)%10 ;
if(spaydian[ndian].nf > (spaydian[ndian].ng+nh) && spaydian[ndian].nf != nmax)
{
spaydian[ndian].nf = spaydian[ndian].ng+nh;
close_list = srebirth(close_list,ndian);
close_list = del(close_list,nnewpay_x,nnewpay_y); /*删除close链表的结点*/
open_list = insert(open_list,ndian);/*点插入open 表中*/
}
}/*end else if*/
}/*end if*/
}/*end for*/
close_list = insert(close_list,(10*npay_x+npay_y));/*点插入close 表中*/
if(open_list != NULL)
{
npay_x = open_list->n_x;
npay_y = open_list->n_y;
}

}/*end while*/
if(open_list == NULL)
{printf("无路可走 \n");}
}

/*建立链表*/
spaylist *creat(void)
{
spaylist *head;
spaylist *p1;
int n=0;
p1=(spaylist*)malloc(sizeof(spaylist));
p1->n_f = 18;
p1->n_x = 0;
p1->n_y = 0;
p1->nfather_x = -1;
p1->nfather_x = -1;
p1->next = NULL;
head = NULL;
head=p1;
return(head);
}

/*删除结点*/
spaylist *del(spaylist *head,int num_x,int num_y)
{
spaylist *p1, *p2;
if(head == NULL)
{
printf("\nlist null!\n");
return (head);
}
p1 = head;
while((num_y != p1->n_y ||num_x != p1->n_x )&& p1->next != NULL)
{
p2=p1;
p1=p1->next;
}
if(num_x == p1->n_x && num_y == p1->n_y )
{
if(p1==head)
head=p1->next;
else
p2->next=p1->next;
}

return (head);
}

/*输出*/
static void spath()
{
int nxx;
int nyy;
nxx = spaydian[nend].nfatherx;
nyy = spaydian[nend].nfathery;

spayshow(nxx,nyy) ;
}

/*递归*/
void spayshow(int nxx,int nyy)
{ achar[nxx][nyy] = '=';
if( nxx != 0 || nyy != 0 )
{
int nxxyy = 10*nxx+nyy;
nxx = spaydian[nxxyy].nfatherx;
nyy = spaydian[nxxyy].nfathery;
spayshow(nxx,nyy);
}
}

/* 判断周围四个点是否可行 */
static int sjudge(int nx,int ny,int i)
{
if (i==1) /*判断向右可否行走*/
{
if (achar[nx][ny+1]=='O' && ny<9)
{
return 1;
}
else
return 0;
}
else if (i==2) /*判断向下可否行走*/
{
if (achar[nx+1][ny]=='O' && nx<9)
{
return 1;
}
else
return 0;
}
else if (i==3)/*判断向左可否行走 */
{
if (ny > 0&&achar[nx][ny-1]=='O')
{
return 1;
}
else
return 0;
}
else if (i==4)/*判断向上可否行走 */
{
if (nx > 0&&achar[nx-1][ny]=='O')
{
return 1;
}
else
return 0;
}
else
return 0;
}

/* 求新的x点 */
static int snewx(int nx,int i)
{
if(i == 1)
nx = nx;
else if(i == 2)
nx = nx+1;
else if(i == 3)
nx = nx;
else if(i == 4)
nx = nx-1;
return nx;
}
/* 求新的y点 */
static int snewy(int ny, int i)
{
if(i == 1)
ny = ny+1;
else if(i == 2)
ny = ny;
else if(i == 3)
ny = ny-1;
else if(i == 4)
ny = ny;
return ny;
}

/*判定点是否在open表中*/
int sifopen(int nx,int ny)
{
spaylist *p1, *p2;
p1 = open_list;
while((ny != p1->n_y || nx != p1->n_x )&& p1->next != NULL)
{
p2 = p1;
p1 = p1->next;
}
if(nx == p1->n_x && ny == p1->n_y)
return 1;
else
return 0;
}

/*判定点是否在close表中*/
int sifclose(int nx,int ny)
{

spaylist *p1, *p2;
p1 = close_list;
while((ny != p1->n_y ||nx != p1->n_x )&& p1->next != NULL)
{
p2=p1;
p1=p1->next;
}
if(nx == p1->n_x && ny == p1->n_y)
return 1;
else
return 0;
}

/*插入结点*/
spaylist * insert(spaylist *head,int ndian)
{
spaylist *p0,*p1,*p2;
p1=head;
p0=(spaylist*)malloc(sizeof(spaylist));
p0->n_f = spaydian[ndian].nf;
p0->n_x = spaydian[ndian].nmy_x;
p0->n_y = spaydian[ndian].nmy_y;
p0->nfather_x = spaydian[ndian].nfatherx;
p0->nfather_x = spaydian[ndian].nfathery;
p0->next = NULL;
if(head==NULL)
{
head=p0;
p0->next=NULL;
}
else
{
while((p0->n_f > p1->n_f)&&(p1->next!=NULL))
{
p2=p1;
p1=p1->next;
}
if(p0->n_f <= p1->n_f)
{
if(head==p1)
head=p0;
else
p2->next=p0;
p0->next=p1;
}
else
{
p1->next=p0;
p0->next=NULL;
}
}
return (head);
}

/* 更新链表 */
spaylist * srebirth(spaylist *head,int ndian)
{
spaylist *p1, *p2;
p1=head;
while(spaydian[ndian].nmy_x!=p1->n_x&&spaydian[ndian].nmy_x!=p1->n_x&&p1->next!=NULL)
{
p2=p1;
p1=p1->next;
}
if(spaydian[ndian].nmy_x==p1->n_x&&spaydian[ndian].nmy_x==p1->n_x)
{
p1->n_f = spaydian[ndian].nf;
}
return (head);
}