We could have a different objective, for example, minimize the average price paid, but this would be a different optimization problem. Our goal is to maximize the chances of getting the cheapest station. The definition of a good choice in this case is one that has a high probability of giving us the cheapest station. STEP Scroll down to see why you ended up at that station and read the text on the sheet.Ĭell F7 always displays the first station that is better (lower) than the best of the K stations in cell F5. Cell F7 displays the station you ended up at. This reshuffles the stations and draws a border in column D for the cell at the K th station.Ĭell F5 reports the best of the K stations (that were rejected). We pass up stations 1 to 10, then take the next station that is better than the best of the 10 stations we rejected. Our goal is to determine the value of K that maximizes the probability that we get the lowest priced station. This is the choice variable in this problem. Column D changes every time you click the button because the stations are shuffled.Ĭell F2 sets the value of K. Columns C and D report the location of each station. It shuffles the stations, randomly distributing them along the road you are traveling in column D.Ĭell B7 reports where the lowest priced station (#1) is located. The lowest priced station is 1, and the highest priced station is 100. STEP Open the Excel workbook SequentialSearch.xls and read the Intro sheet, then proceed to the Setup sheet.Ĭolumn A has the 100 stations ranked from 1 to 100. It also applies to many other areas, including marriagesearch online for Kepler optimal stopping to see how the famous astronomer chose his spouse. A firm picks the first K applicants, interviews and rejects them, then picks the next applicant that is better than the best of the K applicants. In hiring, it is called the secretary problem. The Sequential Search Model can be used for much more than buying gasit has extremely wide applicability and, in math, it is known as optimal stopping. On the other hand, a high value of K, say 98, suffers from the fact that the lowest price station is probably in that group and you’ve already rejected it! Yes, this problem is certainly tricky. That might be 1, but with 26 possibilities, that’s not likely. Then as soon as you see a station better than 27, you will pull in there. For example, say the first three stations are ranked 41, 27, and 90. So, K = 3 is probably not going to work well because you probably won’t get a super low price in a set of just three so you probably won’t end up choosing the lowest price. But if you choose K too small, you will get only a few prices and the first station with a price lower than the lowest of the K stations is unlikely to give you the lowest price. This strategy will fail if the lowest price is in the group of the K stations you drove by, so you might want to choose K to be small.
If it is cheaper than the previous 51 (or 1 to 50 since we know the 51 st station isn’t cheaper than the cheapest of the first 50), get gas there.Ĭontinue this process until you get gas somewhere, pulling into the last (100 th) station if you get to it (it will have a sign that says, “Last chance gas station”). If not, pass it up and consider the 52 nd station. Perhaps K = 50 is the right answer? That is, drive by stations 1 to 50, then look at the next (51 st) station and if it is better than the lowest of the 50 you drove by, pull in. The chances of that are 1 in a 100.Ī strategy for choosing a station goes like this: Pick some number \(K < N\) where you reject (drive by) stations 1 to K, then choose the first station that has a price lower than the lowest of the K stations that you rejected. So, this strategy will only work if the cheapest station is the very last one. Once you pass a station, you cannot return to it. This is a terrible idea because you cannot go back (remember, no U-turns). You might argue that you should drive by all of the stations, and then just pick the best one. Suppose you focus on the following question: How do you maximize the chances of finding the cheapest station? The lowest price station might be 18 th or 72 nd or even the very first one.
You do not know the prices coming up because the stations are randomly distributed on the road. There is a lowest price station and the stations can be ranked from 1 (lowest, best price) to 100 (highest, worst price). If you drive past a station, turning around is out of the question (there is traffic and you have a weird phobia about U-turns). As you drive, there are gas stations (say N = 100) to the left and right (taking a left does not bother you too much) and you can easily read the price per gallon as you drive up to each station. Imagine you are driving down the road and you need fuel.
0 kommentar(er)
