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

learn more… | top users | synonyms

3
votes
1answer
12 views

Informed search with a lower-bound heuristic?

I am well aware of informed graph / tree search strategies for optimal solutions when one has an admissible heuristic - i.e. one that never overestimates the minimum cost from a node to any goal ...
1
vote
1answer
26 views

Is there a name for algorithms which detect nearly-similar structures?

I'm interested in how you might detect similarities in tree structures. For example, in these three JSON documents; ...
1
vote
1answer
35 views

Difference between heuristic-based searching and optimal path searching

I'm currently studying for an AI computer-science course. One thing is difficult for me to grasp and somewhat vaguely explained in my course-material: I understand that with search-methods like e.g. ...
1
vote
1answer
62 views

Algorithm A vs Algorithm A*: What's the difference?

I can find quite a bit of literature on A* but very little on A. What is the difference between the two search algorithms?
0
votes
0answers
24 views

Optimal shortest path: When heuristic overestimates

Is it possible (or does there exists a special case) where the optimal shortest path is guaranteed even where the heuristic function always overestimates? Intentions for such a query : Trying to ...
3
votes
1answer
33 views

Search problem when the effects of actions are not deterministic

The standard search problem studied in AI contains: An initial state $A$; A final (goal) state $Z$; A set of actions that can change the state; each action takes as input a certain state and returns ...
1
vote
0answers
29 views

Does the vehicle routing problem and variations have approximation ratios or a PTAS?

This is a somewhat big question since there are many variations on the VRP. The most studied seems to be the capacitated version, the CVRP, but variations considering time windows, backhaul/linehaul, ...
0
votes
1answer
35 views

Heuristic function

Is there any way to prove that an admissible heuristic may not be consistent? Most proof I came across are through examples .Is there a generalized proof?
3
votes
1answer
196 views

the meaning of heuristics in artificial intelligence

I would like to know what 'heuristics' actually means in artificial intelligence. For example, I am reading a paper by Engelbrecht on the convergence analysis of the particles of the algorithm. The ...
3
votes
0answers
45 views

Testing whether an analytic function vanishes identically

I have an application that basically reduces to testing whether a given function vanishes identically. The function is given symbolically, using unary and binary operators on complex numbers. For ...
1
vote
0answers
38 views

TSP heuristics for limited distance information [closed]

this is my first question on ComputerScience beta. :) I've posted a similiar question on Mathoverflow and a friendly user advised me to post my question on this site. Problem: I'm looking for ...
3
votes
1answer
66 views

What makes a metaheuristic meta?

According to Wikipedia: ...metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a lower-level procedure or heuristic (partial search algorithm) that may ...
2
votes
1answer
53 views

Heuristic for weighted maximum independent set in graph with ~$2 \times 10^5$ nodes and $|E| \propto |V|$

I want to find a near-optimal solution for a maximum weight independent set. i.e given a graph $G = (V,E)$ I want to find a set $S = \{v_1,v_2,\dots,v_n\}$ of nodes in $V$ such that the sum of their ...
2
votes
2answers
851 views

Why is 'Manhattan distance' a better heuristic for 15 puzzle than 'number of tiles misplaced'?

Consider two heuristics $h_1$ and $h_2$ defined for the 15 puzzle problem as: $h_1(n)$ = number of misplaced tiles $h_2(n)$ = total Manhatten distance Could anyone tell why $h_2$ is a better ...
3
votes
1answer
250 views

How can I fill bookcases with shelves of books using the least number of bookcases?

Sorry for layman's term question, my background in computer science is weak. What I have is a list of shelves with books of varying height. Each shelf stores a value that describes how many shelves ...
0
votes
1answer
310 views

Heuristic for sokoban puzzle problem

I am trying to write IDA* for Sokoban puzzle problem (http://en.wikipedia.org/wiki/Sokoban) but It seems that my heuristic is not so good for making the algorithm fast. My heuristic is to consider ...
0
votes
1answer
204 views

Given two heuristic values how do I tell which one is admissible?

I am given 2 list of admissible values for a graph, and the graph with the real cost to each of the nodes. Am I correct in thinking the way to see which one is admissible is add up all the values of ...
0
votes
2answers
74 views

Why is it the lower the h(n) cost the more nodes need to be expanded in A*?

Why is it the lower the h(n) cost the more nodes need to be expanded in A*? As found here - http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html If h(n) is always lower than (or ...
3
votes
1answer
105 views

Global relabeling heuristic: Push-relabel maxflow

I have a correct, working implementation of the preflow-push-relabel maxflow algorithm [2]. I am trying to implement the global relabeling update heuristic [3], but have run into some issues. I have ...
2
votes
2answers
120 views

Heuristic for Tournament Scheduling

I am holding a bi-yearly tournament in my city, for which I want to write a program that gives me (nearly-)optimal pairings, and waiting time. The setup is as follows: ...
3
votes
1answer
89 views

Unsplittable flow in capacitated networks

I have an undirected network with capacitated links/edges. Between some nodes unsplittable traffic has to be routed. All demands and capacities are known, but it is uncertain if all flows can be ...
0
votes
1answer
56 views

Why do heuristic functions only approximate the real value of the cost?

As stated in the title I'm wondering why do heuristic functions only approximate the real value of the cost? I understand it can never overestimate, but can it ensure the cost is accurate?
3
votes
1answer
45 views

What algorithm is suitable for very small scale, time dependent optimization?

I have a time-dependent (dynamic) optimization problem: $$ f_t : [0;1]^2 \mapsto \mathbb{R}^+; t \in [1, \dots, n] $$ $f_t$ is to be maximized. That is for each $t$ I would like to find a relatively ...
5
votes
2answers
2k views

Why is the A* search heuristic optimal even if it underestimates costs?

A* search finds optimal solution to problems as long as the heuristic is admissible which means it never overestimates the cost of the path to the from any given node (and consistent but let us focus ...
1
vote
1answer
43 views

Is there a way to predict rendering times? [closed]

In purpose of load balancing I need to approximatively predict rendering time my graphics software (in the specific case it's Autodesk Maya) needs to render a task given an input file (.ma/.mb) and ...
1
vote
0answers
200 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
311 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 ...
2
votes
2answers
469 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
425 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
28 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
104 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 ...
8
votes
1answer
138 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 ...
1
vote
0answers
38 views
2
votes
0answers
212 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
62 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
224 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. ...
5
votes
2answers
2k 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
555 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
72 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
497 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
175 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
531 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
4k 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
111 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
135 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
333 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. ...
3
votes
2answers
5k 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
2answers
686 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.
5
votes
2answers
6k 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 ...
5
votes
1answer
745 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, ...