citymap.cpp

旅行商问题

        return;
    }
    static int i, tmp;
    static bool change;
    static double d0, d1, d2, d3;
    static int count;
    count = 0;
    do
    {
        change = false;
        d0 = this->m_pDPCitySites[gene.index[0]].Distance(
                this->m_pDPCitySites[gene.index[m_iCityNum - 1]]);
        d1 = this->m_pDPCitySites[gene.index[1]].Distance(
                this->m_pDPCitySites[gene.index[m_iCityNum - 1]]);
        // 寻找钝角
        for(i = 1; i < this->m_iCityNum - 1; i++)
        {
            d2 = this->m_pDPCitySites[gene.index[i]].Distance(
                    this->m_pDPCitySites[gene.index[i + 1]]);
            d3 = this->m_pDPCitySites[gene.index[i - 1]].Distance(
                    this->m_pDPCitySites[gene.index[i + 1]]);
            if(d0 + d2 > d1 + d3)
            {
                // 交换公共点顺序
                tmp = gene.index[i];
                gene.index[i] = gene.index[i - 1];
                gene.index[i - 1] = tmp;
                change = true;
            }
            d0 = this->m_pDPCitySites[gene.index[i]].Distance(
                this->m_pDPCitySites[gene.index[i - 1]]);
            d1 = d3;
        }
        count++;
        if(count > 5)
        {
            break;
        }
    }
    while(change);
    this->Mark(gene);
}

// 开始计算
bool CCityMap::StartCompute()
{
    if(this->m_bCompute == false)
    {
        this->m_bKillMsg = false;
        AfxBeginThread(CCityMap::ThreadProc, this);
    }
    ::Sleep(100);
    return this->m_bCompute;
}

// 停止计算
bool CCityMap::StopCompute()
{
    this->m_bKillMsg = true;
    for(int i = 0; i < 10 && m_bCompute; i++)
    {
        ::Sleep(100);
    }
    this->m_bKillMsg = false;
    return !m_bCompute;
}

// 写到文件
bool CCityMap::WriteFile(CString fileName)
{
    FILE * fp = fopen(fileName, "w");
    if(fp)
    {
        for(int i = 0; i < this->m_iCityNum; i++)
        {
            fprintf(fp, "%lf, %lf, %d\n", this->m_pDPCitySites[i].x, this->m_pDPCitySites[i].y, this->m_piBestIndex[i]);
        }
        fclose(fp);
        return true;
    }
    return false;
}

// 读取文件
bool CCityMap::ReadFile(CString fileName)
{
    FILE * fp = fopen(fileName, "r");
    if(fp)
    {
        double x, y;
        int index;
        this->Clear();
        while(!feof(fp))
        {
            fscanf(fp, "%lf, %lf, %d\n", &x, &y, &index);
            this->AddCity(x, y);
            m_piBestIndex[this->m_iCityNum - 1] = index;
        }
        GENE gene;
        gene.index = this->m_piBestIndex;
        this->ComputeDistanceMatrix();
        this->Mark(gene);
        this->DestroyDistanceMatrix();
        gene.index = NULL;
        this->m_dBestMark = gene.mark;
        this->m_i64BestGen = 1;
        this->m_i64GenNum = 1;
        fclose(fp);
        return true;
    }
    return false;
}

// 绘制城市
void CCityMap::Draw(CDC * pDC, CRect rect, int highLight, int highLight2)
{
    if(m_iCityNum == 0)
    {
        return;
    }
    int width = rect.Width();
    int height = rect.Height();
    int i;
    // 绘制全局最优连线
    {
        CDPoint dp = m_pDPCitySites[m_piBestIndex[0]];
        pDC->MoveTo(
            rect.left + int(dp.x * width),
            rect.left + int(dp.y * height));
        for(i = 1; i < m_iCityNum; i++)
        {
            dp = m_pDPCitySites[m_piBestIndex[i]];
            pDC->LineTo(
                rect.left + int(dp.x * width),
                rect.left + int(dp.y * height));
        }
        dp = m_pDPCitySites[m_piBestIndex[0]];
        pDC->LineTo(
            rect.left + int(dp.x * width),
            rect.left + int(dp.y * height));
    }
    if(this->m_bCompute && this->m_iJumpCount)
    {
        if(memcmp(m_piBestIndex, m_piCurrBestIndex, sizeof(int) * m_iRoomSize))
        {
            // 绘制当前最优连线
            CDPoint dp = m_pDPCitySites[m_piCurrBestIndex[0]];
            CPen pen(PS_DOT, 1, RGB(198, 198, 198));
            CPen * pold = pDC->SelectObject(&pen);
            pDC->MoveTo(
                rect.left + int(dp.x * width) + CM_OFFSET,
                rect.left + int(dp.y * height) + CM_OFFSET);
            for(i = 1; i < m_iCityNum; i++)
            {
                dp = m_pDPCitySites[m_piCurrBestIndex[i]];
                pDC->LineTo(
                    rect.left + int(dp.x * width) + CM_OFFSET,
                    rect.left + int(dp.y * height) + CM_OFFSET);
            }
            dp = m_pDPCitySites[m_piCurrBestIndex[0]];
            pDC->LineTo(
                rect.left + int(dp.x * width) + CM_OFFSET,
                rect.left + int(dp.y * height) + CM_OFFSET);
            pDC->SelectObject(pold);
        }
    }
    // 绘制坐标
    for(i = 0; i < m_iCityNum; i++)
    {
        pDC->FillSolidRect(
            rect.left + int(this->m_pDPCitySites[i].x * width) - CM_CITY_DRAW_SIZE,
            rect.top  + int(this->m_pDPCitySites[i].y * height) - CM_CITY_DRAW_SIZE,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 1,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 1,
            RGB(0, 0, 168));
    }

    if(highLight2 >= 0 && highLight2 < m_iCityNum)
    {
        pDC->FillSolidRect(
            rect.left + int(this->m_pDPCitySites[highLight2].x * width) - CM_CITY_DRAW_SIZE - 1,
            rect.top  + int(this->m_pDPCitySites[highLight2].y * height) - CM_CITY_DRAW_SIZE - 1,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 3,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 3,
            RGB(255, 0, 0));
        pDC->FillSolidRect(
            rect.left + int(this->m_pDPCitySites[highLight2].x * width) - CM_CITY_DRAW_SIZE,
            rect.top  + int(this->m_pDPCitySites[highLight2].y * height) - CM_CITY_DRAW_SIZE,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 1,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 1,
            RGB(0, 255, 0));
    }
    if(highLight >= 0 && highLight < m_iCityNum)
    {
        pDC->FillSolidRect(
            rect.left + int(this->m_pDPCitySites[highLight].x * width) - CM_CITY_DRAW_SIZE - 1,
            rect.top  + int(this->m_pDPCitySites[highLight].y * height) - CM_CITY_DRAW_SIZE - 1,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 3,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 3,
            RGB(0, 255, 0));
        pDC->FillSolidRect(
            rect.left + int(this->m_pDPCitySites[highLight].x * width) - CM_CITY_DRAW_SIZE,
            rect.top  + int(this->m_pDPCitySites[highLight].y * height) - CM_CITY_DRAW_SIZE,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 1,
            CM_CITY_DRAW_SIZE + CM_CITY_DRAW_SIZE + 1,
            RGB(255, 0, 0));
    }
}

