2 2 4 划线法
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

对网上的博弈论划线法的总结如下。
 
完全信息静态博弈是指博弈各方同时决策，任何博弈参与者对博弈信息均完全了解。博弈信息包括：博弈过程、博弈结果、博弈各方的策略集、收益等。它的均衡可以用纳什均衡，且每个完全信息静态博弈都存在这样的均衡。纳什均衡可以用划线法+支付矩阵来求得，但并不是所有的求解纳什均衡都可以用这个方法。
 
参与者位于支付矩阵的上部和左部，参与者的策略位于矩阵左部和上部，矩阵中的数值为组合策略对于参与者的利益值。
 
这里拿剪刀石头布博弈来说，支付矩阵如下图所示：
 
 
其中第一行第一列（0，0）表示参与者都选择锤头的策略对于两个参与者的利益都是0。
 
 
划线原理：假设除了最后一个参与者其他参与者都选定某个策略，最后一个参与者选择对他来说利益最大的策略，相应最大值下面划横线。划线方法：按列比较各行第一个分量; 按行比较各列的第二的分量; 分别在最大值下划线; 其实就是找双方赢得都最大的偶对
 
所以以第一行为例，对于第一行所有数据的第二个分量的最大值为1，在1下面画横线。对于两个分量都画了横线的数据就是双赢的情况，显然图中没有这样的数据，说明有些博弈通过划线法不能找出纳什均衡，这就是两个参与者划线方法。
 
 
 
那如果是3个参与者呢，如下图所示问题：
 
 
以博弈方3来划分为3个支付矩阵，上图是博弈方3在选择A的时候对应的支付矩阵。第一个和第二个分量的划线方法和之前的两个参与者划线方法一样，对每一列只看第一个分量，每一行只看第二个分量，找最大值划线。因为划线的实质就是假设某个参与者选择了某个策略，对于另一个参与者选择当前情况收益最大的策略。类似的原理，对于第三个分量划线的方法是：三个支付矩阵的同一格进行比较第三个分量，在最大值下面划线，这等价于在参与者1和参与者2都选定策略的情况下，对不同策略对应的利益值中选择最大值。
 
 
 
 

DDA划线法(Digital Differenttial Analyzer,数值微分法)@TOC
 
利用计算机画出一条高质量直线
 输入：直线两个端点的坐标p0(x0,y0)和p1(x1,x2)
 输出：最佳逼近这条直线的像素点集
 
 在计算机中这些点集都是离散的，高质量直线的要求应满足
 以下三个条件：
 （1）直线要直，像素点尽可能靠近理想直线
 （2）直线要均匀，连续，点数不能多也不能少
 （3）显示线段的速度应该快，不能有卡顿现象（像素点的定位不能用乘除法，要用加减法，而且是正数加减法）
 
DDA算法是计算机图形学中画直线的基本算法，主要根据直线的斜截方程式（y=kx+b）推导出来的。
 假设(|k|<=1)
 x(i+1)=xi+1
 y(i+1)=yi+k
 
推导 y0=kx0+b;
 x1=x0+1;
 y1=k(x0+1)+b=kx0+k+b=y0+k;
 
