我的一个小程序，用到求哈密顿回路。和大家讨论

咕哝玄虚

我做的一个程序，用到求哈密顿回路的知识。在求哈密顿回路时用的是分枝限界算法，没有使用堆的技术。运行程序，当节点数大于30时出现内存不足。
有哪位 能在节点数大于5000的无向完全图中找出一条哈密顿回路。
介绍一下我程序的功能：解决的是基于折叠计数器的串行扫描过程中的低功耗问题，只进行了简单的翻转模拟。程序里一个子功能 SearchEdge（）是要求哈密顿回路。 哪位大虾可以有一个好的解决哈密顿回路的方法，有源码的话能否发给我。email:  butooduan@163.com
真诚希望能在这里和大家认识。
代码如下：
// reordering.cpp :
//
#include <stdafx.h>
#include "fstream.h"
#include "iostream.h"
#include <string.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>

#define no (30)
#define INFINITY  (999999999)
#define I INFINITY

/**************定义边的结构****************/
typedef struct _EDGE {
        int head;
        int tail;
} EDGE;
/////////////////定义路径结构
typedef struct _PATH {
        EDGE edge[no];
        int  EdgesNumber;
} PATH;
//////////////////定义成本矩阵结构
typedef struct _MATRIX {
        int distance[no][no];
        int NodeNumber;
} MATRIX;
////////////////////定义状态空间树结点
typedef struct _NODE {
        int bound;       
        MATRIX matrix;       
        PATH path;       
        _NODE* left;
        _NODE* right;       
} NODE;

class _Seeds {
public:
        int GuiYue(MATRIX*);
    EDGE SelectBestEdge(MATRIX);
    MATRIX LeftNode(MATRIX, EDGE);
    MATRIX RightNode(MATRIX, EDGE, PATH);
        int append(MATRIX, EDGE);
    PATH AddEdge(EDGE, PATH);
    PATH SearchEdge(NODE);
        void PrimarylLink(PATH);
        void OptimalLink();
    PATH MendPath(PATH, MATRIX);
    int MatrixSize(MATRIX, PATH);
        EDGE LoopEdge(PATH, EDGE);
        void initiate1();
        void initiate2();
    void PrintCycle(PATH);
    void ZhanKai();
        void WuGuanWei();
    void WeightCount();
        void HamiltonCycle();
    void TransitionCount1();
    int TransitionCount2();
        void TransitionCount3();

    PATH path;
    char seed[no];
    char FoldingSet[no+1][no];
    int WeightSet[no][no];
    int r,vtxnum,count1,count2,depth;
private:
        int A[2*no-1],B[no],Optimal[no],C[no];
        NODE root;
};

void main()
{
        _Seeds Seeds;

        int v1 = 0; int v2 = 0;
        int num = 0;
        float p;

        cout<<"请输入种子长度:   ";
        cin>>Seeds.vtxnum;cout<<endl;
        Seeds.initiate1();

        fstream file1,file2;
        file1.open("seeds.txt",ios::in);
        char ch1,ch2;

        while (!file1.eof()){
                if (v1<Seeds.vtxnum){
                        if (!file1.eof()){
                                file1.read(&ch1,1);
                                v1++;
                        }
                        Seeds.seed[v1-1] = ch1;
                }
                else{
                        Seeds.ZhanKai();
                        Seeds.WuGuanWei();
                        Seeds.TransitionCount1();
                        Seeds.WeightCount();
                        v1 = 0; num++;
                }
        };
        file1.close();
    printf("\n在扫描链优化前向量输入发生的翻转数%d :",Seeds.count1);cout<<endl;

        if (num>=1){
                Seeds.initiate2();
            Seeds.HamiltonCycle();
            Seeds.PrimarylLink(Seeds.path);
            Seeds.OptimalLink();

            file2.open("seeds.txt",ios::in);
            while (!file2.eof()){
                    if (v2<Seeds.vtxnum){
                            if (!file2.eof()){
                                    file2.read(&ch2,1);
                                    v2++;
                                }
                            Seeds.seed[v2-1] = ch2;
                        }
                    else{
                            Seeds.ZhanKai();
                            Seeds.WuGuanWei();
                            Seeds.TransitionCount3();
                            v2 = 0;
                        }
                };
            file2.close();
            printf("\n在扫描链优化后向量输入发生的翻转数%d : ",Seeds.count2);cout<<endl;
            p=100*(Seeds.count1-Seeds.count2)/Seeds.count1;
            cout<<"\n优化后在扫描链中输入翻转数减少了 :"<<p<<"%\n";
        }
        else cout<<"\n实际种子的长度达不到 "<<Seeds.vtxnum<<" 请重新输入\n";
               
};


