Talk:AC-3 algorithm - Revision history

Masterhatch: Removed from Category:Talk pages with comments before the first section

2025-01-15T02:55:12Z

Removed from Category:Talk pages with comments before the first section

← Previous revision		Revision as of 02:55, 15 January 2025
Line 2:		Line 2:
	{{WikiProject Computer science \|importance=Low}}		{{WikiProject Computer science \|importance=Low}}
	}}		}}

			== Untitled ==
	I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist		I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist

Supyovalk: Assessment (Low): banner shell, Computer science (Rater)

2024-07-25T13:19:29Z

Assessment (Low): banner shell, Computer science (Rater)

← Previous revision		Revision as of 13:19, 25 July 2024
Line 1:		Line 1:
	{{WikiProject banner shell\|class=\|		{{WikiProject banner shell\|class=Start\|1=
	{{WikiProject Computer science}}		{{WikiProject Computer science \|importance=Low}}
	}}		}}
	I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist		I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist

Qwerfjkl (bot): Implementing WP:PIQA (Task 26)

2024-01-19T11:08:31Z

Implementing WP:PIQA (Task 26)

← Previous revision		Revision as of 11:08, 19 January 2024
Line 1:		Line 1:
			{{WikiProject banner shell\|class=\|
	{{WikiProject Computer science}}		{{WikiProject Computer science}}
			}}
	I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist		I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist

91.2.85.9: /* Early version too inefficient, later versions difficult to implement => often taught algorithm!? */ new section

2016-03-03T18:22:36Z

Early version too inefficient, later versions difficult to implement => often taught algorithm!?: new section

