mirror of https://github.com/microsoft/autogen.git
116 lines
3.4 KiB
Plaintext
116 lines
3.4 KiB
Plaintext
|
|
Now, we have a system to solve TSP problems. Let's try to solve a problem.
|
|
|
|
Given a distance dictionary `dicts`, where the key is a pair of nodes and the
|
|
value is the distance between them. For example, `dists[(1, 2)]` is the distance
|
|
between node 1 and node 2. We want to find the optimal cost for the TSP problem.
|
|
|
|
The users might have some questions regarding the solution. So, you are
|
|
responsible to write code to answer the their questions. Note that you usually
|
|
would need to run `solve_tsp` and `compare_costs` to compare the costs before
|
|
and after the change.
|
|
|
|
Here are the functions and their information that you can use directly:
|
|
|
|
----------
|
|
def change_dist(dist: dict, i: int, j: int, new_cost: float) -> float:
|
|
"""Change the distance between two points.
|
|
|
|
Args:
|
|
dist (dict): distance matrix, where the key is a pair and value is
|
|
the cost (aka, distance).
|
|
i (int): the source node
|
|
j (int): the destination node
|
|
new_cost (float): the new cost for the distance
|
|
|
|
Returns:
|
|
float: the previous cost
|
|
"""
|
|
----------
|
|
|
|
----------
|
|
def compare_costs(prev_cost, new_cost) -> float:
|
|
"""Compare the previous cost and the new cost.
|
|
|
|
Args:
|
|
prev_cost (float): the previous cost
|
|
new_cost (float): the updated cost
|
|
|
|
Returns:
|
|
float: the ratio between these two costs
|
|
"""
|
|
----------
|
|
|
|
----------
|
|
def solve_tsp(dists: dict) -> float:
|
|
"""Solve the TSP problem
|
|
|
|
Args:
|
|
dists (dict): the distance matrix between each nodes. Each item in the
|
|
dict is a pair (node A, node B) to the distance from A to B.
|
|
|
|
Returns:
|
|
float: the optimal cost
|
|
"""
|
|
----------
|
|
|
|
|
|
We also provide some sample questions and answers here:
|
|
----------
|
|
Question: Why should we go from point 1 to point 2?
|
|
Code:
|
|
```
|
|
from extensions.tsp import solve_tsp
|
|
from extensions.tsp_api import change_dist, compare_costs, dists
|
|
prev_cost=solve_tsp(dists)
|
|
change_dist(dists, 1, 2, float('inf'))
|
|
new_cost = solve_tsp(dists)
|
|
gap = compare_costs(prev_cost, new_cost)
|
|
print('If not, then the cost will increase', gap * 100, 'percent.')
|
|
```
|
|
|
|
----------
|
|
Question: Can we double the distance between point 4 and 2?
|
|
Code:
|
|
```
|
|
from extensions.tsp import solve_tsp
|
|
from extensions.tsp_api import change_dist, compare_costs, dists
|
|
prev_cost=solve_tsp(dists)
|
|
change_dist(dists, 3, 4, dists[(3, 4)] * 2)
|
|
new_cost = solve_tsp(dists)
|
|
gap = compare_costs(prev_cost, new_cost)
|
|
print('If we double the distance between 4 and 2, then the cost will decrease', - gap * 100, 'percent.')
|
|
```
|
|
|
|
----------
|
|
Question: what would happen if we remove point 2?
|
|
Code:
|
|
```
|
|
from extensions.tsp import solve_tsp
|
|
from extensions.tsp_api import compare_costs, dists
|
|
prev_cost=solve_tsp(dists)
|
|
for i, j in list(dists.keys()):
|
|
if i == 2 or j == 2:
|
|
del dists[i, j] # remove the edge cost
|
|
new_cost = solve_tsp(dists)
|
|
gap = compare_costs(prev_cost, new_cost)
|
|
print('If we remove point 2, then the cost will decrease', - gap * 100, 'percent.')
|
|
```
|
|
|
|
----------
|
|
Question: What if the edge between point 2 to 3 is removed?
|
|
Code:
|
|
```
|
|
from extensions.tsp import solve_tsp
|
|
from extensions.tsp_api import change_dist, compare_costs, dists
|
|
prev_cost=solve_tsp(dists)
|
|
change_dist(dists, 2, 3, float('inf'))
|
|
new_cost = solve_tsp(dists)
|
|
gap = compare_costs(prev_cost, new_cost)
|
|
print('If we remove the edge, then the cost will increase', gap * 100, 'percent.')
|
|
```
|
|
|
|
Now, answer the questions by using Python code:
|
|
Question: {question}
|
|
Code:
|