void _Seeds::initiate1()
{
        count1 = 0; count2 = 0;
        for (int i1 = 0; i1<vtxnum; i1++){
                for (int i2=0; i2<vtxnum; i2++){
                        if (i1 == i2) WeightSet[i1][i2] = I;
                        else WeightSet[i1][i2] = 0;
                }
        };
}
void _Seeds::initiate2()
{
        root.bound = 0;
        root.left = root.right = NULL;
        root.path.edge[0].head = 0;
        root.path.edge[0].tail = 0;
        root.path.EdgesNumber = 0;
        root.matrix.NodeNumber = vtxnum;
        for (int i = 0; i<vtxnum; i++)
                for (int j = 0; j<vtxnum;j++)
                        root.matrix.distance[j] = WeightSet[j];

}
void _Seeds::HamiltonCycle()
{
        root.bound += GuiYue(&root.matrix);
        path = SearchEdge(root);
        printf(" \n找出的哈密顿回路如下所示 :\n");
        PrintCycle(path);
}

PATH _Seeds::SearchEdge(NODE root)
{
        static int minDist = INFINITY;
        static PATH minPath;
        EDGE selectedEdge;
        NODE *left, *right;

        if (MatrixSize(root.matrix, root.path) == 2) {
                if (root.bound < minDist) {
                        minDist = root.bound;
                        minPath = MendPath(root.path, root.matrix);
                        return (minPath);
                }
        }
        selectedEdge = SelectBestEdge(root.matrix);
        left = (NODE *)malloc(sizeof(NODE));
        right = (NODE *)malloc(sizeof(NODE));
        if (left == NULL || right == NULL) {
                exit(-1);
        }

        left->bound = root.bound;
        left->matrix = LeftNode(root.matrix, selectedEdge);
        left->path = root.path;
        left->left = NULL;
        left->right = NULL;

        right->bound =         root.bound;
        right->matrix = RightNode(root.matrix, selectedEdge, root.path);
        right->path = AddEdge(selectedEdge, root.path);
        right->left = NULL;
        right->right = NULL;

        left->bound += GuiYue(&left->matrix);
        right->bound += GuiYue(&right->matrix);
        root.left = left;
        root.right = right;

        if ((right->bound < minDist) && (depth <= vtxnum))
                SearchEdge(*right);
        else free(right);
        if ((left->bound < minDist) && (depth <=vtxnum))
                SearchEdge(*left);
        else free(left);
        return (minPath);
}

PATH _Seeds::MendPath(PATH path, MATRIX c)
{
        int row, tier;
        EDGE edge;
        int n = c.NodeNumber;

        for (row = 0; row < n; row++) {
                edge.head = row;
                for (tier = 0; tier < n; tier++) {
                        edge.tail = tier;
                        if (c.distance[row][tier] == 0) {
                                path = AddEdge(edge, path);
                        }
                }
        }
        return path;

}
int _Seeds::GuiYue(MATRIX* c)
{
        int row, tier, min_dist, h;
        int n = c->NodeNumber;

        h = 0;
        for (row = 0; row < n; row++) {
                min_dist = I;
                for (tier = 0; tier < n; tier++) {
                        if (c->distance[row][tier] < min_dist) {
                                min_dist = c->distance[row][tier];
                        }
                }
                if (min_dist == I) continue;
                for (tier = 0; tier < n; tier++) {
                        if (c->distance[row][tier] != I) {
                                c->distance[row][tier] -= min_dist;
                        }
                }
                h += min_dist;
        }
        for (tier = 0; tier < n; tier++) {
                min_dist = I;
                for (row = 0; row < n; row++) {
                        if (c->distance[row][tier] < min_dist) {
                                min_dist = c->distance[row][tier];
                        }
                }
                if (min_dist == I) continue;
                for (row = 0; row < n; row++) {
                        if (c->distance[row][tier] != I) {
                                c->distance[row][tier] -= min_dist;
                        }
                }
                h += min_dist;
        }
        return (h);
}
EDGE _Seeds::SelectBestEdge(MATRIX c)
{
        int row, tier;
        int n = c.NodeNumber;
        int maxD;
        EDGE best, edge;
        maxD = 0;
        for (row = 0; row < n; row++) {
                for (tier = 0; tier < n; tier++) {
                        edge.head = row;
                        edge.tail = tier;
                        if (!c.distance[row][tier] && maxD < append(c, edge)) {
                                maxD = append(c, edge);
                                best = edge;
                        }
                }
        }
        return (best);
}
int _Seeds::append(MATRIX c, EDGE edge)
{
        int row, tier, dRow, dtier;
        int n = c.NodeNumber;

        dRow = 0;
        for (tier = 0; tier < n; tier++) {
                if (dRow < c.distance[edge.head][tier] && tier != edge.tail) {
                        dRow = c.distance[edge.head][tier];
                }
        }
        dtier = 0;
        for (row = 0; row < n; row++) {
                if (dtier < c.distance[row][edge.tail] && row != edge.head) {
                        dtier = c.distance[row][edge.tail];
                }
        }
        return (dRow + dtier);
}

