Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.
6
votes
2answers
67 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
31 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)$ ...
3
votes
3answers
177 views
Difference between heuristic and approximation algorithm?
i have a problem regarding the following situation.
I have two arrays of numbers like this:
...
3
votes
1answer
86 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
40 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
97 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
58 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
141 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
183 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
200 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
24 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
225 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 ...
6
votes
1answer
126 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
114 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 ...
1
vote
1answer
228 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
1k 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
153 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 ...
6
votes
1answer
236 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 ...
14
votes
1answer
214 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 ...
