「活性边表算法java算法」活性边表算法例题

今天给各位分享活性边表算法java算法的知识，其中也会对活性边表算法例题进行解释，如果能碰巧解决你现在面临的问题，别忘了关注本站，现在开始吧！

本文目录一览：

• 1、多边形扫描转换中，活性边表的数据结构有哪几项
• 2、北大青鸟java培训：人工智能开发机器学习的常用算法？
• 3、JAVA中有哪几种常用的排序方法？每个排序方法的实现思路是如何的？每个方法的思想是什么？？
• 4、用java求最短路径问题，求源程序

多边形扫描转换中，活性边表的数据结构有哪几项

该算法用到的数据结构有：

typedef struct nodeEdge

{

int ymax; //边的上端点的y坐标

float x; //在AEL中表示当前扫描线与边的交点的x坐标，

//初值(即在ET中的值)为边的下端点x的坐标

float deltax; //边的斜率的倒数

nodeEdge *nextEdge; //指向下一条边的指针

}Edge; //边的分类表和活化边表的数据结构（扫描转换多边形的扫描线算法）

void CGraphicsView::SCanPolygon(int color,CDC*pDC)

{

//扫描转换多边形—扫描线算法

Edge *et[ARRLENGTH];

Edge e[90];

Edge* ael;

Edge test;

Edge *left,*right; //left和right做配对用

int i;

for(i=0;iARRLENGTH;i++)

{

et[i]=NULL;

}

//手动生成et表

e[0].ymax=40; e[0].x=50; e[0].deltax=-1; e[0].nextEdge=e[20];

e[20].ymax=50; e[20].x=70; e[20].deltax=5.0/4; e[20].nextEdge=NULL;

e[60].ymax=80; e[60].x=20; e[60].deltax=0; e[60].nextEdge=NULL;

e[30].ymax=110; e[30].x=120; e[30].deltax=0; e[30].nextEdge=NULL;

e[50].ymax=80; e[50].x=70; e[50].deltax=-5; e[50].nextEdge=e[40];

e[40].ymax=110; e[40].x=70; e[40].deltax=5.0/4; e[40].nextEdge=NULL;

et[0]=NULL; et[10]=e[0]; et[20]=NULL; et[30]=NULL;

et[40]=e[60]; et[50]=e[30]; et[60]=NULL; et[70]=e[50]; et[80]=NULL;

北大青鸟java培训：人工智能开发机器学习的常用算法？

我们在学习人工智能以及智能AI技术的时候曾经给大家介绍过不同的机器学习的方法，而今天我们就着重介绍一下，关于机器学习的常用算法都有哪些类型。

支持向量机是什么?支持向量机是一种有监督的机器学习算法，可以用于分类或回归问题。

它使用一种称为核技巧的技术来转换数据，然后根据这些转换在可能的输出之间找到一个边界。

简单地说，它做一些非常复杂的数据转换，然后根据定义的标签或输出来划分数据。

那么是什么让它如此伟大呢?支持向量机既能进行分类又能进行回归。

在本文中，我将重点介绍如何使用SVM进行分类。

我将特别关注非线性支持向量机，或者说是使用非线性核的支持向量机。

非线性支持向量机意味着算法计算的边界不一定是直线。

好处是您可以捕获数据点之间更复杂的关系，而不必自己做困难的转换。

缺点是训练时间更长，因为它需要更多的计算。

那么核技巧是什么?核技巧对你获得的数据进行转换。

有一些很好的特性，你认为可以用来做一个很好的分类器，然后出来一些你不再认识的数据。

这有点像解开一条DNA链。

你从这个看起来很难看的数据向量开始，在通过核技巧之后，它会被解开并自我复合，直到它现在是一个更大的数据集，通过查看电子表格无法理解。

但是这里有魔力，在扩展数据集时，你的类之间现在有更明显的界限，SVM算法能够计算出更加优化的超平面。

接下来，假设你是一个农民，你有一个问题-你需要设置一个围栏，以保护你的奶牛免受狼的攻击。

但是你在哪里建造篱笆?好吧，如果你是一个真正的数据驱动农民，你可以做的一件事就是建立一个基于你牧场中奶牛和狼的位置的分类器。

天津北大青鸟建议通过几种不同类型的分类器，我们看到SVM在从狼群中分离你的奶牛方面做得很好。

我认为这些图也很好地说明了使用非线性分类器的好处。

您可以看到逻辑和决策树模型都只使用直线。

JAVA中有哪几种常用的排序方法？每个排序方法的实现思路是如何的？每个方法的思想是什么？？

一、冒泡排序

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较 a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，以此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对 a[1]~a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]~a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，以此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

优点：稳定；

缺点：慢，每次只能移动相邻两个数据。

二、选择排序

