贪心算法着色
Ⅰ 关于C语言的问题,高手进
1. 迷宫问题
/////////////////////////
/////////迷宫求解////////
//////作者:hacker/////
/////时间:11.10.2006/////
/////////////////////////
//Migong.h
//利用栈进行回溯
/*class:
Matrix:矩阵类
offsets:搜索偏移
enum directions:四个方向
struct item:搜索节点
Migong:迷宫类
1.创建一个Migong对象
2.使用用Create方法输入数据
3.使用Solve方法进行求解
4.ShowSolve方法显示解
5.可以重复使用Create方法
6.入口只能在左上角
7.默认出口在右下角
ShowAllPath:穷举所有的路径
备注:
由于算法原因,这里的所有路径应该是指
介于:
a.如果两条路存在某个点不同那么就是不同的路
b.如果在一条路中去掉一个或者一个以上的圈,那么他们是同一条路
之间意义上的路
*/
#include <iostream>
#include <stack>
#include <vector>
using namespace std;
#ifndef MIGONG_H
#define MIGONG_H
///////////////////
///////矩阵类//////
///////////////////
class Matrix{
int* m;
int row, col;
bool iscreate;
public:
Matrix(){m=0;iscreate=false;};
~Matrix() {Release();};
bool Create(int, int);
int& operator () (int, int);
int GetRow(){return row;};
int GetCol(){return col;};
void Release();
void Show(char, char );
};
bool Matrix::Create(int r, int c)
{
if( r<=0 || c<=0) return false;
Release();
row = r;
col = c;
m = new int[row*col];
for (int i=0;i<row*col;i++)
{
*(m+i) = 0;
}
iscreate = true;
return true;
}
int& Matrix::operator ()(int r, int c)
{
return *(m+r*col+c);
}
void Matrix::Release()
{
if (iscreate)
{
row = col = 0;
if (m) delete[] m;
m = 0;
}
iscreate = false;
}
void Matrix::Show(char blk='#', char nblk=' ')
{
int i, j;
for (i=0;i<row;i++)
{
for (j=0;j<col;j++)
{
if (*(m+i*col+j) == 0)
cout<<nblk;
else
cout<<blk;
}
cout<<endl;
}
}
/////////////////////////////
////迷宫相关数据结构的定义///
/////////////////////////////
struct offsets{
int a, b;
};
enum directions{
_S = 0,
_E,
_N,
_W
};
struct item{
int row, col, dir;
};
class Migong{
static offsets move[4];
Matrix maze;
Matrix mark;
int row;
int col;
int desr;
int desc;
stack<item> stk;
bool iscreate;
int pathlength;
bool GetPath();
bool IsInPath(int, int);
public:
Migong(){issolved=false;result=0;pathlength=row=col=0;iscreate=false;};
~Migong(){Release();};
bool Create(int* , int , int , int , int );
void Solve();
void Release();
void OutputMaze();
void ShowSolve(char, char );
public:
bool issolved;
item* result;
};
offsets Migong::move[4]={ {1, 0}, {0, 1},
{-1, 0}, {0, -1}};
////////////////////////////
//迷宫数据应该是不含边框的//
////////////////////////////
bool Migong::Create(int* m, int r, int c, int desrow=-1, int descol=-1)
{
if (r<=0 || c<=0) return false;
Release();
if (desrow==-1 || descol==-1)
{
desr = r;
desc = c;
}
else
{
desr = desrow;
desc = descol;
}
row = r;
col = c;
maze.Create(r+2, c+2);
mark.Create(r+2, c+2);
int i, j;
for (i=0;i<r+2;i++)
{
for (j=0;j<c+2;j++)
{
if (j==0 || j==c+1 || i==0 || i==r+1)
{
mark(i, j) = maze(i, j) = 1;
}else
{
mark(i, j) = 0;
maze(i, j) = m[((i-1)*col+j-1)];
}
}
}
return iscreate = true;
}
bool Migong::GetPath()
{
mark(1,1) = 1;
item temp;
temp.col = 1;
temp.row = 1;
temp.dir = _S;
stk.push(temp);
while (!stk.empty())
{
temp = stk.top();
stk.pop();
int i = temp.row;
int j = temp.col;
int d = temp.dir;
while (d<4)
{//根据当前点的状态确定下一个搜索点
int g = i + move[d].a;
int h = j + move[d].b;
if (g==desr && h==desc)
{
return true;
}
//如果这个点不是障碍点且没有被搜索过那么可以对这个点进行搜索
if (maze(g, h)==0 && mark(g, h)==0)
{
mark(g, h) = 1;
temp.row = g;
temp.col = h;
temp.dir = d+1;
stk.push(temp);
i = g;
j = h;
d = _S;//对一下个点进行搜索
}
else d++;
}
}
return false;
}
void Migong::Solve()
{
issolved = GetPath();
if (issolved)
{
pathlength = stk.size();
result = new item[pathlength];
for (int i=0;i<pathlength;i++)
{
*(result+i) = stk.top();
stk.pop();
// cout<<"("<<(*(result+i)).row<<","<<(*(result+i)).col<<")"<<endl;
}
}
while (!stk.empty())
stk.pop();
}
void Migong::Release()
{
if (iscreate)
{
maze.Release();
mark.Release();
row=col=0;
if (result)
delete [] result;
result = 0;
while (!stk.empty())
stk.pop();
}
iscreate = false;
issolved = false;
pathlength = 0;
}
void Migong::OutputMaze()
{
if (!iscreate) return;
maze.Show();
}
bool Migong::IsInPath(int r, int c)
{
if (!iscreate || !issolved)
return false;
item temp;
for (int i=0;i<pathlength;i++)
{
temp = *(result+i);
if ((temp.row==r) && (temp.col==c))
return true;
}
return false;
}
void Migong::ShowSolve(char blk='#',char s='o')
{
if (!iscreate) return;
if (!issolved)
{
cout<<"无解"<<endl;
}
else
{
int i, j;
for (i=0;i<row+2;i++)
{
for (j=0;j<col+2;j++)
{
if ((i==1 && j==1) || (i==desr && j==desc))
{
cout<<s;
}
else if (maze(i, j) == 1)
{
cout<<blk;
}else
{
if (IsInPath(i, j))
cout<<s;
else
cout<<' ';
}
}
cout<<endl;
}
}
}
//////////////////////
//////穷举所有路径////
//////////////////////
offsets move[4]={ {1, 0}, {0, 1},
{-1, 0}, {0, -1}};
struct node
{
int row,col;
};
vector<node> path;
int count;
bool IsReachable( Matrix& maze, Matrix& mark, node beg, node des)
{
if (beg.row==des.row&&beg.col==des.col)
{//如果达到的话那么显示路径
count++;
cout<<"第"<<count<<"条路径:"<<endl;
for (int i=0;i<path.size();i++)
cout<<"("<<path[i].row<<","<<path[i].col<<")";
cout<<"("<<des.row<<","<<des.col<<")";
cout<<endl;
return false;
}
if (maze(beg.row, beg.col)==1 || mark(beg.row, beg.col)==1)
{
return false;
}
path.push_back(beg);
mark(beg.row, beg.col) = 1;
node nextnode;
for (int i=_S;i<_W+1;i++)
{
nextnode.row = beg.row + move[i].a;
nextnode.col = beg.col + move[i].b;
IsReachable(maze, mark, nextnode, des);
}
path.resize(path.size()-1);
mark(beg.row, beg.col) = 0;
return false;//如果不是穷举的话应该根据for循环的结果重新设置返回值
}
/*
参数maze,mark为迷宫长宽均加二的矩阵
desr,desc为出口点
*/
void FindAllPath( Matrix& maze, Matrix& mark, int desr, int desc)
{
node first, last;
first.row = 1;
first.col = 1;
last.row = desr;
last.col = desc;
IsReachable(maze, mark, first, last);
path.clear();
}
/*
m迷宫矩阵数据
r,c行和列的大小
desr,desc目标位置
*/
void ShowAllPath(int* m, int r, int c, int desr=-1, int desc=-1)
{
Matrix maze, mark;
maze.Create(r+2, c+2);
mark.Create(r+2, c+2);
if (desr==-1 || desc==-1)
{
desr = r;
desc = c;
}
int i, j;
for (i=0;i<r+2;i++)
{
for (j=0;j<c+2;j++)
{
if (j==0 || j==c+1 || i==0 || i==r+1)
{
mark(i, j) = maze(i, j) = 1;
}else{
mark(i, j) = 0;
maze(i, j) = m[((i-1)*c+j-1)];
}
}
}
count = 0;
FindAllPath(maze, mark, desr, desc);
maze.Release();
mark.Release();
}
#endif
//main.cpp
#include <iostream>
#include "Migong.h"
using namespace std;
int mg[]={
0,0,1,0,0,0,1,0,//1
0,0,1,0,0,0,1,0,//2
0,0,0,0,1,1,0,1,//3
0,1,1,1,0,0,1,0,//4
0,0,0,1,0,0,0,0,//5
0,1,0,0,0,0,0,1,//6
0,1,1,1,1,0,0,1,//7
1,1,0,0,0,1,0,1,//8
1,1,0,0,0,0,0,0,//9
};
void main()
{
Migong m;
m.Create(mg, 9, 8);
m.OutputMaze();
m.Solve();
m.ShowSolve();
ShowAllPath(mg,9,8,9,8);
}
2.任意两点的最短路
class Matrix
{
bool IsCreated;
int* data;
int row;
int col;
public:
Matrix(){IsCreated = false;row = 0; col = 0; data = 0;};
~Matrix(){if (data!=0) delete [] data;};
bool Create(int r, int c, int n);
int& operator () (int r, int c);
};
bool Matrix::Create(int r, int c, int n = 0)
{
if ( IsCreated)
return false;
if ( (row = r) <=0 || (col = c) <=0)
return false;
data = new int[row*col];
int i,j;
for (i=0;i<row;i++)
for (j=0;j<col;j++)
data[i*col+j] = n;
IsCreated = true;
return true;
}
int& Matrix::operator()(int r, int c)
{
return data[r*col+c];
}
jingdian//Matrix类,存储点
dist//Matrix类,存储任意两点间的距离
MAX_DIST//一个大数,大于任意两点间的距离,当两点间没有路的时候设为它
bestdist//Matrix类,存储任意两点的最近距离
bestpath//Matrix类,i到j的最短路为i.......bestpath(i,bestpath(i,pbestpath(i,j))), bestpath(i,pbestpath(i,j)), j bestpath(i,j)表示i到j的最短路中j的前一个结点号
void GetBestPath()
{
int n = jingdian.size();
int i, j, k;
bestdist.Create(n, n);
bestpath.Create(n, n);
for (i=0;i<n;i++)
for (j=0;j<n;j++)
{
if ( (bestdist(i,j) = dist(i,j)) == -1)
bestdist(i,j) = MAX_DIST;
if ( i!=j && bestdist(i,j)<MAX_DIST )
bestpath(i,j) = i;
else
bestpath(i,j) = -1;
}
for (k=0;k<n;k++)
for (i=0;i<n;i++)
for (j=0;j<n;j++)
if (bestdist(i,k)+bestdist(k,j) < bestdist(i,j))
{
bestdist(i,j) = bestdist(i,k)+bestdist(k,j);
bestpath(i,j) = bestpath(k,j);
}
}
Ⅱ 贪心算法之会场安排问题
三星算法之间最好还是不要安排互相的问题，这样不利于你们俩的关系的便有好。
Ⅲ 求高手帮忙做一套算法分析的题目。做好之后再加100。
如何选择排序、矩阵相乘、树和图算法的时间复杂性计量单位？
排序：排序的循环次数（或递归次数）。
矩阵相乘：做实数乘法的次数。
树：搜索的次数。
图：同树。
算法有几种基本结构？各种结构的时间复杂度的计算规则？
3种
顺序结构：T(n)=O(c)
选择结构：T(n)=O(c)
循环结构：T(n)=O(n)
最坏情况下的时间复杂性和平均情况下的时间复杂性的定义？
在规模n的全部输入中，可以找寻执行一个算法所需的最大时间资源的量，这个量称为对规模n的输入，算法的最坏情况时间复杂性。
对规模都为n的一些有限输入集，执行算法所需的平均时间资源的量称为平均情况下的时间复杂性。
为什么选择时间复杂度的渐进性态评价算法？
因为在规模较小的时候无法客观体现一个算法的效率。
解释f(n)=O(g(n))的意义。
若f(n)和g(n)是定义在正整数集合上的 两个函数，则f(n)=O(g(n))表示存在正的常数C和n0 ,使得当n≥n0时满足0≤f(n)≤C*g(n)。
简述之就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。
有效算法和无效算法的划分原则？
区分在于问题是否能够精确求解。
用分治法设计算法有什么好处？为什么描述分治算法需要使用递归技术？
分治法可以将问题分为许规模更小的子问题，这些子问题相互独立且与原问题相同。使用递归技术，虽然一些简单的循环结构替代之，但是复杂的问题，比如二阶递归是无法替代的。
归并排序算法和快速排序算法划分子问题和合并子问题的解的方法各是是怎样的？
归并排序算法：
划分子问题：每次分成2个大小大致相同的子集和
合并子问题：将2个排好序的子数组合并为一个数组
快速排序算法：对输入的子数组a[p:r]
划分子问题：划分为a[p:q-1],a[q]和a[q+1:r]使a[p:q-1]任意元素小于a[q]，a[q+1:r] 任意元素大于a[q]
合并子问题：不需要（因为划分过程就已经排序完成了）
简述二分检索（折半查找）算法为什么比顺序查找的效率高？
对于二分搜索 最坏情况为O(logn)时间完成
而顺序查找 需要O(n)次比较
显然二分搜索效率高
贪心法的核心是什么？
贪心算法是通过一系列选择得到问题的解，它所作出的选择都是当前状态下的最佳选择。
背包问题的目标函数是什么？背包问题贪心算法的最优量度是什么？算法是否获得最优解？ 用贪心算法解0/1背包问题是否可获得最优解？
Max=∑Vi*Xi (V是价值X取1，0表示装入或不装)
每次选取单位重量价值最高的
不一定是最优解
情况不妙啊 LZ还要继续否。。。
早知发邮件了。。。