MATRIX _Seeds::LeftNode(MATRIX c, EDGE edge)
{
        c.distance[edge.head][edge.tail] = I;
        return c;
}
MATRIX        _Seeds::RightNode(MATRIX c, EDGE edge, PATH path)
{
        int row, tier;
        int n = c.NodeNumber;
        EDGE loopEdge;
        for (tier = 0; tier < n; tier++)
                c.distance[edge.head][tier] = I;
        for (row = 0; row < n; row++)
                c.distance[row][edge.tail] = I;

        loopEdge = LoopEdge(path, edge);
        c.distance[loopEdge.head][loopEdge.tail] = I;

        return (c);
}

EDGE _Seeds::LoopEdge(PATH path, EDGE edge)
{
        int i, j;
        EDGE loopEdge;
        loopEdge.head = edge.tail;
        loopEdge.tail = edge.head;

        for (i = 0; i < path.EdgesNumber; i++) {
                for (j = 0; j < path.EdgesNumber; j++) {
                        if (loopEdge.head == path.edge[j].head) {
                                loopEdge.head = path.edge[j].tail;
                                break;
                        }
                }
        }
        for (i = 0; i < path.EdgesNumber; i++) {
                for (j = 0; j < path.EdgesNumber; j++) {
                        if (loopEdge.tail == path.edge[j].tail) {
                                loopEdge.tail = path.edge[j].head;
                                break;
                        }
                }
        }

        return (loopEdge);
}

PATH _Seeds::AddEdge(EDGE edge, PATH path)
{
        path.edge[path.EdgesNumber++] = edge;
        return path;
}

int _Seeds::MatrixSize(MATRIX c, PATH path)
{
        return (c.NodeNumber - path.EdgesNumber);
}

void _Seeds::PrintCycle(PATH path)
{
        int i;
        EDGE edge;
        int n = path.EdgesNumber;

        for (i = 0; i < n; i++) {
                edge = path.edge;
                printf("(%d, %d) ", edge.head + 1, edge.tail + 1);
        }
}
void _Seeds::PrimarylLink(PATH path)
{
        bool visited[no];
        for (int i1 = 0; i1 < vtxnum; i1++)
                visited[i1] = false;
        EDGE edge1,edge2;
        edge1 = path.edge[0];
        A[0] = edge1.head + 1;
        for (int i = 1; i < vtxnum; i++){
                for (int j = 1; j < vtxnum; j++){
                        edge2 = path.edge[j];
                        if ((!visited) && (edge1.tail+1 == edge2.head+1)){
                                A = edge2.head+1;
                                visited = true;
                                edge1 = edge2;
                        }
                };
        };
        /*
        cout<<endl;
        for (int h = 0; h<vtxnum; h++)
                printf("%d ",A[h]);
                */
}
void _Seeds::OptimalLink()
{
        int k = -1;
        int min = I;
        for (int i = 0; i < vtxnum; i++){
                k++;
                for (int j = 0; j< vtxnum; j++){
                        B[j] = A[j+k];
                };
                A[vtxnum+k] = A[k];

                if (TransitionCount2() < min){
                        min = TransitionCount2();
                        for (int l = 0; l<vtxnum; l++){
                                Optimal[l] = B[l];
                        }
                }
        }
        printf("\n对扫描链进行优化后的顺序如下所示  :\n");
        for ( int l1 = 0; l1<vtxnum; l1++)
                printf("%d ",Optimal[l1]);
};

void _Seeds::ZhanKai()
{
        int i,j,k,m;
        j=1;k=1;m=1;
        for (i=0;i<vtxnum;i++) {
                FoldingSet[0]=seed;
        }
        while (k!=0) {
                if (j==1){
                        if (seed[k-1]=='1') seed[k-1]='0';
                        else if (seed[k-1]=='0') seed[k-1]='1';
                        for (int l=0;l<vtxnum;l++)
                                FoldingSet[m][l]=seed[l];
                        k+=2; m+=1;
                        if (k==vtxnum+1){
                                j=0; k--;
                        };
                        if (k==vtxnum+2){
                                j=0; k-=3;
                        };
                }
                else {
                        if (seed[k-1]=='1') seed[k-1]='0';
                        else if (seed[k-1]=='0') seed[k-1]='1';
                        for (int l1=0;l1<vtxnum;l1++)
                                FoldingSet[m][l1]=seed[l1];
                        k-=2;m++;
                };
        }
        /*
        cout<<endl;cout<<"由该种子向量产生的折叠集为:  "<<endl;
        for (int i1=0; i1<=vtxnum; i1++){
                for (int i2=0; i2<vtxnum; i2++)
                        cout<<FoldingSet[i1][i2];
                cout<<endl;
        }
        */
};

