Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.

learn more… | top users | synonyms

1
vote
0answers
42 views

Improving MSE as fitness function for a genetic algorithm

I am implementing an autoencoder neural network in matlab, the weights of which are being optimised by a genetic algorithm. At the moment I am working on the first layer, trying to get an improved ...
0
votes
1answer
58 views

Longest Path A*, Admissible Heuristics, and Optimalness

Im working on a modified A Star algorithm, that instead of attempting to find the shortest path, it tries to find the longest past, or in my specific case, the highest weighted path. I have some ...
0
votes
2answers
72 views

Ant colony optimization for continuous functions

I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and ...
1
vote
1answer
54 views

Can heuristic methods and machine learning approaches be considered alternate methods to solve NP-Complete problems?

I was watching the videos from Skiena's Computational Biology Lectures, which is also available at youtube. In those videos, the professor made a statement that, most of the problems posed to computer ...
0
votes
1answer
22 views

Quickly pruning edges below average weight for a membership-based weighting

I have points represented as sparse high-dimensional binary vectors, or put another way, I have a list of groups that each point belongs to. For two points, the edge weight between them is $\sum_i ...
4
votes
1answer
67 views

How to perform local search on simple paths?

I have a local search problem. The set of valid solutions are all the simple paths (i.e. without repeated nodes) from a node $S$ to a node $T$ in a directed graph. The question is: given a current ...
0
votes
0answers
52 views

How to populate the tabu list in tabu search?

I am trying to implement Tabu search, as shown here, for my problem. I am now stuck on how to generate the tabu list. In algorithm it mentions that if cost of the candidate is better than the best, ...
8
votes
1answer
106 views

Maximum Stacking Height Problem

Has the following problem been studied before? If yes, what approaches/algorithms were developed to solve it? Problem ("Maximum Stacking Height Problem") Given $n$ polygons, find their ...
0
votes
0answers
29 views
2
votes
0answers
155 views

Trying to understand the Gilmore-Lawler lower bound

For a class project we're developing a software that solves a common optimisation problem. After some research we've found out that our problem is called QAP (Quadratic Asssignment Problem) and the ...
1
vote
0answers
32 views

Mutation and crossover operations in discrete differential evolutionary operations?

I need to use discrete differential evolutionary algorithm for assigning discrete values from set size $L$ to vectors of size $D$ where $L$ could be smaller, equal or larger than $D$. Elements of ...
2
votes
1answer
81 views

Genetic algorithm fitness function [closed]

I'm trying to write some little code (POC for the selection/mutation operators) that uses a genetic algorithm to solve a global maximum for a function. ...
4
votes
2answers
510 views

What is the no free lunch theorem?

I've been reading about the No Free Lunch Theorem, but I can't quite understand what it is about. I've heard this theorem described elsewhere as the claim that "no general purpose universal optimiser ...
-1
votes
1answer
106 views

Where is the recursion, in the minimax-decision algorithm?

The below is from an article titled: Minimax: Recursive Implementation To be a recursive function, you need to call yourself. What part of this pseudo code is calling itself? How does ...
1
vote
1answer
36 views

How do I compute this non terminal positions evaluation, for tic-tac-toe?

Looking at this solution on page 3 but having trouble understanding the evaluation function specifically. For non terminal positions, we use a linear evaluation function defined as Eval ...
3
votes
2answers
194 views

A heuristic for finding a maximum disjoint set

Background I need to find a largest set of non-overlapping axis-parallel squares, out of a given collection of candidate squares. This problem is NP-complete. Many papers suggest approximation ...
2
votes
1answer
152 views

Solving AlienTiles with an A* heuristic

Hello I am trying to solve the AlienTiles problem described at alientiles.com using the A* algorithm but I cannot find any good heuristic function so far. In AlienTiles you have a board with $N ...
2
votes
1answer
123 views

Creating admissible heuristics from functions?

I'm having trouble figuring out how to create admissible heuristics from cost functions. For example, if I was trying to create an admissible heuristic from a cost function that takes in starting ...
3
votes
2answers
1k views

How does the 3-opt algorithm for TSP work?

I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers ...
1
vote
1answer
71 views

Local search: Problem with neighborhood definition

I have question on understanding the following neighborhood relation within a local-search approximation scheme. Let $M$ be a legal matching on any bipartite graph. Let $U_k$ be the neighborhood ...
1
vote
1answer
78 views

Algorithm to use for a TSP variant

What type of algorithm would you suggest me to use for this problem? I want to implement an algorithm that minimize the total distance in a graph (TSP) but for only X nodes. Also, we can go as many ...
1
vote
2answers
101 views

Heuristics & Constrain Satisfaction Problem Differences

I'm currently taking an Algorithms course, and we are covering Backtracking, CSP, and heuristics. However, I'm getting confused on exactly the differences between these terms and their applications. ...
-1
votes
2answers
1k views

How does an admissible heuristic ensure an optimal solution?

When using A* or any other best path finding algorithm we say that the heuristic used should be admissible i.e. it should never overestimate the actual solution path (moves). Can someone tell me how ...
0
votes
0answers
20 views

Fast energy function substitute for Hopfield network?

The energy function in a Hopfield network to determine whether it has converged seems to be the major sink of computational time and makes the Hopfield network run very slowly. Is there a fast ...
0
votes
2answers
273 views

When does the nearest neighbor heuristic fail for the Traveling Salesperson?

Can you provide an example of NN algorithm failure on the Euclidean traveling salesman problem? I was trying to construct a specific example of this for my friends and was failing.
4
votes
2answers
3k views

Trying to improve minimax heuristic function for connect four game in JS

