cpp-taskflow/examples/tsp.cpp at master · feiyunwill/cpp-taskflow · GitHub

History

174 lines (152 loc) · 6.69 KB

Raw

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

// tsp.cpp: parallel branch-and-bound solver for the Travelling Salesman Problem

// using tf::TaskGroup for recursive task parallelism.

// The example uses a hand-constructed 4-city instance:

// A B C D

// A [ 0 10 15 20 ]

// B [ 10 0 35 25 ]

// C [ 15 35 0 30 ]

// D [ 20 25 30 0 ]

// Optimal tour: A -> B -> D -> C -> A = 80

#include <taskflow/taskflow.hpp>

// ── problem constants ────────────────────────────────────────────────────────

// Use NUM_CITIES instead of N to avoid shadowing template parameter 'N'

// inside Taskflow's internal headers (e.g. SmallVector, UnboundedWSQ).

static constexpr int NUM_CITIES = 4;

static constexpr int INF = std::numeric_limits<int>::max();

static const int DIST[NUM_CITIES][NUM_CITIES] = {

{ 0, 10, 15, 20 }, // A

{ 10, 0, 35, 25 }, // B

{ 15, 35, 0, 30 }, // C

{ 20, 25, 30, 0 }, // D

};

// ── shared state ─────────────────────────────────────────────────────────────

static tf::Executor executor;

static std::atomic<int> best_cost{ INF };

// ── lower bound ──────────────────────────────────────────────────────────────

// Any valid completion of the partial tour must include:

// (1) at least one edge leaving the current city to some unvisited city

// (2) at least one edge touching each remaining unvisited city

// We use the cheapest available option for each of these, giving a floor on

// the best possible tour cost from this node onward.

// If this floor already meets or exceeds best_cost, the subtree is pruned.

// Example: at A->C (cost=15, best_cost=80 after first leaf):

// (1) min edge from C to unvisited {B,D}: min(35,30) = 30

// (2) min edge from B to anywhere: min(10,35,25) = 10

// min edge from D to anywhere: min(20,25,30) = 20

// lb = 15 + 30 + 10 + 20 = 75 < 80 => not pruned

// At A->C->B (cost=50):

// (1) min edge from B to unvisited {D}: 25

// (2) min edge from D to anywhere: 20

// lb = 50 + 25 + 20 = 95 >= 80 => PRUNED

static int lower_bound(

int current,

const std::vector<bool>& visited,

int cost_so_far

) {

int bound = cost_so_far;

// (1) cheapest edge out of the current city to any unvisited city

int min_curr = INF;

for(int v = 0; v < NUM_CITIES; v++) {

if(!visited[v]) {

min_curr = std::min(min_curr, DIST[current][v]);

}

if(min_curr == INF) return bound; // no unvisited cities: tour is complete

bound += min_curr;

// (2) cheapest outgoing edge from each unvisited city to any other city

for(int u = 0; u < NUM_CITIES; u++) {

if(visited[u]) continue;

int min_u = INF;

for(int v = 0; v < NUM_CITIES; v++) {

if(v != u) {

min_u = std::min(min_u, DIST[u][v]);

}

bound += min_u;

}

return bound;

}

// ── branch and bound ─────────────────────────────────────────────────────────

// Each call represents one node in the TSP search tree.

// It creates a tf::TaskGroup and spawns one async task per unvisited city

// (except the first, which runs on the current worker to avoid task overhead).

// tg.corun() cooperatively waits for all spawned branches without blocking

// the worker thread.

static void branch_and_bound(

int current, // city we are currently at

std::vector<bool> visited, // which cities have been visited

int cost_so_far, // accumulated tour cost so far

int depth // number of cities visited so far

) {

// compute lower bound and prune if it cannot improve on best_cost

int lb = lower_bound(current, visited, cost_so_far);

if(lb >= best_cost.load(std::memory_order_relaxed)) return;

// all cities visited: close the tour by returning to city 0

if(depth == NUM_CITIES) {

int total = cost_so_far + DIST[current][0];

// update best_cost if this tour is cheaper; compare_exchange_weak retries

// on spurious failure so the true minimum is always stored correctly

int cur = best_cost.load(std::memory_order_relaxed);

while(total < cur &&

!best_cost.compare_exchange_weak(

cur, total,

std::memory_order_relaxed,

std::memory_order_relaxed));

return;

}

// create a task group for parallel branching.

// task_group() is valid here because every call to branch_and_bound runs

// inside a worker thread: either the root executor.async() task or a

// tg.silent_async() task spawned by a parent call.

auto tg = executor.task_group();

bool first = true;

for(int v = 0; v < NUM_CITIES; v++) {

if(visited[v]) continue;

// prepare state for the branch where city v is visited next

std::vector<bool> new_visited = visited;

new_visited[v] = true;

int new_cost = cost_so_far + DIST[current][v];

if(first) {

// run the first unvisited branch directly on this worker to avoid

// unnecessary task creation overhead

first = false;

branch_and_bound(v, new_visited, new_cost, depth + 1);

}

else {

// spawn remaining branches as independent async tasks in the group.

// all spawned tasks share best_cost, so a better solution found in any

// branch immediately tightens the pruning bound for all other branches.

tg.silent_async([=]() {

branch_and_bound(v, new_visited, new_cost, depth + 1);

});

}

// cooperatively wait for all spawned branches to complete.

// corun() re-enters the executor's work-stealing loop rather than blocking,

// preventing worker starvation in deep recursion.

tg.corun();

}

// ── main ─────────────────────────────────────────────────────────────────────

int main() {

std::vector<bool> visited(NUM_CITIES, false);

visited[0] = true; // start from city A (index 0)

// the root call must be submitted as an async task so it runs inside a

// worker thread, which is required for executor.task_group() to be valid

executor.async([&]() {

branch_and_bound(0, visited, 0, 1);

}).get();

const char* names[] = { "A", "B", "C", "D" };

printf("Optimal tour cost: %d\n", best_cost.load());

(void)names;

return 0;

}

cpp-taskflow/examples/tsp.cpp at master · feiyunwill/cpp-taskflow · GitHub

Expand file tree

Breadcrumbs

tsp.cpp

Latest commit

History

Breadcrumbs

tsp.cpp

File metadata and controls