Apply a sequential k-opt move described by chain = [t_1, t_2, ..., t_{2k}]. Edges x_i = (t_{2i-1}, t_{2i}) are removed, edges y_i = (t_{2i}, t_{2i+1}) are added for i = 1..k-1, and the move is closed with y_k = (t_{2k}, t_1). Returns the resulting route as a numpy array, or None if the m
(route0, chain)
| 709 | return np.array(route, dtype = np.int64) |
| 710 | |
| 711 | def _apply_sequential_chain(route0, chain): |
| 712 | """Apply a sequential k-opt move described by chain = [t_1, t_2, ..., t_{2k}]. |
| 713 | Edges x_i = (t_{2i-1}, t_{2i}) are removed, edges y_i = (t_{2i}, t_{2i+1}) |
| 714 | are added for i = 1..k-1, and the move is closed with y_k = (t_{2k}, t_1). |
| 715 | Returns the resulting route as a numpy array, or None if the move does |
| 716 | not produce a valid single Hamiltonian cycle.""" |
| 717 | n = route0.shape[0] |
| 718 | k = len(chain) // 2 |
| 719 | if 2 * k != len(chain) or k < 2: |
| 720 | return None |
| 721 | |
| 722 | edges = _build_edge_set_from_route(route0) |
| 723 | |
| 724 | # Remove x_i edges |
| 725 | for i in range(k): |
| 726 | a = int(chain[2 * i]) |
| 727 | b = int(chain[2 * i + 1]) |
| 728 | e = (a, b) if a < b else (b, a) |
| 729 | if e not in edges: |
| 730 | return None |
| 731 | edges.remove(e) |
| 732 | |
| 733 | # Add y_i edges (i = 1..k-1) |
| 734 | for i in range(k - 1): |
| 735 | a = int(chain[2 * i + 1]) |
| 736 | b = int(chain[2 * i + 2]) |
| 737 | e = (a, b) if a < b else (b, a) |
| 738 | if e in edges: |
| 739 | return None |
| 740 | edges.add(e) |
| 741 | |
| 742 | # Closing y_k |
| 743 | a = int(chain[-1]) |
| 744 | b = int(chain[0]) |
| 745 | e = (a, b) if a < b else (b, a) |
| 746 | if e in edges: |
| 747 | return None |
| 748 | edges.add(e) |
| 749 | |
| 750 | return _rebuild_tour_from_edges(n, edges, start = int(route0[0])) |
| 751 | |
| 752 | def _lk_sequential_search_from(distance_matrix, route0, succ, pred, cand_arr, t1, max_depth, breadth): |
| 753 | """Run the faithful sequential k-opt search starting from a single t_1. |
no test coverage detected