Week 4: Neighbourhood Functions and Energy Landscapes

Question 1

Neighbourhood Function

Answer 1

A method of making alternate configurations that may be more optimal than the current configuration.

Question 2

NH_1 for MAX-3-SAT

Answer 2

This involves flipping the state of one of the variables. The total number of configurations possible is the number of variables in the problem.

Question 3

NH_2 for TSP

Answer 3

This involves swapping two non-consecutive edges.

Question 4

NH_3 for TSP

Answer 4

This involves swapping three non-consecutive edges.

Question 5

Weighted Graph Bisection Problem - Greedy Construction

Answer 5

Start with a root node one one side. Keep adding edges that maximise the total weight. Repeat until half of the vertices are assigned to the current subgraph. The other edges belong to the other subgraph.

Question 6

Nearest Neighbour Construction Heuristic

Answer 6

Start at a root vertex, take in the nearest unvisited vertex, and repeat until you’ve reached the last vertex. Then return to the root vertex.

The runtime is O(n^2).

Question 7

Insertion Construction Heuristic

Answer 7

Start with three nodes as the initial subtour. Then add another vertex where the increase in total length of the subtour is minimised. Repeat until all vertexes are added.