冒泡排序的改进版。

每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

选择排序是不稳定的排序方法。

n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果：

①初始状态：无序区为R[1..n]，有序区为空。

②第1趟排序

在无序区R[1..n]中选出关键字最小的记录R[k]，将它与无序区的第1个记录R[1]交换，使R[1..1]和R[2..n]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

……

③第i趟排序

第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(1≤i≤n- 1)。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

这样，n个记录的文件的直接选择排序可经过n-1趟直接选择排序得到有序结果。

优点：移动数据的次数已知（n-1次）；

缺点：比较次数多。

三、插入排序

已知一组升序排列数据a[1]、a[2]、……a[n]，一组无序数据b[1]、 b[2]、……b[m]，需将二者合并成一个升序数列。首先比较b[1]与a[1]的值，若b[1]大于a[1]，则跳过，比较b[1]与a[2]的值，若b[1]仍然大于a[2]，则继续跳过，直到b[1]小于a数组中某一数据a[x]，则将a[x]~a[n]分别向后移动一位，将b[1]插入到原来 a[x]的位置这就完成了b[1]的插入。b[2]~b[m]用相同方法插入。（若无数组a，可将b[1]当作n=1的数组a）

优点：稳定，快；

缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决这个问题。

三、缩小增量排序

由希尔在1959年提出，又称希尔排序(shell排序)。

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。发现当n不大时，插入排序的效果很好。首先取一增量d(dn)，将a[1]、a[1+d]、a[1+2d]……列为第一组，a[2]、a[2+d]、 a[2+2d]……列为第二组……，a[d]、a[2d]、a[3d]……列为最后一组以次类推，在各组内用插入排序，然后取d'd，重复上述操作，直到d=1。

优点：快，数据移动少；

缺点：不稳定，d的取值是多少，应取多少个不同的值，都无法确切知道，只能凭经验来取。

四、快速排序

快速排序是目前已知的最快的排序方法。

已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先任取数据 a[x]作为基准。比较a[x]与其它数据并排序，使a[x]排在数据的第k位，并且使a[1]~a[k-1]中的每一个数据a[x]，a[k+1]~a[n]中的每一个数据a[x]，然后采用分治的策略分别对a[1]~a[k-1]和a[k+1]~a[n] 两组数据进行快速排序。

优点：极快，数据移动少；

缺点：不稳定。

五、箱排序

已知一组无序正整数数据a[1]、a[2]、……a[n]，需将其按升序排列。首先定义一个数组x[m],且m=a[1]、a[2]、……a[n]，接着循环n次，每次x[a]++.

优点：快，效率达到O(1)

缺点：数据范围必须为正整数并且比较小

六、归并排序

归并排序是多次将两个或两个以上的有序表合并成一个新的有序表。最简单的归并是直接将两个有序的子表合并成一个有序的表。

归并排序是稳定的排序.即相等的元素的顺序不会改变.如输入记录 1(1) 3(2) 2(3) 2(4) 5(5) (括号中是记录的关键字)时输出的 1(1) 2(3) 2(4) 3(2) 5(5) 中的2 和 2 是按输入的顺序.这对要排序数据包含多个信息而要按其中的某一个信息排序,要求其它信息尽量按输入的顺序排列时很重要.这也是它比快速排序优势的地方.

用java求最短路径问题，求源程序

import java.util.Vector;

public class Link {

private Vector link = new Vector();

// private Link next = null;

public Link() {

}

public boolean addNode(Node setNode){//增加一个节点

setNode = checkNode(setNode);

if(setNode != null){

this.link.addElement((Node)setNode);

return true;

}

return false;

}

public void delNode(Node setNode){ //删除一个节点

if(!this.link.isEmpty()){

for(int i=0;i this.link.size(); i++)

{

if(setNode.getPos() == ((Node)this.link.elementAt(i)).getPos()){

this.link.remove(i);

//System.out.println("asdfasdfas:"+this.link.size());

break;

}

}

}

}

public Node checkNode(Node setNode){//判断节点是否在链表里面并取得两者的最佳值

if(!this.link.isEmpty() setNode!=null){

for(int i=0;i this.link.size(); i++)

{

if(setNode.getPos() == ((Node)this.link.elementAt(i)).getPos()){

if(setNode.getStep() ((Node)this.link.elementAt(i)).getStep()){

setNode = (Node)this.link.elementAt(i);

this.link.remove(i);

}

else

return null;

break;

}

}

}

return setNode;

}

public boolean isEmpty(){

return this.link.isEmpty();

}

public Node getBestNode(){ //得到最好的节点

Node tmpNode = null;

if(!this.link.isEmpty()){

tmpNode = (Node)this.link.elementAt(0);

//System.out.println("tmpNodeStep:"+tmpNode.getStep());

//System.out.print("OpenNode(pos,step):");

for(int i=1;i this.link.size(); i++)

{

//System.out.print("("+((Node)this.link.elementAt(i)).getPos()+","+((Node)this.link.elementAt(i)).getStep()+")");

if(tmpNode.getJudgeNum() = ((Node)this.link.elementAt(i)).getJudgeNum()){

tmpNode = (Node)this.link.elementAt(i);

}

}

}

return tmpNode;

}

}

