Greedy and backtracking solutions to an arrangement problem with constraints

Question

I'm revising for my finals. I have found a pattern in past papers in terms of a recurring question, reworded coming up every year. But I've no idea what the marker actually wants... I've asked class mates but they all seemed to be confused. One gave me a sample answer of code doing it, whereas another one thought he wants some sort of graph with nodes/edges to represent the answer.

1) A group of $n$ teenagers $T_1,\dots,T_n$ are to sit in a single row of $n$ chairs watching a particularly boring comedy movie. Some teenagers quarrel with each other all the time. The problem is to devise a seating arrangement for the group in such a way that teenagers sat next to each other do not quarrel.

a) Propose a solution to this problem using the Backtracking approach. Specify clearly the search space and any pruning conditions used. Show how your algorithm would work for 3 teenagers, $T_1,T_2,T_3$, assuming that the only quarrelling teenagers are $T_2$ and $T_3$. Note: stop the search after finding a solution. [12 marks]

b) Propose a solution to this problem using the Greedy approach. Estimate the complexity of the resulting algorithm. [8 marks]

I've spent days going through my notes and reading up on greedy/backtracking but I still don't see how it fits with the question. Whenever I look up Backtracking/greedy approach questions the questions are nothing like how college asks them which makes me very confused...

We've covered dynamic programming, backtracking, greedy algorithms knapsack problem, first fit, next fit minimal spanning trees, Kruskal's algorithm, Prim's algorithm, divide and conquer $N$ queens problem for backtracking.

Answer 1

Overview of the problem

If you takes teenagers as vertices of a graph, and have an edge whenever the two teenagers are compatible. This gives you an undirected graph, and what you need is a Hamiltonian path in this graph (a path that contains every node exactly once). Maybe searching the web on this abstract version of the problem will yield more information. Much is said in wikipedia about the Hamiltonian path problem, which is a NP complete problem. I will only try to discuss some apects, with my limited competence on the topic, taking into account the way your question is stated.

Backtracking is just a way of implementing a non-deterministic algorithm. It is usually simpler to describe the non-deterministic algorithm, and just say that it is implemented by backtracking, and possibly explain separately what that is (as I do below)

The non-deterministic algorithm

In the case of the Hamiltoniam path problem (which you can translate back into your teenagers problem), the non-deterministic algorithm is as follow:

1. Choose a starting node for the path, and mark it used.

2. While there are unmarked nodes do:

   Choose a new unmarked node connected to the last node added to the path, add it at the end of the path, and mark it used.

At the end of the loop you have a Hamiltonian path. The choose statement is non deterministic, as you have to take one of many possibilities, many (or all) of which may not succeed.

Backtracking interpretation

Failure may in general occur in different ways. Here you have failure when none of the unmarked nodes is connected to the last node added to the path (i.e. none of the remaining teenagers is compatible with the last one chosen).

The backtracking implementation consist in keeping track, at each occurrence of a choose statement, of all the possible choices that have not yet been tried. If you fail, you go back to the previous choose, undoing what was done (i.e. node addition to the path and node marking), discard the choice made and make a new choice from those that have not yet been tried at that choose statement.

One way of implementing this is to associate a list of remaining alternative choices to each node of the constructed path. Another possibility is to rely on the exception mechanism of the programming language.

Pruning

I am not sure what is (or should be) considered pruning in this case.

Checking that a node chosen is connected to the previously chosen one is a very trivial form of pruning. No pruning at all would be exploring the complete set of remaining nodes at each choose statement, to discover soon after that some fail because the node is not connected to the end of the path.

Greedy algorithm

The greedy algorithm as described by Yuval Filmus' answer is just the non-deterministic algorithm, except for the fact that you do not backtrack. You just fail. I do not know whether there is more to be said.

He is much more expert than I am on these issues. However, my own feeling is that the very concept of greedy algorithm makes less or little sense in this case. The reason is that I understand greedy algorithms as a way of finding good solutions to quantitative optimization problems, which may not be optimal in some cases.