最终下一坐标(x,int(y+0.5) //y取整)
 
假设(|k|>1)
 y(i+1)=yi+1;
 x(i+1)=xi+1/k
 
推导 y0=kx0+b;
 y1=y0+1;
 y0+1=k(x1)+b; x1=(y0+1-b)/k;
 x1=x0+1/k;
 
最终下一坐标(int(x+0.5),y) //x取整)
 代码
 
void CthreeView::OnDraw(CDC* pDC)
{
	CthreeDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	if (!pDoc)
		return;

	 //TODO: 在此处为本机数据添加绘制代码
	//DDA算法
	int x0 = 100, y0 = 100, x1 = 300, y1 = 200;
	float x, y, i, dx, dy, k;
	dx = (float)(x1 - x0); dy = (float)(y1 - y0);
	k = dy / dx; y = y0; x = x0;
	if (abs(k) < 1)
	{
		for (; x <= x1; x++)
		{
			pDC->SetPixel(x, int(y + 0.5), RGB(255, 0, 0));
			y = y + k;
		}
	}
	if (abs(k) >= 1)
	{
		for (; y <= y1; y++)
		{
			pDC->SetPixel(int(x + 0.5), y, RGB(255, 0, 0));
			x = x + 1 / k;
		}
	}
}

      第一次学绘图，后来发现书上的SetPixel函数在vc6.0中不能用。就去百度查找了，找了好久才找到easyx（包含graphics.h头文件）。最后又查找了easyx帮助文档找到putpixel(x,y,color)( 在指定位置画一像素)能够代替书上的SetPixel（x,y,color）。
 
       由于书本上只有斜率在0~1范围内的终点划线法，又根据书本上的方法找到了在其它斜率下的情况。
 
 
0<=k<=1
 
 
-1<=k<=0
 
 
k>1
 
 
k<-1
 
 
d=2a+b
 
 
d=2a-b
 
 
d=a+2b
 
 
d=a-2b
 
 
d>0:d2=d1+2a
 
d<=0:d2=d1+2a+2b
 
 
d>0:d2=d1+2a-2b
 
d<=0:d2=d1+2a
 
 
d>0:d2=d1+2a+2b
 
d<=0:d2=d1+2b
 
 
d>0:d2=d1-2a
 
d<=0:d2=d1+2a-2b
 
由于在graphics.h头文件中使用initgraph(x,y)建立绘图屏幕 只能是左上角为（0,0）
 
坐标，x坐标向右，y坐标向下的第一象限。所以在测试数据时候只能写起始坐标（x0,y0）终点坐标(x1,y1)在第一象限内的直线（即x0>=0,x1>=0,y0>=0,y1>=0）；
 
Easyx下载地址：http://www.easyx.cn/downloads/
 
编程环境：vc6.0(安装了easyx)
 
运行:windows7旗舰版
 
至于源代码，等我的作业交上去了在贴上吧，先贴上运行结果
 
 
 
#include <stdio.h>
#include <graphics.h>
#include <conio.h>
//中点画线法斜率为0~1斜率为0~1
void MidPointLine1(int x0,int y0,int x1,int y1)
{
	//初始一个480*480的绘图屏幕
	initgraph(480, 480); 
	int a,b,delta1,delta2,d,x,y;
	a=y0-y1;
	b=x1-x0;
	d=2*a+b;
	delta1=2*a;
	delta2=2*(a+b);
	x=x0;
	y=y0;
	//在对应的x,y像素点着色
	putpixel(x,y,GREEN);
	while(x<x1)
	{
		if(d<0)
		{
			x++;
			y++;
			d+=delta2;
		}
		else
		{
			x++;
			d+=delta1;
		}
		//在对应的x,y像素点着色
		putpixel(x,y,GREEN);
	//可以把下面这句取消注释，按回车看画线过程。
	//	system("pause");

	}
	//为了能够看到绘图效果 加了getch() 否则会直接关闭绘图屏幕
	getch();
	closegraph();
}
//斜率>1
void MidPointLine2(int x0,int y0,int x1,int y1)
{
	//初始一个480*480的绘图屏幕
	initgraph(480, 480); 
	int a,b,delta1,delta2,d,x,y;
	a=y0-y1;
	b=x1-x0;
	d=a+2*b;
	delta1=2*(a+b);
	delta2=2*b;
	x=x0;
	y=y0;
	//在对应的x,y像素点着色
	putpixel(x,y,GREEN);
	while(y<y1)
	{
		if(d<0)
		{
			y++;
			d+=delta2;
		}
		else
		{
			y++;
			x++;
			d+=delta1;
		}
		//在对应的x,y像素点着色
		putpixel(x,y,GREEN);
	//可以把下面这句取消注释，按回车看画线过程。
	//	system("pause");

	}
	//为了能够看到绘图效果 加了getch() 否则会直接关闭绘图屏幕
	getch();
	closegraph();
}
//斜率为-1~0
void MidPointLine3(int x0,int y0,int x1,int y1)
{
	//初始一个480*480的绘图屏幕
	initgraph(480, 480); 
	int a,b,delta1,delta2,d,x,y;
	a=y0-y1;
	b=x1-x0;
	d=2*a-b;
	delta1=2*a-2*b;
	delta2=2*a;
	x=x0;
	y=y0;
	//在对应的x,y像素点着色
	putpixel(x,y,GREEN);
	while(x<x1)
	{
		if(d<0)
		{
			x++;
			d+=delta2;
		}
		else
		{
			x++;
			y--;
			d+=delta1;
		}
		//在对应的x,y像素点着色
		putpixel(x,y,GREEN);
	//可以把下面这句取消注释，按回车看画线过程。
	//	system("pause");

	}
	//为了能够看到绘图效果 加了getch() 否则会直接关闭绘图屏幕
	getch();
	closegraph();
}

//斜率<-1
void MidPointLine4(int x0,int y0,int x1,int y1)
{
	//初始一个480*480的绘图屏幕
	initgraph(480, 480); 
	int a,b,delta1,delta2,d,x,y;
	a=y0-y1;
	b=x1-x0;
	d=a-2*b;
	delta1=-2*b;
	delta2=2*(a-b);
	x=x0;
	y=y0;
	//在对应的x,y像素点着色
	putpixel(x,y,GREEN);
	while(y>y1)
	{
		if(d<0)
		{
			x++;
			y--;
			d+=delta2;
		}
		else
		{
			y--;
			d+=delta1;
		}
		//在对应的x,y像素点着色
		putpixel(x,y,GREEN);
	//可以把下面这句取消注释，按回车看画线过程。
	//	system("pause");
	}
	//为了能够看到绘图效果 加了getch() 否则会直接关闭绘图屏幕
	getch();
	closegraph();
}
int main()
{
	int x1,y1,x2,y2;
	printf("请输入起始点，终点坐标（用空格隔开，回车结束）：");
	scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
	//根据斜率范围判断对应函数
	float k=(float)(y2-y1)/(float)(x2-x1);
	
	if(k>=0&&k<=1)
		MidPointLine1(x1,y1,x2,y2);//斜率为0~1 测试数据0 0 320 100
	else if(k>1)
		MidPointLine2(x1,y1,x2,y2);//斜率为>1  测试数据0 0 100 320
	else if(k>=-1&&k<=0)
		MidPointLine3(x1,y1,x2,y2);//斜率为-1~0 测试数据0 100 200 0
	else
		MidPointLine4(x1,y1,x2,y2);//斜率为<-1 测试数据0 200 100 0

}
 
 
 
 
 
 
 
 
 
 
 
 
 
运行结果：
 
1.测试数据：0 0 320 100
 
 
 
运行结果：
 
 
 
 
 
 
2.测试数据：0 0 100 320
 
 
 
运行结果：
 
 
 
 
 
 
 
3.测试数据：0 100 200 0
 
 
 
运行结果：
 
 
 
 
 
 
 
4.测试数据：0 200 100 0
 
 
 
运行结果：