Finding a maximal matching is pretty easy to do in O(N^2) – for instance, we traverse the board in row order, and for each row, in column order. However, it turns out that the size of a simpler, but maximal, greedy matching works better. Anyway, my initial version of the scoring function was the size of the maximum matching (where you have an edge between two adjacent cells if they both contain pegs). My scoring function was pretty good (though not good enough to get me the first place at the contest ) - it only got me 0.359456 points. Probably developing this ideas further and seeking for better combinations could allow to reach desirable 0.36 which would bring the second place at the contest.Īs usual, the scoring function is the most important aspect of strategies like beam search (I also used something similar). Combining this with my previous solution allows to reach 0.346 (see here). Just using this for both residues mod 2 without any combination with other score functions allows me to score 0.334 as before (see here, but be careful there is 20Kb of code :)). The best and the simplest scoring function is to maximize the number of pegs in the cells with fixed (x+y) mod 2. It was quite challenging for some of these functions to implement update after the move in O(1).Īnother idea I use is to divide the grid into several sub-grids, run beam-search on each one (which allows to use larger width) and then run on their union.Īfter the contest I looked through solution and realized how I fool I was. With different combinations of this functions I can reach only 0.334 points. but has some cost (negative or positive) for full row or column of pegs Minimize the number of existing pairs of consecutive pegs (was better).Minimize the number of available moves (for me performs very pure).I also have used a beam search but did not come with a good scoring function. For every empty cell, reduce the score by 0.7.For every move that could be made, reduce the score by 1.Initialize the score with a large value.The scoring function used by the tester’s solution is as follows Hence we tradeoff Optimality (since we don’t go through the entire search tree) for Completeness (we will always have some valid solution).īeam Search will always end up in a state in which no moves can be made, while pruning to find a state that hopefully has more pegs remaining.Beam Search always terminates at Final states (those from which you cannot go ahead).Only the top B nodes ordered by some scoring funciton (that scores each state). But, not all the nodes for the next level are stored.We iterate through the nodes at each level and find the nodes for the next level.Beam Search builds the search tree similar to Breadth First search.This editorial is based on Beam Search, which was used by Hiroto while testing this problem. Search techniques try to explore the solution tree and percolate towards the optimal solution. Metaheuristics pick a candidate solution and try to optimize them. This problem can be solved using some metaheuristic or search technique. The desirability of the state is defined by the number of pegs that are left when there is no move possible. We have to search the state space and end up at the most desirable state. There are finitely many states that are reachable from the initial state. Maximize the number of pegs that are left at the end. Given a board with some pegs, where you are allowed to make moves that are valid in Peg Solitaire, This problem presents an alternative objective to Peg Solitaire. You may or may not be aware of the game of Peg Solitaire. Combinatorial Optimization, Search PROBLEM
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |