7 ms·

Originally saw this in a twitter thread by Daniel Piker: https://twitter.com/kangaroophysics/status/1625423951156375553 https://twitter.com/kangaroophysics/stat

Originally saw this in a twitter thread by Daniel Piker: https://twitter.com/kangaroophysics/status/1625423951156375553 https://twitter.com/kangaroophysics/status/16254239511563755... As a former architect, it's tempting to see similarities in the way architects do space planning: continually re-arranging the various rooms/circulation elements to find the most efficient use of space. Seeing how counter-intuitive these solutions are (and the fact that most of them are not proved, only "found") makes me think that space-planning may not be "solvable" computationally.

NKosmatos 4y ago
I saw it as well and immediately I thought of posting it here, but as always I search before I post and it was reposted a year ago, so I decided not to. Glad you did post it though because it’s a really nice visualization and a very good page and deserves to be seen by more people who like such things!
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]
    - 4y ago

NKosmatos 4y ago

I saw it as well and immediately I thought of posting it here, but as always I search before I post and it was reposted a year ago, so I decided not to. Glad you did post it though because it’s a really nice visualization and a very good page and deserves to be seen by more people who like such things!

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]
  - 4y ago