TSP递归求解其迭代形式

Question

我有一个函数 returns n 个城市之间可能的最短距离。又名旅行商问题。

int tsp(int mask, int pos, int n) 
{

    if (mask == VISITED_ALL) 
    {
        return dist[pos][0];
    }
    
    int result = 2147483647;

    for (int i = 0; i < n; i++) 
    {

        if ((mask & (1 << i)) == 0) 
        {

            int new_result = dist[pos][i] + tsp(mask | (1 << i), i, n);
            result = min(result, new_result);
        }

    }

    return result;
}

我想将此递归解决方案修改为迭代形式，但我正在努力这样做。我正在按照本指南进行操作，该指南描述了从递归解决方案到带有几个示例的迭代的转换 https://www.codeproject.com/Articles/418776/How-to-replace-recursive-functions-using-stack-and

这是我试过的方法，但似乎不起作用

int tspIterative(int mask, int pos, int n)
{
    struct MyStructure
    {
        int mask;
        int pos;
        int n;

        int new_result;
        int result;

        int stage;
    };


    int retVal = 0;

    stack<MyStructure> myStack;

    MyStructure currentStruct;
    currentStruct.mask = mask;
    currentStruct.pos = pos;
    currentStruct.n = n;

    currentStruct.new_result = 0;
    currentStruct.result = 2147483647;

    currentStruct.stage = 0;

    myStack.push(currentStruct);


    while (myStack.empty() != true)
    {
        currentStruct = myStack.top();
        myStack.pop();

        switch (currentStruct.stage)
        {
        case 0:
            if (currentStruct.mask == VISITED_ALL)
            {
                retVal = dist[pos][0];
                continue;
            }
            else
            {
                currentStruct.stage = 1;
                myStack.push(currentStruct);

                for (int i = 0; i < currentStruct.n; i++)
                {
                    if ((currentStruct.mask & (1 << i)) == 0)
                    {
                        MyStructure newStruct;
                        newStruct.mask = currentStruct.mask | (1 << i);
                        newStruct.pos = i;
                        newStruct.n = currentStruct.n;

                        newStruct.result = currentStruct.result;
                        newStruct.new_result = currentStruct.new_result;

                        newStruct.stage = 0;

                        myStack.push(newStruct);
                    }
                }
                continue;
                break;

        case 1:

            for (int i = 0; i < currentStruct.n; i++)
            {

                if ((currentStruct.mask & (1 << i)) == 0)
                {
                    currentStruct.new_result = dist[currentStruct.pos][i] + retVal;
                    currentStruct.result = min(currentStruct.result, currentStruct.new_result);
                    retVal = currentStruct.result;
                }

            }
            continue;
            break;

            }

        }

        return retVal;
    }

}

Answer 1

好的，我已经弄明白了。如果有人感兴趣，这是我的解决方案。

int tspIterative(int mask, int pos, int n)
{
    struct MyStructure
    {
        int mask;
        int pos;
        int n;

        int new_result;
        int result;

        int nextPos;

        int stage;
    };


    int retVal = 0;
    int k = 0;

    stack<MyStructure> myStack;

    MyStructure currentStruct;
    currentStruct.mask = mask;
    currentStruct.pos = pos;
    currentStruct.n = n;

    currentStruct.new_result = 0;
    currentStruct.result = 2147483647;

    currentStruct.nextPos = 0;

    currentStruct.stage = 0;

    myStack.push(currentStruct);


    while (myStack.empty() != true)
    {
        currentStruct = myStack.top();
        myStack.pop();

        switch (currentStruct.stage)
        {

        case 0:
        {
            jump:
            if (currentStruct.mask == VISITED_ALL)
            {
                retVal = dist[currentStruct.pos][0];
                continue;
            }

            else
            {
                currentStruct.stage = 1;
                myStack.push(currentStruct);

                for (int i = currentStruct.nextPos + k; i < currentStruct.n; i++)
                {
                    if ((currentStruct.mask & (1 << i)) == 0)
                    {
                        MyStructure newStruct;
                        newStruct.mask = (currentStruct.mask) | (1 << i);
                        newStruct.pos = i;
                        newStruct.n = currentStruct.n;

                        newStruct.result = 2147483647;
                        newStruct.new_result = 0;

                        newStruct.nextPos = 0;

                        newStruct.stage = 0;

                        currentStruct = myStack.top();
                        myStack.pop();
                        currentStruct.nextPos = i;
                        myStack.push(currentStruct);


                        myStack.push(newStruct);
                        break;
                    }
                }
                continue;
            }

            break;
        }
        case 1:
        {
            k = 0;
            for (int i = currentStruct.nextPos + k; i < currentStruct.n; i++)
            {

                if ((currentStruct.mask & (1 << i)) == 0)
                {
                    if (k > 0)
                    {
                        goto jump;
                    }
                    currentStruct.new_result = dist[currentStruct.pos][i] + retVal;
                    currentStruct.result = min(currentStruct.result, currentStruct.new_result);
                    retVal = currentStruct.result;
                    k = 1;
                }

            }
            continue;
            break;
        }
        }
    }


        return retVal;
}

TSP递归求解其迭代形式

TSP recursive solution to its iterative form

c++

iteration

recursion

traveling-salesman