Backtracking Alg.

تفضل اخي هذا مثال بسيط على استخدام الـ BackTracking في السي ++

#include <iostream>
using namespace std;

int G[50][50]; //adjacency matrix for the graph
int num_edges; //number of edges
int num_nodes; //number of nodes

bool diff_color(int node, int color, int colored[])
{
for(int v = 0; v < node; v++)
if(G[v][node] && colored[v] == color) //check if they have same color and
return false; //if the edge exists between the two nodes.

return true;
}

bool backtracking(int colored[], int node)
{
for(int color = 0; color < 2; color++) //try for both colors
if(diff_color(node, color, colored))
{
colored[node] = color; //set the color to the current vertice
if(node == num_nodes-1) //check if the current node == last node
return true;
else
return backtracking(colored, node+1); //backtrack it again
}
return false;
}

int main()
{
int u, v, counter; //input vertices that are connected
int colored[50]; //colored vertices,
cin >> num_nodes >> num_edges;

for(int i = 0; i < 50; i++) //make all the vertices unconected by
for(int j = 0; j < 50; j++) //setting the matrix G[all][all]=0
G[j] = 0;

while(num_edges>0) //loop until all edges are entered
{
num_edges–; //num_edges one less
cin >> u >> v;
G[v] = 1; //when an edge exists then put in the
G[v] = 1; //adjecency matrix a 1
}
if(backtracking(colored, 0)) //check if the graph is bicolorable
cout << “The graph can be bicolored.” << endl;
else
cout << “The graph can not be bicolored.” << endl;
}

مشكور اخي على الرد بس اذا ممكن يكون المثال التوضيحي مثلا على زيارة المدن والحصول على اقصر طريق للوصول الها...

خوارزميه Backtracking تستخدم لايجاد كل الحلول أو بعض الحلول لمشكله أو طريقه ما ، وليست لايجاد الحل الأمثل كما ذكرت ، هذه لها طرق وخوارزميات أخرى ، أذكر منها طريقه Dijkstra

هنا مقاله من 4 صفحات جيده عن الموضوع :

The Backtracking Algorithm Technique

مثل هكذا مواضيع لن يفيدك سورس كود أو مثال واحد بقدر ما يفيدك فهمك للنظريه والطرق التي تستخدمها وميزات وعيوب كل منها ، لذلك عليك بايجاد كتاب جيد يتكلم عن الخوارميات وخصوصا Graph,Tree وستجد كل شيء ان شاء الله في الكتاب بالإضافه الى الأمثله اللازمه ..

بالتوفيق ،