1
$\begingroup$

I am trying to plant a row in 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(I have one of each):

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 peppers  6,5,11,10,2 
10  Swiss chard   2            5
11  Rhubarb       9,3

How do I find the arrangement? Sort them using an algorithm? The title was my best guess at the answer. I am trying to understand the thought process and the implementation.

Improve this question
$\endgroup$
  • $\begingroup$ Watermelon 1's friends includes Zucchini 4 but Zuccihini 4's friends does not include Watermelon 1. Is that intentional? $\endgroup$ – John L. May 19 '20 at 21:24
  • $\begingroup$ I believe so. I got my information from From Seed To Spoon, and I think it means that watermelon benefits from zucchini, but zucchini does not particularly benefit from watermelon. $\endgroup$ – Sam May 19 '20 at 21:27
  • $\begingroup$ It happens all foes are mutual in the table. Interesting. $\endgroup$ – John L. May 19 '20 at 21:30
  • $\begingroup$ Most Constrained Variable and Least Constraining Values could be helpful. $\endgroup$ – John L. May 19 '20 at 21:37
2
$\begingroup$

As @Steven wrote, this problem is NP-hard. However that doesn't mean that you can't solve the problem for small instances.

You can solve such a problem by simply iterating over all $n!$ different permutations, and checking each if any of the arrangements is allowed and how good it is. This has complexity $O(n \cdot n!)$.

Much faster (but still exponential complexity) will be a variation to the Bellman–Held–Karp algorithm. Compute for each pair $(V, v)$ with $V$ being a subset of all vegetables and and $v \in V$, if it is possible to arrange the vegetables $V$ in a way such that $v$ is the last one and what it's best value is. You can define a recursive formula for this function, and apply dynamic programming, like in the BHK algorithm. That should run in $O(n^2 \cdot 2^n)$.

Improve this answer
$\endgroup$
1
$\begingroup$

Even just determining if your problem admits a feasible solution is NP-hard.

Let $G = (V,E)$ be a graph. For each vertex $u$ create a vegetable that has no friends and has all vegetables corresponding to vertices in $\{v : (u,v) \not\in E\}$ as foes.

There is a way to plant all vegetables in a row with no adjacent foes if and only if there is a simple path of length $|V|$ in $G$, that is, if and only if there is an Hamiltonian path in $G$ .

Improve this answer
$\endgroup$

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.