基于遗传算法路径优化C++编程

发布网友发布时间：2022-05-23 22:57

共1个回答

热心网友时间：2024-03-09 21:15

[cpp]
bool CAStar::Search(int X, int Y, std::list<POINT> &lResult, double dbGapBreak)
{
if(X < 0 || Y < 0
|| X > m_dwMapWidth || Y > m_dwMapWidth ||
m_dwDestinationX < 0 || m_dwDestinationX < 0 ||
m_dwDestinationX > m_dwMapWidth || m_dwDestinationY > m_dwMapHeight)
{
//_outf("坐标或地图参数错误！");
return false;
}

LPAPOINT p = new APOINT;
p->x = X;
p->y = Y;
p->parent = NULL;
p->dbGap = _p2g(X, Y, m_dwDestinationX, m_dwDestinationY);
m_lOpen.push_front(p);//起始节点加入到开启列表
m_lSafe.push_back(p);//加入到公共容器，任何新分配的节点，都要加入到这里，便于算法执行完后清理

std::list<LPAPOINT>::iterator it;
DWORD dwTime = clock();
while(!m_lOpen.empty())
{
//这里就是反复遍历开启列表选择距离最小的节点
it = GetMingapNode();
if((*it)->dbGap <= dbGapBreak)
break;
p = *it;
GenerateSuccessors(it);
}

if(!m_lOpen.empty())
{
//如果列表不为空，从最后一个节点开始拷贝路径到返回值中
//_outf("最终寻路到：%X, %X", p->x, p->y);
POINT point;
while(p)
{
point.x = p->x;
point.y = p->y;
lResult.push_front(point);
p = p->parent;
}
}

for(it = m_lSafe.begin(); it != m_lSafe.end(); ++it)
{
//清理内存
if(*it != NULL)
{
m_pMap[(*it)->y][(*it)->x] = 1;//会被添加到m_lSafe的节点，一定是最初为1的节点，所以可以在这里恢复地图数据
delete (*it);
*it = NULL;
}
}

m_lSafe.clear();//清空容器

//_outf("耗时：%d 毫秒", clock() - dwTime);

if(m_lOpen.empty())
{
//_outf("寻路失败");
return false;
}

m_lOpen.clear();//清空开启列表
//_outf("寻路成功，节点数：%d", lResult.size());
return true;
}
bool CAStar::Search(int X, int Y, std::list<POINT> &lResult, double dbGapBreak)
{
if(X < 0 || Y < 0
|| X > m_dwMapWidth || Y > m_dwMapWidth ||
m_dwDestinationX < 0 || m_dwDestinationX < 0 ||
m_dwDestinationX > m_dwMapWidth || m_dwDestinationY > m_dwMapHeight)
{
//_outf("坐标或地图参数错误！");
return false;
}

LPAPOINT p = new APOINT;
p->x = X;
p->y = Y;
p->parent = NULL;
p->dbGap = _p2g(X, Y, m_dwDestinationX, m_dwDestinationY);
m_lOpen.push_front(p);//起始节点加入到开启列表
m_lSafe.push_back(p);//加入到公共容器，任何新分配的节点，都要加入到这里，便于算法执行完后清理

std::list<LPAPOINT>::iterator it;
DWORD dwTime = clock();
while(!m_lOpen.empty())
{
//这里就是反复遍历开启列表选择距离最小的节点
it = GetMingapNode();
if((*it)->dbGap <= dbGapBreak)
break;
p = *it;
GenerateSuccessors(it);
}

if(!m_lOpen.empty())
{
//如果列表不为空，从最后一个节点开始拷贝路径到返回值中
//_outf("最终寻路到：%X, %X", p->x, p->y);
POINT point;
while(p)
{
point.x = p->x;
point.y = p->y;
lResult.push_front(point);
p = p->parent;
}
}

for(it = m_lSafe.begin(); it != m_lSafe.end(); ++it)
{
//清理内存
if(*it != NULL)
{
m_pMap[(*it)->y][(*it)->x] = 1;//会被添加到m_lSafe的节点，一定是最初为1的节点，所以可以在这里恢复地图数据
delete (*it);
*it = NULL;
}
}

m_lSafe.clear();//清空容器

//_outf("耗时：%d 毫秒", clock() - dwTime);

if(m_lOpen.empty())
{
//_outf("寻路失败");
return false;
}

m_lOpen.clear();//清空开启列表
//_outf("寻路成功，节点数：%d", lResult.size());
return true;
}

新增的SearchEx源代码如下：
nBeginSift 参数为循环初始值，nEndSift为循环结束值，其实就是一个for循环的起始值与结束值。
这个循环的引用计数，最终会被乘于 10 来作为距离分段选择路径进行路线优化
nBeginSift 与 nEndSift的间距越大，并不表示最终路径就越好，最终优化出来的路径，还是会和地形有关。
其实最好路径优化算法是按照角度的变化来选择路径优化，但是预计开销会比较大，有了这个优化方式作为基础，你可以自己去写根据角度变化来优化的算法。

[cpp]
bool CAStar::SearchEx(int X, int Y, std::list<POINT> &lResult, double dbGapBreak, int nBeginSift, int nEndSift)
{
DWORD dwTime = clock();
if(!Search(X, Y, lResult, dbGapBreak))
return false;
std::list<POINT>::iterator it = lResult.begin();
std::list<POINT>::iterator it2 = it;

std::list<POINT> l2;
for(int i = nBeginSift; i < nEndSift; i++)
{
it = lResult.begin();
it2 = it;
for(;it != lResult.end(); ++it)
{
if(_p2g(it2->x, it2->y, it->x, it->y) > (double)(i * 10))
{
SetDestinationPos(it->x, it->y);
l2.clear();
if(Search(it2->x, it2->y, l2, 0.0))
{
it = lResult.erase(it2, it);
lResult.insert(it, (l2.begin()), (l2.end()));
}
it2 = it;
}
}
}

_outf("耗时：%d 毫秒", clock() - dwTime);
return true;
}
bool CAStar::SearchEx(int X, int Y, std::list<POINT> &lResult, double dbGapBreak, int nBeginSift, int nEndSift)
{
DWORD dwTime = clock();
if(!Search(X, Y, lResult, dbGapBreak))
return false;
std::list<POINT>::iterator it = lResult.begin();
std::list<POINT>::iterator it2 = it;

std::list<POINT> l2;
for(int i = nBeginSift; i < nEndSift; i++)
{
it = lResult.begin();
it2 = it;
for(;it != lResult.end(); ++it)
{
if(_p2g(it2->x, it2->y, it->x, it->y) > (double)(i * 10))
{
SetDestinationPos(it->x, it->y);
l2.clear();
if(Search(it2->x, it2->y, l2, 0.0))
{
it = lResult.erase(it2, it);
lResult.insert(it, (l2.begin()), (l2.end()));
}
it2 = it;
}
}
}

_outf("耗时：%d 毫秒", clock() - dwTime);
return true;
}