i would like a heuristic/evaluation method coded for the general case
of the chain problem( which is any starting configuration of
chains)below. i want to alter the class to embed the heuristic within
the evaluate() method. only that.
/* ChainState.java
*
*
*
* A State representation for the general case of the Chain Problem.
*
* Each state has a fixed number of links that can be either open or
* joined together in either a line or a loop (a special sort of
* line).
*
* Operators are opening links and closing open links. Closing a link
* means creating or extending a line, or creating a loop from an
* exising line.
*
*/
import java.io.*;
import java.util.*;
import packag.search.*;
public class ChainState implements State {
static ChainState goal;
Vector lines;
int totalLinks;
/* The ChainState constructor parameters are an integer,
* representing the total number of links, plus a vector of any
* lines or loops that exist in the state.
*/
public ChainState(int links, Vector v) { // constructor from vector
totalLinks = links;
lines = new Vector();
Enumeration e = v.elements();
while(e.hasMoreElements()) {
Line l = (Line) e.nextElement();
add(new Line(l));
}
}
public ChainState(ChainState cs) { // copy constructor
totalLinks = cs.totalLinks;
lines = new Vector();
Enumeration e = cs.lines.elements();
while(e.hasMoreElements()) {
Line l = (Line) e.nextElement();
add(new Line(l));
}
}
/* Method to (re-)set the goal state. This may be needed for the
* method evaluate() to assess how "near" we are to the goal.
*/
public static void setGoal(ChainState g) {
goal = g;
}
/* Method to evaluate the current state (usually by comparison
* with the goal state).
*/
public double evaluate() {
// put the code for the heuristic/evaluation function here
// compare number of "differences" to goal
double differences = 0.0;
// this currently returns a dummy value
return differences;
}
/* Method to return all the possible successors of this state. */
public Enumeration successors() {
// try all possible ops in all combinations
// and return resulting States
// System.err.println("Creating successors");
Vector successors = new Vector();
// First open any links that exist in lines. Note that if a
// line is n links long, this amounts to opening the first n/2
// links only (and for loops only one link will do).
//
// For example, if a line is 5 links long (00000) this would
// require 3 links to be opened to form:
//
// 1) one link plus one line 0000
// 2) one link plus two lines 0 000
// 3) one link plus two lines 00 00
Iterator it = lines.iterator();
while(it.hasNext()) {
Line line = (Line) it.next();
for(int i = 1; i <= (line.length() + 1) / 2; i++) {
// create a copy so as not to alter original state
ChainState nextState = new ChainState(this);
nextState.remove(line);
Vector v = line.openLinkAt(i);
Enumeration e = v.elements();
while(e.hasMoreElements()) {
Line l = (Line) e.nextElement();
nextState.add(l);
}
//System.err.println("Opened link "+i+" of " + line + nextState);
successors.addElement(new Successor(nextState,
new String(" --> " +
"Opened link "
+ i + " of "
+ line),
1));
// if the line is a loop you only need to open
// the first link, so we can break out of the
// for loop after one iteration
if(line.isLoop())
break ;
}
} // end-while
// if any open link exists, try closing it on its own,
// to each line and to each pair of lines
if(noOfOpenLinks() > 0) {
// first do it alone
ChainState nextState = new ChainState(this);
nextState.add(new Line(1));
// System.err.println("Closed single link" + nextState);
successors.addElement(new Successor(nextState,
new String(" --> " +
"Closed a link "),
1));
// now close at end of each single line and pairs of lines
for(int i = 0; i < lines.size(); i++) {
Line line1 = (Line) lines.elementAt(i);
ChainState nextState2 = new ChainState(this);
nextState2.remove(line1);
nextState2.add(new Line(line1.length() + 1));
//System.err.println("Closed link round " + line1 + nextState2);
successors.addElement(new Successor(nextState2,
new String(" --> " +
"Closed link "
+ "round "
+ line1),
1));
// also could make it a loop
ChainState nextStateL = new ChainState(this);
nextStateL.remove(line1);
Line loop = new Line(line1.length() + 1);
loop.setLoop();
nextStateL.add(loop);
//System.err.println("Closed link to make " +line1+nextStateL);
successors.addElement(new Successor(nextStateL,
new String(" --> " +
"Closed link "
+ "to make "
+ loop),
1));
// now around pairs if there are any
for(int j = i + 1; j < lines.size(); j++) {
Line line2 = (Line) lines.elementAt(j);
ChainState nextState3 = new ChainState(this);
nextState3.remove(line1);
nextState3.remove(line2);
nextState3.add(new Line(line1.length() +
line2.length() +
1));
// System.err.println("Closed link round " + line1
// + " and " + line2 + nextState3);
successors.addElement(new Successor(nextState3,
new String(" --> " +
"Closed link "
+ "round "
+ line1 +
" and " +
line2),
1));
}
}
}
//System.err.println("There are " + successors.size() + " successors");
return successors.elements();
}
/* Method to check whether two ChainStates are isomorphic
* (identical).
*
* To check this, it creates copies of both states by duplicating
* their contents. It then takes each component of one and removes
* it from both. If both are empty at the end, then they matched.
*
*/
public boolean goalTest(State state) {
ChainState thisState = new ChainState(this);
ChainState otherState =
new ChainState(((ChainState) state));
boolean allFound = true;
Iterator i1 = thisState.lines.iterator();
while(i1.hasNext() && allFound) {
Line l1 = (Line) i1.next();
boolean thisFound = false;
Iterator i2 = otherState.lines.iterator();
while(i2.hasNext() && !thisFound) {
Line l2 = (Line) i2.next();
if(l1.equals(l2)) {
i1.remove();
i2.remove();
thisFound = true;
}
}
if(!thisFound)
allFound = false;
}
if(thisState.noOfOpenLinks() != otherState.noOfOpenLinks())
allFound = false;
return allFound;
}
/* Auxilary methods for the ChainState class. */
/* Method to compute the number of open links. */
private int noOfOpenLinks() {
int count = totalLinks;
Enumeration e = lines.elements();
while(e.hasMoreElements()) {
Line l = (Line) e.nextElement();
count -= l.length();
}
return count;
}
/* Method to add a new line to the state. */
private void add(Line l) {
lines.addElement(l);
}
/* Method to remove an existing line from the state
* (returns false if no such line can be found).
* [Actually, it aborts the whole program in such a case.]
*/
private void remove(Line l) {
boolean found = false;
Iterator i = lines.iterator();
while(i.hasNext() && !found) {
Line l2 = (Line) i.next();
if(l.equals(l2)) {
i.remove();
found = true;
}
}
if(!found) {
System.err.println("Can't remove such a line!");
System.exit(0);
}
}
/* Method to display the state. */
public String toString() {
String s = new String();
int open = noOfOpenLinks();
s += ("\nThis ChainState has " + open + " open link(s) and ");
s += (lines.size() + " line(s)/loop(s)\n");
Enumeration e = lines.elements();
while(e.hasMoreElements()) {
Line line = (Line) e.nextElement();
s += line + "\n";
}
s += "Difference from goal is " + Text.format(evaluate(),4,0);
return s;
}
} |
Request for Question Clarification by
majortom-ga
on
23 Feb 2004 06:30 PST
Hello,
Your code contains this line, which imports a package I can find no
reference to via web searches:
import packag.search.*;
It then refers to the interface "State," which is presumably imported by that line:
public class ChainState implements State...
While the State interface appears to be simple, there is also a Line
class used in your code, with methods such as isLoop(), which is also
in that package.
As a result, I cannot compile your code. I believe the "packag."
package is something you have been provided by those who have assigned
you this task. In order to answer this question for you, I would need
to have access to it; otherwise I would have to guess at the nature of
each method of these classes, reimplement them, and hope for the best,
which would not guarantee a correct answer. If copyright permits, you
should provide a link at which the "packag" package can be downloaded.
If the code is part of a copyrighted textbook or similar document and
cannot be legally made available by you, it will unfortunately not be
possible for me to complete this program for you independently, but it
may still be possible to assist you in answering the question;
however, testing, understanding and feedback on your part would be
essential to that process, since only you would be able to actually
compile and execute the code. Please let me know. Thank you.
|
Clarification of Question by
breaklabel-ga
on
24 Feb 2004 18:52 PST
hi. i have the package in a location where you can access them:
http://www.streamload.com/breaklabel.
the password is : swankypig.
i wont have it there for long though. thanks
|
Clarification of Question by
breaklabel-ga
on
24 Feb 2004 19:34 PST
pls do let me know if you got all the files in the package.
|
Request for Question Clarification by
majortom-ga
on
25 Feb 2004 08:46 PST
Hello, breaklabel-ga,
The Line class was not present among the files you provided. Without
this class your code does not compile. I would like to work on this
problem for you, but if I am to do so, I will need all of the pieces
of the puzzle. Thank you.
|
Clarification of Question by
breaklabel-ga
on
25 Feb 2004 18:45 PST
oops. sorry i copped that out. i have put Line and ChainMain up, same
pswd. when you been able to compile it, could you test it by using
greedy and AStar searches and note down the results? i know how to
appreciate good work. thanks
|
Request for Question Clarification by
majortom-ga
on
26 Feb 2004 04:42 PST
I was eventually able to get this to compile after downloading the new
class files you just put up and replacing a few Text.format calls with
things I did have.
When I run ChainMain in its current, as-yet-unimproved form, it runs
for a while and produces an Out of Memory error. Is this normal?
|
Request for Question Clarification by
majortom-ga
on
26 Feb 2004 04:45 PST
This is what I get when I run "java ChainMain" in its initial form as
you provided it. Is this what you get? If not, my best guess is that
the code somehow depends heavily on exactly what the javagently.Text
class does and I'll have to have that too.
Start State
-----------
This ChainState has 0 open link(s) and 4 line(s)/loop(s)
Line: 000
Line: 000
Line: 000
Line: 000
Difference from goal is 0.0
Goal State
----------
This ChainState has 0 open link(s) and 1 line(s)/loop(s)
Loop: 000000000000
Difference from goal is 0.0
Breadth First Search object created
Exception in thread "main" java.lang.OutOfMemoryError
|
Clarification of Question by
breaklabel-ga
on
26 Feb 2004 07:03 PST
yes that is normalwith ChainMain. BFS (as well as DFS, GreedySearch
and AStar) will, give you an exception. IDS and DLS will get you to
the goal state. i got all the results for that. what i need to find
out is to to embed the heuristic in the evaluate() method and use the
Greedy and AStar serch with it to record the results and compare it to
the methods in the main problem. could you have the evaluate() method
commented out? thanks
|
Request for Question Clarification by
majortom-ga
on
26 Feb 2004 11:21 PST
Can you provide me with a quick definition of the chain problem
itself? I find many different "chain problems" in the computer science
literature, but only one generic reference to "the chain problem,"
which did not contain a definition, only a problem assignment that
referred to text not available on the web. I want to make sure I'm
solving the right problem here. Thank you.
|
Clarification of Question by
breaklabel-ga
on
26 Feb 2004 14:59 PST
the chain problem here is any starting configuration of chains.
the state for each chain has a fixed number of links that can be either open or
joined together in either a line or a loop (a special sort of line).
Operators are opening links and closing open links. Closing a link
means creating or extending a line, or creating a loop from an
exising line.
so we could have:
States
? Lines/loops of n links
? Nb of open links
Operators
? Open a link
? Close a link
Path cost
? nb of operations
Goal test
? Single loop of 12 links
? Initial state
? 4x3 link lines (4 chains, 3 links each)
|
Clarification of Question by
breaklabel-ga
on
26 Feb 2004 15:02 PST
the chain problem here is any starting configuration of chains.
the state for each chain has a fixed number of links that can be either open or
joined together in either a line or a loop (a special sort of line).
Operators are opening links and closing open links. Closing a link
means creating or extending a line, or creating a loop from an
exising line.
so we could have:
States
? Lines/loops of n links
? Nb of open links
Operators
? Open a link
? Close a link
Path cost
? nb of operations
so for example:
Goal test
? Single loop of 12 links
Initial state
? 4x3 link lines (4 chains, 3 links each)
Heuristic
? Minimise nb of lines + number of open loops
Solution
? 3 open + 3 close
|
Request for Question Clarification by
majortom-ga
on
26 Feb 2004 17:26 PST
Given this:
--- --- --- ---
The simplest solution appears to be four opens, bridging the four
lines. But the listed solution is three opens and three closes. How is
a close operation useful at all in this situation? I suspect I still
don't understand the problem statement correctly.
|
Clarification of Question by
breaklabel-ga
on
26 Feb 2004 20:44 PST
hi, pls have a look at this and lets see.
http://www.streamload.com/breaklabel
pswd: swankypig.
|
Request for Question Clarification by
majortom-ga
on
27 Feb 2004 07:13 PST
Hello, breaklabel-ga,
I have coded a heuristic that works very well on the great majority of
randomly generated chain problems. It does not work well for every
conceivable chain problem. My understanding of heuristic search is
that there is no "perfect" heuristic for most situations. The
heuristic's task is to reduce the number of states that must be
examined; in principle the program always works eventually even if the
heuristic leads to blind alleys for a particular problem, however in
practice of course one can run out of memory if the problem is large
enough. Is a good heuristic that usually results in a solution on a
real computer a valid answer, or is a perfect solution expected? If
you know that a "perfect" solution (which always works for every valid
set of starting and goal conditions) does exist, please let me know
that, otherwise please confirm that a heuristic that works quite well
for most cases is a valid answer. Thank you.
|
Request for Question Clarification by
majortom-ga
on
27 Feb 2004 09:24 PST
Just to be clear about what I've got: I have a heuristic that finds a
solution via the AStar algorithm, sometimes after considerable
grinding away of course, on all of the randomly generated cases I've
tried with up to five lines or loops with up to six links per chain
and various numbers of open links. The greedy algorithm is not as
successful; it is more likely to look at too many possibilities and
run out of memory. This makes sense, A* is a better algorithm. I am
pleased with this heuristic's performance; however I cannot invest any
more time in this solution. Please let me know whether you consider it
an acceptable $30 answer, and I'll upload it if so. Thank you!
|
Request for Question Clarification by
majortom-ga
on
27 Feb 2004 09:25 PST
Needless to say, the example starting state and goal provided (four
lines of three, one loop of twelve) work correctly as well, of course.
|
Clarification of Question by
breaklabel-ga
on
27 Feb 2004 14:46 PST
hello major, i dont need a perfect one , but one that is quite optimal
and can can a sloution if there is one and ir works well for most
cases. i think you got it right and it will do just fine. this will
give me the results i need in order to compare them with the
uninformed search methods of the problem in main. thats good and
definitely worth a tip.lets see it.
|
