Timeline for Transfinite algorithms
Current License: CC BY-SA 4.0
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 9, 2020 at 13:28 | comment | added | Tony Huynh | @StellaBiderman What I proposed does get rid of all loops (including transfinite ones), but it may not be possible to assign this parameter for hill climber. For hill climber, what you propose makes sense to me. | |
| Apr 9, 2020 at 7:10 | comment | added | Patrick Lutz | @Stella Yeah I just meant the problem with the specific example you gave, not the only problem in general. | |
| Apr 9, 2020 at 3:42 | comment | added | Stella Biderman | @Tony I’m not sure if that is going to do exactly what you think it does, but it seems to be on the right track. My intuition is that the “right way” to handle this problem would assign a hill climber a value of $n\omega$, where $n$ is the largest number of local optima that it can get stuck in. Do you agree? | |
| Apr 9, 2020 at 3:37 | history | edited | Stella Biderman | CC BY-SA 4.0 |
deleted 7 characters in body
|
| Apr 9, 2020 at 3:37 | comment | added | Stella Biderman | @Patrick That handles the specific example of a hill climber, but not the extension to transfinite loops. | |
| Apr 9, 2020 at 3:19 | comment | added | Tony Huynh | Thanks for your answer! We can avoid ''transfinite loops'' by adding the property (4) There is a strictly increasing parameter associated to each step of the algorithm, and this parameter is bounded. For Ford-Fulkerson, this parameter is the value of the current flow. | |
| Apr 9, 2020 at 3:04 | comment | added | Patrick Lutz | The problem here seems to be that the states the algorithm could converge to are also fixed points of the algorithm. Presumably running the algorithm for transfinitely many steps is only interesting when the algorithm does not always get stuck at a fixed point on step $\omega$. | |
| Apr 8, 2020 at 19:52 | history | answered | Stella Biderman | CC BY-SA 4.0 |