2

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.

  • Since this is a question about algorithms, not software architecture, it might be a better fit for Computer Science Stack Exchange (https://cs.stackexchange.com/). – Solomon Ucko May 19 at 2:30
  • Your question is fine here, I think we have enough experts in this community who can answer your question. CS.SE is better suited if you want to get help for a full runtime analysis in terms of Big-O. – Doc Brown May 19 at 3:12
2

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.

| improve this answer | |
  • Fascinating. As an aside, I tagged it not really knowing what it was, but it sounded right so I put it in there. – Sam May 19 at 12:00
  • Adding more constraints can also help with pruning. Right now, I don't think this has a single optimal solution If you specify a requirement that e.g. every plant type must be represented or you specify a minimum/maximums for each plant etc. it will reduce the search space greatly. – JimmyJames May 19 at 14:25
  • Sorry, I missed the constraint that to have one of each plant and that it's a single row. Still no one solution but it's a smaller space than I was thinking. – JimmyJames May 19 at 14:32
1

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:

enter image description here

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.

| improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.