// 清空
void CCityMap::Clear()
{
    this->m_tsTimeUsed = 0;
    this->m_iCityNum = 0;
}

// 添加城市
void CCityMap::AddCity(double x, double y)
{
    if(this->m_bCompute)
    {
        return;
    }
    // 扩充存储空间
    if(this->m_iCityNum >= this->m_iRoomSize)
    {
        int newSize = this->m_iRoomSize + CM_ROOM_CREATE_SIZE;
        CDPoint * newRoom = new CDPoint [newSize];
        if(this->m_pDPCitySites)
        {
            memcpy(newRoom, m_pDPCitySites, sizeof(CDPoint) * m_iRoomSize);
            delete [] m_pDPCitySites;
        }
        int * newIndex = new int [newSize];
        int * newCurrIndex = new int [newSize];
        if(this->m_pDPCitySites)
        {
            memcpy(newIndex, m_piBestIndex, sizeof(int) * m_iRoomSize);
            delete [] m_piBestIndex;
            memcpy(newCurrIndex, m_piCurrBestIndex, sizeof(int) * m_iRoomSize);
            delete [] m_piCurrBestIndex;
        }
        m_pDPCitySites = newRoom;
        m_piBestIndex = newIndex;
        m_piCurrBestIndex = newCurrIndex;
        m_iRoomSize = newSize;
    }
    // 添加城市
    this->m_pDPCitySites[m_iCityNum].x = x;
    this->m_pDPCitySites[m_iCityNum].y = y;
    m_piBestIndex[m_iCityNum] = m_iCityNum;
    m_piCurrBestIndex[m_iCityNum] = m_iCityNum;
    m_iCityNum++;
}

// 删除城市
void CCityMap::DeleteCity(int index)
{
    if(this->m_bCompute)
    {
        return;
    }
    if(index >= 0 && index < m_iCityNum)
    {
        int i;
        for(i = 0; i < m_iCityNum - 1; i++)
        {
            if(m_piBestIndex[i] == index)
            {
                break;
            }
            else if(m_piBestIndex[i] > index)
            {
                m_piBestIndex[i]--;
            }
        }
        for(; i < m_iCityNum - 1; i++)
        {
            m_piBestIndex[i] = m_piBestIndex[i + 1];
            if(m_piBestIndex[i] > index)
            {
                m_piBestIndex[i]--;
            }
        }

        for(i = 0; i < m_iCityNum - 1; i++)
        {
            if(m_piCurrBestIndex[i] == index)
            {
                break;
            }
            else if(m_piCurrBestIndex[i] > index)
            {
                m_piCurrBestIndex[i]--;
            }
        }
        for(; i < m_iCityNum - 1; i++)
        {
            m_piCurrBestIndex[i] = m_piCurrBestIndex[i + 1];
            if(m_piCurrBestIndex[i] > index)
            {
                m_piCurrBestIndex[i]--;
            }
        }

        for(; index < m_iCityNum - 1; index++)
        {
            m_pDPCitySites[index] = m_pDPCitySites[index + 1];
        }
        m_iCityNum--;
    }
}

// 点击测试,返回城市序号或者-1
int CCityMap::HitTest(double x, double y, double dx, double dy)
{
    double x1 = x - dx, x2 = x + dx;
    double y1 = y - dy, y2 = y + dy;
    for(int index = m_iCityNum - 1; index >= 0; index--)
    {
        if(     m_pDPCitySites[index].x > x1
            &&  m_pDPCitySites[index].x < x2
            &&  m_pDPCitySites[index].y > y1
            &&  m_pDPCitySites[index].y < y2)
        {
            return index;
        }
    }
    return -1;
}