public class FindBestPath {

private char[][] map = null;//地图

private int maxX,maxY;//最大的地图边界大小

Node startNode = null;//入口

Node endNode = null;//出口

private int endX,endY;

/*初始化

*@param setMap 地图

*@param setX,setY 边界值

//////////*@param startNode 入口

//////////*param endNode 出口

*@param sX,sY:开始点

*@param eX,eY:结束点

*/

public FindBestPath(char[][] setMap,int setX,int setY,int sX,int sY,int eX,int eY) {

this.map = setMap;

this.maxY = setX - 1; //x,y互换

this.maxX = setY - 1; //x,y互换

//this.startNode = sNode;

//this.endNode = eNode;

Node sNode = new Node();

Node eNode = new Node();

sNode.setFarther(null);

sNode.setPos(posToNum(sX,sY));

sNode.setStep(0);

eNode.setPos(posToNum(eX,eY));

this.startNode = sNode;

this.endNode = eNode;

this.endX = eX;//numToX(eNode.getPos());

this.endY = eY;//numToY(eNode.getPos());

}

public int posToNum(int x,int y){//从xy坐标获得编号

return (x+y*(this.maxY+1));

}

public int numToX(int num){//从编号获得x坐标

return (num%(this.maxY+1));

}

public int numToY(int num){//从编号获得y坐标

return (int)(num/(this.maxY+1));

}

public boolean checkVal(int x,int y){//判断是否为障碍

//System.out.println("map["+x+"]["+y+"]="+map[x][y]);

if(this.map[x][y] == 'N')

return false;

else

return true;

}

public int judge(Node nowNode){//一定要比实际距离小

//System.out.println("nowNodePos:"+nowNode.getPos());

int nowX = numToX(nowNode.getPos());

int nowY = numToY(nowNode.getPos());

int distance = Math.abs((nowX-this.endX))+Math.abs((nowY-this.endY));

// System.out.println("distance:"+distance);

return distance;

}

public Node getLeft(Node nowNode){//取得左节点

int nowX = numToX(nowNode.getPos());

int nowY = numToY(nowNode.getPos());

Node tmpNode = new Node();

if(nowY 0){//判断节点是否到最左

if(checkVal(nowX,nowY-1)){

tmpNode.setFarther(nowNode);

tmpNode.setPos(posToNum(nowX,nowY-1));

tmpNode.setStep(nowNode.getStep()+1);

tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));

return tmpNode;

}

}

return null;

}

public Node getRight(Node nowNode){//取得右节点

int nowX = numToX(nowNode.getPos());

int nowY = numToY(nowNode.getPos());

Node tmpNode = new Node();

if(nowY this.maxX){//判断节点是否到最左

if(checkVal(nowX,nowY+1)){

tmpNode.setFarther(nowNode);

tmpNode.setPos(posToNum(nowX,nowY+1));

tmpNode.setStep(nowNode.getStep()+1);

tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));

return tmpNode;

}

}

return null;

}

public Node getTop(Node nowNode){//取得上节点

int nowX = numToX(nowNode.getPos());

int nowY = numToY(nowNode.getPos());

Node tmpNode = new Node();

if(nowX 0){//判断节点是否到最左

if(checkVal(nowX-1,nowY)){

tmpNode.setFarther(nowNode);

tmpNode.setPos(posToNum(nowX-1,nowY));

tmpNode.setStep(nowNode.getStep()+1);

tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));

return tmpNode;

}

}

return null;

}

public Node getBottom(Node nowNode){//取得下节点

int nowX = numToX(nowNode.getPos());

int nowY = numToY(nowNode.getPos());

Node tmpNode = new Node();

if(nowX this.maxY){//判断节点是否到最左

if(checkVal(nowX+1,nowY)){

tmpNode.setFarther(nowNode);

tmpNode.setPos(posToNum(nowX+1,nowY));

tmpNode.setStep(nowNode.getStep()+1);

tmpNode.setJudgeNum(tmpNode.getStep()+judge(tmpNode));

return tmpNode;

}

}

return null;

}

