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);
}