3 ms·

> space-planning may not be "solvable" computationally It isn't. The knapsack problem is NP-complete and roughly translates to "Given a space of size X and a s

by Swizec 4y ago

> space-planning may not be "solvable" computationally It isn't. The knapsack problem is NP-complete and roughly translates to "Given a space of size X and a set of items of sizes A, B, C, how do you pack X optimally?". Designing a room layout seems like it would fall squarely into that, with additional restrictions added on top to make it even harder. https://en.wikipedia.org/wiki/Knapsack_problem https://en.wikipedia.org/wiki/Knapsack_problem According to wikipedia we do have algorithms that are useful in practice, but that's not quite the same as "definitely optimal"

Sharlin 4y ago
I mean, NP-complete problems are perfectly solvable computationally, and given the relatively small number of rooms per floor that architects are concerned with, finding the optimal solution with a computer should still take much less time than it takes a human to come up with some local optimum in the design space. The real problem is actually encoding all the constraints that an architect is really working under, including such inherently difficult-to-quantify aspects as aesthetics, ergonomics, and familiarity! A solution that maximizes the available m^2 is useless if its human users find it too weird.
layer8 4y ago
The knapsack solution space is countable and effectively finite, and thus is solvable, even if not efficiently due to NP-completeness. Space-planning has to work with a potentially uncountable number of positions/orientations in continuous space, and thus might be different.
- turtledragonfly 4y ago
  > effectively finite This made me scratch my head a bit. I'm aware of there being different types of infinities, but to call a "smaller" infinity "effectively finite" seems a bit odd. I'm not up-to-date on math terminology, though. In truth, I'm not quite sure what you mean by "solvable" vs "not solvable" here, either. In the above discussion I thought it meant "not tractable in a reasonable amount of time" (i.e. NP-complete => "not solvable"). But you seem to have a different definition you're working from. Could you elaborate on what you mean by "effectively finite => solvable" ?
  - layer8 4y ago
    It is effectively finite in that the knapsack has a finite capacity and there is a finite selection of items with positive weight, hence the number of items that can fit into the knapsack is limited by the knapsack capacity divided by the smallest item weight. So, while for the unbounded knapsack problem the number of instances of an item that may be included is not limited, it is effectively still limited by the knapsack capacity. Therefore the number of item combinations that have to be considered is finite as well. The GP had put "solvable" in quotes. I understood the GP to say that for space planning, there may not be an algorithm that is guaranteed to produce an answer in finite time. For the knapsack problem there is such an algorithm (even if that finite time, due to NP-completeness, could be very long). The formal term "solvable", as applied to decision problems, actually only means "semidecidable", a much weaker property, see https://en.wikipedia.org/wiki/Decision_problem#Decidability https://en.wikipedia.org/wiki/Decision_problem#Decidability.
  - deleted 4y ago
    [deleted]
  - SamBam 4y ago
    The knapsack problem has a finite number of solutions. You can brute-force the optimal solution, if you don't care about efficiency. Ditto the Traveling Salesman problem. I'm not sure whether this problem is finite or not, given that you can place objects at any real-number coordinates and any real-number angle. But if you simply make those increments small enough (you can only put boxes a whole number of planck-lengths apart) then there are a finite number of possible arrangements, so it's possible to brute-force.

by Swizec 4y ago

Sharlin 4y ago

I mean, NP-complete problems are perfectly solvable computationally, and given the relatively small number of rooms per floor that architects are concerned with, finding the optimal solution with a computer should still take much less time than it takes a human to come up with some local optimum in the design space. The real problem is actually encoding all the constraints that an architect is really working under, including such inherently difficult-to-quantify aspects as aesthetics, ergonomics, and familiarity! A solution that maximizes the available m^2 is useless if its human users find it too weird.

layer8 4y ago

The knapsack solution space is countable and effectively finite, and thus is solvable, even if not efficiently due to NP-completeness. Space-planning has to work with a potentially uncountable number of positions/orientations in continuous space, and thus might be different.

turtledragonfly 4y ago
> effectively finite This made me scratch my head a bit. I'm aware of there being different types of infinities, but to call a "smaller" infinity "effectively finite" seems a bit odd. I'm not up-to-date on math terminology, though. In truth, I'm not quite sure what you mean by "solvable" vs "not solvable" here, either. In the above discussion I thought it meant "not tractable in a reasonable amount of time" (i.e. NP-complete => "not solvable"). But you seem to have a different definition you're working from. Could you elaborate on what you mean by "effectively finite => solvable" ?
- layer8 4y ago
  It is effectively finite in that the knapsack has a finite capacity and there is a finite selection of items with positive weight, hence the number of items that can fit into the knapsack is limited by the knapsack capacity divided by the smallest item weight. So, while for the unbounded knapsack problem the number of instances of an item that may be included is not limited, it is effectively still limited by the knapsack capacity. Therefore the number of item combinations that have to be considered is finite as well. The GP had put "solvable" in quotes. I understood the GP to say that for space planning, there may not be an algorithm that is guaranteed to produce an answer in finite time. For the knapsack problem there is such an algorithm (even if that finite time, due to NP-completeness, could be very long). The formal term "solvable", as applied to decision problems, actually only means "semidecidable", a much weaker property, see https://en.wikipedia.org/wiki/Decision_problem#Decidability https://en.wikipedia.org/wiki/Decision_problem#Decidability.
- deleted 4y ago
  [deleted]
- SamBam 4y ago
  The knapsack problem has a finite number of solutions. You can brute-force the optimal solution, if you don't care about efficiency. Ditto the Traveling Salesman problem. I'm not sure whether this problem is finite or not, given that you can place objects at any real-number coordinates and any real-number angle. But if you simply make those increments small enough (you can only put boxes a whole number of planck-lengths apart) then there are a finite number of possible arrangements, so it's possible to brute-force.