Algorithm for rule-based sorting?

Question

I am trying to plant a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as defined in this table:

Num Vegetable   Friends       Foes
1   Watermelon  7,4,3          8,6
2   Tomatoes    9,8,6,5,1      7
3   Sunflowers  7,6,11  
4   Zucchini    9,7,3   
5   Eggplant    9,6,2          7,10
6   Cucumbers   9,7,3          8,1
7   Corn        8,6,4,3,1      5,2
8   Cantaloup   7,4,3          6,1
9   Bell peppers6,5,11,10,2 
10  Swiss chard 2              5
11  Rhubarb     9,3 

Assuming I have one of each plant and they are being planted in a row, how do I sort them (most efficiently) so that I will get the most adjacent friends and no adjacent enemies? There are tools online, but I am trying to understand the thought process and the implementation. Java is a language I know, so that would be the most helpful out of any language, but the concepts are the main point for me.

Answer 1

This kind of problem can be approached by using branch & bound techniques. In short

• the search space forms a tree, which can be traversed by a depth-first search, or breadth-first search, or a combined approach (see Wikipedia, tree traversal)

• each level of the tree represents one of the entries in the planting row

• at the top of the tree, there are 11 possibilities to pick one plant

• at each level below, the number of available plants reduces by one

• for avoiding to explore all 11! (=39.916.800) different orders, one needs to prune the search tree

• pruning can be done

  (1) by forbidding to place foes beneath each other, or

  (2) by estimating the maximum number of possible friends for a given partial solution, and stopping the exploration of the subtree when this number is lower than the current best known solution

If such a full analysis of the search space is feasible depends heavily on the number of items, and if the contraints allow effective pruning of the tree.

For huge number of items (several hundreds or thousands) it might not effectively be possible to find the globally optimal solution within a reasonable amount of time. However, algorithms like simulated annealing may allow to find a "good enough" solutions which approximate the global optimum. Since you tagged your question with "genetic algorithms": that is indeed also an approach to find approximative solutions, but usually more effort to implement than an evolutionary algorithm like SA.

Answer 2

If I understand properly, the way this problem is structured allows it to be solved by building a directed graph and determining whether there is any path that includes all nodes without repeating any node. I've gone ahead and drawn an (ugly) drawing of the friend graph:

I haven't checked but I think there probably is at least one such path. Given that, you there shouldn't be any need to consider the 'enemies' data because any path through this graph would be one where only 'friends' are adjacent.

Now if you were to try to maximize the distance between 'enemies' or add more rows, this would be a far more complex problem but as stated it's fairly well-known. This is equivalent in structure to the Seven Bridges of Königsberg problem. I believe You could use a variant of Dijkstra's algorithm to come up with shortest path solutions that touch all nodes where all vertexes have a distance of 1.

On looking at the graph again, it was thinking about the fact that some friend relationships are on-directional. This could be modeled by adding a weight (distance) to each vertex based on whether they are bi-directional e.g. 1 for a 1-directional and 0.5 for a bi-directional relationship. This would allow the shortest path algorithm to optimize such that you get answers where plants have friends on both sides as much as possible.