Algorithms in Production – Prevalence of Generic-Case Exponential Time Algorithms

algorithms

I know that exponential time algorithms should generally be avoided but are sometimes necessary. A case being the Traveling Salesman. How common are such algorithms in production software? Are these cases typically necessary or a result of rush jobs? I understand that many can be solved with a good heuristic. What is typically done with those that cannot?

Best Answer

Something that not in production software but done on production software is formal verification. It is probably not adopted for most customer software but gains track for embedded systems and drivers, that is for hard- and software whose correctness is important (and tractable).

Those verficiation problems that are actually computable (barrier #1) are often EXPTIME-hard, in the more lucky cases you get PSPACE-complete problems (barrier #2). Both classes are (suspected to be) harder than NP-complete problems, which are easy in comparison. Doubly-exponential problems are also easily obtained.

In these cases, heuristics (in the sense of end result) don't cut it as you need definite results; therefore you need big machines and time. There are heuristics (in the sense of alternative selection) that often lead to shorter runtime (i.e. clever search space exploration when error states are searched) but in the worst case, waiting is all you can do. Or you can do a pen-and-paper proof and have it checked by machines, which is computationally simpler.

Related Solutions

Algorithm for Exact Solution to the Travelling Purchaser Problem

The NP-Hard domain of problems means that, as far as current mathematical knowledge goes, the problem can only be solved by trying every permutation and choosing the correct answer.

If you can solve the problem more efficiently than the brute force method, you will win a Noble Prize in mathematics as a bonus. The best mathematicians have been working on a general answer to this problem for decades.

Perhaps as you are wanting to create a test data-set for your NP-Hard problem solver, your approach may be to design the test data backwards - rather than solve the NP-Hard problem, create an NP-Hard problem with a known answer - I don't even know if that is a NP-Hard problem on it's own.

Algorithms – How to Sort an Array of Numbers with Decimals

Your problem is that your "numbers" don't have decimal places. You have a string which consists of two integers which are separated by .. Parse them as two integers and write a custom comparer. The sorting algorithm can remain the same, you just need to pass in the comparer.

In C# such a comparer could look similar to this:

void Test()
{
    var data=new string[]{ "1.34", "1.15", "1.1", "1.2", "1.26", "1.10", "1.20", "1.17" };
    Array.Sort(data, VersionComparer);
    data.Dump();
}

static int VersionComparer(string s1, string s2)
{
    List<int> parts1 = s1.Split('.').Select(int.Parse).ToList();
    List<int> parts2 = s2.Split('.').Select(int.Parse).ToList();

    while(parts1.Count < parts2.Count)
        parts1.Add(0);
    while(parts2.Count < parts1.Count)
        parts2.Add(0);

    for(int i = 0; i < parts1.Count; i++)
    {
         if(parts1[i] < parts2[i])
             return -1;
         if(parts1[i] > parts2[i])
             return +1;
    }
    return 0;
}

Best Answer

Related Solutions

Algorithm for Exact Solution to the Travelling Purchaser Problem

Algorithms – How to Sort an Array of Numbers with Decimals

Related Topic