← Previous revision		Revision as of 18:22, 3 March 2016
Line 35:		Line 35:
	:::::You're right, arcs starting at the pruned variable ''x'' and pointing to a different variable ''z'' are not added when pruning according to the algorithm; all arcs are included just once at the initialization, or later when a variable may lose support because a neighbor variable is pruned. I recommend that you read the original paper [http://cse.unl.edu/~choueiry/Documents/Mackworth-AIJ77.pdf here] (algorithms AC2 and AC3 are on page 106).		:::::You're right, arcs starting at the pruned variable ''x'' and pointing to a different variable ''z'' are not added when pruning according to the algorithm; all arcs are included just once at the initialization, or later when a variable may lose support because a neighbor variable is pruned. I recommend that you read the original paper [http://cse.unl.edu/~choueiry/Documents/Mackworth-AIJ77.pdf here] (algorithms AC2 and AC3 are on page 106).
	:::::Talk pages are for improving the article. If there's an error in the article, this conversation can uncover it, so there's no reason to delete it. [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 07:13, 7 March 2013 (UTC)		:::::Talk pages are for improving the article. If there's an error in the article, this conversation can uncover it, so there's no reason to delete it. [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 07:13, 7 March 2013 (UTC)

			== Early version too inefficient, later versions difficult to implement => often taught algorithm!? ==

			The text says that because of inefficiencies of early implementations and difficulties of modern implementations: "... and so AC-3 is the one most often taught ...". I don't understand this conclusion. I suspect this needs to be reworded? [[Special:Contributions/91.2.85.9\|91.2.85.9]] ([[User talk:91.2.85.9\|talk]]) 18:22, 3 March 2016 (UTC)

Christian75: Assessment: +Computer science (assisted)

2015-05-15T15:37:28Z

Assessment: +Computer science (assisted)

← Previous revision		Revision as of 15:37, 15 May 2015
Line 1:		Line 1:
			{{WikiProject Computer science}}
	I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist		I'm not sure the pseudocode is right: the arc-reduce(x,y) function only reduces the domain of x, therefore you also need to call arc-reduce(y,x) to reduce the domain of y and add (z,y) arcs to the worklist if it was indeed reduced. This is done once in the current implementation, as the code for initiating the worklist

Diego Moya at 07:16, 7 March 2013

2013-03-07T07:16:10Z

← Previous revision		Revision as of 07:16, 7 March 2013
Line 32:		Line 32:

	::::"Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it. This works because constraints are 'not' directed" Ok, that part wasn't clear in my mind. Thanks again. One last detail : "all the arcs of constraints including that pruned variable (except the current arc) are added to the collection" should become "all the arcs of constraints pointing to that pruned variable (except the arc of the current constraint) are added to the collection" if I'm not mistaken again. And shall we leave this discussion on the talk page or erase it ? [[User:Baha2490\|Baha2490]] ([[User talk:Baha2490\|talk]]) 02:18, 7 March 2013 (UTC)		::::"Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it. This works because constraints are 'not' directed" Ok, that part wasn't clear in my mind. Thanks again. One last detail : "all the arcs of constraints including that pruned variable (except the current arc) are added to the collection" should become "all the arcs of constraints pointing to that pruned variable (except the arc of the current constraint) are added to the collection" if I'm not mistaken again. And shall we leave this discussion on the talk page or erase it ? [[User:Baha2490\|Baha2490]] ([[User talk:Baha2490\|talk]]) 02:18, 7 March 2013 (UTC)
	:::::You're right, arcs starting at the pruned variable ''x'' and pointing to a different variable ''z'' are not added according to the algorithm. I recommend that you read the original paper [http://cse.unl.edu/~choueiry/Documents/Mackworth-AIJ77.pdf here] (algorithms AC2 and AC3 are on page 106).		:::::You're right, arcs starting at the pruned variable ''x'' and pointing to a different variable ''z'' are not added when pruning according to the algorithm; all arcs are included just once at the initialization, or later when a variable may lose support because a neighbor variable is pruned. I recommend that you read the original paper [http://cse.unl.edu/~choueiry/Documents/Mackworth-AIJ77.pdf here] (algorithms AC2 and AC3 are on page 106).
	:::::Talk pages are for improving the article. If there's an error in the article, this conversation can uncover it, so there's no reason to delete it. [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 07:13, 7 March 2013 (UTC)		:::::Talk pages are for improving the article. If there's an error in the article, this conversation can uncover it, so there's no reason to delete it. [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 07:13, 7 March 2013 (UTC)

Diego Moya at 07:13, 7 March 2013

2013-03-07T07:13:46Z

← Previous revision		Revision as of 07:13, 7 March 2013
Line 32:		Line 32:

	::::"Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it. This works because constraints are 'not' directed" Ok, that part wasn't clear in my mind. Thanks again. One last detail : "all the arcs of constraints including that pruned variable (except the current arc) are added to the collection" should become "all the arcs of constraints pointing to that pruned variable (except the arc of the current constraint) are added to the collection" if I'm not mistaken again. And shall we leave this discussion on the talk page or erase it ? [[User:Baha2490\|Baha2490]] ([[User talk:Baha2490\|talk]]) 02:18, 7 March 2013 (UTC)		::::"Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it. This works because constraints are 'not' directed" Ok, that part wasn't clear in my mind. Thanks again. One last detail : "all the arcs of constraints including that pruned variable (except the current arc) are added to the collection" should become "all the arcs of constraints pointing to that pruned variable (except the arc of the current constraint) are added to the collection" if I'm not mistaken again. And shall we leave this discussion on the talk page or erase it ? [[User:Baha2490\|Baha2490]] ([[User talk:Baha2490\|talk]]) 02:18, 7 March 2013 (UTC)
			:::::You're right, arcs starting at the pruned variable ''x'' and pointing to a different variable ''z'' are not added according to the algorithm. I recommend that you read the original paper [http://cse.unl.edu/~choueiry/Documents/Mackworth-AIJ77.pdf here] (algorithms AC2 and AC3 are on page 106).
			:::::Talk pages are for improving the article. If there's an error in the article, this conversation can uncover it, so there's no reason to delete it. [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 07:13, 7 March 2013 (UTC)

Baha2490 at 02:51, 7 March 2013

2013-03-07T02:51:17Z

← Previous revision		Revision as of 02:51, 7 March 2013
Line 31:		Line 31:
	::I'd say that the paragraph which describes the CSP as [[directed graph]]s is misleading - the consistency between arcs is directed (when x->y is arc-consistent, y->x may not be; this depends on the current state of the variable domains), but at a different level the definition of the constraints must be symmetric ( R(x,y)=R(y,x), and this depends only on the mathematical definition of the constraints, not on the algorithm current state ). [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 10:15, 6 March 2013 (UTC)		::I'd say that the paragraph which describes the CSP as [[directed graph]]s is misleading - the consistency between arcs is directed (when x->y is arc-consistent, y->x may not be; this depends on the current state of the variable domains), but at a different level the definition of the constraints must be symmetric ( R(x,y)=R(y,x), and this depends only on the mathematical definition of the constraints, not on the algorithm current state ). [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 10:15, 6 March 2013 (UTC)

	::::"Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it. This works because constraints are 'not' directed" Ok, ~~it's~~ that part ~~that~~ wasn't clear in my mind. Thanks again. ~~Shall~~ we leave this discussion on the talk page or erase it ? [[User:Baha2490\|Baha2490]] ([[User talk:Baha2490\|talk]]) 02:18, 7 March 2013 (UTC)		::::"Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it. This works because constraints are 'not' directed" Ok, that part wasn't clear in my mind. Thanks again. One last detail : "all the arcs of constraints including that pruned variable (except the current arc) are added to the collection" should become "all the arcs of constraints pointing to that pruned variable (except the arc of the current constraint) are added to the collection" if I'm not mistaken again. And shall we leave this discussion on the talk page or erase it ? [[User:Baha2490\|Baha2490]] ([[User talk:Baha2490\|talk]]) 02:18, 7 March 2013 (UTC)

Baha2490 at 02:18, 7 March 2013

2013-03-07T02:18:28Z

← Previous revision		Revision as of 02:18, 7 March 2013
Line 30:		Line 30:
	::This works because constraints are 'not' directed - if there's a value Y in D(y) that ''supports'' a value X in D(x), then the the inverse is also true - the X value also supports the Y value.		::This works because constraints are 'not' directed - if there's a value Y in D(y) that ''supports'' a value X in D(x), then the the inverse is also true - the X value also supports the Y value.
	::I'd say that the paragraph which describes the CSP as [[directed graph]]s is misleading - the consistency between arcs is directed (when x->y is arc-consistent, y->x may not be; this depends on the current state of the variable domains), but at a different level the definition of the constraints must be symmetric ( R(x,y)=R(y,x), and this depends only on the mathematical definition of the constraints, not on the algorithm current state ). [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 10:15, 6 March 2013 (UTC)		::I'd say that the paragraph which describes the CSP as [[directed graph]]s is misleading - the consistency between arcs is directed (when x->y is arc-consistent, y->x may not be; this depends on the current state of the variable domains), but at a different level the definition of the constraints must be symmetric ( R(x,y)=R(y,x), and this depends only on the mathematical definition of the constraints, not on the algorithm current state ). [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 10:15, 6 March 2013 (UTC)

			::::"Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it. This works because constraints are 'not' directed" Ok, it's that part that wasn't clear in my mind. Thanks again. Shall we leave this discussion on the talk page or erase it ? [[User:Baha2490\|Baha2490]] ([[User talk:Baha2490\|talk]]) 02:18, 7 March 2013 (UTC)

Diego Moya at 10:32, 6 March 2013

2013-03-06T10:32:53Z

← Previous revision		Revision as of 10:32, 6 March 2013
Line 28:		Line 28:

	::The pseudo code is right. The main benefit of AC3 over other weaker propagation algorithms is that, once you finish arc-reduce(x,y), you don't need to check anything of y nor add (y, x) to the worklist - everything that could be pruned in x because of y will have been checked and taken care of. Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it.		::The pseudo code is right. The main benefit of AC3 over other weaker propagation algorithms is that, once you finish arc-reduce(x,y), you don't need to check anything of y nor add (y, x) to the worklist - everything that could be pruned in x because of y will have been checked and taken care of. Also pruning a value in x won't affect y, because a value is pruned from x only when no values in y are connected to it.
	::This works because constraints are 'not' directed - if there's a value Y in D(y) that ''supports'' a value X in D(x), then the the inverse is also true - the X value also supports the Y value. I'd say that the paragraph which describes the CSP as [[directed graph]]s is misleading - the consistency between arcs is directed (when x->y is arc-consistent, y->x may not be; this depends on the current state of the variable domains), but at a different level the definition of the constraints must be symmetric ( R(x,y)=R(y,x), and this depends only on the mathematical definition of the constraints, not on the algorithm current state ). [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 10:15, 6 March 2013 (UTC)		::This works because constraints are 'not' directed - if there's a value Y in D(y) that ''supports'' a value X in D(x), then the the inverse is also true - the X value also supports the Y value.
			::I'd say that the paragraph which describes the CSP as [[directed graph]]s is misleading - the consistency between arcs is directed (when x->y is arc-consistent, y->x may not be; this depends on the current state of the variable domains), but at a different level the definition of the constraints must be symmetric ( R(x,y)=R(y,x), and this depends only on the mathematical definition of the constraints, not on the algorithm current state ). [[User:Diego Moya\|Diego]] ([[User talk:Diego Moya\|talk]]) 10:15, 6 March 2013 (UTC)