I have made a connect four game in JS and currently have a functioning minimax algorithm. The problem I'm having is that it is very, very easy to beat, even with a large depth. This is leading me to ...
2
votes
1answer
279 views

Classification of job shop scheduling problems

I'm writing a program (using genetic algorithms) that finds sort-of-optimal scheduling plan for a factory. The factory has several types of machines (say, ...
6
votes
1answer
170 views

When to use SAT vs Constraint Satisfaction?

If I have a hard problem, one standard approach is to express it as a SAT instance and try running a SAT solver on it. Another standard approach is to express it as a constraint satisfaction problem, ...
4
votes
1answer
125 views

How approximate are “approximate” nearest neighbor (ANN) search algorithms?

Starting to use nanoflann to do some point cloud nearest neighbor searching and it got me thinking about just how "approximate" ANN methods are. If I have a (more or less) randomly distributed point ...
9
votes
2answers
2k views

Initial temperature in simulated annealing algorithm

I've done some testing of different initial temperatures in my simulating annealing algorithm and noticed the starting temperature has an affect on the performance of the algorithm. Is there any way ...
2
votes
0answers
171 views

Time complexity 2-opt method

I'm doing a practice test for a course on routing problems. There's a question asking to infere the time complexity of the 2-opt method. I can see that the complexity per iteration is in $O(n^2)$ ...
4
votes
3answers
1k views

Difference between heuristic and approximation algorithm?

i have a problem regarding the following situation. I have two arrays of numbers like this: ...
4
votes
1answer
673 views

A Good Resource for Christofides' Heuristic

Is there an explanation Christofides's Heuristic for solving TSP which does not simply state the algorithm and go ahead to prove the bound? To be specific: (Disclaimer : I am an engineer who knows ...
2
votes
0answers
100 views

Experimental Survey on Different Heuristics for Knapsack Problem

I am looking for a good survey/study of experimental results of heuristics for Knapsack problem (or implemented libraries in java/c++). Any help is appreciated!
3
votes
1answer
165 views

Quick union and heuristic by size

Studying Quick-Find and Quick-Union heuristic I've found clear that: with quick find trees and a union based on the size of the trees we can make a union in $T_{am}(n)=O(\log(n))$ with quick find ...
2
votes
0answers
89 views

Heuristics for tree decomposition into k shortest paths

What kind of heuristics are useful in a tree decomposition of a graph to find the k shortest paths from a given source to a vertex? Moreover, the local shortest paths at each node in a tree are ...
3
votes
1answer
315 views

'Texas Hold Em Poker' Agent Heuristics to help decide whether to fold or bet?

I am designing a poker agent with different heuristics to decide whether to raise, fold or pass (in Texas holdem poker). I am planning to have 4 heuristics with the agent biased to one of them. The ...
1
vote
1answer
321 views

Why is Uniform cost search called “uniform” cost search?

By this possibly good attempt to explain this, the "uniformity" in the Uniform cost search is actually the uniformity of the heuristic function. Is this explanation correct ? If yes, then don't all ...
1
vote
1answer
1k views

Heuristic for Finding Multiple Goals in Graph - e.g. using Kruskals Algorithm

I'm a none-computer-science-student and get some knowledge on AI by taking the CS188.1x Course (Artificial Intelligence) on www.edx.org . Currently, I am working on the "Search in Pacman" Project; ...
0
votes
3answers
36 views

Heuristically determine a value f such that a probability d/f approaches 1/2

We have a set X of N elements. We want to get a new set X' having a size M < N. ...
3
votes
1answer
335 views

Heuristics for an Artificial Intelligence problem

Problem : Given a (one dimensional) row containing $2N$ tiles arranged in $2N + 1$ spaces. There are $N$ black tiles (B), $N$ white tiles (W), and a single empty space. The tiles are initially in ...
7
votes
1answer
164 views

Problem similar to set packing

Call a family of sets $\mathcal{F} = \{S_1, \dotsc, S_k\}$ "diverse" if each set $S_i \in \mathcal{F}$ has at least one unique element. What are possible approaches for finding the largest diverse ...
1
vote
1answer
149 views

Neighbourhood in local search metaheuristic

I cannot seem to find an answer to this question with Google, so I am going to ask here: is it required for a good neighbourhood function that it in principle (i. e. by recursively considering all ...
3
votes
1answer
656 views

Forward checking vs arc consistency on 3-SAT

If I were to let the variables be the propositions and, constraint be all clauses being satisfied, which technique would be more effective in solving 3-SAT? Forward checking or arc consistency? From ...
2
votes
1answer
2k views

Nilsson's sequence score for 8-puzzle problem in A* algorithm

I am learning the A* search algorithm on an 8-puzzle problem. I don't have questions about A*, but I have some for the heuristic score - Nilsson's sequence score. Justin Heyes-Jones web pages - A* ...
3
votes
1answer
462 views

Is using a more informed heuristic guaranteed to expand fewer nodes of the search space?

I'm reading through the RMIT course notes on state space search. Consider a state space $S$, a set of nodes in which we look for an element having a certain property. A heuristic function ...
7
votes
1answer
420 views

How to implement the details of shotgun hill climbing to make it effective?

I am currently working on a solution to a problem for which (after a bit of research) the use of a hill climbing, and more specificly a shotgun (or random-restart) hill climbing algorithmic idea seems ...
19
votes
1answer
306 views

Measuring the difficulty of SAT instances

Given an instance of SAT, I would like to be able to estimate how difficult it will be to solve the instance. One way is to run existing solvers, but that kind of defeats the purpose of estimating ...