solution scoring

solution scoring

Imagen de john_e_lilley
I and (apparently) one other contestant are discovering that it is very easy for a problem to flip between solvable in a short time to unsolvable in hours, based on minor adjustments to algorithms. See some of the samples I've uploaded. Because of that it has been hard to find cases suitable for multi-thread optimization -- they seem to either solve very quickly (in which case multi-core doesn't matter), or they solve so slowly that nobody wants to wait for the result, even with multi-core. Due to this effect, what do the judges anticipate doing when a solver does not come back for a very long time?
publicaciones de 6 / 0 nuevos
Último envío
Para obtener más información sobre las optimizaciones del compilador, consulte el aviso sobre la optimización.
Imagen de 邓辉

Same feeling. Find all the solutions. More reasonable

写字楼里写字间,写字间里程序员 程序人员写程序,又拿程序换酒钱 酒醒只在网上坐,酒醉还来网下眠 酒醉酒醒日复日,网上网下年复年
Imagen de mdma

Taking this more generally, I feel that the NP complete problems are a poor choice for these challenges if the entire search tree is not searched (i.e. finding a single solution rather than a count of all solutions.) Then it's just about how lucky you are in choosing a start in the search, or smart pruning of the search space. Consequently, multi-threading does little to improve solution times compared to choosing a smart search strategy. However, if the challenge is to count all possible solutions, then "luck" doesn't come into it, and multi-threading and be used more to gain a performance advantage.

Imagen de john_e_lilley

In the Masyu puzzle case, the NP-completeness of the problem is a minor factor. Even the "np complete" sample that I uploaded does not have that many configurations that absolutely must be tested (I think that the equivalent NP-complete Binary satisfiability problem only has a few terms). Pruning the search space and having good heuristics is what really matters when finding a solution. It is also easy to construct samples that have an exponential number of solutions, so outputting all of them is strictly infeasible even in cases where finding a solution is easy. However, I do find that the scalability ascpect of the problem is lacking for the reasons you state, and finding all solutions would actually test that (except that for some problems you can prove by constraint logic that there is only one solution, and no searching is needed).

Imagen de fmstephe

It is definitely true that a really well built sequential solver could beat the pants off my parallel solver, no matter how good the worksharing is. It seems to me that we just have to not worry about the competition aspect. You work-sharing multi-threading cleverness probably won't win you the day in this comp, but I think that just thinking about writing NP-complete for multi-core problems seems really important. Even better, it's so much fun :) TLDR: Maybe it's not a great challenge for a threading comp - but it's still pretty awesome.

Imagen de john_e_lilley

I agree, its been a really fun problem to work on. My solver has undergone multiple iterations as I've explored different problems and found ways for my solver to get confused and chase its tail forever.

Inicie sesión para dejar un comentario.