如何在2D阵列中找到最佳可用位置 [英] How do I find the best available position in a 2D array

问题描述

我会尽量保持这个简短，



所以我正在开发一个电影预订系统，现在是时候考虑算法了决定电影中的最佳地方。我一直在考虑使用BFS，但得出结论认为这可能不起作用，因为每个大厅的大小可能不同，大厅可能有20x30个座位，而另一个只能有8x5。



问题是，给了很多人，找到每个人最好的座位，这样他们仍然可以坐在一起。



我目前的解决方案是^ 2的复杂性，我只是向左/右和Y向上/向下检查X，但我很好奇我能否将它带入线性甚至恒定的时间哪个算法对此有用。



现在决定最好的地方总是在中间，当你向前/向后或向左/向右移动时这个地方变慢了。例如，最糟糕的地方就在拐角处。



感谢您，我不希望这个问题过于愚蠢:)



- Jackie

Hi I'll try to keep this short,

So I'm working on a Cinema booking system and it is time for me to think of an algorithm to decide the "best" place(s) in the Cinema. I've been thinking of maybe using a BFS but jumped to the conclusion that this may not work as each hall may vary in size, on hall could have 20x30 seats, where an other could only have 8x5.

The problem is, given a number of people, find the best possible Seat(s) for each person so they're still able to sit next to each other.

My current solution is a n^2 complexity where I simply just check X to the left/right and Y up/down, but I'm curious if I could bring it into linear or even constant time and which algorithm could be useful for this.

For now it's decided that the best place is always right in the middle and as you move forward/backward or left/right the the place slow becomes worse. eg the worst place would be in a corner.

Thanks in regards, I don't hope this question is overly dumb :)

- Jackie

推荐答案

请看我对这个问题的评论，主要的一个是关于个人偏好的，整个想法毫无意义。但是，目前尚不清楚，也许你已经解决了它。可以通过某种方式询问个人偏好来解决。每次我必须为我的门票预订固定座位时，我被问及我的偏好，有一些选项跟我一起。



现在，它看起来像你的算法，实际的时间复杂度是O（N），更糟糕的情况。实际上，你有N个座位，可以检查所有N，作为一张票的起点。它已经给你O（N）了。对于每个这样的座位，您需要在此点附近检查最多X * Y座位。但X * Y是一个常数参数。你没有测试y的所有值从0到X - 1，并且对Y来说都是相同的。这个常量带括号，它不会影响复杂性。这是因为常数因子不会改变函数的渐近行为。



请参阅：

http：/ /en.wikipedia.org/wiki/Computational_complexity_theory [ ^ ]，

http://en.wikipedia.org/wiki/Time_complexity [< a href =http://en.wikipedia.org/wiki/Time_complexitytarget =_ blanktitle =New Window> ^ ]，

http://en.wikipedia.org/wiki/Big_O_notation [ ^ ]。

-SA

Please see my comments to the question, and the main one would be the first, about personal preference, which render the whole idea making little sense. However, it's not clear, maybe you already solved it. It can be solved by asking about personal preferences in some way. Every time I had to book fixed seats for my tickets, I was asked about my preferences, with some options followed with me.

Now, it looks like with your algorithm, the actual time complexity is O(N), in a worse case. Indeed, you have N seats, and can check all N, as a starting point for just one ticket. It gives you O(N) already. With each such seat, you need to check up at most X*Y seats around this point. But X*Y is a constant parameter. You don't test all values of y from 0 to X − 1, and the same for Y. This constant "carries out of brackets", it does not effect the complexity. This is because the constant factor does not change asymptotic behavior of a function.

Please see:
http://en.wikipedia.org/wiki/Computational_complexity_theory[^],
http://en.wikipedia.org/wiki/Time_complexity[^],
http://en.wikipedia.org/wiki/Big_O_notation[^].

—SA

添加谢尔盖所说的（在那个发现座位是O（N），但实际上并没有说什么是最好的。



您可以为每个座位分配重量，更好的座位具有更高的值UE的。在搜索座位时，您将当前所选座位保持为最高值（y的总和（其中y是所需座位的数量），每个座位连续排座位）。如果您发现y座位值较高，请选择这些座位。



这可以归结为一个简单的排序算法，您可以从列表中删除占用的座位，然后根据索引进行排序。之后，您只需选择连续的前y座位。

To add to what Sergey said (in that finding the seats is O(N), but really doesn't say what ones are the "best".

You could assign weights to each seat, with "better" seats having higher values. While searching for seats you hold the currently selected seats as the highest value (sum of y (where y is the number of required seats) seats in a row for each guest). If you find y seats with a higher value, select those.

This then can come down to a simple sorting algorithm, where you remove occupied seats from the list and then sort based on index. After that you just select the top y seats that are sequential.

这篇关于如何在2D阵列中找到最佳可用位置的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！