public Link getBestPath(){//寻找路径

Link openLink = new Link();//没有访问的路径

Link closeLink = new Link();//访问过的路径

Link path = null;//最短路径

Node bestNode = null;

Node tmpNode = null;

openLink.addNode(this.startNode);

while(!openLink.isEmpty())//openLink is not null

{

bestNode = openLink.getBestNode();//取得最好的节点

//System.out.println("bestNode:("+numToX(bestNode.getPos())+","+numToY(bestNode.getPos())+")step:"+bestNode.getJudgeNum());

if(bestNode.getPos()==this.endNode.getPos())

{

/*this.endNode.setStep(bestNode.getStep()+1);

this.endNode.setFarther(bestNode);

this.endNode.setJudgeNum(bestNode.getStep()+1);*/

path = makePath(bestNode);

break;

}

else

{

tmpNode = closeLink.checkNode(getLeft(bestNode));

if(tmpNode != null)

//System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");

openLink.addNode(tmpNode);

tmpNode = closeLink.checkNode(getRight(bestNode));

if(tmpNode != null)

// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");

openLink.addNode(tmpNode);

tmpNode = closeLink.checkNode(getTop(bestNode));

if(tmpNode != null)

// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");

openLink.addNode(tmpNode);

tmpNode = closeLink.checkNode(getBottom(bestNode));

if(tmpNode != null)

// System.out.println("("+numToY(tmpNode.getPos())+","+numToX(tmpNode.getPos())+")");

openLink.addNode(tmpNode);

openLink.delNode(bestNode);

closeLink.addNode(bestNode);

}

}

return path;

}

public Link makePath(Node lastNode){//制造路径

Link tmpLink = new Link();

Node tmpNode = new Node();

int x,y;

tmpNode = lastNode;

if(tmpNode != null){

do{

x=numToX(tmpNode.getPos());

y=numToY(tmpNode.getPos());

System.out.println("map["+x+"]["+y+"]="+map[x][y]);

tmpLink.addNode(tmpNode);

tmpNode = tmpNode.getFarther();

}while(tmpNode != null);

}else

{

System.out.println("Couldn't find the path!");

}

return tmpLink;

}

/**

* @param args the command line arguments

*/

public static void main(String[] args) {

char[][] map ={

{'Y', 'N', 'z', 'y', 'x', 'w', 'v', 'N', 'N', 'N'},

{'Y', 'N', '1', 'N', 'N', 'N', 'u', 't', 'N', 'N'},

{'N', '1', '2', '1', '1', '1', 'N', 's', 'N', 'N'},

{'N', 'N', '1', 'N', '9', 'N', 'q', 'r', 'N', 'N'},

{'N', 'N', '1', 'N', 'n', 'o', 'p', 'N', 'N', 'N'},

{'N', '4', '5', '6', 'm', 'N', 'N', 'N', 'N', 'N'},

{'N', '3', 'N', '5', 'l', 'k', 'j', 'N', 'N', 'N'},

{'N', 'N', '3', '4', 'N', 'd', 'i', 'd', 'N', 'N'},

{'N', '1', 'N', 'N', '1', 'N', 'h', 'N', 'N', 'N'},

{'N', '1', 'N', 'N', '1', 'N', 'g', 'N', 'N', 'N'},

{'N', 'a', 'b', 'c', 'd', 'e', 'f', 'N', 'N', 'N'}

};

/*map[x][y]

*如上所示：maxY=10 maxX=11 横的代表maxY,竖的代表maxX 可以自己替换

*地图的读取是

*for(i=1;i行的最大值;i++)

* for(j=1;j列的最大值;j++)

* map[i][j] = 地图[i][j]

*/

Link bestPath = new Link();

/*startNode.setFarther(null);

startNode.setPos(21);

startNode.setStep(0);

//endNode.setFarther(startNode);

endNode.setPos(79);

//endNode.setStep(0);*/

FindBestPath path = new FindBestPath(map, 11, 10, 10, 1, 0, 2);

//FindBestPath path = new FindBestPath(map, 11, 10, startNode, endNode);

bestPath = path.getBestPath();

//bestPath.printLink();

}

}

public class Node {

private int step;//从入口到该节点经历的步数

private int pos;//位置

private Node farther;//上一个结点

private int judgeNum;

public Node() {

}

public void setStep(int setStep){

this.step = setStep;

}

public int getStep(){

return this.step;

}

public void setPos(int setPos){

this.pos = setPos;

}

public int getPos(){

return this.pos;

}

public void setFarther(Node setNode){

this.farther = setNode;;

}

public Node getFarther(){

return this.farther;

}

public void setJudgeNum (int setInt){

this.judgeNum = setInt;;

}

public int getJudgeNum(){

return this.judgeNum;

}

}

活性边表算法java算法的介绍就聊到这里吧，感谢你花时间阅读本站内容，更多关于活性边表算法例题、活性边表算法java算法的信息别忘了在本站进行查找喔。