void _Seeds::WuGuanWei()///在对无关位进行确定值的时候，为了降低扫描链的功耗，可能会破坏测试向量
{                     ///之间的相关性。当相关性降低很大时，优先考虑的是提高相关性，当相关性
                      ////降低不太大时，优先考虑的降低扫描链的功耗。
        for (int i=0;i<=vtxnum;i++)
                for (int j=vtxnum-1;j>=0;j--){
                        if (FoldingSet[j] !='0' && FoldingSet[j] !='1'){
                                if (j==vtxnum-1) {
                                        int w; w=j;
                                        while (FoldingSet[w] !='0' && FoldingSet[w] !='1')
                                                w--;
                                        while (w<=j){
                                                FoldingSet[w+1]=FoldingSet[w];
                                                w++;
                                        };
                                }
                                else {
                                        int w1; w1=j;
                                        while (FoldingSet[w1] !='0' && FoldingSet[w1] !='1')
                                                w1++;
                                        while (w1>=j){
                                                FoldingSet[w1-1]=FoldingSet[w1];
                                                w1--;
                                        };
                                };
                                int f=0;int x=0;
                                if (i>0){
                                        while (x<vtxnum){
                                                if (FoldingSet[i-1][x]!=FoldingSet[x])
                                                        f++;
                                                x++;
                                        };
                                };
                                if((i>0)&&(f==0))
                                        if (FoldingSet[i-1][j]=='0') FoldingSet[j]='1';
                                        else FoldingSet[j]='0';
                                        if(f>1) FoldingSet[j]=FoldingSet[i-1][j];
                        };
                };
/*
        cout<<endl;cout<<"对无关位进行定值后的折叠集为:  "<<endl;
        for (int i1=0;i1<=vtxnum;i1++){
                for (int i2=0;i2<vtxnum;i2++)
                        cout<<FoldingSet[i1][i2];
                cout<<endl;
        };
*/
};
void _Seeds::WeightCount()
{   
        for (int i=0;i<vtxnum;i++){
                for (int j=i+1;j<vtxnum;j++){
                        for (int k=0;k<=vtxnum;k++){
                                if ( FoldingSet[k]!=FoldingSet[k][j])
                                        WeightSet[j]=WeightSet[j]+1;
                        };
                        WeightSet[j]=WeightSet[j];
                };
        };
};
void _Seeds::TransitionCount1()
{
        for (int i=0;i<=vtxnum;i++)
                for (int j=0;j<vtxnum-1;j++)
                        if (FoldingSet[j] != FoldingSet[j+1])
                                count1=count1+j+1;
};
int _Seeds::TransitionCount2()
{
        int count = 0;
        for (int i = 0; i<=vtxnum; i++){
                for (int j = 0; j<vtxnum; j++)
                        C[j] = FoldingSet[B[j]-1];
                for (int k = 0; k<vtxnum-1; k++)
                        if (C[k] != C[k+1])
                                count = count+k+1;
        };
        return count;

}
void _Seeds::TransitionCount3()
{
        for (int i = 0; i<=vtxnum; i++){
                for (int j = 0; j<vtxnum; j++)
                        C[j] = FoldingSet[Optimal[j]-1];
                for (int k = 0; k<vtxnum-1; k++)
                        if (C[k] != C[k+1])
                                count2 += k+1;
        };
};

Leeo

在数学课上学过，现在已经忘光了，更别提编程了，呵呵

三人行_必

楼主确实厉害，什么时候帮我写写基于蚁群算法的TSPC++程序，我现在正在为这个程序头痛
谢谢

咕哝玄虚

打算这个暑假好好学习一下相关类的算法
希望大虾们多多指教 真诚希望在这里认识大家

JUST

求哈密顿回路是NPC，求最短的就更困难了

haha00701

C++已经N 久没有摸过了
。。。。。。
（汗颜中。。。）

heyhelloworld

楼主确实厉害
但是stdafx.h这个文件好象在vc++里没有

517755

都是曾经熟悉的东西,在政府部门混了N年的饭,基本全部忘光了,汗啊!

sakeki

引用 517755 在 2006-3-1 09:12 时的帖子:
都是曾经熟悉的东西,在政府部门混了N年的饭,基本全部忘光了,汗啊!

同汗

cc3000c

哈哈。  ^_^  新手上路

以上程序能够多加些注释的话…… o(∩_∩)o ...

[ 本帖最后由 cc3000c 于 2008-12-16 02:32 编辑 ]

JUST

最优解本身就是NPC，复杂度是不会变的。只能考虑一些剪枝手段加速一下。

5000个节点以目前人类的计算能力是不可能办到的