什么是贪婪最佳搜索算法中的回溯跟踪的有效方法？ [英] What is an efficient way of back-tracking in greedy best search algorithm?

问题描述

我编码了一个贪婪的搜索算法，但它转到一个无限循环，因为它不能回溯，并达到最终状态。如何可以在C ++中以最佳方式完成回溯跟踪？

I coded a greedy search algorithm , but it goes to an infinite loop as its not able to back - track , and reach the final state . How can a back-tracking be done in C++ in the most optimal way !

    while(!f1.eof() )
        {
            f1>>temp1>>time;

            A[i].loc_name=temp1;
            A[i].time_taken=time;

                initial_start=1; // make initial to 1 and final to i

                final_finish=i;

        i=i+1;
        }

    while(!f2.eof())
        {
            f2>>temp1>>temp2>>time;
            int ci=0;
            while( ci != i )
                {

                    if (temp1 == A[ci].loc_name)
                        {
                            flag1=ci;
                            tf1=time;

                        }
                    if (temp2 == A[ci].loc_name)
                        {
                            flag2=ci;
                            tf2=time;
                        }
                    ci=ci+1;
                }



            A[flag1].loc.push_back(flag2);
            A[flag1].time_live.push_back(time);

            A[flag2].loc.push_back(flag1);
            A[flag2].time_live.push_back(time);         

        }


//Greedy Search algorithm   
                int min,min_time,finish,start,l;
                vector<int>path;
                min_time=99999;
                l=0;
                finish=1;
                start=0;
//Choosing the node with the minimum value 
            while(finish != final_finish)
                {

                for(int u=0;u<A[start].loc.size();u++)
                    {
                        l=A[start].loc[u];
                        if(A[l].time_taken < min_time)
                            {   
                                min_time=A[l].time_taken;
                                finish = l;

                            }

                    }
                min=min+min_time;
                path.push_back(start);
                    start=finish;   
//Printing the path found by Greedy search into an output file
            f3<<A[l].loc_name<<min<<endl;
                }

推荐答案

int algo(int value, int stopValue, list<int> & answer)
{
    if(value == stopValue)
    {
        return 0;
    }
    if(value > stopValue)
    {
        return 1;
    }

    if(algo(value+2, stopValue) == 0)
    {
        answer.push_back(2);
        return 0;
    }
    if(algo(value+1, stopValue) == 0)
    {
        answer.push_back(1);
        return 0;
    }
    return 1;
}

这里是一个简单的贪心递归算法，找到2的数字和1的数字由...组成。贪婪算法只适用于一些问题，并且在大多数情况下产生次优结果。

Here's a trivial greedy recursive algorithm that finds the number of 2s and 1s a number is composed of. Greedy algorithms are only good for some problems and produce suboptimal results in most.

这篇关于什么是贪婪最佳搜索算法中的回溯跟踪的有效方法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！