The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
2answers
59 views

How to find the Branch factor of 8 Puzzle

I would like to know how to find the average branching factor for 8 puzzle.While referring Artificial Intelligence by George F Luger it says that: Suppose,for example we wish to establish the ...
1
vote
1answer
47 views

negative effective branching factor it's possible?

i've implemented A* algorithm in python,after that i calculate with this python function the effective branching factor $ B^* $ $ T+1=1+B^*+(B^*)^2+⋯+(B^*)^L$ where $T$ is the number of expanded ...
1
vote
1answer
31 views

How does the Vertex Cover algorithm by Chen et al find its tuples?

I'm still fighting with the aforementioned paper "Improved upper bounds for vertex cover" by Chen, Kanj, Xia (PDF kindly provided by Yuval Filmus). My current problem is that it's specified that the ...
2
votes
1answer
164 views

Traveling Salesman: how to use a lower bound?

Let me preface this question by giving some helpful background material. I'm trying to solve the traveling salesman problem using branch and bound. Concretely, for a partial solution, I'm using the ...
2
votes
0answers
175 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 ...
4
votes
3answers
519 views

What is the difference between bounding and pruning in branch-and-bound algorithms?

Could anybody please explain what the difference between "bounding" and "pruning" in branch and bound algorithms is? I'd also appreciate references (preferably books), where this distinction is made ...
8
votes
2answers
3k views

Branch and Bound explanation

I have a test about the branch and bound algorithm. I understand theoretically how this algorithm works but I couldn't find examples that illustrates how this algorithm can be implemented practically. ...