Algorithms to achieve reasonable result with most economic efforts

Question

Suppose that there are six kinds of problems to be handled when reading a book,
I illustrate the details as follow:

while True:
    if encounter A :
        handle A
    #during handling the problem, it might spawn new problems of
    #A, B, C, D, E,
        produce  (A,B..E or null)
        continue

    if B occurs:
        handle B
    #during hanlding the problem, it might spwan new problems
    #A, B, C, D, E,
        produce  (A,B..E or null)
        continue

    if C happens:
        handle C
        produce (A,B..E or null)
        continue
    ...

    if there are no problmes:
        break

Assume I have 3 problems,
the above program might endless loop on first one and never touch the second.

Take an example that I am reading a book,
'Problem A' is defined as encounter a 'new word', handle it is to look up dictionary.
When looking up, I might come acorss another new word, another and another.
In this case, I will never end up reading one sentence of a book.

As a solution,
I introduce a container to collect problems, value-weighted them then determine to execute which one.

def solve_problems(problems)
    problem_backet = list(problems)
    while True:
        if problem_backet not is null:
            #value-weighted all the problem 
            #and determine one to implement
            value_weight problems
            problem = x

        if problem == A:
            handle A
            problem_backet.append(new_problem)
            continue

        if problem == B:
            handle B
            problem_backet.append(new_problem)
            continue
        ...
        if problem_backet is null:
            return 

I tried alternatively to seek inspiration and improve efficiency.

def solve_problems(problems):
    global problem_backet
    problem_backet = list(problems)
    value_weight problems
    problem = x
    if problem == A:
        handle A
        problem_backet.append(new_problem)
        solve_problems(problem_backet)
    if problem == B:
        handle B
        problem_backet.append(new_problem)
        solve_problems(problem_backet)
    if problem == C:
        handle C
        problem_backet.append(new_problem)
        solve_problems(problem_backet)
    ...
    if problem_backet is null:
        return

Again, the value_weighted process consume huge efforts and time.

How to solve such a problem in a proper algorithms?

Answer 1

You can do several things to approach such a problem.

One of them is to set a value of "max-iterations" or "max-effort" in a Machine Learning style that you can invest into reading a book. Therefore you will execute (handle) only up to a number of actions, until the limit has been reached. This solution will look like:

while(effortRemaining > 0){
     # Do your actions
}

The actions you do should be the ones that report more benefit/less effort according to some metric that you need to define.

When you perform a certain action (handle) you substract the cost/effort of that action from effortRemaining and you continue with your flow.

Answer 2

'Problem A' is defined as encounter a 'new word', handle it is to look up dictionary. When looking up, I might come across another new word, another and another. In this case, I will never end up reading one sentence of a book.

Looks like it will eventually end up reading the sentence, since the number of new words is limited by dictionary size. In general it sounds OK to me, unless there are some other restrictions not explicitly mentioned, like finish sentence reading in a limited time.

How to solve such a problem in a proper algorithms?

Well, if there is no a "limited time" restriction, your original algorithm is almost perfect. To make it even better in therms of overall performance, we might handle all problems A first, then move to B and so on. It will increase the data locality and overall performance of our algorithm.

But if there is a "limited time" restriction, we can end up reading full sentence in that time (without full understanding) or end up reading part of the sentence (fully understanding that part) or something in between (like suggested by @Lauro Bravar).

From the example above it is not quite clear how we do the value_weight, but the proper name for this kind of problems is Priority Queueing. There are variety of algorithms and implementations, please have a look at Wikipedia page for the details: https://en.wikipedia.org/wiki/Priority_queue

Answer 3

You have already the algorithm (with the help of Andriy for the priority queue), but you lack the design. When I see your multple ifs that check the type of the problem, I think to polymorphism. Why not try OOP? You have two objects to define: a problem and a priority queue. Fortunately, the priority queue is defined in the heapq module. Let's focus on the problem: in its core definition, it is handled and may be compared to other problems (it is more or less urgent). Note that, guided by the OOP principles, I do not talk of the structure or implementation of a problem, but only of the functions of a problem:

class Problem()
    def handle(self, some args): # we may need a dictionary, a database connection, ...
        ...

    def compare(self, other):
        ...

But you said that when a problem is handled, it may add new problems to the queue. So let's add a precision to the definition of handle:

def handle(self, queue, some args): # we still may need a dictionary, a database connection, ...
    ...

In Python, compare is a special method named __lt__, for "lower than". (You have other special comparison methods, but __lt__ will be sufficient here.)

Here's a basic implementation example:

class Problem():
    def __init__(self, name, weight):
        self.__name = name
        self.__weight = weight

    def handle(self, queue):
        print ("handle the problem {}".format(self))
        while random.random() > 0.75: # randomly add new problems for the example
            new_problem = Problem(name*2, random.randint(0, 100))
            print ("-> Add the problem {} to the queue".format(new_problem))
            heapq.heappush(queue, new_problem) # add the problem to the queue

    def __lt__(self, other):
         return self.__weight > other.__weight # note the >

    def __repr__(self): # to show in lists
        return "Problem({}, {})".format(self.__name, self.__weight)

Wait! Why "lower than" and a >? That's because the module heapq is a min-heap: it returns the smallest element first. Thus, we define the big weights as smaller than the little weights.

Now, we can build a begin queue with fake data for the example:

queue = []
for name in ["foo", "bar", "baz"]:
    problem = Problem(name, random.randint(0, 100))
    heapq.heappush(queue, problem) # add the problem to the queue

And run the main loop:

while queue:
    print ("Current queue", queue)
    problem = heapq.heappop(queue) # the problem with the max weight in O(lg n)
    problem.handle(queue)

I guess you will be able to subclass the Problem class to represent the various problems you might want to handle.