google-research

unfair-prophet.cc
230 строк · 13.9 Кб
Перенос по словам
1
// Copyright 2024 The Google Research Authors.
2
//
3
// Licensed under the Apache License, Version 2.0 (the "License");
4
// you may not use this file except in compliance with the License.
5
// You may obtain a copy of the License at
6
//
7
//     http://www.apache.org/licenses/LICENSE-2.0
8
//
9
// Unless required by applicable law or agreed to in writing, software
10
// distributed under the License is distributed on an "AS IS" BASIS,
11
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12
// See the License for the specific language governing permissions and
13
// limitations under the License.
14

15
#include "unfair-prophet.h"
16
#include <functional>
17
namespace fair_secretary {
18

19
using std::vector;
20

21
SecretaryInstance UnfairProphetAlgorithm::ComputeSolutionOneMinusOneE(
22
    const vector<SecretaryInstance>& elements,
23
    const std::vector<std::reference_wrapper<RandomDistribution>> distributions,
24
    const vector<double>& q) {
25
  for (int i = 0; i < elements.size(); i++) {
26
    if (elements[i].value >= distributions[elements[i].type].get().Reverse(
27
                                 1.0 - (1.0 / elements.size()))) {
28
      return elements[i];
29
    }
30
  }
31
  return SecretaryInstance(-1, -1);
32
}
33

34
SecretaryInstance UnfairProphetAlgorithm::ComputeSolutionOneHalf(
35
    const vector<SecretaryInstance>& elements,
36
    const std::vector<std::reference_wrapper<RandomDistribution>> distributions,
37
    const vector<double>& q) {
38
  for (int i = 0; i < elements.size(); i++) {
39
    if (elements[i].value >=
40
        distributions[elements[i].type].get().Middle(elements.size())) {
41
      return elements[i];
42
    }
43
  }
44
  return SecretaryInstance(-1, -1);
45
}
46

47
SecretaryInstance UnfairProphetAlgorithm::ComputeSolutionThreeForth(
48
    const vector<SecretaryInstance>& elements,
49
    const std::vector<std::reference_wrapper<RandomDistribution>> distributions,
50
    const vector<double>& q) {
51
  for (int i = 0; i < elements.size(); i++) {
52
    if (elements[i].value >=
53
        distributions[elements[i].type].get().PThreshold(i)) {
54
      return elements[i];
55
    }
56
  }
57
  return SecretaryInstance(-1, -1);
58
}
59

60
SecretaryInstance UnfairProphetAlgorithm::ComputeSolutionDiffEq(
61
    const vector<SecretaryInstance>& elements,
62
    const std::vector<std::reference_wrapper<RandomDistribution>> distributions,
63
    const vector<double>& q) {
64
  // Precomputed Threshold.
65
  vector<double> diff_solution_50 = {
66
      1.00E+00, 9.73E-01, 9.45E-01, 9.18E-01, 8.91E-01, 8.63E-01, 8.36E-01,
67
      8.09E-01, 7.82E-01, 7.56E-01, 7.29E-01, 7.03E-01, 6.76E-01, 6.50E-01,
68
      6.24E-01, 5.99E-01, 5.74E-01, 5.49E-01, 5.24E-01, 4.99E-01, 4.75E-01,
69
      4.52E-01, 4.28E-01, 4.05E-01, 3.83E-01, 3.61E-01, 3.39E-01, 3.18E-01,
70
      2.98E-01, 2.77E-01, 2.58E-01, 2.39E-01, 2.20E-01, 2.02E-01, 1.85E-01,
71
      1.68E-01, 1.52E-01, 1.36E-01, 1.21E-01, 1.07E-01, 9.32E-02, 8.02E-02,
72
      6.78E-02, 5.60E-02, 4.50E-02, 3.46E-02, 2.49E-02, 1.59E-02, 7.65E-03,
73
      1.95E-04};
74
  vector<double> diff_solution_1000 = {
75
      1.00E+00, 9.99E-01, 9.97E-01, 9.96E-01, 9.95E-01, 9.93E-01, 9.92E-01,
76
      9.91E-01, 9.89E-01, 9.88E-01, 9.87E-01, 9.85E-01, 9.84E-01, 9.83E-01,
77
      9.81E-01, 9.80E-01, 9.79E-01, 9.77E-01, 9.76E-01, 9.74E-01, 9.73E-01,
78
      9.72E-01, 9.70E-01, 9.69E-01, 9.68E-01, 9.66E-01, 9.65E-01, 9.64E-01,
79
      9.62E-01, 9.61E-01, 9.60E-01, 9.58E-01, 9.57E-01, 9.56E-01, 9.54E-01,
80
      9.53E-01, 9.52E-01, 9.50E-01, 9.49E-01, 9.48E-01, 9.46E-01, 9.45E-01,
81
      9.44E-01, 9.42E-01, 9.41E-01, 9.40E-01, 9.38E-01, 9.37E-01, 9.36E-01,
82
      9.34E-01, 9.33E-01, 9.32E-01, 9.30E-01, 9.29E-01, 9.28E-01, 9.26E-01,
83
      9.25E-01, 9.24E-01, 9.22E-01, 9.21E-01, 9.20E-01, 9.18E-01, 9.17E-01,
84
      9.16E-01, 9.14E-01, 9.13E-01, 9.11E-01, 9.10E-01, 9.09E-01, 9.07E-01,
85
      9.06E-01, 9.05E-01, 9.03E-01, 9.02E-01, 9.01E-01, 8.99E-01, 8.98E-01,
86
      8.97E-01, 8.95E-01, 8.94E-01, 8.93E-01, 8.91E-01, 8.90E-01, 8.89E-01,
87
      8.87E-01, 8.86E-01, 8.85E-01, 8.83E-01, 8.82E-01, 8.81E-01, 8.79E-01,
88
      8.78E-01, 8.77E-01, 8.75E-01, 8.74E-01, 8.73E-01, 8.71E-01, 8.70E-01,
89
      8.69E-01, 8.67E-01, 8.66E-01, 8.65E-01, 8.63E-01, 8.62E-01, 8.61E-01,
90
      8.59E-01, 8.58E-01, 8.57E-01, 8.55E-01, 8.54E-01, 8.53E-01, 8.51E-01,
91
      8.50E-01, 8.49E-01, 8.47E-01, 8.46E-01, 8.45E-01, 8.43E-01, 8.42E-01,
92
      8.41E-01, 8.39E-01, 8.38E-01, 8.37E-01, 8.35E-01, 8.34E-01, 8.33E-01,
93
      8.31E-01, 8.30E-01, 8.29E-01, 8.28E-01, 8.26E-01, 8.25E-01, 8.24E-01,
94
      8.22E-01, 8.21E-01, 8.20E-01, 8.18E-01, 8.17E-01, 8.16E-01, 8.14E-01,
95
      8.13E-01, 8.12E-01, 8.10E-01, 8.09E-01, 8.08E-01, 8.06E-01, 8.05E-01,
96
      8.04E-01, 8.02E-01, 8.01E-01, 8.00E-01, 7.98E-01, 7.97E-01, 7.96E-01,
97
      7.94E-01, 7.93E-01, 7.92E-01, 7.90E-01, 7.89E-01, 7.88E-01, 7.87E-01,
98
      7.85E-01, 7.84E-01, 7.83E-01, 7.81E-01, 7.80E-01, 7.79E-01, 7.77E-01,
99
      7.76E-01, 7.75E-01, 7.73E-01, 7.72E-01, 7.71E-01, 7.69E-01, 7.68E-01,
100
      7.67E-01, 7.65E-01, 7.64E-01, 7.63E-01, 7.62E-01, 7.60E-01, 7.59E-01,
101
      7.58E-01, 7.56E-01, 7.55E-01, 7.54E-01, 7.52E-01, 7.51E-01, 7.50E-01,
102
      7.48E-01, 7.47E-01, 7.46E-01, 7.45E-01, 7.43E-01, 7.42E-01, 7.41E-01,
103
      7.39E-01, 7.38E-01, 7.37E-01, 7.35E-01, 7.34E-01, 7.33E-01, 7.31E-01,
104
      7.30E-01, 7.29E-01, 7.28E-01, 7.26E-01, 7.25E-01, 7.24E-01, 7.22E-01,
105
      7.21E-01, 7.20E-01, 7.18E-01, 7.17E-01, 7.16E-01, 7.15E-01, 7.13E-01,
106
      7.12E-01, 7.11E-01, 7.09E-01, 7.08E-01, 7.07E-01, 7.06E-01, 7.04E-01,
107
      7.03E-01, 7.02E-01, 7.00E-01, 6.99E-01, 6.98E-01, 6.96E-01, 6.95E-01,
108
      6.94E-01, 6.93E-01, 6.91E-01, 6.90E-01, 6.89E-01, 6.87E-01, 6.86E-01,
109
      6.85E-01, 6.84E-01, 6.82E-01, 6.81E-01, 6.80E-01, 6.78E-01, 6.77E-01,
110
      6.76E-01, 6.75E-01, 6.73E-01, 6.72E-01, 6.71E-01, 6.69E-01, 6.68E-01,
111
      6.67E-01, 6.66E-01, 6.64E-01, 6.63E-01, 6.62E-01, 6.61E-01, 6.59E-01,
112
      6.58E-01, 6.57E-01, 6.55E-01, 6.54E-01, 6.53E-01, 6.52E-01, 6.50E-01,
113
      6.49E-01, 6.48E-01, 6.47E-01, 6.45E-01, 6.44E-01, 6.43E-01, 6.41E-01,
114
      6.40E-01, 6.39E-01, 6.38E-01, 6.36E-01, 6.35E-01, 6.34E-01, 6.33E-01,
115
      6.31E-01, 6.30E-01, 6.29E-01, 6.28E-01, 6.26E-01, 6.25E-01, 6.24E-01,
116
      6.22E-01, 6.21E-01, 6.20E-01, 6.19E-01, 6.17E-01, 6.16E-01, 6.15E-01,
117
      6.14E-01, 6.12E-01, 6.11E-01, 6.10E-01, 6.09E-01, 6.07E-01, 6.06E-01,
118
      6.05E-01, 6.04E-01, 6.02E-01, 6.01E-01, 6.00E-01, 5.99E-01, 5.97E-01,
119
      5.96E-01, 5.95E-01, 5.94E-01, 5.92E-01, 5.91E-01, 5.90E-01, 5.89E-01,
120
      5.87E-01, 5.86E-01, 5.85E-01, 5.84E-01, 5.82E-01, 5.81E-01, 5.80E-01,
121
      5.79E-01, 5.78E-01, 5.76E-01, 5.75E-01, 5.74E-01, 5.73E-01, 5.71E-01,
122
      5.70E-01, 5.69E-01, 5.68E-01, 5.66E-01, 5.65E-01, 5.64E-01, 5.63E-01,
123
      5.61E-01, 5.60E-01, 5.59E-01, 5.58E-01, 5.57E-01, 5.55E-01, 5.54E-01,
124
      5.53E-01, 5.52E-01, 5.50E-01, 5.49E-01, 5.48E-01, 5.47E-01, 5.46E-01,
125
      5.44E-01, 5.43E-01, 5.42E-01, 5.41E-01, 5.40E-01, 5.38E-01, 5.37E-01,
126
      5.36E-01, 5.35E-01, 5.33E-01, 5.32E-01, 5.31E-01, 5.30E-01, 5.29E-01,
127
      5.27E-01, 5.26E-01, 5.25E-01, 5.24E-01, 5.23E-01, 5.21E-01, 5.20E-01,
128
      5.19E-01, 5.18E-01, 5.17E-01, 5.15E-01, 5.14E-01, 5.13E-01, 5.12E-01,
129
      5.11E-01, 5.09E-01, 5.08E-01, 5.07E-01, 5.06E-01, 5.05E-01, 5.03E-01,
130
      5.02E-01, 5.01E-01, 5.00E-01, 4.99E-01, 4.97E-01, 4.96E-01, 4.95E-01,
131
      4.94E-01, 4.93E-01, 4.92E-01, 4.90E-01, 4.89E-01, 4.88E-01, 4.87E-01,
132
      4.86E-01, 4.84E-01, 4.83E-01, 4.82E-01, 4.81E-01, 4.80E-01, 4.79E-01,
133
      4.77E-01, 4.76E-01, 4.75E-01, 4.74E-01, 4.73E-01, 4.72E-01, 4.70E-01,
134
      4.69E-01, 4.68E-01, 4.67E-01, 4.66E-01, 4.65E-01, 4.63E-01, 4.62E-01,
135
      4.61E-01, 4.60E-01, 4.59E-01, 4.58E-01, 4.56E-01, 4.55E-01, 4.54E-01,
136
      4.53E-01, 4.52E-01, 4.51E-01, 4.50E-01, 4.48E-01, 4.47E-01, 4.46E-01,
137
      4.45E-01, 4.44E-01, 4.43E-01, 4.41E-01, 4.40E-01, 4.39E-01, 4.38E-01,
138
      4.37E-01, 4.36E-01, 4.35E-01, 4.34E-01, 4.32E-01, 4.31E-01, 4.30E-01,
139
      4.29E-01, 4.28E-01, 4.27E-01, 4.26E-01, 4.24E-01, 4.23E-01, 4.22E-01,
140
      4.21E-01, 4.20E-01, 4.19E-01, 4.18E-01, 4.17E-01, 4.15E-01, 4.14E-01,
141
      4.13E-01, 4.12E-01, 4.11E-01, 4.10E-01, 4.09E-01, 4.08E-01, 4.06E-01,
142
      4.05E-01, 4.04E-01, 4.03E-01, 4.02E-01, 4.01E-01, 4.00E-01, 3.99E-01,
143
      3.98E-01, 3.96E-01, 3.95E-01, 3.94E-01, 3.93E-01, 3.92E-01, 3.91E-01,
144
      3.90E-01, 3.89E-01, 3.88E-01, 3.87E-01, 3.85E-01, 3.84E-01, 3.83E-01,
145
      3.82E-01, 3.81E-01, 3.80E-01, 3.79E-01, 3.78E-01, 3.77E-01, 3.76E-01,
146
      3.75E-01, 3.74E-01, 3.72E-01, 3.71E-01, 3.70E-01, 3.69E-01, 3.68E-01,
147
      3.67E-01, 3.66E-01, 3.65E-01, 3.64E-01, 3.63E-01, 3.62E-01, 3.61E-01,
148
      3.60E-01, 3.58E-01, 3.57E-01, 3.56E-01, 3.55E-01, 3.54E-01, 3.53E-01,
149
      3.52E-01, 3.51E-01, 3.50E-01, 3.49E-01, 3.48E-01, 3.47E-01, 3.46E-01,
150
      3.45E-01, 3.44E-01, 3.43E-01, 3.41E-01, 3.40E-01, 3.39E-01, 3.38E-01,
151
      3.37E-01, 3.36E-01, 3.35E-01, 3.34E-01, 3.33E-01, 3.32E-01, 3.31E-01,
152
      3.30E-01, 3.29E-01, 3.28E-01, 3.27E-01, 3.26E-01, 3.25E-01, 3.24E-01,
153
      3.23E-01, 3.22E-01, 3.21E-01, 3.20E-01, 3.19E-01, 3.18E-01, 3.17E-01,
154
      3.16E-01, 3.15E-01, 3.14E-01, 3.13E-01, 3.12E-01, 3.10E-01, 3.09E-01,
155
      3.08E-01, 3.07E-01, 3.06E-01, 3.05E-01, 3.04E-01, 3.03E-01, 3.02E-01,
156
      3.01E-01, 3.00E-01, 2.99E-01, 2.98E-01, 2.97E-01, 2.96E-01, 2.95E-01,
157
      2.94E-01, 2.93E-01, 2.92E-01, 2.91E-01, 2.90E-01, 2.89E-01, 2.88E-01,
158
      2.87E-01, 2.86E-01, 2.85E-01, 2.84E-01, 2.84E-01, 2.83E-01, 2.82E-01,
159
      2.81E-01, 2.80E-01, 2.79E-01, 2.78E-01, 2.77E-01, 2.76E-01, 2.75E-01,
160
      2.74E-01, 2.73E-01, 2.72E-01, 2.71E-01, 2.70E-01, 2.69E-01, 2.68E-01,
161
      2.67E-01, 2.66E-01, 2.65E-01, 2.64E-01, 2.63E-01, 2.62E-01, 2.61E-01,
162
      2.60E-01, 2.59E-01, 2.58E-01, 2.57E-01, 2.56E-01, 2.56E-01, 2.55E-01,
163
      2.54E-01, 2.53E-01, 2.52E-01, 2.51E-01, 2.50E-01, 2.49E-01, 2.48E-01,
164
      2.47E-01, 2.46E-01, 2.45E-01, 2.44E-01, 2.43E-01, 2.42E-01, 2.41E-01,
165
      2.41E-01, 2.40E-01, 2.39E-01, 2.38E-01, 2.37E-01, 2.36E-01, 2.35E-01,
166
      2.34E-01, 2.33E-01, 2.32E-01, 2.31E-01, 2.30E-01, 2.30E-01, 2.29E-01,
167
      2.28E-01, 2.27E-01, 2.26E-01, 2.25E-01, 2.24E-01, 2.23E-01, 2.22E-01,
168
      2.21E-01, 2.21E-01, 2.20E-01, 2.19E-01, 2.18E-01, 2.17E-01, 2.16E-01,
169
      2.15E-01, 2.14E-01, 2.13E-01, 2.13E-01, 2.12E-01, 2.11E-01, 2.10E-01,
170
      2.09E-01, 2.08E-01, 2.07E-01, 2.06E-01, 2.06E-01, 2.05E-01, 2.04E-01,
171
      2.03E-01, 2.02E-01, 2.01E-01, 2.00E-01, 1.99E-01, 1.99E-01, 1.98E-01,
172
      1.97E-01, 1.96E-01, 1.95E-01, 1.94E-01, 1.93E-01, 1.93E-01, 1.92E-01,
173
      1.91E-01, 1.90E-01, 1.89E-01, 1.88E-01, 1.87E-01, 1.87E-01, 1.86E-01,
174
      1.85E-01, 1.84E-01, 1.83E-01, 1.82E-01, 1.82E-01, 1.81E-01, 1.80E-01,
175
      1.79E-01, 1.78E-01, 1.77E-01, 1.77E-01, 1.76E-01, 1.75E-01, 1.74E-01,
176
      1.73E-01, 1.73E-01, 1.72E-01, 1.71E-01, 1.70E-01, 1.69E-01, 1.68E-01,
177
      1.68E-01, 1.67E-01, 1.66E-01, 1.65E-01, 1.64E-01, 1.64E-01, 1.63E-01,
178
      1.62E-01, 1.61E-01, 1.60E-01, 1.60E-01, 1.59E-01, 1.58E-01, 1.57E-01,
179
      1.56E-01, 1.56E-01, 1.55E-01, 1.54E-01, 1.53E-01, 1.53E-01, 1.52E-01,
180
      1.51E-01, 1.50E-01, 1.49E-01, 1.49E-01, 1.48E-01, 1.47E-01, 1.46E-01,
181
      1.46E-01, 1.45E-01, 1.44E-01, 1.43E-01, 1.43E-01, 1.42E-01, 1.41E-01,
182
      1.40E-01, 1.39E-01, 1.39E-01, 1.38E-01, 1.37E-01, 1.36E-01, 1.36E-01,
183
      1.35E-01, 1.34E-01, 1.33E-01, 1.33E-01, 1.32E-01, 1.31E-01, 1.31E-01,
184
      1.30E-01, 1.29E-01, 1.28E-01, 1.28E-01, 1.27E-01, 1.26E-01, 1.25E-01,
185
      1.25E-01, 1.24E-01, 1.23E-01, 1.22E-01, 1.22E-01, 1.21E-01, 1.20E-01,
186
      1.20E-01, 1.19E-01, 1.18E-01, 1.17E-01, 1.17E-01, 1.16E-01, 1.15E-01,
187
      1.15E-01, 1.14E-01, 1.13E-01, 1.13E-01, 1.12E-01, 1.11E-01, 1.10E-01,
188
      1.10E-01, 1.09E-01, 1.08E-01, 1.08E-01, 1.07E-01, 1.06E-01, 1.06E-01,
189
      1.05E-01, 1.04E-01, 1.04E-01, 1.03E-01, 1.02E-01, 1.02E-01, 1.01E-01,
190
      1.00E-01, 9.95E-02, 9.88E-02, 9.82E-02, 9.75E-02, 9.68E-02, 9.62E-02,
191
      9.55E-02, 9.49E-02, 9.42E-02, 9.35E-02, 9.29E-02, 9.22E-02, 9.16E-02,
192
      9.09E-02, 9.03E-02, 8.96E-02, 8.90E-02, 8.83E-02, 8.77E-02, 8.71E-02,
193
      8.64E-02, 8.58E-02, 8.51E-02, 8.45E-02, 8.39E-02, 8.32E-02, 8.26E-02,
194
      8.20E-02, 8.13E-02, 8.07E-02, 8.01E-02, 7.95E-02, 7.89E-02, 7.82E-02,
195
      7.76E-02, 7.70E-02, 7.64E-02, 7.58E-02, 7.52E-02, 7.45E-02, 7.39E-02,
196
      7.33E-02, 7.27E-02, 7.21E-02, 7.15E-02, 7.09E-02, 7.03E-02, 6.97E-02,
197
      6.91E-02, 6.85E-02, 6.79E-02, 6.73E-02, 6.68E-02, 6.62E-02, 6.56E-02,
198
      6.50E-02, 6.44E-02, 6.38E-02, 6.32E-02, 6.27E-02, 6.21E-02, 6.15E-02,
199
      6.09E-02, 6.04E-02, 5.98E-02, 5.92E-02, 5.87E-02, 5.81E-02, 5.75E-02,
200
      5.70E-02, 5.64E-02, 5.59E-02, 5.53E-02, 5.47E-02, 5.42E-02, 5.36E-02,
201
      5.31E-02, 5.25E-02, 5.20E-02, 5.14E-02, 5.09E-02, 5.03E-02, 4.98E-02,
202
      4.93E-02, 4.87E-02, 4.82E-02, 4.77E-02, 4.71E-02, 4.66E-02, 4.61E-02,
203
      4.55E-02, 4.50E-02, 4.45E-02, 4.40E-02, 4.34E-02, 4.29E-02, 4.24E-02,
204
      4.19E-02, 4.14E-02, 4.08E-02, 4.03E-02, 3.98E-02, 3.93E-02, 3.88E-02,
205
      3.83E-02, 3.78E-02, 3.73E-02, 3.68E-02, 3.63E-02, 3.58E-02, 3.53E-02,
206
      3.48E-02, 3.43E-02, 3.38E-02, 3.33E-02, 3.29E-02, 3.24E-02, 3.19E-02,
207
      3.14E-02, 3.09E-02, 3.04E-02, 3.00E-02, 2.95E-02, 2.90E-02, 2.85E-02,
208
      2.81E-02, 2.76E-02, 2.71E-02, 2.67E-02, 2.62E-02, 2.57E-02, 2.53E-02,
209
      2.48E-02, 2.44E-02, 2.39E-02, 2.35E-02, 2.30E-02, 2.26E-02, 2.21E-02,
210
      2.17E-02, 2.12E-02, 2.08E-02, 2.03E-02, 1.99E-02, 1.94E-02, 1.90E-02,
211
      1.86E-02, 1.81E-02, 1.77E-02, 1.73E-02, 1.69E-02, 1.64E-02, 1.60E-02,
212
      1.56E-02, 1.52E-02, 1.47E-02, 1.43E-02, 1.39E-02, 1.35E-02, 1.31E-02,
213
      1.27E-02, 1.23E-02, 1.19E-02, 1.15E-02, 1.10E-02, 1.06E-02, 1.02E-02,
214
      9.85E-03, 9.45E-03, 9.06E-03, 8.67E-03, 8.28E-03, 7.89E-03, 7.50E-03,
215
      7.12E-03, 6.73E-03, 6.35E-03, 5.97E-03, 5.60E-03, 5.22E-03, 4.85E-03,
216
      4.48E-03, 4.11E-03, 3.74E-03, 3.38E-03, 3.01E-03, 2.65E-03, 2.30E-03,
217
      1.94E-03, 1.59E-03, 1.24E-03, 8.87E-04, 5.40E-04, 1.95E-04};
218
  auto diff_solution =
219
      elements.size() == 50 ? diff_solution_50 : diff_solution_1000;
220
  for (int i = 0; i < elements.size(); i++) {
221
    if (elements[i].value >=
222
        distributions[elements[i].type].get().Reverse(
223
            std::pow(diff_solution[i], 1.0 / (elements.size() - 1)))) {
224
      return elements[i];
225
    }
226
  }
227
  return SecretaryInstance(-1, -1);
228
}
229

230
}  // namespace fair_secretary
231
google-research

Использование cookies
