New answers tagged optimization
0
No. If the game is the prisoner's dilemma, depending on the random choices, this could converge to "everyone defects", which is not (globally) optimal; the (globally) optimal solution is "everyone cooperates". Also, it is possible that it may fail to converge at all and loop forever. Even if it does converge, it may only converge to a ...
1
Yes, it's possible. Let $S$ be the original linear problem, i.e., a conjunction of inequalities. You can form two LPs. One LP has the form $S \land x=0$, which can be solved with a LP solver. The other LP has the form $S \land 1 \le x \le 2$. If either one has a feasible solution, your problem has a feasible solution. This procedure takes polynomial ...
0
After seeing @Tassle's answer, I did a bit Google search and found that the largest empty rectangle is a well researched subject.
In the following, I try to draft an algorithm on my own.
Suppose the polygon has $2n$ sides. There has to be $n$ horizontal and $n$ vertical sides. For simplicity sake, we assume no two horizontal sides of the rectilinear polygon ...
2
Daniels, Milenkovic and Roth [1] show how this can be done in $O(n\log^2 n)$ time ($n$ being the number of vertices) even for general polygons (possibly with holes). They also mention that the algorithm from Aggarwal and Suri [2] for largest empty rectangle can be adapted to your problem in the rectilinear case, but I haven't thought about how one would do ...
2
You can determine simply if there is no solution. Case $K=2$ with the players on different and non-adjacent cities (thanks orlp to point it).
Let's first assume a simpler problem where players may move several time in a row. Then you know the arrival point is necessarily one of the initial position of a player. Indeed, a city just before one with no player ...
0
Quite simple if time complexity O(K*N) is acceptable:
For each of the N towns, you calculate how long it takes for everyone to reach that town. First, you add everyone's distance to that town. That's one minimum requirement. Second, since nobody can do two turns in a row, find the person furthest away. If the person is X steps away, then they can't reach ...
0
Based on the answer by D.W. I was able to implement an alternative algorithm. This effectively iterates over all permutations of $D$-length factorizations of $c$. Instead of utilizing the prime factorization to explicitly enumerate all the factorizations, I increment one element of $b$ to the next multiple of a divisor of $c$, then divide out that divisor ...
2
I think if you choose all $d$'s to be exactly $1$ and choose $L$ to be exactly $n$ (number of cities), any solution must visit all cities, so the reduction will work out.
0
You first need to transform this into normal form. Depending on how you learned it, you need to transform all constraints to the form $a\ge b$, or $a\le b$, where in $a$ you have variables and in $b$ only constants.
Transform $=$ into $\le$ and $\ge$ and from there you can easily transform this into normal form
0
This sounds like a reinforcement learning problem.
Construct the following MDP:
The states are the different values of $x$
The actions are $u_1,\dots,u_L$
The transition is given by $f$
The reward is given by $g$ of the current state.
Define it as a finite horizon problem.
Then, if the set of the values of $x$ is finite, use any RL technique to solve the ...
0
Using log-barrier constraints (suggestion from the comments) along with a Nelder-Mead simplex approach got fantastic results.
As clarification to some of the other comments, the points were in Euclidean space comprised of real numbers.
0
Well, I finally find out I'm just writing bad code that results in too many computations.
The condition in slow() should be P[i*i+a*i+b] != 1 instead of P[..] == 0 because there are cases when the index is smaller than 0.
Top 50 recent answers are included
