Questions tagged [heuristics]

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

242 questions
Filter by
Sorted by
Tagged with
377 views

Applicability of approximation algorithms vs meta-heuristics in practice

How useful are approximation algorithms over say, metaheuristics or even problem-specific heuristics in practice? Let's say a certain NP-hard minimization problem (take the travelling salesman problem ...
• 555
9 views

Managing hashing overlaps (building a heuristic for the edge of a 3x3x3)

I'm trying to build a 3x3x3 solver for a school project. I got inspired by Ben Botto's solver, which you can find here. Such as Ben does with his solver, I'd like to implement Korf's heuristic ...
14 views

ROBDDs heuristics for optimal variable ordering

I have this slide about how a BDD can vary in size depending on the order of the boolean variables fixed for it, and how it is NP-Complete to find the optimal ordering. It says there are heuristics ...
• 90
12 views

A stagnation check for heuristics, especially simulated annealing?

I'm studying heuristics for a course in my Master's. Our professor has told us that in order to point to a higher grade in the exam, we should check if our algorithm hits a stagnation points and that ...
1 vote
68 views

How far out can one determine a program is halting?

Suppose we have a finite set of programs, say, something like every Turing machine with 2 states and 7 symbols. After running all of them for a very long time, we've narrowed it down to a small subset ...
• 306
28 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 ...
41 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 vote
60 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
27 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 ...
1 vote
61 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
61 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 ...
1 vote
144 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 ...
1 vote
64 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
64 views

• 217
113 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 ...
• 217
1 vote
46 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
189 views

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
112 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.
937 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 ...
194 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’...
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,992
1 vote
55 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)=\...
56 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
86 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
208 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
116 views

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
232 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
37 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. ...
194 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 ...
• 6,152
1 vote
89 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 ...
1 vote
61 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
381 views

• 128
42 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
61 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
107 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
117 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
244 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 ...
1 vote
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
79 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 ...
• 133
1 vote