Questions tagged [heuristics]
Questions about algorithmic strategies that quickly solve a problem well most of the time, but give no guarantees.
240
questions
0
votes
0
answers
22
views
Manhattan distance always less node expansion than misplaced tiles heuristic?
I created a 8-puzzle search solver using BFS, A* with manhattan distance, and A* with misplaced tiles.
I generated data that said that for a particular random board, misplaced tiles did less node ...
0
votes
0
answers
26
views
A* (A-star) search algorithm including closest distance from a node to an obstacle in heuristic and step cost
I want to include the distance of a node to the closest obstacle in the cost function, so that the path length is not only minimal, but also not near obstacles.
We know that:
Dijkstra's algorithm uses ...
- 1
0
votes
0
answers
14
views
How to choose cells from a table to maximize their sum, with selection constraints?
I have a table of fixed positive integer values of anything up to several dozen. There are six columns and several hundred rows. I must choose exactly two values from each column, and zero or one ...
- 101
1
vote
1
answer
49
views
Greedy algorithms criterion/ intution
Can anyone please explain (not just through examples) that why does the greedy approach does not work in this case? Or more generally, is there any particular condition under which only the greedy ...
- 113
0
votes
0
answers
25
views
Designing Algorithm for MST problem for a optical fiber network bounded by costs
So I need to design an algorithm for the following problem:
Suppose we need to build an optical fibre network for 20 cities. We are given a distance matrix of the cities which tells us which cities ...
- 101
1
vote
1
answer
36
views
What is a good heuristic for multi-point A* on a directed graph?
I am conducting a stateful search of a large graph in an effort to find some solutions of minimal cost. With an admissible heuristic for estimated time to completion from a given state (as in A*), I ...
- 11
0
votes
1
answer
48
views
Which combinatorial problem is reminiscent to mine?
I am trying to understand which combinatorial problem best fits the one I have. I am mostly asking from the perspective of being pointed towards relevant literature. I will explain the problem with an ...
- 321
1
vote
0
answers
81
views
Simplified Memory Bounded A*
I have been studying the SMA* algorithm and I am having trouble understanding the backup operation. Specifically, I don't understand why the f value of a child node should be the maximum of its own f ...
- 11
0
votes
0
answers
11
views
Simple example where informed heuristic has larger state space?
So far, I understand that not all informed heuristics can guarantee small search spaces than uninformed, but I am not sure what's a simple example for this type of scenario?
- 1
1
vote
1
answer
47
views
What is a heuristic in human computer interaction?
I have found multiple definitions of what a heuristic is, and I have found multiple computer science-related definitions.
In my university course, the lectures cite the Nielson Norman Group defining a ...
- 13
2
votes
0
answers
46
views
Modified DPLL for 3-SAT by reducing to 2-SAT
In Boolean Satisfiability of CNF formulae we have $k$-SAT where each clause has at most $k$ literals. It is well known that $k$-SAT is polynomial time reducible to $3$-SAT. It is also well known that $...
- 135
0
votes
1
answer
36
views
Is there an optimisation algorithm that does not require a good initial solution?
I was reading this question on CS stack exchange called How important is initial state for local search optimisation?
I would like to extend it with the following example:
I have been reading about ...
- 3
0
votes
0
answers
56
views
Is a metaheuristics a Markov Decision Process?
Is a metaheuristics optimization algorithm, such as simulated annealing, a Markov Decision Process?
For example, considering the combinatorial optimization problem of finding the minimum of $f : \{0,1\...
- 459
1
vote
1
answer
150
views
Kolmogorov complexity and data compression revisited
The question of the relationship between Kolmogorov complexity and data compression is rather difficult.
However, at the heuristic level, the complexity of an object and the rate of its compression by ...
- 111
1
vote
1
answer
104
views
If the heuristic $h(n)$ is the estimated cost from node $n$ to the goal, then why would we want a heuristic that has a greater cost?
I am currently studying the concept of heuristics in search algorithms. I recently asked this question about the so-called "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\...
- 203
0
votes
0
answers
75
views
How is this "pathmax modification," $f(n^\prime) = \max(g(n^\prime) + h(n^\prime), f(n))$, useful?
I am studying the concept of heuristics in search algorithms, and the $A^*$ search algorithm in particular. I am told the following:
Greedy search minimises estimated path-cost to goal.
But it's ...
- 203
1
vote
1
answer
42
views
Algorithm/heuristic for large tournament matchup pairings
I'm scheduling a large invitational tournament with the following conditions
The event takes place over 8 weeks
Teams arrive and depart on different dates/times, so each day of the event will have a ...
- 113
1
vote
1
answer
122
views
search with inadmissible heuristics
I was told that search algorithm such as IDA* or Beam Search with any inadmissible heuristic is not guaranteed to find a solution. Can someone explain why that is the case? I was thinking sure the ...
- 163
-1
votes
1
answer
57
views
Is there an algorithm able to finding the best cost in a graph that is weighted on both vertices and edges?
I have a problem that consists of finding a good solution for a graph that has vertex weights (and this cost is the highest priority), but also has edge costs.
- 1
2
votes
1
answer
580
views
Difference between cost and the heuristic function in A* search
Looking at the image above, thinking in terms of A* search. I don't fully understand the heuristic function. The cost makes sense, so thinking in terms of a traditional map or navigation scenario. I'd ...
- 123
0
votes
1
answer
191
views
How to analyze the amortized running time of indexed linked list operations using potential method?
I have implemented an indexed linked list that runs (under mild assumptions) all single-element operations in $\mathcal{O}(\sqrt{n})$ time. The description is here and Java implementation is here.
It’...
- 52
0
votes
0
answers
36
views
Special case of single vehicle routing
I have a metric space $(V,d)$ described by a tree $T$. And I have $k$ pair of vertices $\{s_i,t_i\}$ ($i \in [k]$) s.t. each of the vertices $s_i$ and $t_i$ are leaves of $T$. There is a car at one ...
- 2,932
1
vote
1
answer
51
views
Partition data into two sets of the same size such that the sum of the average distances is maximized
Say I have a set of strings $S=\{s_1, s_2, ..., s_N\}$, and I want to partition $S$ into two sets $S_1$ and $S_2$ equally, i.e., $||S_1|-|S_2||\leq1$.
Define the difference of a set as
$$Diff(S_k)=\...
- 13
0
votes
0
answers
52
views
How to build a data-structure for a moving points
Problem:- I have moving points in a 2d space with a fixed obstacle(A polygon) and a fixed destination. I want to find at what time Source(which is moving) can get a path to destination and what is ...
- 157
2
votes
1
answer
79
views
Why the choice of the adjacent vertex with the least degree is a good heuristic for the hamiltonian path problem?
Even if the hamiltonian path problem is NP-hard there exist heuristics which return a correct path for many instances in linear time. In particular one of the main rules is always choosing the ...
- 167
4
votes
1
answer
180
views
Warnsdorff's rule: more errors with odd sized boards
I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
- 167
1
vote
1
answer
95
views
How to think about heuristics
I have a game about drone delivery company.
The game consists of a rectangular map, which contains tiles that cannot be passed. I can control a certain amount of drones, each one of them starts at a ...
- 131
2
votes
0
answers
197
views
Can A* with an inadmissible heuristic still be optimal?
It is clear to me that if some heuristic $h(x)$ is admissible, then $A^*$ is guaranteed to find a least-cost path. But is it also possible that $A^*$ is optimal if $h(x)$ is not admissible? In other ...
- 21
1
vote
1
answer
33
views
Heuristics for a variant of the traveling salesman problem
I am looking at a variant of TSP in which rather than visiting every node, there is a given collection of (possibly overlapping) subset, and the salesman must pass through one node from each subset.
...
- 339
8
votes
1
answer
163
views
What is the approximation ratio of this bin-backing algorithm?
Consider the following algorithm for bin packing:
Initially, sort the items by their size.
Put the largest item in a new bin.
Fill the bin with small items in ascending order of size, up to the ...
- 5,730
1
vote
0
answers
84
views
minimising Longest-Path in DAG
Assume we have weighted DAG (directed-acycle-graph), source s and target t.
Define the number of edges as $E$.
Given $0<\alpha<1$:
Choose $\alpha*E$ edges to cut their weight by half so that the ...
- 11
1
vote
1
answer
53
views
CVRP and removing edges from a graph
I am solving a CVRP (Constrained Vehicle Routing Problem) on a connected graph, that is not necessarily complete. Edge weights represent Euclidean distances.
I know that, in general, the complexity of ...
1
vote
1
answer
281
views
How do I solve a search problem on an infinite graph?
I have a search problem that requires me to find a path from $v_s$ to $v_g$ in the graph $G = (V, E)$ where $v_s, v_g \in V$ are the start and goal vertices in a set of vertices and $E \subset V \...
- 165
1
vote
1
answer
70
views
Grasshopper Optimization Algorithm
I am currently reading a paper on a meta-heuristic called 'Grasshopper Optimization Algorithm'.
The main idea of the algorithm is to utilize the social behavior of grasshoppers in a swarm to solve ...
- 111
-1
votes
1
answer
25
views
A very simple question about Admissible Heurisitcs
Given admissible heuristics f(s), g(s), h(s).
It is true that max(f(s), g(s), h(s)) is still admissible.. but is it still admissible if its max(f(s), g(s) + h(s)). I believe it is not admissible but I ...
- 11
6
votes
0
answers
95
views
Scheduling tasks on a graph with assistance
This is a follow-up to a question that I recently posted here: Completing tasks on a graph. In that question, I posted the following:
Consider a graph $G = (V, E)$, where $V = \{0, 1, 2, \ldots, n\}$. ...
user127619
2
votes
1
answer
68
views
Optimization problem over bidirectional connected graph
A company has several automatic vertical warehouses (called elevators). Each elevator have several trays and each tray has several slots. A slot contains a given quantity of a given article. Elevators,...
- 145
4
votes
1
answer
139
views
One-dimensional packing problem: Optimal decomposition of music structure
I am currently working on my Master thesis on the visualization of music structure and I'm looking to find an optimal description of repetitions found in a piece of music.
Problem Description
Given a ...
2
votes
1
answer
67
views
Graph partition that maximize the number of triangles within its parts
Given a graph $G = (V,E)$, how to partition $V$ into $k$ parts $P_1, P_2, \ldots P_k$ of at most $M$ vertices, such that the number of triangles (3-cliques) contained in the parts is maximal?
This ...
- 128
1
vote
1
answer
53
views
How can I make the variance of a multiple sum of set of fixed number of variables minimum?
Here is the problem:
There are $MN$ people, where there are $M>1$ seeds and $N>0$ people are in each seed.
We have to make $N$ teams of $M$ people where everyone in the team have different seeds....
- 128
2
votes
0
answers
39
views
Messy Representation Encoding example
I am currently working through Metaheuristics by El-Ghazali Talbi where he discusses encodings of algorithms.
"Messy representations: In linear representations of fixed length, the semantics
of ...
- 21
1
vote
1
answer
54
views
Efficient calculation or estimation of “minimized combined Manhattan distance” between two sets of points
I’m attempting to write a heuristic for an implementation of A* search. The problem involves rearranging cells in a 3D grid until they match a particular solved state. I’m looking for options for a ...
- 151
2
votes
1
answer
93
views
How important is initial state for local search optimisation?
I have been enjoying Pascal van Hentenryck's Discrete Optimisation course and we're in Week 4 on the wonders of Local Search algorithms for combinatorial optimisation.
I'm wondering how important the ...
- 153
0
votes
0
answers
111
views
Minimizing the length a Boolean Algebra Expression in disjunctive normal form
I'm looking to minimize the length of an expression in boolean algebra that has been given in disjunctive normal form and is free from redundancy. To remove redundancy from the original expression I ...
1
vote
0
answers
223
views
Which non convex optimization algorithms guarantee a global optima?
Most non-convex optimization algorithms I have come across so far rely basically on random restart to find a better solution. e.g. Genetic Algorithm, Simulated Annealing, Metropolis Hastings Monte ...
- 289
1
vote
0
answers
19
views
Is there an heuristic for finding out the smallest height you can get when packing items in a tube?
It's sort of similar to bin packing, but instead of the minimum amount of bins,I was interested in just one infinite bin and finding out what's the smallest height you could get when you start packing ...
- 141
1
vote
2
answers
71
views
Algorithm for optimal rule-based arrangements?
I am trying to plant a row in a garden. Certain plants are good for some plants and bad for others, and I am trying to find the best order of plants: most adjacent friends and no adjacent foes, as ...
- 123
1
vote
1
answer
88
views
What solution to apply for finding the optimal parameters?
For a study, I have a system (black-box) that requires an input in the form of an array with 4 values (input_array) and depending on their values it produces an ...
- 113
0
votes
0
answers
90
views
Search algorithm for vehicles moving through a square grid
I started to learn AI and I'm trying to solve the following problem like a search problem and I'm wondering which search algorithm would be the best in this case. Please give me at least some tips, I ...
- 1
1
vote
0
answers
61
views
What is an example of meta-heuristic algorithm for solving Mario NP-hard problem?
Applying entertainment with computations is my main motivation in studying Computer Science, however, I'm still a neophyte to this field. While searching across the net, I came across this paper ...