A greedy algorithm also has to make choices, and does so on the basis of local optimizations that may not be optimal globally. But it is expected to succeed anyway and does not have to backtrack: the price of greediness is that the "cost" (however defined) of the result obtained by the algorithm may be higher than the cost of the optimal solution.

I do not think that is really very meaningful in an all or nothing situation, were you are supposed to succeed or to fail, without any measure of intermediate situations, like placing the largest possible number of teenagers, or placing them all with the smallest number of conflictual sittings. These examples may be seen as optimization variants of the problem where greediness makes sense.

However, we can use heuristics that could possibly increase the chances of success. In the case of our optimization variants, they could e seen as greedy techniques that improve the chances of having near otpimal solution (Though I did not prove anything). But the greedy algorithm remains basically the non-deterministic description. The heuritic comes as a way to choose that improves chances of success, or of approaching the least cost.

One such heuristic, is to always choose one of the unmarked nodes that has the least number of edges connecting to other unmarked nodes. The purpose is to keep in your bag nodes that will be easier to connect to the path, while removing those that are getting hard to use. And if one of these node is disconnected from all others, or has only one connection but cannot be added to the path immediately, you know you have failed and can start backtracking earlier.

We could say that we try to optimize the cost of the search reather than the cost of the solution obtained, and that this "greedy" algorithm does increase the chances of success if there is no backtrack, or reduce the number of search steps if we use backtrack, or improve the solution obtained if we consider one of the two optimization variants I described above (maximum number of non-conflicting teenagers, or minimum number of conflicts).

A global improvement

A global way to improve the algorithm is to decompose the graph into a a block tree of the graph, where each node is a biconnected components. This can be done in linear time.

A Hamiltonian path for the whole graph is composed of subpaths in each of the biconnected components, connected by the edges of the block tree.

In practice, you solve the given problem at the level of the block tree, and then you solve it independently for each block, i.e. for each biconnected component.

Since the algorithm is exponential anyway (NO complete), there is much to be gained whenever it can be decomposed, thus reducing the size of the sub-problems.

Actually, if the block tree is not composed of a simple path without branching, there is no solution to the problem. So that may be a way of getting much faster negative answers.

This may also be seen as a form of global pruning of the search space.

Answer 2

The idea of the backtracking algorithm is simple, though somewhat cumbersome to express. Perhaps it's easiest to explain it working through the example in the question. We start by putting $T_1$ on chair 1. We then put $T_2$ on chair 2. Then we put $T_3$ on chair 3, and we discover a conflict. So we backtrack, replacing $T_3$ with the next available student. In this particular instance, there is no other student, so we also remove $T_2$ and replace it with the next available student, $T_3$. The situation now is $T_1T_3?$. We put the first available student, namely $T_2$, on chair 3. Again we discover a conflict, so we backtrack. We attempt to replace $T_2$ with another student, but there are no such. Then we attempt to replace $T_3$ with the next student, but there are none. So we backtrack once again, and replace $T_1$ with $T_2$. The situation now is $T_2??$. We then put the first available student, which is $T_1$, on chair 2, and then $T_3$ on chair 3. At this point we stop since this is a feasible solution. The entire transcript is:

• ???
• T_1??
• T_1T_2?
• T_1T_2T_3
• T_1T_3?
• T_1T_3T_2
• T_2??
• T_2T_1?
• T_2T_1T_3

Hopefully you can now formulate the general algorithm.

As for the greedy approach, I don't really see where they're going. The natural greedy algorithm in this case works as follows:

• Put $T_!$ on chair 1.
• Put the lowest-indexed student $T_{i_2}$ not conflicting with $T_1$ on chair 2.
• Put the lowest-indexed student not conflicting with $T_{i_2}$ on chair 3.
• And so on.

The problem with this algorithm is that it could fail – as it indeed does in the example analyzed in part (a). So the greedy approach fails.

As babou mentions, the problem described in the exercise is Hamiltonian Path in disguise, so (unless P=NP) doesn't have efficient solutions.